Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
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 DY, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most Δ. The target accuracy ε 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 σ2 and mean-square smoothness, we prove the lower bound Ω (L2DYΔε−3+L3DY2Δσ2ε−6). 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 μ>0 and condition number κ:=L/μ, we obtain Ω (LΔ√κ ε−2+LΔκσ2ε−4) under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant L̅, we obtain Ω (LΔ√κ ε−2+ΔL̅σκ3/2ε−3). 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.
Related
- Optimal Algorithms for Nonsmooth Nonconvex Stochastic Optimization with Constraints
- Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Soft-Update MSA for Nonconvex Stochastic Optimal Control: Theory and Algorithms
- Variable Bregman Majorization-Minimization algorithms for nonconvex nonsmooth optimization, with application to Poisson imaging
- Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
BibTeX
@misc{song2026lower,
title = {{Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization}},
author = {Jiayi Song and Zi Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01662},
eprint = {2610.01662},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01662},
}
RIS
TY - UNPB
TI - Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
AU - Jiayi Song
AU - Zi Xu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01662
UR - https://arxiv.org/abs/2610.01662
AB - 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 Δ. The target accuracy ε 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 σ^2 and mean-square smoothness, we prove the lower bound Ω (L^2D_YΔε^−3+L^3D_Y^2Δσ^2ε^−6). 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 μ>0 and condition number κ:=L/μ, we obtain Ω (LΔ√κ ε^−2+LΔκσ^2ε^−4) under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant L̅, we obtain Ω (LΔ√κ ε^−2+ΔL̅σκ^3/2ε^−3). 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.
ER -