Online learning, links with optimization and games


Université Paris–Saclay — 2023–2024
Thursdays 2:30–5:45 — 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, 25th
Convexity tools
February, 1st
UMD Theory
February, 15th
Online optimization
February, 29th
Blackwell's approachability
March, 7th
Gradient methods in optimization
March, 14th
AdaGrad
March, 21th
Monotone operators and fixed point iterations
March, 28th
Regret learning in 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).

The deadline is April 21st, 23:59.

Candidates for validation

  1. Abbadi, Omar — ★★ [theory, code] UMD-based extension of AdaGrad-Norm and application to games
  2. André, Pascaline — ★★ [RL, code] Adaptive diagonal scalings for Q-learning
  3. Benali, Nafissa — ★★ [theory, code] Solving games with line-search
  4. Bertrand, Virgile — ★★ [theory, code] Solving games with alternating iterations
  5. Biechy, Lucas — ★★★ [theory, code] AdaGrad for approachability and application to games
  6. Boukir, Nabil — ★★★ [theory] Alternatives to FTRL and FTL
  7. Bulaich Mehamdi, Abdellah — ★★ [theory] Yet another algorithm for online strongly convex optimization
  8. Charles, Nicolas — ★★ [theory] Composite optimization
  9. Gaillard, Pierre — ★★ [theory, code] Sparse payoff vectors
  10. Gonidec, Robin — ★ [theory] Perceptron
  11. Kaichouch, Elias — ★ [theory, code] A hybrid of mirror descent and dual averaging
  12. Papegay-Vallet, Vincent — ★★ [theory] Asynchronous fixed point iterations
  13. Pierron, Alex — ★★ [theory, code] Solving games: extrapolation vs optimism
  14. Pla, Corentin — ★★★ [theory] Variants of AdaGrad-Norm and application to games
  15. Prevost, Adrien — ★★ [theory] Generalized regularizers
  16. Reyero Lobo, Angel — ★★ [theory] Hyperbolic entropy
  17. Riveline, Malkiel — ★★ [theory] AdaGrad-Diagonal and generalized co-coercivity
  18. Roche, Matisse — ★★ [theory, code] AdaGrad on the simplex and application to games
  19. Saidi Alaoui, Imad — ★ [theory] Optimistic iterations with arbitrary norms for solving games
  20. Scarcella, Dylan — ★★★ [code] Alternative to Vovk–Azoury–Warmuth
  21. Schwarz, Stefanie — ★ [theory] Online linear classification with absolute loss
  22. Sow, Dahibou — ★ [theory] Exponential weights with step-sizes
  23. Taupin, Jérôme — ★★★ [theory, code] Parameter-free approachability algorithms
  24. Vilhes, Samy — ★★ [theory] AdaGrad-Diagonal: Stronger adaptivity to smoothness
  25. Weng, Weihao — ★★★ [theory] Online Newton step
  26. Wu, Chengyang — ★★ [theory] Regret minimization with global costs
  27. Xu, Minrui — ★★ [theory] Sparse bandits
  28. Zhang, Zhiyuan — ★ [theory] Iterates based on squared Mahalanobis norms
  29. Zhou, Yanyu — ★★★★ [theory, code] On the Chambolle–Pock method