Matching Randomized Bounds for Finite-Sum Minimax Optimization
A near-tight characterization quantifies the randomized component-oracle cost of finding Moreau-envelope stationary points with bounded dual domains.
Underlying Paper
Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
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 $\varepsilon$-stationary point of the Moreau envelope $\Phi_{1/(2L)}$ with probability at least $2/3$ and a fixed query budget. Let $A=L\Delta/\varepsilon^2$, $B=LD_Y/\varepsilon$, 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\Theta\!\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.
Finite-sum nonconvex-concave optimization considers objectives of the form
where an algorithm accesses component functions rather than the full average directly. This paper studies the randomized component-oracle complexity of finding an -stationary point of the Moreau envelope of when the dual domain has bounded diameter.
Core Contribution
Let and , where bounds the initial primal gap, bounds the dual diameter, and . For above a universal constant, the paper gives the worst-case complexity characterization
The upper and lower bounds agree within constants when . For larger , they differ by one logarithmic factor. This distinguishes how the complexity changes with the dual-domain scale instead of providing only a single aggregate rate.
Assumptions and Scope
The upper bound requires mean-squared averaged smoothness and concavity of the average objective in the dual variable. The lower bound already applies under individual smoothness. The characterization is worst-case over admissible known bounded dual domains and finite-dimensional instances.
The lower-bound setting permits adaptive component selection, arbitrary query norms, private randomization, and outputs that were not queried. These allowances make the result a broad oracle-complexity statement rather than an analysis limited to a narrowly specified algorithm class.
Technical Result
On the upper-bound side, the paper combines a persistent estimator with primal averaging and accelerated proximal dual steps, together with an explicit primal certificate. On the lower-bound side, it uses constructions covering the small-diameter and larger-diameter regimes, along with replication to extend hard instances across finite-sum sizes.
The result is theoretical rather than empirical: its evidence consists of matching algorithmic guarantees and lower-bound constructions. It characterizes the randomized query cost of Moreau-envelope stationarity, not global optimization or practical runtime on a benchmark suite.
Interpretation
The main conclusion is that the dependence on finite-sum size, target accuracy, and dual diameter is nearly fully determined for this problem class. The high-diameter logarithmic gap is the remaining qualification: the result is exactly matched up to constants in the smaller- regime and near-matched beyond it.
Evidence Box
theoreticalKey Claims
- •Characterizes randomized component-oracle complexity for bounded dual domains
- •Provides upper bounds under mean-squared averaged smoothness and average dual concavity
- •Shows lower bounds that allow adaptive selection, private randomization, and unqueried outputs
Key Results
- •Complexity is Õ(n + A min{√n B̄ + B̄⁴, n³⁄⁴ B̄})
- •Upper and lower bounds match within constants for B ≤ n¹⁄⁴
- •For B > n¹⁄⁴, the bounds differ by one logarithmic factor
- •The guarantee targets ε-stationarity of a Moreau envelope
Limitations & Caveats
- •The high-diameter regime retains a logarithmic gap
- •The result is worst-case over bounded known dual domains and finite dimensions
- •No empirical runtime or implementation evaluation is reported
- •The guarantee concerns stationarity rather than global optimality
