Research map / Optimization / Nonconvex and smooth optimization

Accelerated last-iterate convergence of Extragradient via power-law stepsizes

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Proximal finite-sum methods

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that Extragradient with power-law (time-varying) stepsizes achieves accelerated last-iterate convergence on unconstrained bilinear min-max problems, improving on the fixed-stepsize Theta(T^{-1/2}) rate.

Problem

Last-iterate convergence of the Extragradient method for unconstrained bilinear min-max optimization is slow (Theta(T^{-1/2}) with fixed stepsize), compared with the optimal O(T^{-1}) rate that usually requires extra mechanisms such as anchoring.

Approach

Replaces the fixed EG stepsize with a power-law dynamic stepsizing schedule, so that dynamic stepsizes alone (without anchoring) yield accelerated last-iterate convergence for bilinear games.

Key results

• Abstract states fixed-stepsize EG achieves Theta(T^{-1/2}) last-iterate rate, while optimal rate is O(T^{-1}); the paper proposes power-law stepsizes to close this gap for EG without anchoring.

Experimental setup

Metrics: last-iterate convergence rate

Baselines: fixed-stepsize Extragradient anchored Extragradient

Builds on: Extragradient anchoring

Closest papers by meaning

• Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.89)
• Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression (NeurIPS 2025 · similarity 0.89)
• Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.88)
• Double-Step Alternating Extragradient with Increasing Timescale Separation for Finding Local Minimax Points: Provable Improvements (ICML 2024 · similarity 0.88)
• Two-timescale Extragradient for Finding Local Minimax Points (ICLR 2024 · similarity 0.87)
• Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.87)