Research map / Optimization / Nonconvex and smooth optimization
Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games
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.
Proposes Gradient Ascent with Boosting Payoff Perturbation (GABP), a one-line modification of adaptively perturbed gradient ascent that adds a decaying anchor-difference term to the perturbation, giving faster last-iterate convergence in monotone games with full and noisy feedback.
Problem
Last-iterate convergence to Nash equilibria in smooth monotone games with full and noisy gradient feedback, where payoff perturbation must be carefully tuned to converge to an actual equilibrium rather than a stationary point of the perturbed game.
Approach
Adds to the payoff perturbation of APGA the term mu*(sigma^{k}-sigma^1)/(k+1), so the effective anchor evolves as a convex combination of the current and initial anchors that shrinks the perturbation gradually; analyzed with a new potential function that excludes gradient-difference terms, enabling noisy-feedback rates.
Key results
- Theoretical last-iterate rates: O~(1/T) with full feedback and O~(1/T^{1/7}) with noisy feedback, improving APGA/APMD's O~(1/sqrt T) and O~(1/T^{1/10}).
- Individual regret is O((ln T)^2) under full feedback when all players use GABP, versus O(sqrt T) for OG.
- In hard concave-convex games with noisy feedback, GABP shows a substantial GAP advantage over APGA, OG and AOG; in random payoff games with noisy feedback, GABP is slightly better than APGA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the boosting payoff perturbation based on the current and initial anchoring strategies | APGA · Monotone games, full feedback | last-iterate gap convergence rate: \tilde{\mathcal{O}}(1/ \sqrt{T}) -> \tilde{\mathcal{O}}(1/T) | Helped |
| Add the boosting payoff perturbation based on the current and initial anchoring strategies | APGA · Monotone games, noisy feedback | last-iterate gap convergence rate: \tilde{\mathcal{O}}(1 / T^{\frac{1}{10}}) -> \tilde{\mathcal{O}}(1/T^{\frac{1}{7}}) | Helped |
| Use GABP instead of APGA, OG, and AOG | Concave-convex games · Random payoff games, full feedback | gap | No clear effect |
| Use GABP instead of APGA, OG, and AOG | Concave-convex games · Random payoff games, noisy feedback | gap | Helped |
| Use GABP instead of APGA, OG, and AOG | Concave-convex games · Hard concave-convex game, noisy feedback | gap | Helped |
| Use GABP instead of APGA and OG | Concave-convex games · Hard concave-convex game, full and noisy feedback | dynamic regret | Helped |
Limitations
- Analysis assumes bounded-variance zero-mean noise and bounded gradient V(pi) <= zeta for the noisy case.
- Only full and noisy first-order feedback are studied; bandit feedback is left open.
Experimental setup
Benchmarks: random payoff games (d=50) hard concave-convex games (d=100)
Metrics: GAP function dynamic regret tangent residual
Baselines: APGA Optimistic Gradient Accelerated Optimistic Gradient APMD
Builds on: Adaptively Perturbed Mirror Descent Optimistic Gradient Accelerated Optimistic Gradient Mirror Descent
Closest papers by meaning
- Adaptively Perturbed Mirror Descent for Learning in Games (ICML 2024 · similarity 0.93)
- Classic but Everlasting: Traditional Gradient-Based Algorithms Converge Fast Even in Time-Varying Multi-Player Games (ICLR 2025 · similarity 0.90)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.88)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.87)
- Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.87)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.87)
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.