Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
Abstract
We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is Θ̃(n+min{√n κ,n3/4√κ} LΔε−2) throughout κ=L/μ≥1, under exact dual initialization and for 0<ε2≤ c0LΔ, where c0>0 is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for κ≥√n. For 1≤κ≤√n, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains Õ(n+√n κLΔε−2) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most ε2. Under individual smoothness, we also prove Ω(n+min{κ,√(nκ)} LΔε−2) for every κ≥1. It matches the polynomial upper rate for a bilinear subclass when κ≥ n; the intermediate-condition-number gap remains open.
Related
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{zhou2026nearoptimal,
title = {{Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization}},
author = {Qihao Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04944},
eprint = {2610.04944},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04944},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
AU - Qihao Zhou
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04944
UR - https://arxiv.org/abs/2610.04944
AB - We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is Θ̃(n+min{√n κ,n^3/4√κ} LΔε^−2) throughout κ=L/μ≥1, under exact dual initialization and for 0<ε^2≤ c_0LΔ, where c_0>0 is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for κ≥√n. For 1≤κ≤√n, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains Õ(n+√n κLΔε^−2) with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most ε^2. Under individual smoothness, we also prove Ω(n+min{κ,√(nκ)} LΔε^−2) for every κ≥1. It matches the polynomial upper rate for a bilinear subclass when κ≥ n; the intermediate-condition-number gap remains open.
ER -