- 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- 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
-
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.
-
Necessity of the timescale ratio. The paper proves that a timescale ratio of order 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- 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 also satisfies a PL inequality? Understanding this distinction would help assess the broader significance of the timescale-ratio lower bound.
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)?
Yes, Theorem 6.3 actually can be extended to two-sided PL games as well. Consider adding 2γℓ∥∥x−x0∥∥2 to the hard instance in Theorem 6.3, with a sufficiently small γ>0 . This actually gives a strong convexity for x. In the original construction, every initial large step keeps xt=x0 while moving yt along a predetermined path. The added gradient vanishes at x0, 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/ρ) per step size h. Hence, for a sufficiently small γ, the iterates can stay in the cycle.