Abstract
We study finite-sum nonconvex optimization problems, where the objectivefunction is an average of $n$ nonconvex functions. We propose a new stochasticgradient descent algorithm based on nested variance reduction. Compared withconventional stochastic variance reduced gradient (SVRG) algorithm that usestwo reference points to construct a semi-stochastic gradient with diminishingvariance in each iteration, our algorithm uses $K+1$ nested reference points tobuild a semi-stochastic gradient to further reduce its variance in eachiteration. For smooth nonconvex functions, the proposed algorithm converges toan $\epsilon$-approximate first-order stationary point (i.e., $\|\nablaF(\mathbf{x})\|_2\leq \epsilon$) within $\tilde{O}(n\land\epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$ number of stochasticgradient evaluations. This improves the best known gradient complexity of SVRG$O(n+n^{2/3}\epsilon^{-2})$ and that of SCSG $O(n\land\epsilon^{-2}+\epsilon^{-10/3}\land n^{2/3}\epsilon^{-2})$. For gradientdominated functions, our algorithm also achieves a better gradient complexitythan the state-of-the-art algorithms.