Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

arXiv:2610.01662v1 Announce Type: cross Abstract: 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 arepsilon 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_YDeltaarepsilon^{-3}+L^3D_Y^2Deltasigma^2arepsilon^{-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(LDeltasqrt{kappa},arepsilon^{-2}+LDeltakappasigma^2arepsilon^{-4}right) under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant ar L, we obtain Omega!left(LDeltasqrt{kappa},arepsilon^{-2}+Deltaar Lsigmakappa^{3/2}arepsilon^{-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.

Source: arXiv cs.LG | 2026-10-02