ECE 299: Statistical Learning Theory (Spring 2011)

Introduction, history, overview, and administrivia.

• Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi, Introduction to statistical learning theory, in Advanced Lectures in Machine Learning (O. Bousquet, U. von Luxburg, and G. Rätsch, editors), pp. 208-204, Springer, 2004
• Theodoros Evgeniou, Massimiliano Pontil, and Tomaso Poggio, Statistical learning theory: a primer, International Journal of Computer Vision, vol. 38, no. 1, pp. 9-13, 2000
• Ulrike von Luxburg and Bernhard Schölkopf, Statistical learning theory: models, concepts, and results (http://arxiv.org/abs/0810.4752), 2008
• Tomaso Poggio and Steve Smale, The mathematics of learning: dealing with data, Notices of the American Mathematical Society, vol. 50, no. 5, pp. 537-544, 2003
• Cosma Shalizi, Learning theory (formal, computational or statistical) (http://cscs.umich.edu/~crshalizi/notebooks/learning-theory.html), Jan 09, 2011 [A nice succinct summary, with lots of useful references]

Concentration inequalities: Markov, Chebyshev, McDiarmid (bounded differences inequality), examples

• Torben Hagerup and Christine Rüb, A guided tour of Chernoff bounds, Information Processing Letters, vol. 33, no. 6, pp. 305-308, 1990 [Short and sweet]
• Gábor Lugosi, Concentration-of-measure inequalities, lecture notes, 2003-2009
• Colin McDiarmid, Concentration, Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 1-46, 1998
• Terence Tao, Concentration of measure (http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/), Jan 03, 2010

Formulaton of the learning problem: concept and function learning; agnostic (model-free) learning; consistency; Probably Approximately Correct (PAC) learning; Empirical Risk Minimization

• Dana Angluin, Queries and concept learning, Machine Learning, vol. 2, no. 4, pp. 319-342, 1988
• David Haussler, PAC learning model, and decision-theoretic generalizations, with applications to neural nets, in Mathematical Perspectives on Neural Networks, Lawrence Erlbaum Associates, 1995
• Leslie Valiant, A theory of the learnable, Communications of the ACM, vol. 27, no. 11, pp. 1134-1142

Empirical Risk Minimization: abstract risk bounds and Rademacher averages -- stochastic inequalities for ERM; Rademacher averages (structural results, Finite Class Lemma); introduction to VC classes

• Peter Bartlett and Shahar Mendelson, Rademacher and Gaussian complexities: risk bounds and structural results, Journal of Machine Learning Research, vol. 3, pp. 463-482, 2002
• Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi, Theory of classification: a survey of recent advances, ESAIM Probability and Statistics, vol. 9, pp. 323-375, 2005 (Section 3 only)

• Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM, vol. 36, no. 4, pp. 929-965, 1989
• Gábor Lugosi, Pattern classification and learning theory, in Principles of Nonparametric Learning (L. Györfi, editor), pp. 1-56, Springer, 2002 (parts of Section 1.4)

• Robert Gray and David Neuhoff, Quantization, IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2325-2383, 1998
• Tamás Linder, Learning-theoretic methods in vector quantization, in Principles of Nonparametric Learning (L. Györfi, editor), Springer, 2002
• Tamás Linder, Gábor Lugosi and Kenneth Zeger, Rates of convergence in the source coding theorem, in empirical quantizer design, and in universal lossy source coding, IEEE Transactions on Information Theory, vol. 40, no. 6, pp. 1728-1740, 1994

• Peter Bartlett, Michael Jordan, and Jon McAuliffe, Convexity, classification, and risk bounds, Journal of the American Statistical Association, vol. 101, no. 473, pp. 138-156, 2006
• Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi, Theory of classification: a survey of recent advances, ESAIM Probability and Statistics, vol. 9, pp. 323-375, 2005

• V. Koltchinskii, C. T. Abdallah, M. Ariola, P. Dorato, and D. Panchenko, Statistical learning control of uncertain systems: it is better than it seems, University of New Mexico Technical Report EECE-TR-00-001, April 2000
• M. Vidyasagar, Randomized algorithms for robust controller synthesis using statistical learning theory, Automatica, vol. 37, pp. 1515-1528, 2001