Is Negative Momentum Only Slow Because Players Move Together?

When two neural networks train against each other, as the generator and discriminator in a generative adversarial network (GAN) do, plain gradient steps tend to circle around the solution instead of settling on it. A cheap fix is negative momentum: each player subtracts a small fraction of its previous step, which acts like friction on the circling motion. It is known to help. It is also known to be theoretically slow. On smooth, strongly-convex strongly-concave games, negative momentum needs on the order of $\kappa^{1.5}$ iterations, where $\kappa$ is the condition number (the ratio of the largest to smallest curvature). Extragradient and optimistic methods need only order $\kappa$ (On the Suboptimality of Negative Momentum for Minimax Optimization).

That slow rate was derived for simultaneous updates, where both players step from the same old position. A separate line of work shows that alternating updates behave very differently. In alternating updates the second player reacts to the first player's new position within the same iteration. This one change cuts the cost of player coupling from $\Theta(\kappa_{xy}^2)$ to $O(\kappa_{xy}\sqrt{\kappa})$ (Fundamental Benefit of Alternating Updates in Minimax Optimization). Alternating updates are also the only setting where momentum converges at all on bilinear games (Negative Momentum for Improved Game Dynamics, Convergence of Gradient Methods on Bilinear Zero-Sum Games). Yet nobody has computed the rate of the combination that GAN practitioners actually run: alternating updates with negative momentum. This note proposes to do that. On quadratic games the analysis is exact and global. It would then be carried to a nonconvex class with global guarantees. Finally, the result would be tested on real GAN training, where Adam's momentum buffer already supplies the needed mechanism at no extra cost.

Core Claim

The algorithm, which we call Alt-NM, is written below. Here $\eta_x,\eta_y$ are step sizes and $\beta_x,\beta_y<0$ are per-player momentum coefficients for the minimizing player $x$ and maximizing player $y$ of $\min_x\max_y f(x,y)$:

$$x_{t+1}=x_t-\eta_x\nabla_x f(x_t,y_t)+\beta_x(x_t-x_{t-1}),\qquad y_{t+1}=y_t+\eta_y\nabla_y f(x_{t+1},y_t)+\beta_y(y_t-y_{t-1}).$$

Our hypothesis is that the $\kappa^{1.5}$ ceiling comes from simultaneity, not from momentum. Specifically, on strongly-convex strongly-concave quadratics, Alt-NM with tuned $(\eta,\beta)$ should reach accuracy $\epsilon$ in $O(\kappa\log(1/\epsilon))$ iterations. The target bound is order $\kappa$ because $\kappa$ is the extragradient rate the momentum recursion would have to match. The method uses one gradient per player per step and no extrapolation point.

The mechanism is as follows. The suboptimality proof relates simultaneous heavy-ball to a Chebyshev-type polynomial built on the eigenvalues of a normal operator. Alternation makes the iteration matrix non-normal and changes which polynomials the two-term momentum recursion can realize. That is the same structural change that improves plain alternating gradient descent-ascent (Alt-GDA) in Lee et al.

The hypothesis can fail. If the optimal exponent under alternation is still 1.5, we will have extended the ceiling to the alternating case. That is also a clean, publishable answer, and it would tell practitioners to stop tuning momentum and switch to extrapolation.

Research Program

The first stage is exact spectral analysis. On a quadratic game, Alt-NM is a linear system with a four-block iteration matrix, so local and global convergence coincide. We parameterize problems by $\kappa_x,\kappa_y$ (each player's own conditioning) and $\kappa_{xy}$ (coupling strength), as Lee et al. do. We then characterize the minimal spectral radius over $(\eta_x,\eta_y,\beta_x,\beta_y)$.

We start with the pure bilinear case, where Gidel et al. and Zhang and Yu proved convergence but the file reports no explicit rate for alternating momentum. We then move to the full strongly-convex strongly-concave quadratic. The deliverables are an upper bound with explicit hyperparameters and a matching lower bound over this two-term recursion class. The explicit hyperparameters would also give the missing closed-form rule for choosing $\beta$ that Gidel et al. left to grid search.

The second stage is global convergence beyond quadratics. Yang et al. prove global linear convergence of alternating gradient descent-ascent under the two-sided Polyak-Łojasiewicz (PL) condition (Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems). The two-sided PL condition says that gradient size bounds suboptimality for each player, and it makes every stationary point a global saddle. Yang et al.'s rate is $(1-\kappa^{-3})^t$, which they suspect is loose, and their analysis has zero momentum.

We will build a Lyapunov function for Alt-NM on this class. The function adds a term for the momentum "kinetic energy" to the potential used by Yang et al. and by the Lyapunov-based design in From Lyapunov Analysis to Algorithm Design in two-sided PL Minimax Optimization. The question is whether negative momentum keeps a global linear rate and improves the $\kappa$ exponent. This addresses the local-only nature of every existing negative-momentum proof.

The third stage transfers the result to adaptive optimizers. Feng et al. show that simultaneous Adam descent-ascent always diverges on bilinear games, even with negative first-moment $\beta$ (Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach). Their analysis is simultaneous. Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games shows that alternation and negative $\beta$ each widen the stable step-size range, but it gives no rates.

We will test whether alternating Adam with negative $\beta$ converges on bilinear games, first numerically and then, if it does, through the same ODE lens. This decides whether the quadratic theory has any bearing on how GANs are actually trained.

Baselines

The do-nothing references are simultaneous and alternating gradient descent-ascent with no momentum. Their rates are known: $\Theta(\kappa_{xy}^2)$ and $O(\kappa_{xy}\sqrt{\kappa})$ on quadratics (Lee et al.). Alt-GDA alone only cycles on unconstrained bilinear games. Any gain Alt-NM shows must be measured against Alt-GDA, not against the divergent simultaneous method.

The direct predecessor is simultaneous negative momentum, analyzed in On the Suboptimality of Negative Momentum for Minimax Optimization. Its $O(\kappa^{1.5})$ is the number to beat.

The strongest existing competitor is Alex-GDA from Fundamental Benefit of Alternating Updates in Minimax Optimization. It alternates and extrapolates, matches extragradient's rate with one gradient per player per step, and in GAN form reports the best number in the file: Alex-Adam FID 6.3 on LSUN Bedroom 64×64 with WGAN-GP, against Alt-Adam 9.0 and Sim-Adam 131.2. Extragradient and optimistic gradient descent-ascent, which achieve $O(\kappa)$ locally, are included as the classical optimal methods.

In GAN experiments we also include the $R_1$ zero-centered penalty of Which Training Methods for GANs do actually Converge?, the standard regularization-based stabilizer. We further include simultaneous Adam with $\beta=-0.3$ as configured by Feng et al. For that configuration, the file reports an Inception Score of about 7.08, against about 4.16 at $\beta=0.5$, on CIFAR-10 with a ResNet GAN.

All methods get the same architecture, data, number of gradient evaluations (not iterations, since extragradient uses two per step), and the same hyperparameter search budget over step sizes and $\beta$. We use five seeds each. On synthetic problems, every method's hyperparameters are set by the same exact spectral-radius minimization, so tuning luck plays no role.

The key ablation toggles alternation on and off with momentum fixed, and toggles momentum on and off with alternation fixed. A further arm applies momentum to the discriminator only, as Gidel et al. did, to locate where the benefit lives.

Beating the field on synthetic problems means a fitted iteration-complexity exponent near 1 in $\kappa$, clearly below 1.5, at an equal gradient budget. On GANs, the practical claim requires matching Alex-Adam within seed noise on LSUN Bedroom while using no extrapolation step. Clearly beating Alt-Adam's 9.0 is the minimum for the claim to count.

Why not just…?

Why not just use extragradient or optimistic gradient descent-ascent, which are already optimal? On strongly-convex strongly-concave problems they are optimal, and we do not expect Alt-NM to beat their exponent, only to match it. The point is different. If alternation removes the ceiling, the suboptimality result is an artifact of the update order. That would matter because momentum is already present in every Adam-based GAN trainer. Standard extragradient also costs two gradients per step, and in nonmonotone problems its EG+ variant gets trapped in limit cycles (Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems). The gradient-matched comparison settles which method is actually faster in practice.

Why not just use Alex-GDA, which already gets the extragradient rate with one gradient? This is the real threat. If Alt-NM only ties Alex-GDA in theory and loses to Alex-Adam's 6.3 FID in practice, its practical case collapses. What remains is the explanatory result: why negative $\beta$ helps GANs and where its ceiling actually comes from. We will report it that way. Two things could still favor Alt-NM. It needs no change to existing optimizers beyond the sign of $\beta$. And momentum carries information over many steps, which may damp stochastic-gradient noise differently from one-step extrapolation. The mini-batch GAN runs test the second point directly.

Why not just add an $R_1$ gradient penalty? Mescheder et al. show that $R_1$ certifies local convergence even when the data lie on a low-dimensional manifold. That is a guarantee about where the objective's fixed point sits, not about how fast the optimizer reaches it, so the two tools are complementary rather than competing. We run Alt-NM with and without $R_1$ on Dirac-GAN (the one-dimensional GAN whose unregularized dynamics orbit forever) and on CIFAR-10. The test is whether momentum damping adds speed on top of the penalty, or makes the penalty's double-backpropagation cost unnecessary at equal quality.

Why not just tune simultaneous Adam's $\beta$ negative, as Feng et al. recommend? Their own proof says simultaneous Adam descent-ascent diverges on bilinear games regardless of tuning. Lee et al.'s 131.2 versus 9.0 FID gap suggests that update order matters more than momentum sign. The two-by-two ablation of alternation against momentum sign, run within Adam, answers this directly.

Proposed Experiments

The synthetic core uses bilinear games and the 6-dimensional and 200-dimensional strongly-convex strongly-concave quadratics from Lee et al. We sweep $\kappa_x,\kappa_y,\kappa_{xy}$ over several orders of magnitude, compute the optimal spectral radius of each method exactly, and fit log-iterations against log-$\kappa$. The decisive check is the fitted exponent for Alt-NM relative to 1.5 and 1.

For the two-sided PL class we use robust least squares on synthetic Gaussian data and the rescaled Aquatic Toxicity dataset, as in Yang et al. We compare empirical linear rates of Alt-NM and Alt-GDA against the proved bounds, including the stochastic-gradient regime.

As a scope probe, not a claim, we run Alt-NM on PolarGame and GlobalForsaken. The question is whether first-order damping escapes the limit cycles that trap EG+ and that CurvatureEG+ escapes only by using Jacobian-vector products. A failure there marks the boundary of the method.

The Adam-transfer check first runs alternating Adam with negative $\beta$ on unregularized bilinear games. Convergence would contradict a naive extension of Feng et al.'s divergence result to alternating updates; divergence would confirm that Adam's per-coordinate scaling breaks the benefit of alternation. We then train WGAN-GP on CIFAR-10 and LSUN Bedroom 64×64. We report FID and Inception Score, seed-to-seed variance, and wall-clock time per gradient evaluation, against Alex-Adam, Alt-Adam, Sim-Adam, simultaneous negative-$\beta$ Adam, and $R_1$.

The result that would most change practice is the combination of three outcomes: an exponent near 1 on quadratics, convergence of alternating negative-$\beta$ Adam on bilinear games, and LSUN FID within noise of 6.3.