Condition number limits efficiency in complex minimax problems

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

Machine Learning

Summary

This paper studies a mathematical challenge in certain optimization problems where two things compete, but one side behaves more predictably than the other. The authors show that a common measure affecting how quickly algorithms can solve these problems—the condition number—actually sets a fundamental speed limit. They prove that no algorithm following some natural rules can work faster than this limit under certain realistic conditions. This helps clarify when further improvements in algorithm efficiency might be possible and when they are not.

What this means in practice

  • For machine learning engineers: Understand fundamental efficiency limits for algorithms solving adversarial training and robust optimization problems with stochastic updates.
  • For optimization algorithm designers: Avoid investing effort into surpassing inherent runtime limits tied to condition numbers when designing stochastic minimax optimizers.

A theory result. No direct application yet.

Authors

Qihao Zhou

Abstract

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 $σ\ge\varepsilon$, the worst-case complexity of zero-respecting algorithms is $Θ(κLGσ^2\varepsilon^{-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 $\varepsilon/\sqrtκ$, while an undiscovered primal coordinate prevents stationarity. It also yields the primal-gradient lower bound $Ω(LΔ(\sqrtκ\varepsilon^{-2}+κσ^2\varepsilon^{-4}))$ after combination with the known deterministic bound, where $Δ$ bounds the initial primal function gap.