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 $\Phi (x)={\max }_{y\in Y}{n}^{-1}{\sum }_{i=1}^n{f}_i(x,y)$, the goal is to find an $\epsilon$-stationary point of the Moreau envelope ${\Phi }_{1/(2L)}$ with probability at least $2/3$ and a fixed query budget. Let $A=L\Delta /{\epsilon }^2$, $B=L{D}_Y/\epsilon$, and $\bar{B}=\max \{1,B\}$, where $\Delta$ bounds the initial primal gap and $D_Y$ bounds the dual diameter. For $A$ above a universal constant, the worst-case complexity is \[ \widetildeΘ\!\left(n+A\min\left\{ \sqrt n\,\bar B+\bar B^4,\ n^{3/4}\bar B\right\}\right). \] The bounds agree within constants for $B\le 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.

arXiv comment50 pages