Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
复制标题
DOI：
--
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Yazhen Wang;Shang Wu
中科院分区：
文献类型：
--
作者：
Yazhen Wang;Shang Wu
本文研究了在统计学和机器学习中随机优化的背景下梯度下降算法（特别是加速梯度下降和随机梯度下降）的渐近行为，其中目标函数是根据可用数据估计的。我们证明这些算法可以用连续时间常微分方程或随机微分方程来计算建模。我们建立梯度流中心极限定理来描述这些计算算法的极限动态行为和相关统计过程的大样本性能，因为算法迭代次数和数据量都趋于无穷大，其中梯度流中心极限定理由一些线性常微分方程或随机微分方程如时变的Ornstein-Uhlenbeck过程控制。我们表明，我们的研究可以为联合计算和统计渐近分析提供一个新的统一框架，其中计算渐近分析研究这些算法随时间（或算法中的迭代次数）的动态行为，统计渐近分析研究算法应用于计算的统计过程（如估计器和分类器）的大样本行为，事实上，统计过程等于这些迭代算法产生的随机序列的极限随着迭代次数趋于无穷。基于得到的梯度流中心极限定理的联合分析结果可以识别出学习率、批大小、梯度协方差和Hessian四个因素，从而推导出求解非凸优化问题的随机梯度下降法局部最小值的新理论。
This paper investigates asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning where objective functions are estimated from available data. We show that these algorithms can be computationally modeled by continuous-time ordinary or stochastic differential equations. We establish gradient flow central limit theorems to describe the limiting dynamic behaviors of these computational algorithms and the large-sample performances of the related statistical procedures, as the number of algorithm iterations and data size both go to infinity, where the gradient flow central limit theorems are governed by some linear ordinary or stochastic differential equations like time-dependent Ornstein-Uhlenbeck processes. We illustrate that our study can provide a novel unified framework for a joint computational and statistical asymptotic analysis, where the computational asymptotic analysis studies dynamic behaviors of these algorithms with the time (or the number of iterations in the algorithms), the statistical asymptotic analysis investigates large sample behaviors of the statistical procedures (like estimators and classifiers) that the algorithms are applied to compute, and in fact the statistical procedures are equal to the limits of the random sequences generated from these iterative algorithms as the number of iterations goes to infinity. The joint analysis results based on the obtained gradient flow central limit theorems can identify four factors - learning rate, batch size, gradient covariance, and Hessian - to derive new theory regarding the local minima found by stochastic gradient descent for solving non-convex optimization problems.