acceptodds
Under review as a conference paper at ICLR 2027

Tight Lower Bounds for Stochastic Nonconvex–Strongly-Concave Minimax Optimization

Abstract

We study the stochastic first-order oracle complexity of finding -stationary points of the primal function in smooth nonconvex-strongly-concave minimax optimization. For sufficiently small , we establish lower bounds of under the bounded-variance assumption and under the additional assumption of averaged smoothness. Here, and denote the smoothness and averaged-smoothness constants, respectively, is the initial primal gap, bounds the oracle variance, and or in the respective settings, where is the strong-concavity parameter. Our bounded-variance lower bound improves the dependence on the condition number from in previous lower bounds to , while our averaged-smoothness lower bound is the first of its kind. In both settings, the resulting lower bounds match existing upper bounds in their dependence on and . Our proofs are based on a unified quadratic lifting construction that transfers a hardness instance for stochastic nonconvex minimization to unconstrained minimax optimization while preserving the required variance and smoothness properties.

Primary area:
optimization
Keywords:
Minimax Optimization, Lower Bound, Nonconvex Optimization, Oracle Complexity, Stochastic Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1QF5OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proves information-theoretic complexity lower bounds for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) minimax problems. The lower bound matches the convergence rate of SAPD+ from [Zhang et al., 2024] and SPDE from [Zhang et al. 2026] under the bounded variance assumption, which improves the previous results in [Li et al., 2021]. Under the average smoothing setting, the lower bound is new, and it matches the best convergence rate combining SAPD+ from [Zhang et al. 2024] and VR-SPDE from [Zhang et al. 2026].

Critical strengths

The main strength is that the paper addresses an important open theoretical question and derives lower bounds for nonconvex-strongly-concave minimax problems under both the bounded variance assumption and the averaged smooth assumption. All of them match the upper bound in the literature and the lower bound under the second case is new. This is a meaningful contribution to the complexity theory of nonconvex-strongly-concave minimax optimization. Also, the paper is well organized, and I can follow the proofs easily.

Critical weaknesses

My main concern is that the algorithm SAPD+ in [Zhang et al., (2024)] proves the convergence rate under the case where the initial primal dual gap is bounded. However, the paper's construction of the hard case is in the following form: fH(x,y)=αH(βy)−ν2∥y−γx∥2.f_H(x,y)=\alpha H(\beta y)-\frac{\nu}{2}\|y-\gamma x\|^2. In this case, we have inf⁡xfH(x,y)=−∞\inf_x f_H(x,y)=-\infty for every yy. This directly leads to G0=∞\mathcal G_0=\infty, even though the primal gap Δ\Delta is finite. Since the paper claims that the lower bounds match the upper bound, this will substantially weaken its claims. Basically, the matching upper and lower bound are not for the same common class.

The other major point is that the stochastic oracle that is deployed, is more powerful and more general than the gradients of sample losses.

Minor Comments:

  • [Zhang et al. (2022b)] and [Zhang et al. (2024)] both refer to the same paper that introduces SPAD+. Please check all the references and delete repeated ones.
  • It seems that the O(κϵ−3max⁡{κ,ϵ−1/2})O(\kappa \epsilon^{-3} \max \{\kappa, \epsilon^{-1 / 2}\}) is strctly dominated by O(κ3/2ϵ−3)O(\kappa^{3 / 2} \epsilon^{-3}). Maybe it is better to mention only SPAD+ in Table 1 without the rate of SPAD+(VR).
Questions for authors

Questions For Authors


  1. Could you prove the tightness of the convergence bound either by constructing a hard instance that satisfies SAPD+’s assumption with G0=O(Δ)\mathcal G_0=O(\Delta) or by changing the proof of SAPD+ using only Δ\Delta instead?
