acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max games

Abstract

How far can stochastic gradient descent ascent (SGDA) go by tuning its timescale ratio and step sizes in nonconvex min-max games? We answer this question for nonconvex–PL (NC-PL) games by establishing the first tight complexity of two-timescale SGDA with a fixed timescale ratio and non-increasing step sizes. For -smooth games with an inner -PL inequality and fixed initial-gap budgets, we prove a complexity lower bound , where is the condition number, is the gradient variance, and measures the outer gradient norm. This matches existing SGDA upper bounds and establishes a complexity separation from Smoothed-AGDA (Yang et al., 22'). In addition, we show that SGDA can fail to find a stationary point when its timescale ratio is as small as . Our negative results highlight the fundamental limitation of SGDA in NC-PL games, and justify the development of alternative methods.

Primary area:
optimization
Keywords:
min-max games, stochastic gradient descent ascent

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_TnrROpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper establishes tight complexity bounds for simultaneous and alternating SGDA in smooth NC–PL minimax problems, considering fixed timescale ratios and predetermined nonincreasing step sizes. The results match existing SGDA upper bounds and establish the necessity of an order-κ2\kappa^2 timescale ratio for uniform convergence. The lower bounds are proved through explicit hard instances, combining a deterministic corridor with persistent stochastic perturbations in the high-ratio regime and constructing stable periodic dynamics in the low-ratio regime.

Critical strengths
  1. Establishing the suboptimality of SGDA. Yang et al. (2022) established better complexity upper bounds for stochastic Smoothed-AGDA than for SGDA, but this did not establish that SGDA's worse complexity was unavoidable. By proving matching lower bounds, this paper confirms that SGDA is indeed suboptimal within the considered algorithm class, rather than merely suffering from a potentially loose analysis.

  2. Necessity of the timescale ratio. The paper proves that a timescale ratio of order κ2\kappa^2 is necessary for uniform global convergence of SGDA, even when the outer objective is strongly convex. This result answers an open question raised by Cho and Yun (2023) and provides a theoretical justification for the commonly used timescale separation.

Critical weaknesses

Limited significance of the research question. Although the paper establishes novel and technically nontrivial lower bounds, I have concerns about the broader significance of the problem being studied. Yang et al. (2022) already developed Smoothed-AGDA with substantially better complexity guarantees than those previously known for GDA in both deterministic and stochastic NC–PL settings. Moreover, the optimal deterministic first-order complexity for NC–PL problems has recently been characterized. While establishing the tight complexity of SGDA is mathematically meaningful, I am not fully convinced that characterizing the limitations of an algorithm with already less favorable guarantees constitutes a sufficiently important advance, particularly given the availability of more efficient alternatives.

Questions for authors

Timescale-ratio lower bound under two-sided PL. Mourrat (2026) showed that continuous-time GDA can exhibit periodic dynamics under two-sided PL conditions, with the basic construction also admitting an extension to the unconstrained setting. Theorem 6.3 establishes that an order-κ2\kappa^2 timescale ratio is necessary for uniform convergence under NC–PL, even when the outer objective is strongly convex. However, the constructed hard instance is affine in the primal variable and does not satisfy the primal-side PL condition. Does a similar necessity result hold under the stronger two-sided PL assumption, where f(⋅,y)f(\cdot,y) also satisfies a PL inequality? Understanding this distinction would help assess the broader significance of the timescale-ratio lower bound.

1 comment

We thank reviewer TnrR for constructive and thoughtful feedback.

Below, we address each of the concerns and the questions raised in the review.

Significance of the result

We would like to clarify that our contribution lies in guiding researchers and practitioners to focus on more advanced methods than SGDA in NC-PL games, by establishing the provable suboptimality of SGDA – arguably the most straightforward algorithm to solve min-max games. As pointed out by the reviewer, earlier upper bounds showed that advanced methods such as Smoothed-AGDA can attain fast convergence rates. However, it remained open whether well-tuned SGDA could match their performance. That possibility was worth investigating as SGDA uses about 33% less memory than Smoothed-AGDA, and does not require an additional hyperparameter. Our matching lower bound closes that possibility and narrows the algorithm space. In short, we provide a substantive guide for researchers and practitioners to focus on alternative methods.

Does two-sided PL games also require timescale ratio ρ=Ω(κ2)\rho=Ω(\kappa^2)?

Yes, Theorem 6.3 actually can be extended to two-sided PL games as well. Consider adding γℓ2∥∥x−x0∥∥2\frac{\gamma\ell}{2}\|\|x-x_0\|\|^2 to the hard instance in Theorem 6.3, with a sufficiently small γ>0\gamma > 0 . This actually gives a strong convexity for xx. In the original construction, every initial large step keeps xt=x0x_t = x_0 while moving yty_t along a predetermined path. The added gradient vanishes at x0x_0, so the initial large steps still reach exactly the same point on the original orbit.

For the subsequent small steps, the added drift induced by the additional strongly convex term has an order of O(γh/ρ)O(\gamma h/\sqrt{\rho}) per step size h. Hence, for a sufficiently small γ\gamma, the iterates can stay in the cycle.

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

The paper establishes the tight worst-case complexity for simultaneous and alternating SGDA with a fixed timescale ratio and predetermined nonincreasing step sizes. It also proves that ratios o(κ2)o(\kappa^2) cannot guarantee uniform convergence, even with exact gradients and a strongly convex quadratic outer objective. These results characterize SGDA’s limitations and establish its suboptimality relative to Smoothed-AGDA under the stated comparison conditions.

Critical strengths
  1. Matching lower and upper bounds characterize SGDA’s worst-case complexity within the specified algorithm family, including its dependence on condition number, accuracy, and noise.
  2. The analysis covers both simultaneous and alternating updates and permits parameter-dependent choices of fixed timescale ratios and predetermined nonincreasing step sizes.
  3. The stochastic perturbation and attracting-cycle examples explain distinct failure mechanisms. Failure even with a strongly convex quadratic outer objective is particularly informative.
Critical weaknesses
  1. The manuscript says Yang et al. (2022) “introduced Smoothed-AGDA.” However, Yang et al. explicitly credit Zhang et al. A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems (2020) with introducing it. The original paper is absent from the bibliography.
  2. The main text presents Smoothed-AGDA’s improved complexity without explicitly stating the additional initialization condition and the accuracy regime (\varepsilon^2\lesssim \ell\Delta/[\kappa^3\log(2\kappa)]). Outside this regime, the established bound contains additional conversion costs. Although Appendices E–F explain these restrictions and verify the initialization condition for the hard instances, the headline comparison appears broader than the guarantee established. These qualifications should accompany the main claim and Table 1.
Questions for authors

I have no further questions, please try to address the weaknesses menionted above.

1 comment

We appreciate Reviewer oEGA for the positive review and helpful suggestions.

We've updated the manuscript and addressed the reviewer's comments as follows:

  • We added Zhang et al., 2020. "A Single-Loop SMoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems" as the original paper for Smoothed AGDA, and revised the sentence “Yang et al., (2022) introduced Smoothed-AGDA” to “Zhang et al., (2020) introduced Smoothed-AGDA …”.
  • We added a short footnote in page 4 to clarify that Smoothed-AGDA’s complexity requires ε2≲ℓΔ/κ3log⁡(2κ)\varepsilon^2\lesssim \ell\Delta/\kappa^3\log(2\kappa), or otherwise the bound contains an additional output conversion cost. We also briefly mention this fact in the caption of Table 1 to make this point clear to the readers.
Reviewer_ZJqEOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the classic stochastic-GDA (SGDA) dynamics in the nonconvex-PL minimax problems. There was an upper bound for SGDA with alternating updates. The paper establishes the same upper bound for SGDA with simultaneous updates. The main contribution is establishing a lower bound that matches the upper bound for both simultaneous and alternating SGDA when they use a fixed timescale ratio and nonincreasing stepsize schedule. To achieve this, the paper shows that when the timescale ratio is Ω(κ2)\Omega(\kappa^2), there is a lower bound on the gradient norm of the outer objective and the lower bound gets worse when the ratio increases. On the other hand, when the timescale ratio is o(κ2)o(\kappa^2), there is a constant lower bound. These two cases also imply that Θ(κ2)\Theta(\kappa^2) is the optimal timescale ratio.

Critical strengths
  • SGDA in NC-PL minimax problem is a classic setup in the literature and the paper closes a gap in understanding the SGDA algorithm in this problem.
  • It is interesting that by considering the two hard instances the paper can conclude that the Θ(κ2)\Theta(\kappa^2) timescale ratio is optimal, and deviating from the ratio will cause a larger lower bound.
  • I appreciate the author's effort to explain the construction of the hard instances, and provide a table to compare the results with the existing ones. I found it relatively easy to understand the literature and how the lower bounds are established etc.
Critical weaknesses
  • The ideas to prove the results are not very new. The upper bound for SGDA_{Sim} and the lower bound in the o(κ2)o(\kappa^2) case seem to be some extensions following the same proof strategies as the previous papers.
  • In my opinion, the structure of the paper could be further improved. I think the paper could benefit from a more comprehensive introduction section, and more concise Section 5. Also, the last two sections can be merged. I encourage the authors to further improve the writing and presentation of the paper. I would be happy to increase my scores if they do so.
  • Some wordings are used without explicit contexts. For example, “unstable step sizes” and “stable step sizes” in Section 5.
Questions for authors
  • Does any of the lower bounds shown in the paper also hold for the NC-SC class?
2 comments
AuthorsOpenReview ↗

Improved the overall writing and presentation of the paper

We appreciate Reviewer ZJqE for the positive review. Below, we address each of the concerns and the questions raised in the comment.

Presentation of the paper

We acknowledge that the presentation of the initial draft had room for improvements.

We updated the manuscript to incorporate the following improvements suggested by Reviewer ZJqE:

  • We expanded the introduction to make the motivation and background clearer to a broader audience of ICLR. Specifically, we added examples of guarantees that can be attained at an equilibrium of different games (e.g., GANs, DRO, NLHF), (and expanded the landscape of algorithms for min-max games, including extragradient (EG) and optimistic gradient descent ascent (OGDA) methods.
  • We removed the long heuristic calculations in Section 5.2.2; now Section 5 is more concise than before.
  • We merged the last two sections into a single conclusion Section 7.
  • We also replaced unclear terminologies (such as “unstable step sizes” and “stable step sizes” in Section 5) with more explicit and clear wordings, such as "large step sizes" and "small step sizes".

Q. Does any of the lower bounds hold for NC-SC games?

Yes, the deterministic lower bound ∑t1T∥∥∇Φ(xt)∥∥2≥min(ℓΔ,ρℓΔ/T)\sum_t \frac1T\|\|\nabla\Phi(x_t)\|\|^2 ≥ min(\ell\Delta,\rho\ell\Delta/T) in Theorem 5.1 extends to NC-SC. The linear quadratic game funstablef_{unstable} in Section 5.1 is already strongly concave in yy, and gcorridorg_{corridor} in Section 5.2 can be paired with a strongly-concave term −μ∥∥y∥∥2/2-\mu\|\|y\|\|^2/2 and start at y0=0y_0=0. Then the existing corridor proof applies verbatim.

The stochastic construction in Section 5.2, on the other hand, uses an auxiliary coordinates to retain a noise perturbation. Strong concavity rules out this mechanism, and therefore, the stochastic lower bound for NC-SC games remains open in our analysis.

I thank the authors for answering my questions. I hope they can add the NC-SC extension to the paper. i also appreciate their efforts in improving the presentation. I will maintain my positive score and positive attitude toward this paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.