---
abstract: '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}/\epsilon^{3/2})$[^1] 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.'
author:
- 'Dongruo Zhou[^2]    and    Pan Xu[^3]    and    Quanquan Gu[^4]'
bibliography:
- 'reference.bib'
date: 'May 18, 2018[^5]'
title: 'Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method'
---

[^1]: Here $\tilde{O}$ hides poly-logarithmic factors

[^2]: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: [drzhou@cs.ucla.edu]{}

[^3]: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: [panxu@cs.ucla.edu]{}

[^4]: Department of Computer Science, University of California, Los Angeles, CA 90095, USA; e-mail: [qgu@cs.ucla.edu]{}

[^5]: The first version of this paper was submitted to UAI 2018 on March 9, 2018. This is the second version with improved presentation and additional baselines in the experiments, and was submitted to NeurIPS 2018 on May 18, 2018.
