Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization

The cubic regularized Newton method of Nesterov and Polyak has become in-creasingly popular for nonconvex optimization because of its capability of finding an approximate local solution with a second order guarantee and its low iteration complexity. Several recent works extend this method to the setting of minimizing the average of N smooth functions by replacing the exact gradients and Hessians with subsampled approxi-mations. It is shown that the total Hessian sample complexity can be reduced to be sublin-ear in N per iteration by leveraging stochastic variance reduction techniques. We present an adaptive variance reduction scheme for a subsampled Newton method with cubic regu-larization and show that the expected Hessian sample complexity is O(N + N^2/3 ɛ^−3/2 ) for finding an (ɛ, ɛ)-approximate local solution (in terms of first and second order guaran-tees, respectively). Moreover, we show that the same Hessian sample complexity is re-tained with fixed sample sizes if exact gradients are used. The techniques of our analysis are different from previous works in that we do not rely on high probability bounds based on matrix concentration inequalities. Instead, we derive and utilize new bounds on the third and fourth order moments of the average of random matrices, which are of independent interest on their own.