Statistical learning

  • L.G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984
    • Original PAC learning paper
  • A. Blumer, A. Ehrenfeucht, D. Haussler, M.K. Warmuth. Occam’s razor. Information Processing Letters, 24:377-380, 1987.
    • Finite hypothesis classes / bit complexity

Empirical process theory

Boosting and margins

Convex surrogate losses

Approximation theory

Online learning with experts

Multi-armed bandits

Mixtures of Gaussians

Spectral clustering

  • F. McSherry. Spectral partitioning of random graphs. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, 2001.
    • Spectral clustering approaches to finding planted partitions in random graphs (related to stochastic block models).
  • N. Alon, M. Krivelevich, B. Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457-466, 1998.
    • Spectral algorithm for finding cliques of size \(\Omega(\sqrt{n})\) planted in \(G(n,1/2)\) random graphs.