# Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 97 references that are in the map.
- First posted on arXiv 25 Sep 2024.

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

- [Distributionally Robust Optimization: A Review](https://mlsanity.com/paper/1908.05659/) (2019)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Solving stochastic weak Minty variational inequalities without increasing batch size](https://mlsanity.com/paper/2302.09029/) (2023)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity](https://mlsanity.com/paper/2210.13831/) (2022)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems](https://mlsanity.com/paper/2301.03113/) (2023)
- [Sublinear Convergence Rates of Extragradient-Type Methods: A Survey on Classical and Recent Developments](https://mlsanity.com/paper/2303.17192/) (2023)

## Built on by (most cited first, 2 of 2)

- [Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions](https://mlsanity.com/paper/2603.15576/) (2026)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)

## Abstract (arXiv)

This paper presents a comprehensive analysis of the well-known extragradient (EG) method for solving both equations and inclusions. First, we unify and generalize EG for [non]linear equations to a wider class of algorithms, encompassing various existing schemes and potentially new variants. Next, we analyze both sublinear ``best-iterate'' and ``last-iterate'' convergence rates for the entire class of algorithms, and derive new convergence results for two well-known instances. Second, we extend our EG framework above to ``monotone'' inclusions, introducing a new class of algorithms and its corresponding convergence results. Third, we also unify and generalize Tseng's forward-backward-forward splitting (FBFS) method to a broader class of algorithms to solve [non]linear inclusions when a weak-Minty solution exists, and establish its ``best-iterate'' convergence rate. Fourth, to complete our picture, we also investigate sublinear rates of two other common variants of EG using our EG analysis framework developed here: the reflected forward-backward splitting and the golden ratio methods. Finally, we conduct an extensive numerical experiment to validate our theoretical findings. Our results demonstrate that several new variants of our proposed algorithms outperform existing schemes in the majority of examples.