Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
This work provides a theoretical framework that unifies and accelerates optimization algorithms for convex problems, with applications in areas like regression and coordinate descent.
The paper demonstrates that standard extragradient methods achieve optimal accelerated convergence rates for minimizing smooth convex functions, by introducing a condition called relative Lipschitzness to analyze monotone variational inequalities and extending it to local and randomized settings.
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 $\ell_\infty$ regression based on area convexity and complexity bounds achieved by accelerated (randomized) coordinate descent for smooth convex function minimization.