mlsanityData to 7 Oct 2026

Optimization, Learning, and Games with Predictable Sequences

arXiv 1311.1869 ↗First posted 8 Nov 2013cs.LG cs.GTcited by 187

Not on the map. Why?

Abstract (arXiv)

We provide several applications of Optimistic Mirror Descent, an online learning algorithm based on the idea of predictable sequences. First, we recover the Mirror Prox algorithm for offline optimization, prove an extension to Holder-smooth functions, and apply the results to saddle-point type problems. Next, we prove that a version of Optimistic Mirror Descent (which has a close relation to the Exponential Weights algorithm) can be used by two strongly-uncoupled players in a finite zero-sum matrix game to converge to the minimax equilibrium at the rate of O((log T)/T). This addresses a question of Daskalakis et al 2011. Further, we consider a partial information version of the problem. We then apply the results to convex programming and exhibit a simple algorithm for the approximate Max Flow problem.

Key facts. Cited by 187 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Nov 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 29; 2022: 39; 2023: 35; 2024: 22; 2025: 28; 2026: 33.

187 papers.

Sort:

By area:

  1. 2023Nash Learning from Human Feedbackcited by 220
  2. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  3. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  4. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  5. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  6. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  7. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  8. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  9. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  10. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  11. 2022On-Demand Sampling: Learning Optimally from Multiple Distributionscited by 39
  12. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
38 more
  1. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 35
  2. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  3. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 34
  4. 2021Online Learning with Optimism and Delaycited by 33
  5. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  6. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 30
  7. 2023Multi-agent Reinforcement Learning: A Comprehensive Surveycited by 30
  8. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  9. 2021A Max-Min Entropy Framework for Reinforcement Learningcited by 28
  10. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  11. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  12. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  13. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  14. 2024Direct Preference Optimization With Unobserved Preference Heterogeneity: The Necessity of Ternary Preferencescited by 23
  15. 2022Online PAC-Bayes Learningcited by 22
  16. 2022A unified stochastic approximation framework for learning in gamescited by 22
  17. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  18. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  19. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  20. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 20
  21. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  22. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  23. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  24. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  25. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  26. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  27. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  28. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  29. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  30. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  31. 2022Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyondcited by 16
  32. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
  33. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
  34. 2025Extragradient Preference Optimization (EGPO): Beyond Last-Iterate Convergence for Nash Learning from Human Feedbackcited by 15
  35. 2021Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Gamescited by 14
  36. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  37. 2023Online-to-PAC Conversions: Generalization Bounds via Regret Analysiscited by 14
  38. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14

50 most cited of 187 All 187 (JSON)