acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
minimax optimization, negative momentum, computer-assisted Lyapunov analysis

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_o7hJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper carefully analyze the convergence of alternating gradient descent-ascent with negative momentum (AltGDA-NeMo) through PEP approach, and extends the range for the choice of stepsizes and momentum parameters. This paper establishes rate that has tight dependence on the algorithm parameters for convex-concave problems, and a worst-case optimal linear convergence rate for strongly-convex-strongly-concave problems. Numerical experiments on GAN shows the convergence effect of negative momentum.

Critical strengths

The convergence analysis is technically rigorous. The authors construct exact algebraic certificates from numerical SDP solutions and rigorously verify the resulting convergence guarantees. Moreover, for convex-concave problems, the paper establishes matching upper and lower bounds up to constant factors, showing tight dependence on the stepsize, momentum parameter, and iteration count. For strongly-convex-strongly-concave problems, it achieves a worst-case optimal linear convergence rate with an appropriate parameter choice.

Critical weaknesses

For convex-concave minimax problems, several established methods, such as extragradient and optimistic gradient methods, can overcome the convergence issues of AltGDA. Therefore, it is unclear whether negative momentum is a competitive alternative to these methods, which also raises questions about the practical significance of this study. The experiments compare AltAdam-NeMo only with ordinary alternating Adam, without comparisons against established minimax optimizers such as ExtraAdam or Optimistic Adam. Consequently, it remains unclear whether negative momentum offers advantages over existing methods for solving minimax problems.

Moreover, the experiments are not directly aligned with the theoretical results. First, all experiments involve stochastic neural-network training on generally nonconvex-nonconcave problems, whereas the theoretical analysis concerns deterministic convex-concave problems. Second, the main theoretical contribution is to extend the convergence analysis to a broader parameter region and establish matching upper and lower bounds for convex-concave problems. However, the experiments only consider a fixed negative first-moment parameter β1=−0.5\beta_1=-0.5, without investigating how different parameter choices affect the performance. Therefore, it is difficult to assess what additional guidance the extended parameter analysis provides for algorithm design or parameter selection.

Questions for authors

The paper establishes convergence for 0<ηL≤−β≤1/20<\eta L\leq -\beta\leq 1/2. Are there examples showing divergence for parameters outside this region?

Proposition 6.1 provides a way to extend Lyapunov certificates from convex-concave to strongly-convex-strongly-concave problems. Can this technique be applied to other optimization algorithms? It would be helpful to clarify which parts of the proposed parameter-reduction framework are specific to AltGDA-NeMo.

2 comments

We thank the reviewer for their thorough review and constructive critique.

  • [Q1] Convergence outside the triangle

There indeed exist examples that show divergence outside the region. The work by Zhang & Yu (2020) provides a complete characterization of Alternating GDA with general stepsizes momentum parameters for bilinear problems. Applying their result to our settings, for a bilinear objective f(x,y)=Lxyf(x, y) = Lxy with L>0L > 0, AltGDA-NeMo converges if and only if 0<ηL<2(1+β)0< \eta L < 2(1+\beta). Hence, for instance, if η=0.75/L\eta = 0.75/L and β=−0.75\beta =-0.75, which is outside the triangle, AltGDA-NeMo would diverge.

We also remark that Shugart et al. (2026) do actually provide a numerically computed region for (η,β)(\eta, \beta) in which AltGDA-NeMo appears to converge on general convex-concave problems We added mentioning this, and also added a citation to Zhang & Yu (2020), in Section 2; please see the revised version of our manuscript.

  • [Q2] Applicability of parameter reduction techniques beyond AltGDA-NeMo

We are glad that the reviewer has mentioned this point. The applicability of Proposition 6.1 to other settings in fact depends on whether the search for τ\tau that satisfies equation (14) can be tractably solvable, hopefully as an SDP. In particular, if the Lyapunov potentials, E0\mathcal{E}_0 and E1\mathcal{E}_1, take the form of a quadratic of the state variables (χ,ψ,ϕ)(\boldsymbol{\chi}, \boldsymbol{\psi}, \boldsymbol{\phi}), then the search for τ\tau in (14) can be formulated as an SDP.

