A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games

Abstract

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. (ICLR 2018). 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 asa special case – with a last-iterate convergence guarantee to the space of Nash equilibria of the game.