Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
A pure single-loop damped extragradient method achieves last-iterate linear convergence for strongly convex–strongly concave minimax optimization with near-optimal gradient complexity.
The method uses fixed parameters, two full-gradient evaluations per iteration, and an auxiliary feedback recursion, requiring no inner solves, accuracy schedules, or staged restarts. Reducing the squared Euclidean distance to the saddle point to an ε fraction requires O(√(κxκy)·log(2κxκy/ε)) full-gradient queries, attaining the optimal condition-number order up to logarithmic factors. Numerical experiments demonstrate the method's effectiveness.
- Fixed-parameter single-loop extragradient with two full-gradient evaluations per iteration
- O(√(κxκy)log(2κxκy/ε)) gradient queries matches optimal order up to logs
- No inner solves, accuracy schedules, or staged restarts required
- Last-iterate linear convergence proven for smooth strongly convex–strongly concave problems
Full article112 words · extracted from arxiv.org · click to collapse
We study smooth strongly convex--strongly concave minimax optimization with general nonlinear coupling in the deterministic unconstrained setting. We propose a pure single-loop damped extragradient method with fixed parameters and two new full-gradient evaluations per iteration after one initialization query. The method uses an auxiliary feedback recursion and requires no inner solves, accuracy schedules, or staged restarts. We establish last-iterate linear convergence and show that reducing the squared Euclidean distance to the saddle point to an $\varepsilon$ fraction of its initial value requires $O(\sqrt{κ_xκ_y}\log(2κ_xκ_y/\varepsilon))$ full-gradient queries, where $κ_x=L/μ_x$ and $κ_y=L/μ_y$. This bound attains the optimal condition-number order up to logarithmic factors through fixed explicit updates. Numerical experiments demonstrate the effectiveness of the method.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.20327