  We study nonconvex finite-sum problems and analyze stochastic variance
reduced gradient (SVRG) methods for them. SVRG and related methods have
recently surged into prominence for convex optimization given their edge over
stochastic gradient descent (SGD); but their theoretical analysis almost
exclusively assumes convexity. In contrast, we prove non-asymptotic rates of
convergence (to stationary points) of SVRG for nonconvex optimization, and show
that it is provably faster than SGD and gradient descent. We also analyze a
subclass of nonconvex problems on which SVRG attains linear convergence to the
global optimum. We extend our analysis to mini-batch variants of SVRG, showing
(theoretical) linear speedup due to mini-batching in parallel settings.
