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
- March, 19th
- Regret learning in games
- March, 26th
- Extensive-form games
Evaluation
Evaluation will be 100% project-based.
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.
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] Minimizing regret on treeplexes with approachability
Candidates for validation
- Camilli, Petra — ★★ [theory] A finer analysis for convex optimization with step-sizes
- Delbreil, Elisa — ★★★ [theory, code] Approachability algorithms based on time-dependent norms
- 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
- Villeroy de Galhau, Gaspard — ★★ [theory] AdaGrad with normalization
- Yuan, Hongyi — ★★ [theory] Dual averaging variants of AdaGrad
- Benedicto Plagnes, Hugo — ★★★ [theory, code] Variants of AdaGrad-Norm and application to games