Reviewer_Lsv9OpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper establishes two lower bounds on the stochastic first-order oracle complexity of nonconvex-strongly-concave minimax problems. The first bound is Ω(κϵ−4)\Omega(\kappa\epsilon^{-4}) under the bounded-variance assumption, and the second is Ω(min⁡κ3/2ϵ−3,κϵ−4)\Omega(\min{\kappa^{3/2}\epsilon^{-3},\kappa\epsilon^{-4}}) under the additional averaged-smoothness assumption. Both bounds apply to primal and Moreau-envelope stationarity for zero-respecting stochastic first-order algorithms. The worst-case examples are optained by applying quadratic lifting to the hard function of Carmon et al. (2020) and the stochastic oracle constructions of Arjevani et al. (2023).

Both lower bounds match existing upper bounds in their dependence on κ\kappa and ϵ\epsilon. The first lower bound matches the upper bound of SAPD+ and SPDE, while the second lower bound matches those of SPDE and VR-SPDE in different accuracy regimes. However, the upper and lower bounds rely on different domain and initialization assumptions. Thus, the matching rates do not establish full tightness under identical problem assumptions.

Critical strengths

The paper improves the known lower bounds in their dependence on κ\kappa and ϵ\epsilon. In particular, it provides the first lower bound for NC-SC minimax optimization under the averaged-smoothness assumption. The resulting rates have the same dependence on κ\kappa and ϵ\epsilon as existing upper bounds. The results also cover both primal and Moreau-envelope stationarity, reducing the discrepancy in stationarity measures.

The paper develops a quadratic lifting technique. It transfers lower bounds from stochastic nonconvex minimization to NC-SC minimax optimization. The construction preserves the required bounded-variance and averaged-smoothness properties. This technique may also be useful for establishing lower bounds in other stochastic minimax problems.

Critical weaknesses

The paper does not establish whether a finite oracle complexity upper bound exists under its initialization assumptions. The paper assumes only a bounded initial primal gap, without controlling dual initialization. It is unclear whether any algorithm can guarantee finite dimension-independent oracle complexity under these assumptions. This raises a fundamental concern about the significance of the proposed finite lower bounds as a tight complexity characterization.

The claimed tightness is not established under the same assumptions as existing upper bounds. In particular, the constructed hard instances do not satisfy the finite initial primal-dual gap required by SAPD+, while SPDE and VR-SPDE assume a compact dual domain. Thus, matching the dependence on κ\kappa and ϵ\epsilon does not establish tight oracle complexity under a common problem setting. This substantially limits the significance of the claimed tightness.

Questions for authors

Is there an algorithm that provides a finite oracle complexity upper bound under exactly the same problem assumptions as the proposed lower bounds, including the unconstrained domain and primal-gap-only initialization? The upper bound need not match the proposed lower bounds in its dependence on κ\kappa and ϵ\epsilon. If such an algorithm exists, could the authors identify it and clarify its complexity guarantee?

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

This paper establishes stochastic first-order lower bounds for NC–SC minimax optimization over zero-respecting algorithms. The bounds are Ω(κϵ−4)\Omega(\kappa\epsilon^{-4}) under bounded variance and Ω(κ3/2ϵ−3)\Omega(\kappa^{3/2}\epsilon^{-3}) in the high-accuracy averaged smoothness regime. They use a unified quadratic lifting construction that transfers hard instances from stochastic nonconvex minimization while preserving the required oracle properties and stationarity guarantees.

Critical strengths

The bounded variance result improves the previous κ1/3\kappa^{1/3} dependence to κ\kappa.

The paper also establishes a lower bound under averaged smoothness.

The unified quadratic lifting preserves the required smoothness and variance properties while providing an explicit stationarity transfer.

Critical weaknesses

The scope of the tightness comparison could be further clarified. The cited upper bounds involve different domain or initialization assumptions. These differences limit the extent to which the matching rates establish tight bounds under the same assumptions.

The lower bounds are restricted to zero-respecting algorithms. While standard in zero-chain constructions, this restriction leaves open whether the same bounds hold for general stochastic first-order methods. It is also unclear whether the algorithms used in the upper bound comparisons satisfy the zero-respecting condition.

Questions for authors
  1. Can the authors clarify whether the cited upper bounds apply under the assumptions of Theorems 4.1 and 5.1?

  2. Do the algorithms considered in the upper bound comparisons satisfy the zero-respecting condition in Eq. (10)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.