Faster Rates for Convex-Concave Games

2018/05/17 by Jacob Abernethy, Abernethy, Jacob, Kevin A. Lai +5 · 4 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1805.06792

openalex publication_date 2018/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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/T²) 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.

Citations

• Convex relaxations of structured matrix factorizations
• Zur Theorie der Gesellschaftsspiele

Cited by

• Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
• Pure Exploration via Frank-Wolfe Self-Play
• Optimism Without Regularization: Constant Regret in Zero-Sum Games
• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise

Related

• Acceleration through Optimistic No-Regret Dynamics
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
• Near-Optimal No-Regret Learning Dynamics for General Convex Games
• Efficient Regret Minimization in Non-Convex Games