Stochastic Variance-Reduced Cubic Regularized Newton Method
Stochastic Variance-Reduced Cubic Regularized Newton Method
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Dongruo Zhou;Pan Xu;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Dongruo Zhou;Pan Xu;Quanquan Gu
提出了一种求解非凸优化问题的随机降方差三次正则化牛顿法。该算法的核心是一种新的半随机梯度和一种专门为三次正则化方法设计的半随机海森。我们证明了我们的算法在$tide{O}(n^{4/5}/\epsilon^{3/2})$二阶预言机调用内保证收敛到$(\epsilon，\sqrt{\epsilon})$-近似局部最小值，其性能优于包括下采样三次正则化在内的最新的三次正则化算法。我们的工作也为方差化技术在高阶非凸优化方法中的应用提供了有益的启示。在各种非凸优化问题上的深入实验支持了我们的理论。
We propose a stochastic variance-reduced cubic regularized Newton method for non-convex optimization. At the core of our algorithm is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. We show that our algorithm is guaranteed to converge to an $(\epsilon,\sqrt{\epsilon})$-approximately local minimum within $\tilde{O}(n^{4/5}/\epsilon^{3/2})$ second-order oracle calls, which outperforms the state-of-the-art cubic regularization algorithms including subsampled cubic regularization. Our work also sheds light on the application of variance reduction technique to high-order non-convex optimization methods. Thorough experiments on various non-convex optimization problems support our theory.