Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

Qihao Zhou

In the authors' words

We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$ -smooth objectives with dual strong-concavity parameter $μ$ , we prove a lower bound that matches the SAPD+ upper bound under the same Moreau-envelope stationarity criterion and the same primal-dual initialization gap. Specifically, when $σ \geq ε$ , the worst-case complexity of zero-respecting algorithms is $Θ (κ L G σ^{2} ε^{- 4})$ in the stated accuracy regime, where $κ = L / μ$ , $G$ bounds the initial primal-dual gap, and $σ^{2}$ bounds the variance of a general unbiased first-order oracle. The lower bound is realized on a smooth problem class with a bounded dual box. Our construction routes each link of a nonconvex zero-chain through a dual gradient of magnitude proportional to $ε / κ$ , while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $Ω (L Δ (κ ε^{- 2} + κ σ^{2} ε^{- 4}))$ after combination with the known deterministic bound, where $Δ$ bounds the initial primal function gap.

Main resultLimitation the authors admit

Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

In the authors' words

More on Optimization that day

TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

Disjunctive Submodular Functions: Envelopes and Applications to Inventory and 0-1 Quadratic Optimization

Optimal Prophet Inequalities for Gain from Trade

Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms

Moment Ambiguity and the Limits of Robust Stochastic Optimization