Tight Convergence Analysis of Alternating Gradient Descent-Ascent with Negative Momentum via Parametric SDPs

Gradient descent-ascent is a widely used method in minimax optimization, but it cannot guarantee convergence in general convex-concave problems. Alternating gradient descent-ascent with negative momentum has been proposed to resolve this issue, but the existing convergence guarantees cover only a particular choice of the stepsize and the momentum parameter. In this work, we improve the convergence guarantees so that a broader range of parameters is covered, including arbitrarily small negative momentum parameters and stepsizes. For convex-concave objectives, we show both convergence upper and lower bounds that match up to constant factors, establishing a convergence rate tight in the stepsize, momentum, and iteration count. For strongly-convex-strongly-concave objectives, we prove that the method enjoys a worst-case optimal rate. Our convergence proofs use a computer-assisted search for Lyapunov potentials inspired by the performance estimation problem framework. Covering the aforementioned parameter range leads to semidefinite programs with multiple parameters, and to make solving them tractable, we develop techniques for reducing the number of parameters involved.