Online learning, links with optimization and games
Université Paris–Saclay — 2025–2026
Thursdays 9:00–12:15 — Room 1A7
This course proposes a unified presentation of regret minimization for adversarial online learning problems, and its application to various problems such as Blackwell's approachability, optimization algorithms (GD, Nesterov, SGD, AdaGrad), variational inequalities with monotone operators (Mirror-Prox, Dual Extrapolation), fixed-point iterations (Krasnoselskii-Mann), and games. The presentation aims at being modular, so that introduced tools and techniques could easily be used to define and analyze new algorithms.
Schedule
- January, 22th
- Convexity tools — Exercices
- January, 29th
- UMD Theory — Exercices
- February, 5th
- Online linear optimization — Exercices
- February, 12th
- Online convex optimization — Exercices
- February, 19h
- Blackwell's approachability — Exercices
- March, 12th
- Gradient methods in optimization & AdaGrad — Exercices
- March, 19th
- Regret learning in games
- March, 26th
- Extensive-form games
Evaluation
Evaluation will be 100% project-based.
More projects will become available progressively. A project can be attributed to at most one student. You must choose a project below (first come, first served) and notify me by sending an e-mail.
Projects have various levels of estimated difficulty, indicated by a number of stars. Grading will take that into account. If you are facing important difficulties, you can ask for help by sending me an e-mail.
AI is allowed, but should be used with caution, as it can output erroneous or absurd answers. A project that contains wrong AI-generated answers, or right anwsers that does not fit the formalism of the course, cannot obtain a good grade.
Completed work must be sent by e-mail and may contain several files (e.g. a pdf and a Jupyter notebook).
If you need your grade early (for e.g. applications), you can send your project one week before the date on which you need your grade.
Available projects
- ★ [theory,code] Convex optimization with line-search
- ★★★★ [theory, code] Minimizing regret on treeplexes with approachability
Candidates for validation
- Benedicto Plagnes, Hugo — ★★★ [theory, code] Variants of AdaGrad-Norm and application to games
- Camilli, Petra — ★★ [theory] A finer analysis for convex optimization with step-sizes
- Delbreil, Elisa — ★★★ [theory, code] Approachability algorithms based on time-dependent norms
- Gleyo, Alexis — ★★ [theory] Matrix exponential weights
- Jiang, Bingjian — ★★ [theory, code] UMD-based extension of AdaGrad-Norm and application to games
- Luo, Xiangyu — ★★ [theory, code] A generalized approach for nonsmooth convex optimization
- Mas, Fanny — ★★ [theory] AdaGrad-Diagonal: Stronger adaptivity to smoothness
- Melan, David — ★★★ [theory, code] Approachability-based optimization
- Pefura Yone, Eric — ★★ [theory] Composite optimization
- Ren, Fangdu — ★ [theory, code] A hybrid of mirror descent and dual averaging
- Tarmadi, Hamza — ★★ [theory,code] Alternative algorithms for stochastic convex optimization
- Villain, Tanguy — ★★★ [theory, code] An alternative approach for smooth convex optimization
- Villeroy de Galhau, Gaspard — ★★ [theory] AdaGrad with normalization
- Yuan, Hongyi — ★★ [theory] Dual averaging variants of AdaGrad