论文标题
一个可靠的框架，用于分析双线性游戏中的基于梯度的动态
A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
论文作者
论文摘要
在这项工作中，我们建立了一个频域框架，用于分析线性最小值优化问题中的基于梯度的算法。具体而言，我们的方法基于Z-Transform，这是一种在控制理论和信号处理中应用的强大工具，以表征线性离散时间系统。我们采用我们的框架来获得对乐观梯度下降/上升（OGDA）的稳定性的首次严格分析，这是梯度下降/上升的自然变体，该变体显示出Daskalakis等人在双线性游戏中表现出最后近际趋同的收敛。 \ cite {dblp：journals/corr/corr/abs-1711-00141}。重要的是，我们的分析比现有的分析更简单，更简洁。 此外，基于OGDA的直觉，我们考虑了一个基于梯度的算法的一般家族，该算法通过多个历史步骤来增强优化的记忆。我们将双线性游戏中动力学的融合（将其融合到鞍点）降低到多项式的稳定性，为此，有效的算法方案是完善的。作为直接推论，我们获得了一类广泛的算法（包含OGDA作为特殊情况），并获得了最后近期收敛的保证。
In this work, we establish a frequency-domain framework for analyzing gradient-based algorithms in linear minimax optimization problems; specifically, our approach is based on the Z-transform, a powerful tool applied in Control Theory and Signal Processing in order to characterize linear discrete-time systems. We employ our framework to obtain the first tight analysis of stability of Optimistic Gradient Descent/Ascent (OGDA), a natural variant of Gradient Descent/Ascent that was shown to exhibit last-iterate convergence in bilinear games by Daskalakis et al. \cite{DBLP:journals/corr/abs-1711-00141}. Importantly, our analysis is considerably simpler and more concise than the existing ones. Moreover, building on the intuition of OGDA, we consider a general family of gradient-based algorithms that augment the memory of the optimization through multiple historical steps. We reduce the convergence -- to a saddle-point -- of the dynamics in bilinear games to the stability of a polynomial, for which efficient algorithmic schemes are well-established. As an immediate corollary, we obtain a broad class of algorithms -- that contains OGDA as a special case -- with a last-iterate convergence guarantee to the space of Nash equilibria of the game.
