- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies the deterministic first-order oracle complexity of smooth min-max optimization under two-sided Polyak–Łojasiewicz (PŁ) conditions. The authors establish an lower bound using a hard instance that couples geometrically weighted primal and dual chains. They also show that the existing single-loop Smoothed Gradient-Descent-Ascent (S-GDA) algorithm achieves an upper bound for sufficiently small , by combining the Lyapunov descent analysis of Yang et al. (2022) with a new error-bound lemma.
Based on these results, the paper claims optimal deterministic first-order oracle complexity for the two-sided PŁ class. The authors additionally provide a Lean formalization of the lower-bound construction.
Critical strengths
-
The lower-bound construction is interesting and technically nontrivial. To my knowledge, this is the first deterministic first-order oracle lower bound specifically established for two-sided PŁ minimax optimization. The coupling between the primal and dual chains is particularly clever, as it controls the rate at which algorithms can discover primal coordinates while preserving both PŁ conditions. I checked several of the main inequalities and did not identify an issue with the central construction.
-
The upper-bound analysis establishes a useful linear convergence guarantee for an existing single-loop algorithm. The new error-bound lemma allows the authors to obtain a contraction with product condition-number dependence. For the constructed hard instances, the resulting upper bound matches the lower-bound rate, improving the logarithmic dependence on accuracy relative to the bound of Chen et al. (2022).
Critical weaknesses
-
I have a major concern about the claimed optimal complexity and the definition of the problem class.
Definition 2.1 bounds only the initial primal-function gap, , without imposing any restriction on the initial dual gap .
In the proposed hard instance, , where . The initialization quantity used in Appendix C.3 exhibits the same exponential dependence. Therefore, the claimed complexity bound may rely on instances with arbitrarily large initial dual suboptimality.
More importantly, the worst-case oracle complexity in Definition 2.5 appears to be unbounded over the stated function class. In particular, consider extending the dual chain by an arbitrary number of additional blocks while coupling the primal chain only to the final dual blocks. With the geometric weights adjusted accordingly, the PŁ and joint-smoothness estimates appear to remain independent of , while the primal value function and its initial gap remain unchanged. However, a zero-respecting algorithm must traverse the additional dual blocks before observing a nonzero primal gradient, requiring oracle calls. The resisting-oracle argument in Appendix B would then extend this obstruction to arbitrary deterministic first-order methods.
Since is arbitrary, this suggests that the worst-case complexity of the class, as currently defined, is infinite.
This concern is consistent with the complete upper bound in Appendix D, which includes an initialization cost depending on . Theorem 3.2 absorbs this cost only for sufficiently small , with an accuracy threshold that may depend on the particular instance. Such an instance-dependent guarantee does not establish a uniform minimax upper bound over the entire class.
If this argument is correct, the paper provides nontrivial lower-bound instances and matching guarantees for a particular family, but does not establish the claimed optimal worst-case complexity of .
I consider this a significant issue that should be resolved before claiming an optimal complexity characterization.
-
The upper-bound contribution appears relatively incremental.
The analysis primarily combines the existing Lyapunov descent argument for S-GDA with an additional error-bound lemma derived from the primal PŁ condition. Although the resulting linear convergence guarantee is useful, the proof introduces neither a new algorithm nor a substantially different analytical framework.
The authors should better distinguish the contribution from Yang et al. (2022) and more recent work on two-sided PŁ minimax optimization, including Rankawat et al. (2026). Comparisons with existing upper bounds should also account for differences in initialization assumptions and whether the guarantees are uniform over the stated problem class.
-
Some technical details of the lower-bound proof would benefit from additional justification.
In particular, the joint-smoothness argument in Lemma A.2 relies on second-derivative bounds and continuity arguments at vanishing gate values that are only briefly justified. These steps are important because the smoothness constants must remain independent of the chain lengths.
Additionally, several components of the construction and resisting-oracle argument build on the recent work of Pan & Li (2026). The paper should more clearly distinguish the new technical ingredients from those inherited from that work.
The accompanying Lean formalization may address some of these concerns, but its precise scope is not sufficiently clear from the manuscript.
Questions for authors
-
Can the authors rule out the arbitrarily long dual-prefix construction described in Weakness 1? In particular, what prevents the worst-case complexity in Definition 2.5 from being infinite without a uniform restriction on the initial dual gap or initialization cost?
-
Can the authors establish the same lower bound under an additional assumption such as or ? Otherwise, how should the claimed optimal complexity characterization be interpreted?
-
What is the precise novelty of the upper-bound analysis relative to Yang et al. (2022), Chen et al. (2022), and Rankawat et al. (2026)? In particular, are the initialization requirements consistent across the stated comparisons?
-
Which results are fully verified in Lean? Does the formalization include the joint-smoothness argument in Lemma A.2 and the finite-horizon resisting-oracle reduction, or are any of these components assumed?
5 comments
Response (Continued)
Q3 (Continued).
A previously unrecognized property of S-GDA. Interestingly, our result also reveals a stronger convergence guarantee for an existing algorithm. S-GDA was originally developed by Zhang et al. (2020) for nonconvex–concave minimax optimization and subsequently analyzed by Yang et al. (2022) in the NC–PŁ setting. Despite the extensive study of two-sided PŁ minimax optimization, the possibility that the same S-GDA method already achieves the sharper dependence under the two-sided PŁ condition had not been established.
Our analysis shows that the smoothing mechanism already built into S-GDA can be exploited to obtain this improved rate without modifying the algorithm. Specifically, Lemma 5.1 recalls the existing Lyapunov descent inequality from Yang et al. (2022), whereas our new Lemma 5.2 uses the additional primal PŁ condition to control the proximal primal optimality gap by the quantities appearing in that descent inequality. Combining these two lemmas yields
Thus, our result uncovers a sharper convergence guarantee for the original S-GDA method in the two-sided PŁ setting.
Initialization dependence and complete complexity. For a consistent comparison, we consider the complete first-order oracle complexity of each method when started directly from the prescribed initial point, without an additional warm-start phase. Let
and define . For Chen et al. (2022), let
denote the inner accuracy, proximal regularization parameter, and number of outer iterations, respectively. For Rankawat et al. (2026), let and , where denotes the cross-smoothness constant.
| Method | Complete complexity with initialization |
|---|---|
| Yang et al. (2020), AGDA | |
| Chen et al. (2022), AccSPIDER-GDA () | |
| Rankawat et al. (2026), TALDA | |
| Ours, S-GDA |
The initialization quantities are not identical across these methods, but all involve initial dual suboptimality. Yang et al. (2020) retain in their Lyapunov function; Chen et al. (2022) account for it through the initial inner solve; and Rankawat et al. (2026) use a gradient-based initial Lyapunov value controlled by . For our method, we have
The direct-start complexity in the table follows from and our linear Lyapunov contraction. Thus, all methods are compared without imposing an additional bound on the initial dual gap. Beyond this direct-start comparison, our analysis establishes a sharper complete complexity by using an explicit fixed-anchor initialization procedure, whose oracle cost is fully accounted for: . Under the high-accuracy condition specified above, the initialization and output costs are absorbed into the main term, yielding
Response (Continued)
Q4: Scope of the Lean formalization.
Yes. Lean proves both the joint smoothness of the explicit hard instance and the finite-horizon resisting-oracle reduction.
Joint smoothness. For Lemma A.2, Lean proves that the first derivatives extend continuously to vanishing gates and proves dimension-independent second-derivative bounds almost everywhere in the interior. The Lean proof uses , and the revised proof in Appendix A.4 gives the sharper constants . For the unscaled payoff, Lean proves that its joint gradient is globally -Lipschitz, including at zero gate values. The same constant applies to every admissible choice of the chain parameters .
Finite-horizon resisting oracle. For each deterministic first-order method and horizon , Lean constructs a zero-respecting simulator. For each objective in the reduction, it proves that a single pair of primal and dual isometric embeddings makes the projected queries of the original method agree with the simulator's queries at every step . This gives the reduction used in Appendix B to extend the lower bound to arbitrary deterministic methods.
The formalization also covers both PŁ inequalities, the exact primal value function, the coordinate-discovery bounds, and the resulting deterministic oracle lower bound. On the upper-bound side, it verifies the S-GDA bound with its initialization cost and the resulting high-accuracy guarantee for each fixed instance. We have clarified this scope in the revised reproducibility statement.
W3: Proof details and relation to Pan and Li (2026). We thank the reviewer for these constructive comments. We have expanded the proof of Lemma A.2 in Appendix A.4 to provide explicit second-derivative and mixed-derivative calculations, establishing the dimension-independent constants and . We have also added a detailed continuity argument covering vanishing gate values, including cases where multiple gates vanish simultaneously. Together with the geometric summability bounds, these estimates establish joint smoothness with constants independent of the chain lengths , , and (Lemma 4.3).
Regarding the relation to Pan and Li (2026), our construction builds on several techniques of Pan and Li (2026), including their scalar gating functions, dual PŁ chain blocks, terminal-gating and perspective-scaling techniques, and the finite-horizon resisting-oracle reduction. In particular, their NC–PŁ construction already establishes dual PŁ and dimension-independent joint smoothness. We do not claim these ingredients as new.
Our main contributions lie in the following differences.
First, the chain architecture is different. Pan and Li (2026) use a nonconvex primal zero-chain with auxiliary dual chains to delay primal-coordinate discovery. In contrast, we construct a single continuous dual chain as the main sequential chain, whose terminal gates control both subsequent dual blocks and a coupled primal PŁ chain. This yields the coordinate-revelation restriction in Condition 4.1(C2) and Eq. (A.25). Importantly, geometric weighting across the connected dual blocks allows the entire dual chain to retain a PŁ modulus of order , independently of the number of blocks (Lemma 4.1).
Second, the new construction must simultaneously preserve the two-sided PŁ conditions and joint smoothness. In particular, the primal PŁ property must hold uniformly over all dual states, including partially activated gates, while the coupling must not destroy the dual PŁ property or joint smoothness. For the unscaled instance , our analysis establishes
with constants independent of the total chain lengths. The key arguments are the uniform weighted chain bound (Lemma A.1), the dual gap and gradient comparisons (Eqs. (A.22)–(A.23)), and the joint derivative estimates (Lemma A.2).
Third, to obtain a lower bound for the primal-function gap rather than value-function gradient stationarity, we construct a geometrically weighted primal PŁ chain. Its PŁ constant depends only on the segment length , while the unrevealed primal segments retain geometrically decreasing optimality gaps (Lemma 4.2). Together with the exact primal envelope (Lemma 4.3), this produces the logarithmic dependence on the target accuracy.
Finally, we use the finite-horizon resisting-oracle lemma of Pan and Li (2026) to extend the zero-respecting lower bound to general deterministic first-order methods. This reduction is inherited from their work, rather than a new ingredient of our construction.
Q1: Arbitrarily long dual-prefix construction.
We thank the reviewer for this insightful observation. Indeed, the original function class does not impose a uniform restriction on dual initialization and therefore does not rule out arbitrarily long dual prefixes. As the reviewer suggests, the worst case oracle complexity over the unrestricted class may thus be infinite. This observation further motivates the distinction between the complete initialization dependent complexity and the leading high accuracy rate discussed above. In particular, our initialization controlled subclass Freg explicitly bounds the initialization overhead relative to the accuracy-dependent term, thereby ensuring a finite uniform upper bound. Our revised matching complexity characterization holds over this subclass and does not require finite uniform complexity over the unrestricted function class.
Q2: Lower bound under bounded initialization.
We thank the reviewer for raising this interesting question. Establishing the same lower bound under the stronger assumption Gin=O(Δ) or Qin=O(Δ) would require a different hard-instance construction, and is not covered by our current analysis.
As clarified in the discussion above, our matching complexity characterization concerns the high-accuracy regime formalized by Freg, where the initialization overhead is dominated by the accuracy-dependent term. We have verified that our hard instances belong to this subclass, yielding a uniform matching lower and upper bound of Θ(κxκylogϵΔ).
We will make this scope explicit in the revised manuscript. Whether the same product dependence remains necessary under a fixed bounded-initialization assumption is an interesting direction for future work.
Q3: Complexity comparison and initialization requirements.
We thank the reviewer for requesting a more precise comparison. We clarify both the improvements in the leading order complexity and the initialization requirements underlying these results.
Improved leading order complexity. The following table summarizes representative upper bounds under the two-sided PŁ condition.
Here, κf=max{κx,κy}, and κxy denotes the cross-condition number. The table compares the reported leading-order rates under their respective assumptions.
Compared with Yang et al. (2020), our result improves the condition-number dependence from κxκy2 to κxκy. Chen et al. (2022) obtain O(κxκylog(κy/ϵ)log(1/ϵ)) oracle complexity for their accelerated multi-loop AccSPIDER-GDA method when n=1, with a guarantee in expectation (Theorem 5.1 of their revised version). Their acceleration framework also admits a full-gradient GDA implementation (Table 3). In contrast, our analysis establishes a deterministic convergence guarantee of O(κxκylog(1/ϵ)) for the existing single-loop S-GDA method in the specified high-accuracy regime. Thus, we retain the favorable condition-number dependence of Chen et al. while removing an extra logarithmic factor in accuracy and avoiding nested subproblem solves.
Rankawat et al. (2026) provide a complementary cross-smoothness-dependent guarantee. However, since
κf(κf+κxy2)≥κf2≥κxκy,
their reported bound does not improve the general κxκy condition-number dependence. Its advantage lies in exploiting additional weak-coupling structure.