mlsanityData to 7 Oct 2026

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

arXiv 2011.06572 ↗First posted 12 Nov 2020math.OC cs.DS cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

We show that standard extragradient methods (i.e. mirror prox and dual extrapolation) recover optimal accelerated rates for first-order minimization of smooth convex functions. To obtain this result we provide a fine-grained characterization of the convergence rates of extragradient methods for solving monotone variational inequalities in terms of a natural condition we call relative Lipschitzness. We further generalize this framework to handle local and randomized notions of relative Lipschitzness and thereby recover rates for box-constrained ℓ_∞ regression based on area convexity and complexity bounds achieved by accelerated (randomized) coordinate descent for smooth convex function minimization.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 3; 2024: 3; 2025: 0; 2026: 1.

18 papers.

Sort:

By area:

  1. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  2. 2021Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Couplingcited by 16
  3. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 14
  4. 2022Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimizationcited by 13
  5. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  6. 2021Complementary Composite Minimization, Small Gradients in General Norms, and Applicationscited by 9
  7. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  8. 2024Testing Calibration in Nearly-Linear Timecited by 9
  9. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  10. 2024Accelerated Preference Optimization for Large Language Model Alignmentcited by 5
  11. 2021First-Order Methods for Convex Optimizationcited by 4
  12. 2022Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelizationcited by 4
6 more
  1. 2022Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimizationcited by 4
  2. 2022Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimizationcited by 2
  3. 2022Optimal Algorithms for Stochastic Complementary Composite Minimizationcited by 1
  4. 2024Faster Acceleration for Steepest Descentcited by 1
  5. 2023Federated Composite Saddle Point Optimizationcited by 0
  6. 2026Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Sizecited by 0