aiqbench analysis
This theory paper shows that a deterministic, power-law-shaped stepsize schedule can speed up the last-iterate convergence of the Extragradient method on biaffine min-max problems, from $\Theta(T^{-1/2})$ to $\mathcal{O}(T^{-2/3+\varepsilon})$ with equal stepsizes and near-optimal $\mathcal{O}(T^{-1+\varepsilon})$ with separate ones. For ML readers, the relevance is to saddle-point training problems such as GANs and adversarial objectives, where the result suggests stepsize scheduling as a cheap lever. The results are asymptotic and for unconstrained biaffine settings, so transfer to nonconvex deep-learning training is unproven.
Accelerating Min-Max Optimization via Power-Law Stepsizes
arXiv:2606.01764v2 Announce Type: replace-cross Abstract: We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a $\Theta(T^{-1/2})$ last-iterate convergence rate, which is slower than the optimal $\mathcal{O}(T^{-1})$ rate attainable by incorporating additional mechanisms such as anchoring. Motivated by recent advances showing that dynamic stepsizes alone can significantly accelerate gradient descent, we ask whether dynamic stepsizes can similarly accelerate the last-iterate convergence of EG. We present the first positive result in this direction. Specifically, we provide a deterministic dynamic stepsize schedule that accelerates the convergence rate of EG to $\mathcal{O}(T^{-2/3+\varepsilon})$ for any $\varepsilon > 0$. We also show that this rate is nearly tight when the extrapolation and update steps of EG use the same stepsize. We then show that allowing different stepsizes for the extrapolation and update steps further improves the convergence rate to the near-optimal $\mathcal{O}(T^{-1+\varepsilon})$. Our analysis reduces stepsize scheduling to an optimization problem, whose solution leads to a stepsize schedule that follows (a discretization of) a power-law distribution. Our proposed stepsize schedules and analysis extend to other methods, such as Optimistic Gradient (OG), and suggest broader applicability to general min-max optimization problems.
Abstract:We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a $\Theta(T^{-1/2})$ last-iterate convergence rate, which is slower than the optimal $\mathcal{O}(T^{-1})$ rate attainable by incorporating additional mechanisms such as anchoring. Motivated by recent advances showing that dynamic stepsizes alone can significantly accelerate gradient descent, we ask whether dynamic stepsizes can similarly accelerate the last-iterate convergence of EG. We present the first positive result in this direction. Specifically, we provide a deterministic dynamic stepsize schedule that accelerates the convergence rate of EG to $\mathcal{O}(T^{-2/3+\varepsilon})$ for any $\varepsilon > 0$. We also show that this rate is nearly tight when the extrapolation and update steps of EG use the same stepsize. We then show that allowing different stepsizes for the extrapolation and update steps further improves the convergence rate to the near-optimal $\mathcal{O}(T^{-1+\varepsilon})$. Our analysis reduces stepsize scheduling to an optimization problem, whose solution leads to a stepsize schedule that follows (a discretization of) a power-law distribution. Our proposed stepsize schedules and analysis extend to other methods, such as Optimistic Gradient (OG), and suggest broader applicability to general min-max optimization problems.
58 pages. Accepted at NeurIPS 2026
Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG)
arXiv:2606.01764 [math.OC]
(or arXiv:2606.01764v2 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2606.01764 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 303 words
Related coverage
Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time
arXiv · Jun 17, 2026
Nesterov acceleration in optimizing over probability measures
arXiv · Jul 28, 2026
Introducing rocOpt: GPU-Accelerated Decision Optimization on AMD ROCm
AMD · Oct 20, 2026
Triton-Based Optimization of Video Sparse Attention on ROCm
AMD · Jul 13, 2026