Faster Rates for ConvexConcave Games
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:15951625, 2018.
Abstract
We consider the use of noregret algorithms to compute equilibria for particular classes of convexconcave 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 FrankWolfe method and recovers a similar bound \citep{D15}. We also show that such noregret techniques can even achieve a linear rate, $O(\exp(T))$, for equilibrium computation under additional curvature assumptions.
Related Material


