Stochastic Variance-Reduced Cubic Regularized Newton Method
This work addresses faster convergence for non-convex optimization problems, which is incremental but improves upon existing cubic regularization techniques.
The paper tackles non-convex optimization by proposing a stochastic variance-reduced cubic regularized Newton method, achieving convergence to an approximate local minimum within O(n^{4/5}/ε^{3/2}) oracle calls, outperforming state-of-the-art methods.
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 $(ε,\sqrtε)$-approximately local minimum within $\tilde{O}(n^{4/5}/ε^{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.