Therefore, Proposition 6.1 is a general technique, not specific to AltGDA-NeMo. For that reason, the proof of Proposition 6.1 does not use the specific update rule of AltGDA-NeMo, but not mentioning AltGDA-NeMo at all seems to have unfortunately made the wide applicability of it unclear. We added a paragraph in Section 6.1 to make this point clearer.

In addition, removing LL by normalizing the objective function is a fairly common technique, and is also not specific to AltGDA-NeMo. Removing the η\eta (or equivalently in our setting, β\beta), on the other hand, applies to methods for which applying the method to ff with stepsize ϵη\epsilon\eta produces the same iterates as applying it to ϵf\epsilon f with stepsize η\eta, with the other algorithm parameters fixed. AltGDA-NeMo turns out to have this property, as shown in Proposition 6.2, but we think whether this property holds for other methods should be verified case-by-case.

  • [W1] Comparison with extragradient & optimistic gradient methods

We concur that, in terms of the convergence rates with respect to TT, AltGDA-NeMo attains the same asymptotic rates as extragradient and optimistic gradient methods. Nonetheless, as stated in our Introduction, our work answers the question of whether familiar algorithmic ingredients can stabilize GDA. Our results provide a quantitative characterization of this stabilization via convergence guarantees over a range of parameters and matching upper and lower bounds. Accordingly, we use ordinary alternating Adam as the reference for assessing the effect of a simple modification of setting a negative momentum parameter within existing training recipes, and the experiments successfully demonstrate that such a simple modification alone can result in a noteworthy gain. A broader comparison with specialized minimax optimizers would address a different experimental objective, which we believe is slightly out of the scope of our work.

  • [W2] Experiments not aligned to theoretical results

These are indeed valid concerns. However, our experiments are conducted to explore whether the concept of negative momentum remains useful beyond the assumptions of our theoretical analysis. To this end, as stated in Section 9, we keep the existing training recipes fixed and change only β1\beta_1 to a negative value, and using a fixed negative parameter is intentional for this empirical question. Considering that the main contribution of this work is on the theoretical side, we respectfully assert that the current set of experiments is sufficient for this empirical objective, serving as useful complementary empirical investigations and examining simple practical extensions.

 

We hope that our rebuttal has sufficiently addressed the reviewer's concerns. If that turns out to be the case, we kindly ask the reviewer to reassess our work. We also welcome further questions and are willing to address them during the discussion phase.

I thank the authors for their detailed response, which has largely addressed my concerns. Taking into account the practical relevance, I decide to maintain my score.

Reviewer_zSsFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies alternating gradient descent-ascent with negative momentum (AltGDA-NeMo) for smooth minimax problems. Prior work proved convergence for one parameter pair, (η,β)=(1/(5L),−1/2)(\eta,\beta)=(1/(5L),-1/2). This paper extends the guarantees to the region 0<ηL≤−β≤1/20<\eta L\le-\beta\le 1/2:

Convex-concave problems: the average squared gradient norm decays as O(1/(∣β∣η2T))O(1/(|\beta|\eta^2T)). A matching lower bound comes from a bilinear example. Strongly-convex-strongly-concave problems: the method converges linearly at rate 1−3ημ/101-3\eta\mu/10, which is worst-case optimal for η=Θ(1/L)\eta=\Theta(1/L). The proofs come from a computer-assisted search for a Lyapunov function, set up as a semidefinite program (SDP). Two reductions turn a three-parameter SDP into two one-parameter SDPs, whose solutions are rounded to exact rationals and verified symbolically. Experiments show that setting Adam's β1\beta_1 to −0.5-0.5 in alternating updates helps on toy GANs and neural optimal transport.

