Learning Theory and High-Dimensional Statistics (2027, 7 + 3 Hp)

Learning from data is a cornerstone of modern artificial intelligence. This course provides a rigorous introduction to the key mathematical concepts needed to understand and analyze learning algorithms. The first part focuses on fundamental tools for dealing with high dimensionality in probability and statistics. The second part applies these tools to the analysis of learning algorithms.

• Teacher: Antonio Horta Ribeiro
• Credits: 7 (+ 3) HP where the optional extra three credits is given if the student develop a final project.

Register here!

Dates

The course will run from the end of January to March 2027. The initial plan is to have session scheduled on Thursdays from 13:15 to 15:00.

• Part I (tentative dates): 21 and 28 January; 4 and 11 February.
• Part II (tentative dates): 25 February; 4, 11, and 18 March.

Course schedule and content

The course will consist of eight lectures, with the preliminary schedule and content outlined below.

Part 1: High-dimensional probability and statistics

L1: Introduction

• Preliminaries with random variables
• Basic tail and concentration bounds
  • Markov, Chebyshev, and Chernoff bounds
  • Sub-Gaussian random variables

L2: Concentration of measure

• Concentration bounds
  • Hoeffding bounds
  • Sub-exponential random variables
  • Bernstein’s inequality
• Random vectors
  • Concentration of the norm
  • Sub-Gaussian random vectors

L3: Uniform laws of large numbers

• Glivenko–Cantelli theorem
• Rademacher complexity
• VC dimension

L4: Metric entropy and its uses

• Covering numbers
  • Metric-entropy bounds for sub-Gaussian processes
  • Chaining
• Slepian, Sudakov–Fernique, and contraction inequalities
• Sudakov lower bound

Part 2: Learning theory

L5: Fixed- and random-design analysis

• Introduction to supervised learning
• Empirical risk minimization
• Fixed- and random-design analysis
  • Least squares
  • Ridge regression

L6: Learning rates for local averaging and sparse methods

• Local averaging methods
• Random- and fixed-design analysis of sparse methods
  • Lasso
  • Othe l1-penalized methods

L7: Reproducing kernel Hilbert spaces and learning rates for kernel methods

• Reproducing kernel Hilbert spaces
  • Hilbert spaces
  • Reproducing property
  • Mercer’s theorem
  • Sobolev spaces
• Estimation with kernels
  • Gaussian and Matérn kernels
  • Random features and column sampling
  • Fixed-design analysis
  • Random-design analysis

L8: Approximation and estimation error in neural networks

• Approximation error in neural networks
  • Single-hidden-layer networks
  • Barron norm
• Relationship with kernel methods

Examination

• Weekly homework
• Participation and discussion in class
• A project for the additional 3 hp

Prerequisites

• Undergraduate courses in linear algebra, probability theory, and statistics
• Statistical machine learning

Literature

Textbooks

1. Wainwright, M. J. (2019). High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press. Chapters 2, 4, 5, 6, and 12.
2. Vershynin, R. (2026). High-Dimensional Probability. 2nd edition. Cambridge University Press. Parts of Chapters 1–8, can be used instead of 1
3. Bach, F. (2024). Learning Theory from First Principles. MIT Press. Chapters 2, 3, 4, 7, and 9.

Additional references

The course will also draw on the following papers: Paper A in L8, Paper B in L4, Paper C in L3, and Papers D and E in L5.

A. Bach, F. (2017). “Breaking the curse of dimensionality with convex neural networks.” Journal of Machine Learning Research, 18(19), 1–53.

B. Bartlett, P. L., Foster, D. J., & Telgarsky, M. J. (2017). “Spectrally-normalized margin bounds for neural networks.” Advances in Neural Information Processing Systems, 30.

C. Bartlett, P. L., & Mendelson, S. (2002). “Rademacher and Gaussian complexities: Risk bounds and structural results.” Journal of Machine Learning Research, 3, 463–482.

D. Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). “Reconciling modern machine-learning practice and the classical bias–variance trade-off.” Proceedings of the National Academy of Sciences, 116(32), 15849–15854.

E. Curth, A., Jeffares, A., & van der Schaar, M. (2023). “A U-turn on double descent: Rethinking parameter counting in statistical learning.” Advances in Neural Information Processing Systems, 36, 55932–55962.