On the Suboptimality of Negative Momentum for Minimax Optimization

Guodong Zhang, Yuanhao Wang

Abstract

Smooth game optimization has recently attracted great interest in machine learning as it generalizes the single-objective optimization paradigm. However, game dynamics is more complex due to the interaction between different players and is therefore fundamentally different from minimization, posing new challenges for algorithm design. Notably, it has been shown that negative momentum is preferred due to its ability to reduce oscillation in game dynamics. Nevertheless, existing analysis of negative momentum was restricted to simple bilinear games. In this paper, we extend the analysis to smooth and strongly-convex strongly-concave minimax games by taking the variational inequality formulation. By connecting Polyak’s momentum with Chebyshev polynomials, we show that negative momentum accelerates convergence of game dynamics locally, though with a suboptimal rate. To the best of our knowledge, this is the first work that provides an explicit convergence rate for negative momentum in this setting.

TL;DR

While negative momentum is a popular trick to stabilize the oscillatory dynamics of minimax problems (like GANs), this paper proves it is theoretically suboptimal. The authors show that even with optimal tuning, negative momentum only achieves an iteration complexity of $O(\kappa^{1.5})$, falling short of the $O(\kappa)$ optimal rate achieved by methods like Extra-gradient (EG) or Optimistic Gradient Descent Ascent (OGDA).

The Challenge of Minimax Optimization

In standard machine learning, we usually try to minimize a single loss function. However, modern AI often involves "games" where two players compete—think Generative Adversarial Networks (GANs) or adversarial training. These are minimax problems: one player tries to minimize a value while the other tries to maximize it.

The challenge is that the math of "minimization" doesn't translate perfectly to "games." Standard Gradient Descent Ascent (GDA) often fails because the interaction between players causes the system to oscillate wildly or even diverge. Researchers previously found that using negative momentum (slowing down the updates based on previous steps) could dampen these oscillations in simple cases. But until this paper, no one knew exactly how fast it converged for more complex, "strongly-convex strongly-concave" problems, or if it was truly the best tool for the job.

Methodology: From Dynamics to Polynomials

The authors treat minimax optimization through the lens of Variational Inequalities (VI) and Dynamical Systems. Their approach involves three key steps:

  1. Linearization: They analyze local convergence by looking at the Jacobian (the matrix of first-order derivatives) of the game's vector field. This simplifies the problem into solving a linear system.
  2. Polynomial Approximation: They establish a clever link between first-order optimization methods and polynomials. Specifically, they show that Polyak’s momentum method is equivalent to a Chebyshev iteration. The convergence rate of the algorithm then becomes a question of how well a specific polynomial can "squish" the eigenvalues of the system.
  3. The Sandwich Technique: Since the eigenvalues of minimax games are complex (unlike the real eigenvalues in standard minimization), they are harder to bound. The authors "sandwich" the complex spectrum of the game between two simpler geometric shapes (polygons) to derive an explicit convergence rate.

Key Results: The Complexity Hierarchy

The paper provides the first explicit local convergence rate for negative momentum in smooth, strongly-monotone games: $1 - \Theta(\kappa^{-1.5})$. This establishes a clear ranking for these algorithms:

  • GDA: $O(\kappa^2)$ (Slowest/Unstable)
  • Negative Momentum (NM): $O(\kappa^{1.5})$ (Better, but suboptimal)
  • OGDA / Extra-gradient: $O(\kappa)$ (Optimal)
Comparison of convergence complexities for different minimax optimization methods.

Numerical experiments on synthetic quadratic minimax problems perfectly match the theory. As shown in the convergence plots, while negative momentum accelerates GDA significantly, it is consistently outperformed by Optimistic Gradient Descent Ascent (OGDA), which tracks the optimal $O(\kappa)$ rate.

Numerical validation of convergence rates for GDA, OGDA, and Negative Momentum (NM).

Discussion and Limitations

  • Negative is the New Positive: In standard minimization, we use positive momentum to speed up. In minimax games, the interaction between players creates "imaginary" components in the math that cause rotation and oscillation. Negative momentum acts as a stabilizer, pulling the trajectory back toward the equilibrium.
  • Suboptimality Confirmed: The biggest insight is the proof that negative momentum is fundamentally limited. While it improves upon basic GDA, it cannot reach the $O(\kappa)$ efficiency of "optimistic" methods. It effectively hits a theoretical ceiling at $O(\kappa^{1.5})$.
  • Local vs. Global: The analysis is primarily local, describing behavior near the solution. While extensions to global convergence are possible, this work focuses on the local neighborhood where the Jacobian dominates.
  • Future Directions: The authors suggest that the "optimal" algorithm for these games might be found by looking for even better polynomials (like Faber polynomials) using conformal mapping, which could potentially bridge the gap between current methods and theoretical lower bounds.

Summary updated

Abstract

Smooth game optimization has recently attracted great interest in machine learning as it generalizes the single-objective optimization paradigm. However, game dynamics is more complex due to the interaction between different players and is therefore fundamentally different from minimization, posing new challenges for algorithm design. Notably, it has been shown that negative momentum is preferred due to its ability to reduce oscillation in game dynamics. Nevertheless, existing analysis of negative momentum was restricted to simple bilinear games. In this paper, we extend the analysis to smooth and strongly-convex strongly-concave minimax games by taking the variational inequality formulation. By connecting Polyak’s momentum with Chebyshev polynomials, we show that negative momentum accelerates convergence of game dynamics locally, though with a suboptimal rate. To the best of our knowledge, this is the \emph{first work} that provides an explicit convergence rate for negative momentum in this setting.
BibTeX
@inproceedings{zhang2021suboptimality,
  author = {Guodong Zhang and Yuanhao Wang},
  title = {{On the Suboptimality of Negative Momentum for Minimax Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=rv-M98mvvi},
}
Figure