Class 16: Sample Complexity via Rademacher Averages

Instructor: Sasha Rakhlin

Description

We define the notion of sample complexity and go on to discuss Rademacher averages and symmetrization.

Slides

Slides for this lecture: PDF

Class Reference Material

L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2017
 

Suggested Reading

• L. Devroye, L. Gyorfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996.
• O. Bousquet, S. Boucheron, G. Lugosi Introduction to Statistical Learning Theory, Advanced Lectures on Machine Learning pp 169-207.