acceptodds
Under review as a conference paper at ICLR 2027

Optimal Complexity for P-P Minimax Optimization

Abstract

We study the deterministic first-order oracle complexity of smooth two-sided Polyak–Łojasiewicz (PŁ) minimax optimization, where the objective is jointly -smooth, -PŁ in , and -PŁ in . Let , , and . Assuming , we prove that every deterministic first-order method requires oracle queries in the worst case to find a point satisfying . We further show, through a sharper analysis, that the existing single-loop Smoothed Gradient Descent–Ascent (S-GDA) method attains a matching upper bound, removing an extra logarithmic factor from previous upper bounds. Together, these results establish the optimal deterministic first-order oracle complexity of smooth two-sided PŁ minimax optimization.

Primary area:
optimization
Keywords:
Minimax optimization, Polyak--Łojasiewicz condition, Oracle complexity, Lower bounds

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_WF2uOpenReview ↗
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 Ω(κxκylog⁡(Δ/ϵ))\Omega(\kappa_x\kappa_y\log(\Delta/\epsilon)) 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 O(κxκylog⁡(Δ/ϵ))O(\kappa_x\kappa_y\log(\Delta/\epsilon)) upper bound for sufficiently small ϵ\epsilon, 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
  1. 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.

  2. 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
  1. 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, Φ(0)−Φ⋆≤Δ\Phi(0)-\Phi^\star\leq\Delta, without imposing any restriction on the initial dual gap Gin=Φ(0)−f(0,0)G_{\mathrm{in}}=\Phi(0)-f(0,0).

    In the proposed hard instance, Gin/Δ=Θ(κy2M)G_{\mathrm{in}}/\Delta=\Theta(\kappa_y2^M), where M=Θ(κxlog⁡(Δ/ϵ))M=\Theta(\kappa_x\log(\Delta/\epsilon)). The initialization quantity QinQ_{\mathrm{in}} 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 LL of additional blocks while coupling the primal chain only to the final MM dual blocks. With the geometric weights adjusted accordingly, the PŁ and joint-smoothness estimates appear to remain independent of LL, 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 Ω(LN)\Omega(LN) oracle calls. The resisting-oracle argument in Appendix B would then extend this obstruction to arbitrary deterministic first-order methods.

    Since LL 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 QinQ_{\mathrm{in}}. Theorem 3.2 absorbs this cost only for sufficiently small ϵ\epsilon, 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 F(ℓ,μx,μy,Δ)\mathcal F(\ell,\mu_x,\mu_y,\Delta).

    I consider this a significant issue that should be resolved before claiming an optimal complexity characterization.

  2. 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.

  3. 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
  1. 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?

  2. Can the authors establish the same Ω(κxκylog⁡(Δ/ϵ))\Omega(\kappa_x\kappa_y\log(\Delta/\epsilon)) lower bound under an additional assumption such as Gin=O(Δ)G_{\mathrm{in}}=O(\Delta) or Qin=O(Δ)Q_{\mathrm{in}}=O(\Delta)? Otherwise, how should the claimed optimal complexity characterization be interpreted?

  3. 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?

  4. 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

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\mathcal F_{\rm reg} 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(Δ)G_{\mathrm{in}}=O(\Delta) or Qin=O(Δ)Q_{\mathrm{in}}=O(\Delta) 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\mathcal F_{\rm reg}, 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⁡Δϵ)\Theta\left( \kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log\frac{\Delta}{\epsilon} \right).

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.

MethodAlg.Leading complexity
Yang et al. (2020), AGDASingle-loopO(κxκy2log⁡(1/ϵ))\mathcal O(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}^2\log(1/\epsilon))
Chen et al. (2022), AccSPIDER-GDAMulti-loopO~(κxκylog⁡2(1/ϵ))\widetilde{\mathcal O}(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log^2(1/\epsilon))
Rankawat et al. (2026), TALDASingle-loopO(κf(κf+κxy2)log⁡2(1/ϵ))\mathcal O(\kappa_f(\kappa_f+\kappa_{\boldsymbol{x}\boldsymbol{y}}^2)\log^2(1/\epsilon))
Ours, S-GDASingle-loopO(κxκylog⁡(1/ϵ))\boldsymbol{\mathcal O(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log(1/\epsilon))}

