Research map / Optimization / Nonconvex and smooth optimization
High-probability complexity bounds for stochastic non-convex minimax optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first high-probability complexity bound for stochastic nonconvex-PL minimax problems by analyzing single-loop smoothed alternating GDA (sm-AGDA) with a new concentration inequality for Lyapunov descent processes under sub-Gaussian gradient noise.
Problem
High-probability complexity guarantees for stochastic smooth nonconvex minimax problems, where GDA-type single-loop methods previously lacked such bounds outside convex/concave or restrictive VI settings.
Approach
Derive an almost-sure approximate descent inequality for the sm-AGDA Lyapunov function and combine it with a new concentration theorem for martingale-type processes, so the failure probability appears only additively at order eps^-2 log(1/q) rather than multiplying the eps^-4 term as in Markov or parallel-restart approaches.
Key results
- sm-AGDA attains an eps-stationary point with probability 1-q in O(l kappa^2 delta^2/eps^4 + kappa/eps^2 (l + delta^2 log(1/q))) stochastic gradient calls, matching the expectation rate up to an additive eps^-2 log(1/q) term.
- On DRO logistic regression, sm-AGDA's stationarity histograms concentrate more tightly than SAPD+ and SMDAVR across 200 runs on a9a, gisette and sido0.
- Empirical CDF of path averages on the synthetic NCPL game lies below the theoretical quantile bound Q_{q,T}, which is described as loose and worst-case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sm-AGDA with light-tailed stochastic gradients to obtain a high-probability stationarity guarantee | NCPL minimax problems · NCPL minimax problems | stochastic gradient calls: O(\ell\kappa^2\delta^2/\varepsilon^4 + \kappa/\varepsilon^2(\ell + \delta^2\log(1/\bar{q}))) | Helped |
| Use the single-loop high-probability analysis instead of parallel runs | sm-AGDA · NCPL minimax problems | high-probability complexity overhead: log(1/¯q) multiplies the high-order O(1/ε4) term -> it only affects the second-order O(1/ε2) term | Helped |
| Use sm-AGDA rather than SAPD+, SMDA, or SMDAVR | Distributionally robust nonconvex logistic regression · a9a, gisette, and sido0 | stationarity measure concentration | Helped |
| Use sm-AGDA rather than SAPD+, SMDA, or SMDAVR | Distributionally robust nonconvex logistic regression · a9a, gisette, and sido0 | stationarity measure | Helped |
| Use a smaller primal step size | sm-AGDA on the synthetic NCPL game · Synthetic NCPL game | oscillation amplitude | Helped |
Surprising findings
- The empirical CDF has a sigmoid-like shape while the theoretical quantile bound is concave, suggesting the bound is not tight on this example.
Limitations
- Requires light-tailed (sub-Gaussian) gradient noise; heavy-tailed noise not covered.
- Theory is for unconstrained problems while DRO experiments are constrained, so guarantees are only empirically predictive there.
- Bound is worst-case and appears loose compared to the empirical behavior on the synthetic example.
Experimental setup
Datasets: a9a gisette sido0 synthetic NCPL game
Benchmarks: synthetic NCPL game a9a DRO logistic regression gisette DRO logistic regression sido0 DRO logistic regression
Metrics: stationarity measure ||grad f||^2 (log10 histograms) empirical CDF vs theoretical quantile bound average M_kappa(t)
Baselines: SAPD+ SMDAVR Epoch-GDA Clipped-SGDA Clipped-SEG Stochastic APD Mirror-Prox
Builds on: sm-AGDA Lyapunov function for nonconvex-concave problems (Yang et al. 2022) sub-Gaussian concentration (Gorbunov et al. 2022)
Closest papers by meaning
- High Probability Guarantees for Nonconvex Stochastic Gradient Descent with Heavy Tails (ICML 2022 · similarity 0.93)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.91)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.91)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.90)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.90)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (ICML 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.