# Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback arXiv: https://arxiv.org/abs/2310.14085 · HTML: https://mlsanity.com/paper/2310.14085/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Builds on 58 of its 127 references that are in the map. - First posted on arXiv 21 Oct 2023. ## Builds on (most cited first, 30 of 58) - [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019) - [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019) - [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014) - [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018) - [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013) - [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018) - [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018) - [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016) - [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018) - [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018) - [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018) - [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017) - [Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates](https://mlsanity.com/paper/1905.09997/) (2019) - [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015) - [Online Optimization : Competing with Dynamic Comparators](https://mlsanity.com/paper/1501.06225/) (2015) - [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016) - [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016) - [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016) - [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016) - [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019) - [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018) - [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021) - [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016) - [Variants of RMSProp and Adagrad with Logarithmic Regret Bounds](https://mlsanity.com/paper/1706.05507/) (2017) - [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020) - [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021) - [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021) - [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021) - [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017) - [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018) ## Built on by (most cited first, 6 of 6) - [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025) - [Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback](https://mlsanity.com/paper/2602.21436/) (2026) - [Is Thompson Sampling Susceptible to Algorithmic Collusion?](https://mlsanity.com/paper/2405.17463/) (2024) - [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026) - [Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points](https://mlsanity.com/paper/2602.10565/) (2026) - [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026) ## Abstract (arXiv) Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions: (1) in the single-agent setting, it achieves an optimal regret of Theta(log T) for strongly convex cost functions; and (2) in the multi-agent setting of strongly monotone games, with each agent employing OGD, we obtain last-iterate convergence of the joint action to a unique Nash equilibrium at an optimal rate of Theta(frac1T). While these finite-time guarantees highlight its merits, OGD has the drawback that it requires knowing the strong convexity/monotonicity parameters. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters. In the single-agent setting, our algorithm achieves O(log2(T)) regret under strong convexity, which is optimal up to a log factor. Further, if each agent employs textsfAdaOGD in strongly monotone games, the joint action converges in a last-iterate sense to a unique Nash equilibrium at a rate of O(fraclog3 TT), again optimal up to log factors. We illustrate our algorithms in a learning version of the classical newsvendor problem, where due to lost sales, only (noisy) gradient feedback can be observed. Our results immediately yield the first feasible and near-optimal algorithm for both the single-retailer and multi-retailer settings. We also extend our results to the more general setting of exp-concave cost functions and games, using the online Newton step (ONS) algorithm.