Critical strengths
  1. Rigorous, tight results for a very simple method. The bounds hold across a whole parameter region. The convex-concave rate is matched by a lower bound up to a constant factor, in η\eta, β\beta and TT. The certificates are exact rationals, checked over the whole interval η∈(0,1/2]\eta\in(0,1/2] with Sylvester's criterion and Sturm sequences, and the Julia code is provided. So the computer-assisted proofs are verifiable, not just numerical evidence.

  2. The reductions are neat and likely reusable. Rescaling ff removes the stepsize as a parameter (Prop. 6.2). Prop. 6.1 turns a convex-concave certificate into a strongly-convex one with a single extra SDP. These tricks could make similar computer-assisted analyses tractable for other methods. The practical message is also easy to act on: set β1<0\beta_1<0 in two standard Adam optimizers. That cut MNIST→CMNIST FID from 15.6 to 8.8 (64 channels, 5 runs).

Critical weaknesses

The advance over prior work is incremental, and the region is chosen for convenience.

The prior result is close. Shugart et al. (2026) already proved convergence and the optimal strongly-convex rate at one parameter pair, with the same SDP approach. They also found numerically that the method converges slightly beyond that point. This paper's main step is going from a point to a region, plus the lower bound. The region is a convenience choice. The triangle 0<ηL≤∣β∣≤1/20<\eta L\le|\beta|\le 1/2 comes from fixing η=−β\eta=-\beta to make the SDP one-parameter (Sec. 6.2), not from the method itself. So "tight" means tight inside this triangle. We don't learn whether the method converges, or how fast, for ∣β∣>1/2|\beta|>1/2 or larger stepsizes. "Tight" holds for this method only. The O(1/T)O(1/T) rate is slower than the O(1/T2)O(1/T^2) that anchored methods such as EAG achieve. It also covers only the average and best iterates, not the last one. The proofs certify but don't explain, and the practical claims go beyond the theory.

No intuition. The main text never explains why negative momentum stabilizes alternating GDA. The bilinear calculation that motivated the key βη2\beta\eta^2 term appears only in the AI-use statement. A short bilinear analysis would make the result much easier to understand. Small momentum is very slow. Because η≤∣β∣/L\eta\le|\beta|/L, the convex-concave bound grows like 1/∣β∣31/|\beta|^3, and the lower bound shows this slowdown is real. So "arbitrarily small negative momentum" does converge, but very slowly, and in practice ∣β∣|\beta| should be near 1/21/2. The experiments are narrow. They use Adam with second-moment scaling on nonconvex problems, which the theory doesn't cover. They compare only β1=−0.5\beta_1=-0.5 against β1=0\beta_1=0, with no sweep over β1\beta_1. They also skip ExtraAdam and Optimistic Adam, which the paper itself names as alternatives. Wild→Cat is a single run reported at its best checkpoint (FID 9.05 vs. 9.36).

Questions for authors

Clarifications

Does the method converge outside the certified triangle, for example for ∣β∣>1/2|\beta|>1/2 or ηL>∣β∣\eta L>|\beta|? A numerical map of the convergent region would show whether the triangle is close to the true boundary. Can you add a short analysis of the bilinear case to the main text, showing where the ∣β∣η2|\beta|\eta^2 factor comes from? How does AltAdam-NeMo compare with ExtraAdam and Optimistic Adam? How sensitive is it to β1\beta_1 (for example −0.25-0.25, −0.5-0.5, −0.75-0.75)? Suggestions State the 1/∣β∣31/|\beta|^3 slowdown explicitly, and recommend a default β\beta. Report Wild→Cat over several seeds, choosing checkpoints without using the test FID.

2 comments

We are grateful for the reviewer's insightful feedback and encouraging remarks. As there are a lot of points made within each of the paragraphs, let us divide them as below for our convenience and provide our rebuttals.

  • [Q1a] Convergence outside the triangle

