We analyze a stochastic cubic regularized Newton method for finite sum optimization $\textstyle\min_{ x\in\mathbb{ R}^d} F(x) \;=\; \frac{ 1}{ n}\sum_{ i=1}^n f_i(x)$, that uses SARAH-type recursive variance reduction with mini-batches of size $b\sim n^{ 1/2}$ and exponential moving averages (EMA) for gradient and Hessian estimators. We show that the method achieves a $(\varepsilon,\sqrt{ L_2\varepsilon})$-second-order stationary point (SOSP) with total stochastic oracle calls $n + \widetilde{ \mathcal{ O}}(n^{ 1/2}\varepsilon^{ -3/2})$ in the nonconvex case (Theorem 8.3) and convergence rate $\widetilde{ \mathcal{ O}}(\frac{ L R^3}{ T^2} + \frac{ \sigma_2 R^2}{ T^2} + \frac{ \sigma_1 R}{ \sqrt{ T}})$ in the convex case (Theorem 6.1). We also treat the matrix-free variant based on Hutchinson's estimator for Hessian and present a fast inner solver for the cubic subproblem with provable attainment of the required inexactness level.
Categories: math.OC