Near-Optimal Pure Single-Loop Extragradient Method for Minimax Optimization
Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
This is a significant contribution to the field of optimization algorithms, providing a new method with theoretical guarantees for a specific class of problems.
This paper proposes a new algorithm for solving smooth strongly convex--strongly concave minimax optimization problems. The method is a pure single-loop damped extragradient method with fixed parameters that requires two full-gradient evaluations per iteration after initialization. It achieves last-iterate linear convergence and requires O(sqrt(κ_xκ_y) log(2κ_xκ_y/ε)) full-gradient queries to reduce the squared Euclidean distance to the saddle point to an ε fraction of its initial value. Numerical experiments show its effectiveness.
Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
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.