Shugart et al. (2026) in fact provide a numerically computed region for (η,β)(\eta, \beta) in which AltGDA-NeMo appears to converge on general convex-concave problems. Hence, it seems like there indeed exist regions outside of the triangle in which AltGDA-NeMo converges.

We edited our Section 2 to mention the numerical result Shugart et al. (2026).

  • [Q1b, W2a] Short analysis of the bilinear case & Additional Intuition

We have added a discussion on the lower bound result (Theorem 4.3), explaining the bilinear analysis it relies on. We have also included our attempt to provide intuition on why negative momentum would stabilize alternating GDA, via constructing energy functions for alternating GDA. Corollary F.2 is also added, with a brief discussion in the main text, and we hope this provides more intuition on why the ∣β∣η2|\beta|\eta^2 factor arises.

  • [Q1c, W2b] Additional Experiments

We recognize that some natural questions that would require additional experiments to answer arise, such as comparing AltAdam-NeMo to ExtraAdam and/or Optimistic Adam and testing the sensitivity of AltAdam-NeMo with respect to β1\beta_1. Investigating in this direction would clearly be an interesting follow-up work.

Nonetheless, as stated in Section 9, our experiments investigate the effect of changing only β1\beta_1 to a negative value in an existing training recipe, while keeping the other settings fixed. This design isolates the effect of the proposed change of incorporating negative momentum. A broader optimizer comparison and a systematic hyperparameter study would indeed address additional questions about comparative performance and parameter selection, but we would like to point out regretfully that that is beyond our scope. We therefore retain the experimental objective stated in the paper.

In addition, our theoretical guarantees concern AltGDA-NeMo. The simplified Adam update in Section 8 explains its connection to AltAdam-NeMo, while the experiments evaluate full Adam as an empirical extension motivated by the analysis.

  • [Q1d] State the slowdown w.r.t. β\beta & recommend default

The dependence on both η\eta and β\beta is stated explicitly in the upper and lower bounds in Section 4. In particular, when the stepsize is chosen as η=∣β∣L\eta=\frac{|\beta|}L, the factor 1∣β∣η2\frac{1}{|\beta|\eta^2} becomes L2∣β∣3\frac{L^2}{|\beta|^3}. Thus, the cubic dependence corresponds to this particular stepsize choice, while our results describe the joint dependence on η\eta and β\beta.

For the analyzed AltGDA-NeMo, a natural choice based on the theoretical results is β=−12\beta=-\frac12, which allows the largest possible range of stepsizes and simultaneously maximizes ∣β∣η2|\beta|\eta^2 for a fixed η\eta. Our Adam experiments are inspired from this observation and use β1=−12\beta_1 = -\frac{1}2.

  • [Q1e, W2c] Complete the reporting of Wild-to-Cat experiments

As we have promised in the initial manuscript, we have filled out the results and the details on the Wild-to-Cat experiments which had been incomplete due to time limit reasons. We now report three independent runs, evaluating FID at six fixed checkpoints from 10k to 60k iterations. Table 1 reports the mean and standard deviation at every checkpoint, together with those of the per-run best FIDs. It turns out that AltAdam-NeMo achieves a lower mean best-checkpoint FID, 8.04 ± 0.41, compared with 8.75 ± 0.76 for ordinary alternating Adam. We refer the reviewer to the revised Section G.2.2 for more details.

  • [W1] The advance over prior work is incremental, and the region is chosen for convenience.

Beyond establishing convergence at additional parameter choices, our bounds identify the joint effect of the stepsize and momentum on the convergence rate of AltGDA-NeMo. The lower bound matching with the upper bound shows that this parameter dependence is intrinsic to the method within the certified region, rather than an artifact of the analysis. Hence, we have revealed quantitative trade-offs and limitations that a guarantee at one fixed parameter pair cannot determine. Moreover, our reductions are not only a contribution to computer-assisted Lyapunov searching, but also enable exact analytical certification throughout this continuous region.

