Online learning, links with optimization and games
Université Paris–Saclay — 2024–2025
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, 23th
- Convexity tools — Exercices
- January, 30th
- UMD Theory — Exercices
- February, 6th
- Online linear optimization — Exercices
- February, 13th
- Online convex optimization — Exercices
- March, 6th
- Blackwell's approachability
- March, 13th
- Gradient methods in optimization & AdaGrad
- March, 20th
- Regret learning in games
- March, 27th
- 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).
Available projects
- ★★ [theory] Regret minimization with global costs
Candidates for validation
- Brucato, Lorenzo
- Caudard, Joris
- Chahmirian, Armen
- El Aafi, Salma
- Glaib, Ilyas
- Gou, Xinyi
- Kashou, Layth — ★ [theory, code] A hybrid of mirror descent and dual averaging
- Kharisov, Timur — ★★★ [theory, code] Approachability-based optimization
- Khusainov, Marat — ★★ [theory] AdaGrad-Diagonal: Stronger adaptivity to smoothness
- Lahmi, Elona
- Le Dréau, Vincent
- Lemaire, Alicia
- Loret, Alexandre — ★★ [theory] Yet another algorithm for online strongly convex optimization
- Pradignac, Alexandre
- Riveiro, Ilian
- Salama, Saja
- Tapia Riera, Guido Samuel — ★★★ [theory] Finer approachability bounds
- Vantalon, Gautier
- Yagouti, Redouane