# Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization

arXiv: https://arxiv.org/abs/2609.20327 · HTML: https://mlsanity.com/paper/2609.20327/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 21 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Generalization Bounds for Stochastic Saddle Point Problems](https://mlsanity.com/paper/2006.02067/) (2020)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)
- [Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization](https://mlsanity.com/paper/2201.07427/) (2022)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Fundamental Benefit of Alternating Updates in Minimax Optimization](https://mlsanity.com/paper/2402.10475/) (2024)
- [Convergence rate analysis of the gradient descent-ascent method for convex-concave saddle-point problems](https://mlsanity.com/paper/2209.01272/) (2022)

## Abstract (arXiv)

We study smooth strongly convex--strongly concave minimax optimization in the deterministic unconstrained setting, without assuming a bilinear or separable structure. Although existing multi-loop methods attain near-optimal condition-number dependence, standard single-loop methods generally exhibit a substantial complexity gap. To close this gap, we propose the Single-Loop Predictor--Corrector Extragradient Method with Damped Momentum (PCE-DM), which combines an extragradient prediction--correction scheme with a novel auxiliary feedback recursion for the weaker-curvature variable. PCE-DM uses fixed parameters and two new full-gradient evaluations per iteration after one initialization query, while requiring no inner solves, accuracy schedules, or staged restarts. We develop a Lyapunov analysis that controls the predictor--corrector mismatch through corrected-gradient increments and establish last-iterate linear convergence. Specifically, PCE-DM computes an varepsilon-accurate relative solution, measured by the squared Euclidean distance to the saddle point, within O!left(√kappaxkappay log(2kappaxkappay/varepsilon)right) full-gradient queries. This result closes the condition-number complexity gap between standard single-loop methods and near-optimal multi-loop methods, matching the known lower-bound order up to logarithmic factors while retaining fixed, explicit single-loop updates. Numerical experiments on regularized linear regression and AUC maximization demonstrate the computational efficiency of PCE-DM.