Faster Rates for Convex-Concave Games

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 \citep{RS13,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^2)$ rate, and we show how this applies to the Frank-Wolfe method and recovers a similar bound \citep{D15}. We also show that such no-regret techniques can even achieve a linear rate, $O(\exp (-T))$, for equilibrium computation under additional curvature assumptions.

COLT 2018

References in corpus (2)

• Fast Convergence of Regularized Learning in Games
• Convex relaxations of structured matrix factorizations

Cited by in corpus (10)

• Last-iterate convergence rates for min-max optimization
• Projection-Free Optimization on Uniformly Convex Sets
• Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Curvature of Feasible Sets in Offline and Online Optimization
• Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Dynamic Data-Driven Estimation of Non-Parametric Choice Models
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Efficient Online-Bandit Strategies for Minimax Learning Problems