Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
复制标题
DOI：
10.1287/opre.2021.2162
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Xuefeng Gao;M. Gürbüzbalaban;Lingjiong Zhu
中科院分区：
文献类型：
--
作者：
Xuefeng Gao;M. Gürbüzbalaban;Lingjiong Zhu
随机梯度哈密顿蒙特卡罗（SGHMC）是一种具有动量的随机梯度的变体，其中将受控和适当缩放的高斯噪声添加到随机梯度中以将迭代转向全局最小值。许多作品报道了它在解决随机非凸优化问题的实践中取得的经验性成功，特别是它在许多应用中被观察到优于基于过阻尼Langevin Monte Carlo的方法，如随机梯度Langevin动力学（SGLD）。虽然SGHMC的渐近全局收敛性是众所周知的，其有限时间性能还没有得到很好的理解。在这项工作中，我们研究了两个变种的SGHMC的基础上两个替代离散的欠阻尼朗之万扩散。我们提供了有限时间的性能界的全局收敛性的SGHMC变量解决显式常数的随机非凸优化问题。我们的研究结果导致人口和经验风险最小化问题的非渐近保证。对于一个固定的目标精度水平，对一类非凸问题，我们得到的复杂性界SGHMC可以比SGLD更紧。这些结果表明，在全局非凸优化的背景下，动量加速是可能的。
Stochastic gradient Hamiltonian Monte Carlo (SGHMC) is a variant of stochastic gradient with momentum where a controlled and properly scaled Gaussian noise is added to the stochastic gradients to steer the iterates towards a global minimum. Many works reported its empirical success in practice for solving stochastic non-convex optimization problems, in particular it has been observed to outperform overdamped Langevin Monte Carlo-based methods such as stochastic gradient Langevin dynamics (SGLD) in many applications. Although asymptotic global convergence properties of SGHMC are well known, its finite-time performance is not well-understood. In this work, we study two variants of SGHMC based on two alternative discretizations of the underdamped Langevin diffusion. We provide finite-time performance bounds for the global convergence of both SGHMC variants for solving stochastic non-convex optimization problems with explicit constants. Our results lead to non-asymptotic guarantees for both population and empirical risk minimization problems. For a fixed target accuracy level, on a class of non-convex problems, we obtain complexity bounds for SGHMC that can be tighter than those for SGLD. These results show that acceleration with momentum is possible in the context of global non-convex optimization.