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 differentiable games where the goal is to find a Nash
equilibrium. The machine learning community has recently started using variants
of the gradient method (GD). Prime examples are extragradient (EG), the
optimistic gradient method (OG) and consensus optimization (CO), which enjoy
linear convergence in cases like bilinear games, where the standard GD fails.
The full benefits of theses relatively new methods are not known as there is no
unified analysis for both strongly monotone and bilinear games. We provide new
analyses of the EG's local and global convergence properties and use is to get
a tighter global convergence rate for OG and CO. Our analysis covers the whole
range of settings between bilinear and strongly monotone games. It reveals that
these methods converge via different mechanisms at these extremes; in between,
it exploits the most favorable mechanism for the given problem. We then prove
that EG achieves the optimal rate for a wide class of algorithms with any
number of extrapolations. Our tight analysis of EG's convergence rate in games
shows that, unlike in convex minimization, EG may be much faster than GD.

通过分析梯度方法在达到纳什均衡时的线性收敛特性，证明了变异梯度方法在双线性博弈和强单调性博弈中的各种表现，并发现了这些方法在极端情况下收敛机制的差异。同时证明了变异梯度可以在任意外推次数的情况下实现优化率，一个广泛算法类别的最佳值

梯度基方法在全谱游戏中的紧密一致分析

A Tight and Unified Analysis of Gradient-Based Methods for a Whole  Spectrum of Games

A growing number of learning methods are actually differentiable games whose
players optimise multiple, interdependent objectives in parallel -- from GANs
and intrinsic curiosity to multi-agent RL. Opponent shaping is a powerful
approach to improve learning dynamics in these games, accounting for player
influence on others' updates. Learning with Opponent-Learning Awareness (LOLA)
is a recent algorithm that exploits this response and leads to cooperation in
settings like the Iterated Prisoner's Dilemma. Although experimentally
successful, we show that LOLA agents can exhibit 'arrogant' behaviour directly
at odds with convergence. In fact, remarkably few algorithms have theoretical
guarantees applying across all (n-player, non-convex) games. In this paper we
present Stable Opponent Shaping (SOS), a new method that interpolates between
LOLA and a stable variant named LookAhead. We prove that LookAhead converges
locally to equilibria and avoids strict saddles in all differentiable games.
SOS inherits these essential guarantees, while also shaping the learning of
opponents and consistently either matching or outperforming LOLA
experimentally.

该论文提出了稳定对手塑造方法，该方法通过插值实现了区分对手学习（LOLA）和稳定对手塑造的最佳属性，并在可微分游戏中表现出卓越的性能。

可微分游戏中的稳定对手塑造

Stable Opponent Shaping in Differentiable Games

Games generalize the single-objective optimization paradigm by introducing
different objective functions for different players. Differentiable games often
proceed by simultaneous or alternating gradient updates. In machine learning,
games are gaining new importance through formulations like generative
adversarial networks (GANs) and actor-critic systems. However, compared to
single-objective optimization, game dynamics are more complex and less
understood. In this paper, we analyze gradient-based methods with momentum on
simple games. We prove that alternating updates are more stable than
simultaneous updates. Next, we show both theoretically and empirically that
alternating gradient updates with a negative momentum term achieves convergence
in a difficult toy adversarial problem, but also on the notoriously difficult
to train saturating GANs.

本文分析了基于动量的梯度下降法在线性游戏中的应用，证明交替更新比同时更新更加稳定。同时，理论和实验都表明带有负动量项的交替梯度下降法能够实现在困难的攻击问题和难以训练的 saturating GANs 中的收敛。