Minimax optimization has recently gained a lot of attention as adversarial architectures and algorithms proliferate. Often, smooth minimax games proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice for many applications (e.g., GAN training), the majority of existing theoretical analyses focus on simultaneous algorithms. In this paper, we study alternating gradient descent-ascent (Alt-GDA) in minimax games and show that Alt-GDA is superior to its simultaneous counterpart (Sim-GDA) in many settings. In particular, we prove that Alt-GDA achieves a near-optimal local convergence rate for strongly-convex strongly-concave problems while Sim-GDA converges with a much slower rate. Moreover, we show that the acceleration effect of alternating updates remains when the minimax problem has only strong concavity in the dual variables. Numerical experiments on quadratic minimax games validate our claims. Additionally, we demonstrate that alternating updates speed up GAN training significantly and the use of optimism only helps for simultaneous algorithms.

本文研究交替梯度下降-上升算法在极小极大博弈中的应用，表明交替更新算法在多个场景下比同步算法更优，能够在强凸-强凹问题上达到几乎最优的局部收敛速率。同时，作者还介绍了一种全局性能相同的子类应用于极小极大博弈上的积分二次约束理论。实证结果表明，交替更新加速了生成对抗网络的训练，但仅在同步算法上使用乐观主义才有帮助。

交替梯度下降上升法在极小极大优化中的近最优局部收敛