[edit]
Faster Rates for Convex-Concave Games
Proceedings of the 31st Conference On Learning Theory, PMLR 75:1595-1625, 2018.
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/T2) 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.