mlsanityData to 7 Oct 2026

Online Learning: A Modern Introduction Using Convex Optimization

arXiv 1912.13213 ↗First posted 31 Dec 2019cs.LG math.OC stat.MLcited by 407

Not on the map. Why?

Abstract (arXiv)

In this book, I introduce the concepts of online learning through a modern view based on convex optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I attempted to unify all the literature as instantiations of Online Mirror Descent and Follow-the-Regularized-Leader (and their variants). I paid particular attention to the issue of tuning the parameters of the algorithms, through adaptive and parameter-free online learning algorithms. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. Building on fundamental algorithms and concepts, I also cover advanced topics, including black-box reductions, saddle-point optimization, sequential investment, and non-stationary forms of regret analysis. Finally, I conclude with a selection of applications of online learning to domains far from it, such as generalization theory and concentration inequalities. I attempted to maintain an informal, yet mathematically rigorous, tone throughout the book. Moreover, all the included proofs have been carefully chosen to be as simple and as short as possible. This also means that sometimes I have added one or two additional assumptions, just to simplify the proofs.

Key facts. Cited by 407 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 39; 2022: 53; 2023: 67; 2024: 82; 2025: 86; 2026: 80.

407 papers.

Sort:

By area:

  1. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  2. 2024The Road Less Scheduledcited by 158
  3. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  4. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  5. 2021Continual Backprop: Stochastic Gradient Descent with Persistent Randomnesscited by 79
  6. 2023Improved Online Conformal Prediction via Strongly Adaptive Online Learningcited by 76
  7. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  8. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  9. 2024From Words to Numbers: Your Large Language Model Is Secretly A Capable Regressor When Given In-Context Examplescited by 55
  10. 2022Making SGD Parameter-Freecited by 50
  11. 2022Parameter-free Mirror Descentcited by 45
  12. 2023GNNDelete: A General Strategy for Unlearning in Graph Neural Networkscited by 43
38 more
  1. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 42
  2. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  3. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
  4. 2021Online Learning with Optimism and Delaycited by 33
  5. 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 33
  6. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  7. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  8. 2021Online Apprenticeship Learningcited by 28
  9. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  10. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  11. 2022Generalization Bounds via Convex Analysiscited by 27
  12. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  13. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  14. 2023MoMo: Momentum Models for Adaptive Learning Ratescited by 24
  15. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  16. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 23
  17. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  18. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  19. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  20. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  21. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  22. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  23. 2025Why Gradients Rapidly Increase Near the End of Trainingcited by 21
  24. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  25. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  26. 2023Mechanic: A Learning Rate Tunercited by 20
  27. 2024Nearly Minimax Optimal Regret for Multinomial Logistic Banditcited by 20
  28. 2024Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignmentcited by 20
  29. 2022Adaptively Exploiting d-Separators with Causal Banditscited by 18
  30. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  31. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  32. 2023Normalized Gradients for Allcited by 18
  33. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  34. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  35. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  36. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  37. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  38. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16

50 most cited of 407 All 407 (JSON)