Research map / Optimization / Nonconvex and smooth optimization
Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
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.
Shows that OGDA, EGDA and an iterative Nesterov smoothing method solve Gaussian-perturbed zero-sum games in poly(n,m,1/sigma)·log(1/epsilon) iterations w.h.p., via a smoothed analysis of the error bound (OMWU excluded).
Problem
Gradient-based methods for zero-sum games have linear convergence (log(1/eps)) only with condition-number-like quantities that can be exponentially large in the game description, so their worst-case iteration complexity is not polynomial in game dimensions.
Approach
Apply smoothed analysis (Gaussian perturbation of the payoff matrix) to the error bound that drives linear convergence; characterize the error bound modulus via support-based geometric quantities for non-degenerate games, then bound each quantity's small-value probability over support configurations.
Key results
- With high probability under Gaussian perturbation, OGDA, EGDA and IterSmooth reach an epsilon-equilibrium in poly(n,m,1/sigma)·log(1/epsilon) iterations.
- The error bound modulus kappa is at least poly(sigma, 1/(nm)) with high probability in the smoothed model, whereas a 3x3 diagonal game gives kappa arbitrarily close to 0 in the worst case.
- For delta-support-stable games, the error bound holds with kappa >= poly(1/n, 1/m, delta), yielding poly(n,m,1/delta)·log(1/epsilon) convergence; OMWU remains superpolynomial.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Gaussian perturbations to the payoff matrix | OGDA · Zero-sum games | iteration complexity: \poly(n, m, 1/\sigma) \cdot \mathsf{log}(1/\epsilon) | Helped |
| Apply Gaussian perturbations to the payoff matrix | EGDA · Zero-sum games | iteration complexity: \poly(n, m, 1/\sigma) \cdot \mathsf{log}(1/\epsilon) | Helped |
| Apply Gaussian perturbations to the payoff matrix | IterSmooth · Zero-sum games | iteration complexity: \poly(n, m, 1/\sigma) \cdot \mathsf{log}(1/\epsilon) | Helped |
| Analyze OMWU under Gaussian perturbations | OMWU · Zero-sum games | iteration complexity: significant improvement; still remains superpolynomial | Mixed |
Surprising findings
- A 3x3 diagonal zero-sum game has error bound modulus arbitrarily close to zero, so linear convergence can be arbitrarily slow despite being linear.
Limitations
- OMWU is not shown to have polynomial smoothed complexity; its bound remains superpolynomial.
- Results hold with high probability, and expected running time bound is left open.
- Analysis assumes non-degenerate games and does not optimize n, m dependence.
Experimental setup
Baselines: OGDA EGDA IterSmooth OMWU
Builds on: smoothed analysis (Spielman-Teng) linear convergence of OGDA/EGDA via error bound (Wei et al.) iterative smoothing (Nesterov, Gilpin et al.) termination analysis of linear programs (Dunagan-Spielman-Teng-style)
Closest papers by meaning
- Classic but Everlasting: Traditional Gradient-Based Algorithms Converge Fast Even in Time-Varying Multi-Player Games (ICLR 2025 · similarity 0.91)
- Monotone Near-Zero-Sum Games: A Generalization of Convex-Concave Minimax (ICLR 2026 · similarity 0.90)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.89)
- When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation (NeurIPS 2026 · similarity 0.89)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.88)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
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.