Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration

Abstract

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.

32 pages. This is the full version of a paper appearing in ITCS 2021. v2 addresses reviewer comments and adds citations