Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method

11/29/2018
by   Dongruo Zhou, et al.
12

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 Õ(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset