# Accelerated regularized learning in finite N-person games

arXiv: https://arxiv.org/abs/2412.20365 · HTML: https://mlsanity.com/paper/2412.20365/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 29 Dec 2024.

## Builds on (most cited first, 20 of 20)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [Riemannian game dynamics](https://mlsanity.com/paper/1603.09173/) (2016)
- [On Passivity, Reinforcement Learning and Higher-Order Learning in Multi-Agent Finite Games](https://mlsanity.com/paper/1808.04464/) (2018)
- [On the robustness of learning in games with stochastically perturbed payoff observations](https://mlsanity.com/paper/1412.6565/) (2014)
- [Learning in nonatomic games, Part I: Finite action spaces and population games](https://mlsanity.com/paper/2107.01595/) (2021)
- [The equivalence of dynamic and strategic stability under regularized learning in games](https://mlsanity.com/paper/2311.02407/) (2023)
- [Inertial game dynamics and applications to constrained optimization](https://mlsanity.com/paper/1305.0967/) (2013)
- [Passivity Analysis of Higher Order Evolutionary Dynamics and Population Games](https://mlsanity.com/paper/1609.04952/) (2016)
- [Higher-Order Uncoupled Dynamics Do Not Lead to Nash Equilibrium -- Except When They Do](https://mlsanity.com/paper/2304.04282/) (2023)
- [Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discounting](https://mlsanity.com/paper/2111.09982/) (2021)
- [Learning in Games with Quantized Payoff Observations](https://mlsanity.com/paper/2209.04926/) (2022)

## Built on by (most cited first, 2 of 2)

- [Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games](https://mlsanity.com/paper/2505.19537/) (2025)
- [Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach](https://mlsanity.com/paper/2605.19392/) (2026)

## Abstract (arXiv)

Motivated by the success of Nesterov's accelerated gradient algorithm for convex minimization problems, we examine whether it is possible to achieve similar performance gains in the context of online learning in games. To that end, we introduce a family of accelerated learning methods, which we call "follow the accelerated leader" (FTXL), and which incorporates the use of momentum within the general framework of regularized learning - and, in particular, the exponential/multiplicative weights algorithm and its variants. Drawing inspiration and techniques from the continuous-time analysis of Nesterov's algorithm, we show that FTXL converges locally to strict Nash equilibria at a superlinear rate, achieving in this way an exponential speed-up over vanilla regularized learning methods (which, by comparison, converge to strict equilibria at a geometric, linear rate). Importantly, FTXL maintains its superlinear convergence rate in a broad range of feedback structures, from deterministic, full information models to stochastic, realization-based ones, and even when run with bandit, payoff-based information, where players are only able to observe their individual realized payoffs.