Accelerating Min-Max Optimization via Power-Law Stepsizes
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 Θ(T−1/2) last-iterate convergence rate, which is slower than the optimal 𝒪(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 𝒪(T−2/3+ε) for any ε > 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 𝒪(T−1+ε). 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.
Related
- Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
- Accelerating structural optimization via EIFEM: a ROM-based preconditioner
- Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
BibTeX
@misc{wu2026accelerating,
title = {{Accelerating Min-Max Optimization via Power-Law Stepsizes}},
author = {Yue Wu and Weiqiang Zheng and Yang Cai and Haipeng Luo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.01764},
eprint = {2606.01764},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.01764},
}
RIS
TY - UNPB
TI - Accelerating Min-Max Optimization via Power-Law Stepsizes
AU - Yue Wu
AU - Weiqiang Zheng
AU - Yang Cai
AU - Haipeng Luo
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2606.01764
UR - https://arxiv.org/abs/2606.01764
AB - 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 Θ(T^−1/2) last-iterate convergence rate, which is slower than the optimal 𝒪(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 𝒪(T^−2/3+ε) for any ε > 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 𝒪(T^−1+ε). 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.
ER -