Here, κf=max⁡{κx,κy}\kappa_f=\max\{\kappa_{\boldsymbol{x}},\kappa_{\boldsymbol{y}}\}, and κxy\kappa_{\boldsymbol{x}\boldsymbol{y}} 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\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}^2 to κxκy\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}. Chen et al. (2022) obtain O(κxκylog⁡(κy/ϵ)log⁡(1/ϵ))\mathcal O\left( \kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}} \log(\kappa_{\boldsymbol{y}}/\epsilon) \log(1/\epsilon)\right) oracle complexity for their accelerated multi-loop AccSPIDER-GDA method when n=1n=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/ϵ))\mathcal O\left( \kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}} \log(1/\epsilon)\right) 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,\kappa_f(\kappa_f+\kappa_{\boldsymbol{x}\boldsymbol{y}}^2) \ge \kappa_f^2\ge\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}},

their reported bound does not improve the general κxκy\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}} condition-number dependence. Its advantage lies in exploiting additional weak-coupling structure.

AuthorsOpenReview ↗

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 κxκy\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}} 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

Vrt+1≤(1−cκxκy)Vrt.V_r^{t+1} \le \left(1-\frac{c}{\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}}\right) V_r^t.

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

Δ0:=Φ(x0)−Φ⋆,Gin:=Φ(x0)−f(x0,y0),\Delta_0:=\Phi(\boldsymbol{x}_0)-\Phi^\star, \qquad G_{\rm in}:=\Phi(\boldsymbol{x}_0)-f(\boldsymbol{x}_0,\boldsymbol{y}_0),

and define log⁡+(u):=max⁡{0,log⁡u}\log_+(u):=\max\{0,\log u\}. For Chen et al. (2022), let

δ:=ϵ12κy2,β:=2ℓ,KC=O(κx[1+log⁡+Δ0ϵ])\delta:=\frac{\epsilon}{12\kappa_{\boldsymbol{y}}^2}, \qquad \beta:=2\ell, \qquad K_{\rm C} =\mathcal O\left( \kappa_{\boldsymbol{x}}\left[ 1+\log_+\frac{\Delta_0}{\epsilon} \right]\right)

denote the inner accuracy, proximal regularization parameter, and number of outer iterations, respectively. For Rankawat et al. (2026), let κf=max⁡{κx,κy}\kappa_f=\max\{\kappa_{\boldsymbol{x}},\kappa_{\boldsymbol{y}}\} and κxy=ℓxy/μf\kappa_{\boldsymbol{x}\boldsymbol{y}}=\ell_{\boldsymbol{x}\boldsymbol{y}}/\mu_f, where ℓxy\ell_{\boldsymbol{x}\boldsymbol{y}} denotes the cross-smoothness constant.

MethodComplete complexity with initialization
Yang et al. (2020), AGDAO(κxκy2[1+log⁡+Δ0+Gin/10ϵ])\displaystyle\mathcal O\left(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}^2\left[1+\log_+\frac{\Delta_0+G_{\rm in}/10}{\epsilon}\right]\right)
Chen et al. (2022), AccSPIDER-GDA (n=1n=1)O(κy[1+log⁡(1+2400κy5(Δ0+Gin)δ)+KClog⁡(9600κy3+51200κy5(Δ0+KCδ)βδ)])\displaystyle\mathcal O\left(\kappa_{\boldsymbol{y}}\left[1+\log\left(1+\frac{2400\kappa_{\boldsymbol{y}}^5(\Delta_0+G_{\rm in})}{\delta}\right)+K_{\rm C}\log\left(9600\kappa_{\boldsymbol{y}}^3+\frac{51200\kappa_{\boldsymbol{y}}^5(\Delta_0+K_{\rm C}\delta)}{\beta\delta}\right)\right]\right)
Rankawat et al. (2026), TALDAO(κf(κf+κxy2)×[1+log⁡+cκf2κy(Δ0+Gin)ϵ]×[1+log⁡+cκfκy(Δ0+Gin)ϵ])\displaystyle\mathcal O\Bigg(\kappa_f(\kappa_f+\kappa_{\boldsymbol{x}\boldsymbol{y}}^2)\times\left[1+\log_+\frac{c\kappa_f^2\kappa_{\boldsymbol{y}}(\Delta_0+G_{\rm in})}{\epsilon}\right]\times\left[1+\log_+\frac{c\kappa_f\kappa_{\boldsymbol{y}}(\Delta_0+G_{\rm in})}{\epsilon}\right]\Bigg)
Ours, S-GDAO(κxκy[1+log⁡+37κy2(Δ0+Gin)ϵ]+κylog⁡(1+κy))\displaystyle\mathcal O\left(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\left[1+\log_+\frac{37\kappa_{\boldsymbol{y}}^2(\Delta_0+G_{\rm in})}{\epsilon}\right]+\kappa_{\boldsymbol{y}}\log(1+\kappa_{\boldsymbol{y}})\right)

