Linear Convergence and Implicit Regularization of Generalized Mirror Descent with Time-Dependent Mirrors
Linear Convergence and Implicit Regularization of Generalized Mirror Descent with Time-Dependent Mirrors
复制标题
含时间相关镜像的广义镜像下降的线性收敛和隐式正则化
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Caroline Uhler
中科院分区：
文献类型：
--
作者：
Adityanarayanan Radhakrishnan;M. Belkin;Caroline Uhler
以下问题对于理解现代机器学习中的过度参数化的性质是至关重要的：（1）在什么条件下以及以什么速度训练收敛到全局最小值？(2)什么形式的内隐正则化通过训练发生？虽然在回答梯度下降的这两个问题方面已经取得了重大进展，但对于一般的优化方法，它们还没有得到更完整的回答。在这项工作中，我们建立了线性收敛的充分条件，并获得近似的隐式正则化结果广义镜像下降（GMD），一个广义的镜像下降可能与时间相关的镜子。GMD包含流行的一阶优化方法，包括梯度下降，镜像下降和预处理梯度下降方法，如Adagrad。利用Polyak-Lojasiewicz不等式，我们首先给出了一个简单的分析下，非随机GMD线性收敛到一个全局最小值。然后，我们提出了一种新的，泰勒级数为基础的分析建立线性收敛的随机GMD的充分条件。作为推论，我们的结果建立了充分条件，并提供了随机镜像下降和Adagrad的线性收敛的学习率。最后，我们通过证明GMD收敛到一个插值解来获得GMD的近似隐式正则化结果，该插值解近似是对偶空间中l2范数初始化的最接近插值解，从而推广了Azizan，Lale和Hassibi（2019）在全批设置中的结果。
The following questions are fundamental to understanding the properties of over-parameterization in modern machine learning: (1) Under what conditions and at what rate does training converge to a global minimum? (2) What form of implicit regularization occurs through training? While significant progress has been made in answering both of these questions for gradient descent, they have yet to be answered more completely for general optimization methods. In this work, we establish sufficient conditions for linear convergence and obtain approximate implicit regularization results for generalized mirror descent (GMD), a generalization of mirror descent with a possibly time-dependent mirror. GMD subsumes popular first order optimization methods including gradient descent, mirror descent, and preconditioned gradient descent methods such as Adagrad. By using the Polyak-Lojasiewicz inequality, we first present a simple analysis under which non-stochastic GMD converges linearly to a global minimum. We then present a novel, Taylor-series based analysis to establish sufficient conditions for linear convergence of stochastic GMD. As a corollary, our result establishes sufficient conditions and provides learning rates for linear convergence of stochastic mirror descent and Adagrad. Lastly, we obtain approximate implicit regularization results for GMD by proving that GMD converges to an interpolating solution that is approximately the closest interpolating solution to the initialization in l2-norm in the dual space, thereby generalizing the result of Azizan, Lale, and Hassibi (2019) in the full batch setting.
影响因子：
2.5
作者：
Soltanolkotabi, Mahdi;Javanmard, Adel;Lee, Jason D.
通讯作者：
Lee, Jason D.
DOI：
10.1073/pnas.1903070116
发表时间：
2019-08-06
影响因子：
11.1
作者：
Belkin, Mikhail;Hsu, Daniel;Mandal, Soumik
通讯作者：
Mandal, Soumik