Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
复制标题
DOI：
10.4230/lipics.itcs.2021.62
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Michael B. Cohen;Aaron Sidford;Kevin Tian
中科院分区：
文献类型：
--
作者：
Michael B. Cohen;Aaron Sidford;Kevin Tian
我们表明，标准的extragradiation方法（即镜像prox和双外推）恢复最佳的加速率为一阶最小化光滑凸函数。为了获得这一结果，我们提供了细粒度的表征的收敛速度的超梯度方法解决单调变分不等式的自然条件，我们称之为相对Lipschitzness。我们进一步推广这个框架来处理本地和随机的相对Lipschitzness的概念，从而恢复率盒约束$\ell_\infty$回归的基础上实现的面积凸性和复杂性边界加速（随机）坐标下降光滑凸函数最小化。
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 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.