Lower Bounds for Nonconvex-Concave Minimax Optimization
Abstract
We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives f that are jointly L-smooth in the primal and dual variables (x,y), concave in y, and whose primal value function Φ(x) := maxy∈𝒴 f(x,y) satisfies the initial-gap condition Φ(0)−infx∈𝒳Φ(x)≤ ΔΦ, with a bounded dual domain satisfying diam(𝒴)≤ D𝒴. We measure stationarity by the norm of the gradient of the Moreau envelope of Φ+ι𝒳 with parameter 1/(2L). We prove that any deterministic zero-respecting first-order algorithm requires Ω(L2D𝒴ΔΦε−3) oracle evaluations to find an ε-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires Ω(L3D𝒴2ΔΦε−6) oracle evaluations. The same lower bounds hold when ΔΦ is replaced by the initial primal-dual gap 𝒢0. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.
Related
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Envelope Cubic Regularized Newton Method for Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{wu2026lower,
title = {{Lower Bounds for Nonconvex-Concave Minimax Optimization}},
author = {Qilong Wu and Zhihao Gu and Junchi Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14233},
eprint = {2609.14233},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14233},
}
RIS
TY - UNPB
TI - Lower Bounds for Nonconvex-Concave Minimax Optimization
AU - Qilong Wu
AU - Zhihao Gu
AU - Junchi Yang
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14233
UR - https://arxiv.org/abs/2609.14233
AB - We study lower bounds on the first-order oracle complexity of smooth nonconvex-concave minimax optimization. We consider objectives f that are jointly L-smooth in the primal and dual variables (x,y), concave in y, and whose primal value function Φ(x) := max_y∈𝒴 f(x,y) satisfies the initial-gap condition Φ(0)−inf_x∈𝒳Φ(x)≤ Δ_Φ, with a bounded dual domain satisfying diam(𝒴)≤ D_𝒴. We measure stationarity by the norm of the gradient of the Moreau envelope of Φ+ι_𝒳 with parameter 1/(2L). We prove that any deterministic zero-respecting first-order algorithm requires Ω(L^2D_𝒴Δ_Φε^−3) oracle evaluations to find an ε-stationary point. Under an unbiased stochastic first-order oracle with bounded variance, any stochastic zero-respecting algorithm requires Ω(L^3D_𝒴^2Δ_Φε^−6) oracle evaluations. The same lower bounds hold when Δ_Φ is replaced by the initial primal-dual gap 𝒢_0. These deterministic and stochastic lower bounds match the corresponding upper bounds of [14] and [29], respectively, up to a logarithmic factor in the deterministic setting.
ER -