Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
This paper proves worst-case lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, explicitly permitting variance-reduction via same-sample oracle queries. Its main result shows that the stochastic barrier remains $\Omega(L^3 D_Y^2 \Delta \sigma^2 \varepsilon^{-6})$ even with mean-square smoothness. Complementary nonconvex--strongly-concave bounds are also provided. Together the results establish that variance reduction does not improve the fundamental accuracy exponent in the minimax setting.
The main NC--C lower bound is technically correct for the zero-respecting class and usefully closes a gap regarding variance reduction, but the paper never lifts the restriction to zero-respecting algorithms via a randomized reduction, and the stochastic oracle construction requires the restrictive coupling $\sigma \le D\bar{L}/4$. The NC--SC results match rates already obtained by Zhang et al. [18], so their primary role is to exhibit a unified chain construction rather than to advance the state of the art.
The strongest aspects are the clean separation of deterministic and stochastic terms and the explicit allowance of same-sample queries. The Bernoulli-gated oracle in Section 4.2 is carefully designed: it hides the next coordinate with probability $1-p$ while preserving mean-square smoothness, and the support argument shows that each successful draw reveals at most one new coordinate regardless of batch size. Theorem 4.8 correctly stitches the deterministic and stochastic scalings into a single lower bound.
First, the restriction to zero-respecting algorithms is never lifted to general randomized algorithms. Standard lower-bound proofs invoke a random rotation to force any randomized algorithm to behave like a zero-respecting one, but the constructed oracle is tied to a fixed coordinate order and is not rotationally invariant, so this reduction is absent. Without it, the bound may not apply to algorithms that query in adaptively chosen subspaces.\n\nSecond, the stochastic term requires $\sigma \le D\bar{L}/4$ (Lemma 4.5), tying the noise level to the dual-domain diameter and smoothness; the paper does not discuss whether the barrier persists for larger $\sigma$, leaving a regime gap. Additionally, the provided text ends abruptly in the middle of Section 7, cutting off the proof of Theorem 7.6 and making the MSS NC--SC bound impossible to fully verify from the source given.
The evidence is entirely theoretical and built from zero-chain lemmas (Lemma 3.2, Proposition 4.4) that are internally consistent. Comparisons to prior work are mostly fair: the paper correctly notes that Wu et al. [14] restricted oracle access in ways that excluded variance reduction, and it honestly acknowledges that the NC--SC bounds complement rather than supersede Zhang et al. [18]. However, the paper does not provide explicit problem-parameter prefactors for the cited upper bounds (e.g., the exact scaling of VR-SPDE [16] with $D_Y$ or $\bar{L}$), making it difficult to confirm tightness of the lower bound beyond the $\varepsilon$ exponent.
No code, data, or supplementary material is provided, and the dense analytic constructions would be tedious to verify numerically. While the zero-chain properties are standard in principle, the paper asserts numerous unevaluated universal constants such as $C_\varphi < 88$ and $c_b = 3/160$ without showing their derivations in the excerpt. More critically, the supplied text is truncated mid-proof during Section 7, so Theorem 7.6 cannot be independently verified from the available source alone. Full reproducibility would require either the complete source or explicit numerical validation of the chain smoothness and gradient-barrier inequalities.
We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most $\Delta$. The target accuracy $\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter $1/(2L)$. Under an unbiased stochastic first-order oracle with variance at most $\sigma^2$ and mean-square smoothness, we prove the lower bound $\Omega\!\left(L^2D_Y\Delta\varepsilon^{-3}+L^3D_Y^2\Delta\sigma^2\varepsilon^{-6}\right)$. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter $\mu>0$ and condition number $\kappa:=L/\mu$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+L\Delta\kappa\sigma^2\varepsilon^{-4}\right)$ under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant $\bar L$, we obtain $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+\Delta\bar L\sigma\kappa^{3/2}\varepsilon^{-3}\right)$. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.