- 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 , 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 . 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
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.
We thank the reviewer for their thorough review and constructive critique.
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)=Lxy with L>0, AltGDA-NeMo converges if and only if 0<ηL<2(1+β). Hence, for instance, if η=0.75/L and β=−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 (η,β) 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.
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 τ that satisfies equation (14) can be tractably solvable, hopefully as an SDP. In particular, if the Lyapunov potentials, E0 and E1, take the form of a quadratic of the state variables (χ,ψ,ϕ), then the search for τ 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 L by normalizing the objective function is a fairly common technique, and is also not specific to AltGDA-NeMo. Removing the η (or equivalently in our setting, β), on the other hand, applies to methods for which applying the method to f with stepsize ϵη produces the same iterates as applying it to ϵf with stepsize η, 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.
We concur that, in terms of the convergence rates with respect to T, 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.
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 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.