The initialization quantities are not identical across these methods, but all involve initial dual suboptimality. Yang et al. (2020) retain GinG_{\rm in} 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 Δ0+Gin\Delta_0+G_{\rm in}. For our method, we have

Gin≤Qin≤4κy2(Δ0+Gin).G_{\rm in}\le Q_{\rm in} \le 4\kappa_{\boldsymbol{y}}^2(\Delta_0+G_{\rm in}).

The direct-start complexity in the table follows from Vr0≤Δ0+9QinV_r^0\le\Delta_0+9Q_{\rm in} 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: O(κxκy[1+log⁡Δϵ]+κylog⁡[(1+QinΔ)(1+κy)])\mathcal O\left( \kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}} \left[1+\log\frac{\Delta}{\epsilon}\right] + \kappa_{\boldsymbol{y}}\log\left[ \left(1+\frac{Q_{\rm in}}{\Delta}\right) (1+\kappa_{\boldsymbol{y}}) \right] \right). Under the high-accuracy condition specified above, the initialization and output costs are absorbed into the main term, yielding

O(κxκylog⁡Δϵ).\mathcal O\left( \kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log\frac{\Delta}{\epsilon} \right).

AuthorsOpenReview ↗

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 (cρρ,cxρ)=(113,100)(c_{\rho\rho},c_{\boldsymbol{x}\rho})=(113,100), and the revised proof in Appendix A.4 gives the sharper constants (24,13)(24,13). For the unscaled payoff, Lean proves that its joint gradient is globally 20482048-Lipschitz, including at zero gate values. The same constant applies to every admissible choice of the chain parameters K,N,SK,N,S.

