STAT991:
Concentration Inequalities: Theory and Applications

Spring 2015

Time & Location: Tue, Thu 1:30-3:00pm in JMHH F38

Instructor: Alexander Rakhlin

Course Description

Prerequisites: Probability Theory and Linear Algebra.

Topics

• Introduction
  • variance and concentration
  • isoperimetry and Lipschitz concentration
  • martingale method
  • entropy method
  • transportation method
• Basics
  • Cramer-Chernoff method
  • Hoeffding's, Bennet's, Bernstein's
  • Efron-Stein-Steele, Tensorization
  • Bounded differences, self-bounding functions
  • Poincaré inequalities
• Application: JL and Random projections
• Talagrand's convex distance inequality
• Application: TSP
• Application: longest increasing subsequence
• Suprema of empirical processes
  • variance and concentration
  • Nemirovski's inequality
  • Symmetrization and contraction
  • Talagrand's inequality, Bousquet's inequality
  • chaining
  • uniform laws of large numbers
• Application: analysis of regression for misspecified models
• Application: linear inverse problems, sparse recovery, restricted isometry, Gaussian widths
• Application: model selection
• Markov semi-group proofs
• Extensions to martingales, sequential complexities
• In-depth analysis:
  • Log-Sobolev inequalities
  • The entropy method
  • Isoperimetry
  • The transportation method
  • Information Inequalities
• Stein's method
• Superconcentration
• Boolean functions, Fourier analysis
• Concentration of multivariate polynomials (Kim and Vu)
• Matrix concentration
• Application: Learning without concentration, small ball property, offset Rademacher averages

Suggested Readings

books/notes:

S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence.

R. van Handel. Probability in High Dimension.

M. Ledoux. The Concentration of Measure Phenomenon.

J.M. Steele. Probability Theory and Combinatorial Optimization.

R. Vershynin. Introduction to the non-asymptotic analysis of random matrices.

M. Raginsky and I. Sason. Concentration of measure inequalities in information theory, communications and coding.

S. Chatterjee. Superconcentration and Related Topics.

M. Ledoux and M. Talagrand. Probability in Banach Spaces.

A. van der Vaart and J. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics.

Articles: