# Faster Rates for Convex-Concave Games

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 May 2018.

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

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Bitrate-Constrained DRO: Beyond Worst Case Robustness To Unknown Group Shifts](https://mlsanity.com/paper/2302.02931/) (2023)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [On Accelerated Perceptrons and Beyond](https://mlsanity.com/paper/2210.09371/) (2022)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Proximal Point Method for Online Saddle Point Problem](https://mlsanity.com/paper/2407.04591/) (2024)
- [Efficient Online-Bandit Strategies for Minimax Learning Problems](https://mlsanity.com/paper/2105.13939/) (2021)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality](https://mlsanity.com/paper/2511.06597/) (2025)
- [Federated Composite Saddle Point Optimization](https://mlsanity.com/paper/2305.15643/) (2023)
- [Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods](https://mlsanity.com/paper/2305.17544/) (2023)
- [Online Saddle Point Problem and Online Convex-Concave Optimization](https://mlsanity.com/paper/2312.06957/) (2023)
- [Barriers to Welfare Maximization with No-Regret Learning](https://mlsanity.com/paper/2411.01720/) (2024)

## Abstract (arXiv)

We consider the use of no-regret algorithms to compute equilibria for particular classes of convex-concave games. While standard regret bounds would lead to convergence rates on the order of O(T-1/2), recent work citepRS13,SALS15 has established O(1/T) rates by taking advantage of a particular class of optimistic prediction algorithms. In this work we go further, showing that for a particular class of games one achieves a O(1/T2) rate, and we show how this applies to the Frank-Wolfe method and recovers a similar bound citepD15. We also show that such no-regret techniques can even achieve a linear rate, O(exp(-T)), for equilibrium computation under additional curvature assumptions.