Understanding Statistical Learning Theory

Code: MA690 | L-T-P-C: 3-0-0-6

Prerequisites: MA225 or MA 323 or MA590 or equivalent

Course Content/ Syllabus: Probabilistic Formulations of Prediction Problems; Linear Threshold Functions and the Perceptron Algorithm; Minimax Risk Bounds for Linear Threshold Functions; Kernel Methods: Support Vector Machines; Review of Constrained Optimization; Soft-margin SVMs, Reproducing kernel Hilbert spaces; Representer theorem; Constructing kernels; Convex loss versus 0-1 loss; logistic regression; softmax regression; Regularization; AdaBoost; AdaBoost and large margin classifiers; AdaBoost; Risk bounds; Concentration inequalities ; Glivenko-Cantelli classes and Rademacher averages; Rademacher averages and Vapnik-Chervonenkis dimension; Sauer's Lemma; Rademacher averages and growth function; Growth function bounds for parameterized binary classes; Covering numbers; Model selection; Online learning: Halving algorithm. Exponential weights; Online convex optimization: gradient descent; Online convex optimization: mirror descent; Online convex optimization: ridge regression, lasso, elastic net, k-nearest neighbour, adaptivity; Convex optimization in a combined regression (Cobra), XGBoost and Adaboost set up; Formulation of Neural network, recommendation systems as Non-convex optimization with specific theoretical analysis ; Follow the perturbed leader, online shortest path; Online bandit problems; Universal portfolios; Online to batch conversions.

Texts:

1. Shar Shalev-Shwartz and Shar Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014

References:

1. Vladimir N. Vapnik, The Nature of Statistical Learning Theory, Springer, 2013.
2. Christopher Bishop, Pattern Recognition and Machine Learning, Springer, 2006
3. Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning, Springer Series in Statistics, 2009