Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
This work addresses computational efficiency in nonconvex optimization for machine learning practitioners, though it is incremental as it builds on existing cubic regularization and variance reduction techniques.
The authors tackled the problem of efficiently finding local minima in nonconvex optimization by proposing the Lite-SVRC algorithm, which reduces Hessian sample complexity to ˜O(n + n^{2/3}/ε^{3/2}), outperforming existing cubic regularization methods.
We propose a sample efficient stochastic variance-reduced cubic regularization (Lite-SVRC) algorithm for finding the local minimum efficiently in nonconvex optimization. The proposed algorithm achieves a lower sample complexity of Hessian matrix computation than existing cubic regularization based methods. At the heart of our analysis is the choice of a constant batch size of Hessian matrix computation at each iteration and the stochastic variance reduction techniques. In detail, for a nonconvex function with $n$ component functions, Lite-SVRC converges to the local minimum within $\tilde{O}(n+n^{2/3}/ε^{3/2})$ Hessian sample complexity, which is faster than all existing cubic regularization based methods. Numerical experiments with different nonconvex optimization problems conducted on real datasets validate our theoretical results.