The triangle provides an explicit sufficient convergence region, within which our rate characterization is tight. Faster rates achieved by anchored methods involve an additional mechanism, and we would like to point out that we have already acknowledged this with suggesting a potential application to AltGDA-NeMo as future work in Section F.

 

If there are any further comments or questions, feel free to leave them during the discussion phase.

Thanks for the response and the revisions. The bilinear discussion, the energy-function intuition, and Corollary F.2 cover my request for more intuition. The pointer to Shugart et al. (2026) answers my question about convergence outside the triangle, and I accept that a broader optimizer comparison is out of scope. I'm keeping my score at 3.

Reviewer_t8NoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studied AltGDA-NeMo algorithm for convex-concave and strongly-convex-strongly-concave minimax problems. It provided convergence analysis over a wider range of stepsizes and momentum parameters, which extends previous studies, also they established matching lower bound in the convex-concave case. The main technique of the work relies on PEP. Extensive numerical experiments are provided to validate the outperformance of AltGDA-NeMo.

Critical strengths
  1. Extend existing analysis of AltGDA-NeMo on specific parameters to a broad range of parameters.
  2. Matching lower bound is provided to show the tightness of the upper bound results, which matches the dependence on momentum, stepsize, and horizon.
Critical weaknesses
  1. This work furthered the theoretical understanding of existing studies on negative momentum from the upper and lower bound, but there is no new algorithm or improved convergence results, the Adam part only studied a simplified version of Adam, which may hinder the applicability and significance of the work.
  2. The numerical experiments only tuned β1\beta_1 from 0 to -0.5, but the comparisons keep the learning rates fixed, so it remains unclear whether the interaction between the learning rate and momentum parameter is necessary, and it is unclear whether the advantage persists when learning rates are independently tuned for both settings.
Questions for authors
  1. I noticed another work by Feng et al., (2026): Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach. Could the authors clarify how Section 8 and the AltAdam-NeMo experiments differentiate from this work, what additional insight does your results provide, and what role does alternating update in your work.
2 comments

We appreciate the reviewer for the positive feedback and thoughtful comments.

  • [Q1, W1b] Comparison with Feng et al. (2026) & analysis of a simplified version of Adam

We thank the reviewer for pointing out this related work, which we had previously missed. The biggest difference between our work and Feng et al. (2026) is that we consider alternating updates, while they consider simultaneous updates. Moreover, our main contribution is a tight global convergence analysis of AltGDA-NeMo over a range of parameters, while their convergence analysis is local. To further clarify the role of alternating updates, we have added a discussion of their bilinear divergence result for simultaneous Adam at the end of Section 8, noting its consistency with the behavior of simultaneous GDA, with citing the work by Feng et al. (2026).

With that said, the extension to AltAdam-NeMo is an empirical study building on our theoretical analysis. We also note that the simplification in Section 8 is used to explain this connection, while the experiments use full Adam. As we have stated in Section 9, our empirical investigations aim to demonstrate that changing only the first moment parameter β1\beta_1 to a negative value can substantially improve training.

  • [W1a] No new algorithm or improved convergence results

That our work does not propose a new algorithm is a valid concern. However, we believe that providing convergence analyses for an already proposed method is equally valuable. To the best of our knowledge, we have, for the first time, shown that AltGDA-NeMo converges on general smooth convex-concave problems for a range of parameters η\eta and β\beta. Moreover, we have also shown that the rates we established are tight. Hence, we believe that these qualify as improved convergence results.

  • [W2] Learning rates fixed in the experiments

As we have also noted above, the experiments aim to show what effects can be observed by changing only β1\beta_1 to a negative value, starting from an existing training recipe. For this reason, we are aware that the experiments might seem more like ablation studies, and this is indeed intentional. Indeed, fine-tuning the hyperparameters, including the learning rates, would be required in order to evaluate the full potential of the negative momentum approach, which we agree would be an interesting direction for future work.

 

If there are additional questions or comments, we will be happy to discuss them during the discussion phase.

Thank you for the response, I will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.