Recent successes of game-theoretic formulations in ML have caused a
resurgence of research interest in differentiable games. Overwhelmingly, that
research focuses on methods and upper bounds on their speed of convergence. In
this work, we approach the question of fundamental iteration complexity by
providing lower bounds to complement the linear (i.e. geometric) upper bounds
observed in the literature on a wide class of problems. We cast saddle-point
and min-max problems as 2-player games. We leverage tools from single-objective
convex optimisation to propose new linear lower bounds for convex-concave
games. Notably, we give a linear lower bound for $n$-player differentiable
games, by using the spectral properties of the update operator. We then propose
a new definition of the condition number arising from our lower bound analysis.
Unlike past definitions, our condition number captures the fact that linear
rates are possible in games, even in the absence of strong convexity or strong
concavity in the variables.

提出了一种使用单一目标凸优化工具构建适用于各种问题的线性下界，特别是在 n 个玩家可微分对抗博弈中使用谱方法得到了线性下界。

可微博弈的线性下界与条件数

Linear Lower Bounds and Conditioning of Differentiable Games

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.

研究使用无遗憾算法计算特定类别的凸 - 凹游戏的平衡，展示了特定游戏类别可实现 O (1/T^2) 的速率，同时展示了此类无遗憾技术在采用额外曲率假设的情况下甚至可以实现线性速率，文中讨论的无遗憾算法可实现的有效范围包括乐观预测算法、Frank-Wolfe 方法等。