Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems

Abstract

We study finite-sum non-convex optimization ${\min }_{x\in {\mathbb{R}}^d}F(x)=\frac{1}{n}{\sum }_{i=1}^n{f}_i(x)$ and analyze a variance-reduced cubic Newton method based on EMA-smoothed SARAH estimators for both gradient and Hessian information. The method combines a coarse stochastic backbone with a terminal homotopy refinement: once the iterates enter a certified small-step regime, the algorithm decreases the regularization level geometrically, shortens the stage length, and increases the mini-batch size at the reciprocal rate while restarting exact finite-sum snapshots at each stage. We work under average squared gradient smoothness and average mean-cubed Hessian smoothness, thereby avoiding the trajectory-wise Hessian boundedness assumption that is often used in related analyses. Under these assumptions and a standard inexact cubic-subproblem certificate, we establish that the method returns an $(\epsilon ,\sqrt{L_2\epsilon })$-second-order stationary point with total finite-sum oracle complexity $n+\tilde{\mathcal{O}}\left(n^{1/2}{\epsilon }^{-3/2}\right)$. The analysis separates into a coarse progress phase, which yields the $n^{1/2}$-scaled stochastic backbone, and a terminal local bootstrap, which supplies the pointwise accuracy needed to turn the model step certificate into a true second-order certificate.

14 pages