mlsanityData to 14 Oct 2026

Faster Rates for Convex-Concave Games

arXiv 1805.06792 ↗First posted 17 May 2018cs.LG stat.MLcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 3; 2023: 7; 2024: 4; 2025: 4.

23 papers.

Sort:

By area:

  1. 2023Nash Learning from Human Feedbackcited by 224
  2. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  3. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 41
  4. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 16
  5. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  6. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  7. 2023Bitrate-Constrained DRO: Beyond Worst Case Robustness To Unknown Group Shiftscited by 9
  8. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  9. 2024Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descentcited by 7
  10. 2022On Accelerated Perceptrons and Beyondcited by 6
  11. 2021Local and Global Uniform Convexity Conditionscited by 4
  12. 2021On the Initialization for Convex-Concave Min-max Problemscited by 4
11 more
  1. 2023Projection-Free Online Convex Optimization via Efficient Newton Iterationscited by 4
  2. 2024Proximal Point Method for Online Saddle Point Problemcited by 3
  3. 2021Efficient Online-Bandit Strategies for Minimax Learning Problemscited by 2
  4. 2023Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Setscited by 2
  5. 2025Optimism Without Regularization: Constant Regret in Zero-Sum Gamescited by 2
  6. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  7. 2025Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universalitycited by 1
  8. 2023Federated Composite Saddle Point Optimizationcited by 0
  9. 2023Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methodscited by 0
  10. 2023Online Saddle Point Problem and Online Convex-Concave Optimizationcited by 0
  11. 2024Barriers to Welfare Maximization with No-Regret Learningcited by 0