On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
复制标题
DOI：
--
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Xi Chen;S. Du;Xin T. Tong
中科院分区：
文献类型：
--
作者：
Xi Chen;S. Du;Xin T. Tong
随机梯度朗之万动力学（SGLD）是随机优化问题的一个基本算法. Zhang等人最近的工作。[2017]提出了一阶和二阶平稳点的SGLD命中时间的分析。Zhang et al. [2017]中的证明是一个通过界定Cheeger常数的两阶段过程，这是相当复杂的，并导致松散的界限。本文利用随机微分方程的直觉，直接分析了SGLD到达一阶和二阶平稳点的击中时间。我们的分析很简单。它只依赖于基本的线性代数和概率论工具。与Zhang等人[2017]相比，我们的直接分析也导致了更严格的界限，并显示了命中时间对不同因素的显式依赖性，包括维数，平滑度，噪声强度和步长效应。在适当的条件下，我们证明了SGLD到一阶稳定点的击中时间可以是维数无关的。此外，我们将我们的分析应用于研究机器学习中几个重要的在线估计问题，包括线性回归，矩阵分解和在线PCA。
Stochastic gradient Langevin dynamics (SGLD) is a fundamental algorithm in stochastic optimization. Recent work by Zhang et al. [2017] presents an analysis for the hitting time of SGLD for the first and second order stationary points. The proof in Zhang et al. [2017] is a two-stage procedure through bounding the Cheeger's constant, which is rather complicated and leads to loose bounds. In this paper, using intuitions from stochastic differential equations, we provide a direct analysis for the hitting times of SGLD to the first and second order stationary points. Our analysis is straightforward. It only relies on basic linear algebra and probability theory tools. Our direct analysis also leads to tighter bounds comparing to Zhang et al. [2017] and shows the explicit dependence of the hitting time on different factors, including dimensionality, smoothness, noise strength, and step size effects. Under suitable conditions, we show that the hitting time of SGLD to first-order stationary points can be dimension-independent. Moreover, we apply our analysis to study several important online estimation problems in machine learning, including linear regression, matrix factorization, and online PCA.