Finite-horizon resisting oracle. For each deterministic first-order method and horizon TT, 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 t<Tt<T. 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 cρρ=24c_{\rho\rho}=24 and cxρ=13c_{\boldsymbol{x}\rho}=13. 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 KK, NN, and SS (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 1/N1/N, independently of the number MM 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 fˉ\bar f, our analysis establishes

μx,fˉ=Ω(1/K),μy,fˉ=Ω(1/N),ℓfˉ=O(1),\mu_{\boldsymbol{x},\bar f}=\Omega(1/K),\qquad \mu_{\boldsymbol{y},\bar f}=\Omega(1/N),\qquad \ell_{\bar f}=O(1),

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 KK, while the unrevealed primal segments retain geometrically decreasing optimality gaps (Lemma 4.2). Together with the exact primal envelope Φˉ(x)=P(x)\bar\Phi(\boldsymbol{x})=P(\boldsymbol{x}) (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.

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

This paper establishes matching deterministic first-order upper and lower bounds for smooth two-sided PL minimax optimization. In particular, it proves the Θ(κxκylog⁡(Δ/ϵ))\Theta(\kappa_x\kappa_y\log(\Delta/\epsilon)) complexity and sharpens the analysis of the existing single-loop S-GDA method to attain the matching upper bound.

Critical strengths

I find the result strong and clean.

  1. Providing both a lower bound for first-order methods and a matching upper bound convincingly resolves the deterministic complexity of this important PL-PL minimax class.

  2. The lower-bound construction and the refined Lyapunov analysis appear technically meaningful, and the paper is very clearly written and well organized.

  3. Moreover, the upper bound is achieved by the simple single-loop S-GDA algorithm, which further suggests potential practical relevance beyond the theoretical characterization.

Critical weaknesses

A minor limitation is that the stochastic setting is not considered in this paper; extending the results to the stochastic problem remains open. Still, within its stated deterministic setting, the paper offers a complete and elegant characterization.

Questions for authors

Could the authors briefly summarize the most interesting technical idea in the lower-bound construction? More broadly, are there any key techniques that can be generalized to other problems?

2 comments

We thank the reviewer for the positive assessment and constructive comments. We agree that extending our results to stochastic first-order oracles is an interesting direction for future research, particularly in establishing corresponding stochastic lower bounds.

Regarding the lower-bound construction, we highlight two main technical ideas.

First, most existing minimax lower bound constructions often use a primal zero-chain with auxiliary dual chains to delay primal coordinate discovery, as in Pan and Li (2026). In contrast, we use a single continuous dual chain as the main sequential chain, and couple a primal PŁ chain to it through the terminal gates. Consequently, revealing each new primal coordinate requires traversing an additional dual block of length NN, producing the multiplicative dependence on the primal and dual condition numbers.

Second, the main technical challenge is to preserve the two-sided PŁ conditions and joint smoothness under this new coupling. While Pan and Li (2026) establish dual PŁ and dimension-independent joint smoothness in the NC–PŁ setting, our construction must additionally preserve the primal PŁ condition uniformly over all dual states, including partially activated gates. Through geometric weighting and a carefully designed primal–dual coupling, we construct an unscaled hard instance fˉ\bar f satisfying

\mu_{\boldsymbol{y},\bar f}=\Omega(1/N),\qquad \ell_{\bar f}=O(1),$$ with constants independent of $K,N,S$ (Lemma 4.3(i)). The scaling in Lemma 4.4(ii) then matches the prescribed smoothness and two-sided PŁ parameters. Moreover, the construction preserves the exact primal value function $\bar\Phi(\boldsymbol{x})=P(\boldsymbol{x})$, allowing the sequential coordinate restriction to yield a lower bound directly for the primal gap. These ideas may also suggest directions for more general KŁ minimax lower bounds. In particular, the continuous dual-chain construction could provide a starting point for studying two-sided KŁ–KŁ problems, while the analysis of regularity under the primal–dual coupling may offer useful insights for NC–KŁ problems. Establishing either extension would require new constructions that preserve the relevant KŁ inequalities and joint smoothness with controlled constants as the chain length increases.

I thank the authors for their responses. I find the discussion interesting. I will keep my score.

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

The paper studies deterministic first-order oracle complexity for smooth PL-PL minimax problems. They first proposed an Ω(κxκylog⁡(Δ/ϵ))\Omega(\kappa_x\kappa_y\log(\Delta/\epsilon)) lower bound for this problem, then a sharper analysis of S-GDA algorithm reveals a matching upper bound, which shows that the derived lower bound is indeed optimal.

Critical strengths
  1. Derive the optimal oracle complexity for PL-PL minimax optimziation problems, close the gap between the upper and lower bounds, the constribution is significant in the theory side.
  2. The hard instance construction and sharper analysis of S-GDA are nontrivial contributions.
Critical weaknesses

None.

Questions for authors
  1. Theorem 3.2 establishes an instance-wise upper bound for sufficiently small ϵ\epsilon, whereas Definition 2.5 considers worst-case oracle complexity over the entire function class. Could the authors clarify whether the claimed matching optimal complexity is attained in an instance-wise asymptotic sense or as a uniform minimax complexity bound?
2 comments

Response.

We thank the reviewer for raising this important question. In the submitted version, Theorem 3.2 establishes the stated upper bound for each fixed problem instance at sufficiently high accuracy, where the accuracy threshold may depend on the instance. This does not directly imply a uniform minimax upper bound over the original function class.

As clarified in our Common Response, we make the complete initialization-dependent complexity explicit and identify an initialization-controlled subclass Freg(ϵ)\mathcal F_{\mathrm{reg}}(\epsilon). We further verify that our lower-bound hard instances belong to this subclass. Consequently, our lower and upper bounds match uniformly over this subclass, yielding

Θ(κxκylog⁡Δϵ)\Theta\left(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log\frac{\Delta}{\epsilon}\right)

in the specified high-accuracy regime.

We will revise the manuscript to make this distinction and the scope of our complexity characterization explicit.

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

Comments on the paper

2 comments
AuthorsOpenReview ↗

Common Response

We thank the reviewers for their careful assessment and for highlighting the role of initialization in the oracle complexity characterization.

Our main goal is to characterize the optimal dependence on the condition numbers and target accuracy. Since our target criterion is the primal-function gap Φ(x)−Φ⋆≤ϵ\Phi(\boldsymbol{x})-\Phi^\star\le\epsilon, we naturally consider the general two-sided PŁ function class with the initial primal-function gap Φ(0)−Φ⋆≤Δ\Phi(\boldsymbol{0})-\Phi^\star\le\Delta bounded.

Our results establish a deterministic first-order lower bound over this general class and a sharper S-GDA upper bound with explicit initialization costs. To characterize when these bounds match in the uniform worst-case sense, we further identify an initialization-controlled subclass Freg\mathcal F_{\mathrm{reg}}. We verify that our lower-bound hard instances also belong to this subclass, yielding matching upper and lower bounds in the high-accuracy regime.

Initialization dependence in existing results.

Importantly, initialization dependence is also present in existing analyses of two-sided PŁ minimax optimization. While the reported convergence rates typically emphasize their leading dependence on condition numbers and accuracy, the complete guarantees involve initial Lyapunov potentials that may contain both primal and dual gaps. For example, Yang et al. (2020, Theorem 3.2) establish linear convergence under the two-sided PŁ condition through a Lyapunov potential

P0=(Φ(x0)−Φ⋆)+110(Φ(x0)−f(x0,y0)).P_0=\bigl(\Phi(\boldsymbol{x}_0)-\Phi^\star\bigr)+\frac{1}{10}\bigl(\Phi(\boldsymbol{x}_0)-f(\boldsymbol{x}_0,\boldsymbol{y}_0)\bigr).

Similarly, Chen et al. (2022) use a Lyapunov function involving both the primal-function gap and the dual gap. In the related NC–PŁ setting, Yang et al. (2022, Theorem 4.1) also explicitly retain an initial auxiliary primal–dual gap in their S-GDA analysis.

Thus, while the leading convergence rates highlight the dependence on condition numbers and accuracy, the complete oracle complexity may include additional initialization dependent terms. We follow this distinction by explicitly accounting for initialization in our full complexity bound and characterizing the regime in which the accuracy dependent term dominates.

Complete upper bound and high accuracy regime.

In fact, our Appendix D already establishes the following complete nonasymptotic complexity guarantee for S-GDA:

T_\epsilon(f)=\mathcal O\bigg(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\left[1+\log\left(\frac{\Delta}{\epsilon}\right)\right]+\kappa_{\boldsymbol{y}}\log\left[\left(1+\frac{Q_{\rm in}(f)}{\Delta}\right)(1+\kappa_{\boldsymbol{y}})\right]\bigg). \tag{1}

where Qin(f)Q_{\rm in}(f) is the initialization quantity defined in Appendix C.3. This guarantee holds for every instance in the original function class, with universal numerical constants. The first term characterizes the accuracy-dependent optimization complexity, whereas the second accounts for initialization and output conversion. Motivated by the leading order rates commonly studied in the literature, we focus on the high accuracy regime in which the former dominates the latter. To make this regime precise, for each target accuracy ϵ\epsilon, we introduce the initialization controlled subclass

\lbrace f\in\mathcal F \mid \log[(1+Q_{\rm in}(f)/\Delta)(1+\kappa_{\boldsymbol{y}})] \le\kappa_{\boldsymbol{x}}\log(\Delta/\epsilon) \rbrace.\qquad (2)$$ For every instance in $\mathcal F_{\rm reg}$, the initialization and output costs are controlled by the leading accuracy dependent term. Consequently, (1) immediately yields the uniform upper bound $$\mathcal T_\epsilon\bigl(\mathcal A_{\rm det},\mathcal F_{\rm reg}\bigr)=\mathcal O\left(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log\frac{\Delta}{\epsilon}\right)$$ whenever $\log(\Delta/\epsilon)\ge1$.
AuthorsOpenReview ↗

Common Response (Continued)

Matching lower bound on the same subclass.

Importantly, the hard instances constructed in Theorem 3.1 also belong to this subclass in an explicit high-accuracy regime. Indeed, we checked in Appendix D that

\log\left[\left(1+\frac{Q_{\rm in}(f)}{\Delta}\right)(1+\kappa_{\boldsymbol{y}})\right]\le\frac{2\mu_1}{\ell_0}\kappa_{\boldsymbol{x}}\log\frac{\Delta}{\epsilon}+2\log(1+\kappa_{\boldsymbol{y}}). \tag{3}

Since 2μ1/ℓ0≤1/1302\mu_1/\ell_0\le1/130, the defining restriction in (2) is satisfied whenever log⁡(1+κy)≤κx3log⁡Δϵ\log(1+\kappa_{\boldsymbol{y}})\le\frac{\kappa_{\boldsymbol{x}}}{3}\log\frac{\Delta}{\epsilon}. Moreover, the orthogonal transformations used in Appendix B preserve both partial gradient norms at the origin, and hence preserve QinQ_{\rm in}. Therefore, the resisting-oracle reduction remains valid within Freg\mathcal F_{\rm reg}.

Combining this observation with Theorem 3.1, under its condition-number assumptions, for 0<ϵ<Δmin⁡{164,(1+κy)−3/κx}0<\epsilon<\Delta\min\lbrace\frac1{64},(1+\kappa_{\boldsymbol{y}})^{-3/\kappa_{\boldsymbol{x}}}\rbrace, we obtain

\mathcal T_\epsilon\bigl(\mathcal A_{\rm det},\mathcal F_{\rm reg}\bigr)=\Theta\left(\kappa_{\boldsymbol{x}}\kappa_{\boldsymbol{y}}\log\frac{\Delta}{\epsilon}\right). \tag{4}

Thus, our lower and upper bounds establish a uniform minimax complexity characterization over an explicitly defined initialization controlled subclass, rather than merely an instance wise asymptotic comparison.

We will clarify this distinction in the revised manuscript, retaining the original function class for the complete initialization-dependent upper bound while specifying Freg\mathcal F_{\rm reg} for the matching high accuracy complexity result.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.