Statistics and optimization in high dimensions

Toulouse 3 Paul Sabatier, M2 Research and Innovation

Lecture notes, Exam.

The class will be taught in English.

This page contains supporting materials, exercises and practical sessions. Practicals sessions are given in the form of a Python notebook which can be run using Jupyter or online using Google colab.

Feedback form

Students who took the course are invited to fill the following feedback form.

Class sessions

Session 1: Introduction, sub-gaussian random variables
- Regression, Bayes error, conditional expectation.
- Subgaussian random variables, characterization, concentration, uniform concentration.
- Supporting material, proofs and exercises
- Practical session
Session 2: Linear regression
- Fixed design model, least squares, bound in expectation and high probability, minimax optimality.
- Introduction of sparsity, constrained least squares, penalized least squares.
- Supporting material and exercises
- Slides
- Practical session
Session 3: Penalized linear regression, compressed sensing
- Bound in high probability for penalized models.
- Random matrices, fast rates for Lasso, Compressed sensing.
- Supporting material and exercises
- Slides
- Practical session
Session 4: Computation, Complexity, Conic Hierarchy.
- Computational complexity theory, NP hardness for sparse estimation.
- Convex analysis, conic programming, interior point methods, polynomial time solvability.
- Supporting material and exercises
- Slides
- Try the previous Practical session with l0 norm instead of l1.
Session 5: First order methods.
- Introduction to gradient dynamics, nonsmooth analysis, subgradient and Legendre transform.
- Composite objectives, proximal decomposition, lower bounds and acceleration.
- Supporting material and exercises
- Slides
- Practical session
Session 6: Stochastic algorithms.
- Stochastic approximation, algorithms for large sums, convergence rates.
- Block decomposition method, convergence rates for random blocks.
- Supporting material
- Slides
- Consider the Lasso problem from the previous Practical session, try stochastic proximal gradient and block proximal gradient. Rescale the iteration counter so that each method perform roughly the same number of basic vector operation at each iteration. Compare batch composite optimization methods.