Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
Abstract
We characterize the randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain. For Φ(x)=maxy∈ Yn−1∑i=1n fi(x,y), the goal is to find an ε-stationary point of the Moreau envelope Φ1/(2L) with probability at least 2/3 and a fixed query budget. Let A=LΔ/ε2, B=LDY/ε, and B̅=max{1,B}, where Δ bounds the initial primal gap and DY bounds the dual diameter. For A above a universal constant, the worst-case complexity is Θ̃ (n+Amin{ √n B̅+B̅4, n3/4B̅}). The bounds agree within constants for B≤ n1/4 and within one logarithm for larger B. Upper bounds require only mean-squared averaged smoothness and concavity of the average in the dual variable; lower bounds already hold under individual smoothness. The lower constructions cover adaptive component selection, arbitrary query norms, private randomization, and outputs that were never queried. A cone construction gives the small-diameter bound, while a serial branch construction and balanced replication give the remaining two regimes. On the upper side, a persistent estimator with primal averaging complements accelerated proximal dual steps equipped with an explicit primal certificate. The characterization takes the worst case over admissible known dual domains and finite dimensions.
Related
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{wu2026matching,
title = {{Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization}},
author = {Wendao Wu and Haihan Zhang and Qian Chen and Chenheng Zhang and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16991},
eprint = {2610.16991},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16991},
}
RIS
TY - UNPB
TI - Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
AU - Wendao Wu
AU - Haihan Zhang
AU - Qian Chen
AU - Chenheng Zhang
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.16991
UR - https://arxiv.org/abs/2610.16991
AB - We characterize the randomized component-oracle complexity of finite-sum nonconvex-concave optimization with a bounded dual domain. For Φ(x)=max_y∈ Yn^−1∑_i=1^n f_i(x,y), the goal is to find an ε-stationary point of the Moreau envelope Φ_1/(2L) with probability at least 2/3 and a fixed query budget. Let A=LΔ/ε^2, B=LD_Y/ε, and B̅=max{1,B}, where Δ bounds the initial primal gap and D_Y bounds the dual diameter. For A above a universal constant, the worst-case complexity is Θ̃ (n+Amin{ √n B̅+B̅^4, n^3/4B̅}). The bounds agree within constants for B≤ n^1/4 and within one logarithm for larger B. Upper bounds require only mean-squared averaged smoothness and concavity of the average in the dual variable; lower bounds already hold under individual smoothness. The lower constructions cover adaptive component selection, arbitrary query norms, private randomization, and outputs that were never queried. A cone construction gives the small-diameter bound, while a serial branch construction and balanced replication give the remaining two regimes. On the upper side, a persistent estimator with primal averaging complements accelerated proximal dual steps equipped with an explicit primal certificate. The characterization takes the worst case over admissible known dual domains and finite dimensions.
ER -