General Information

Classes (Tutorials)

Syllabus

• Statistical learning frameworks for prediction, estimation, and online learning.
• Probability:
• Maximal inequalities.
• Rademacher and Gaussian complexities.
• Elements of VC theory.
• Covering and packing numbers.
• Chaining.
• Concentration inequalities.
• Statistics:
• Bayes decision rules.
• Empirical risk minimisation. Error decomposition: generalisation, optimisation, and approximation.
• Learning via uniform convergence, margin bounds, and algorithmic stability.
• Regularisation: explicit (constraints and penalisation) and implicit (algorithmic).
• Convex loss surrogates.
• Slow and fast rates.
• Minimax lower bounds and hypothesis testing.
• Optimisation:
• Elements of convex theory.
• Oracle model. Gradient descent. Mirror descent.
• Stochastic oracle model. Stochastic gradient descent. Stochastic mirror descent. Variance reduction techniques.
• Online optimisation.
• Examples:
• Linear predictors, including Boosting.
• Non-linear predictors, including Support Vector Machines and Neural Networks.
• High-dimensional estimators for sparse and low-rank problems, including Lasso.
• Online learning, including multi-armed bandit problems, reinforcement learning and algorithms.

• Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
• Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning, 2015.
• Ramon van Handel. Probability in High Dimension. Lecture notes available online, 2016.
• Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Book available online (draft).
• Martin J. Wainwright. High-Dimensional Statistics. A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.

• The course requires a good level of mathematical maturity. Students are expected to have a working knowledge of core concepts in probability theory (basic properties of probabilities, such as union bounds, and of conditional expectations, such as the tower property; basic inequalities, such as Markov's and Jensen's), statistics (confidence intervals, hypothesis testing), and linear algebra (matrix-vector operations, eigenvalues and eigenvectors; basic inequalities, such as Cauchy-Schwarz's and Hölder's). Previous exposure to machine learning (empirical risk minimisation, overfitting, regularisation) is recommended.
• Students would benefit from being familiar with the material covered in SB2.1 (formerly SB2a) Foundations of Statistical Inference (in particular, Decision Theory) and in SB2.2 (formerly SB2b) Statistical Machine Learning.