Stochastic Recursive VarianceReduced Cubic Regularization Methods
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:39803990, 2020.
Abstract
Stochastic VarianceReduced Cubic regularization (SVRC) algorithms have received increasing attention due to its improved gradient/Hessian complexities (i.e., number of queries to stochastic gradient/Hessian oracles) to find local minima for nonconvex finitesum optimization. However, it is unclear whether existing SVRC algorithms can be further improved. Moreover, the semistochastic Hessian estimator adopted in existing SVRC algorithms prevents the use of Hessianvector productbased fast cubic subproblem solvers, which makes SVRC algorithms computationally intractable for highdimensional problems. In this paper, we first present a Stochastic Recursive VarianceReduced Cubic regularization method (SRVRC) using a recursively updated semistochastic gradient and Hessian estimators. It enjoys improved gradient and Hessian complexities to find an $(\epsilon, \sqrt{\epsilon})$approximate local minimum, and outperforms the stateoftheart SVRC algorithms. Built upon SRVRC, we further propose a Hessianfree SRVRC algorithm, namely SRVRC$_{\text{free}}$, which only needs $\tilde O(n\epsilon^{2} \land \epsilon^{3})$ stochastic gradient and Hessianvector product computations, where $n$ is the number of component functions in the finitesum objective and $\epsilon$ is the optimization precision. This outperforms the bestknown result $\tilde O(\epsilon^{3.5})$ achieved by stochastic cubic regularization algorithm proposed in \cite{tripuraneni2018stochastic}.
Related Material


