Machine Learning II (2007/2008)

6/27 Concentration of measure and prediction bounds

This lecture investigates the connection between learning bounds and some classical inequalities in probability theory. The two main themes are the almost universal phenomenon of concentration of measure in statistics, and different ways of quantifying the complexity of function classes.

Concepts covered: Empirical error vs. generalization error. Concentration of measure in parametric statistics: Markov's inequality, Chebyshev's inequality, Chernoff's bounds, Hoeffding bounds, law of large numbers. Uniform convergence, Glivenko-Cantelli classes. VC theory. Rademacher averages. Empirical processes. Talagrand's inequality, Bousquet's inequality.


  • G. Lugosi: Concentration of measure inequalities. [ps]