Near optimal single loop method speeds up minimax optimization problems
Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
Machine Learning
Summary
Minimax optimization is a mathematical challenge important for problems where two opposing goals must be balanced. The authors proposed a new algorithm that solves these problems faster using a simple loop with consistent steps, avoiding complicated extra calculations. Their method converges quickly to the solution, needing fewer gradient checks than many other approaches. Tests show the method is efficient and reliable for this type of problem.
What this means in practice
- •For machine learning engineers: Improve training efficiency for adversarial models and robust optimization by reducing gradient computations in smooth strongly convex-concave settings.
- •For economic modelers: Accelerate computation of equilibrium states in two-player strategic games modeled by smooth strongly convex-concave minimax problems with nonlinear interactions.
Authors
Minhao Zhang, Zi Xu
Abstract
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.