Optimal First-Order Methods for Nonconvex Optimization Using the Stochastic Path-Integrated Differential Estimator

Abstract In this paper, we tackle the optimization of nonconvex functions prevalent in large-scale statistical learning tasks. We introduce the Stochastic Path-Integrated Differential EstimatoR (SPIDER), a novel method for efficiently tracking deterministic quantities with significantly lower sampling costs. Utilizing SPIDER, we develop the SPIDER-SFO algorithm, which enhances Normalized Gradient Descent (NGD) and achieves faster convergence rates for nonconvex optimization problems in both finite-sum and online cases. Our rigorous analysis shows that SPIDER-SFO achieves a gradient computational cost of O(ε⁻³ (n+n1 / 2 ε⁻²)) for finding an ε-approximate first-order stationary point. Additionally, we extend our method to find approximate second-order stationary points with the SPIDER-SFO ⁺algorithm, which combines SPIDER-SFO with efficient Negative-CurvatureSearch techniques. This algorithm attains an (ε, δ)-approximate second-order stationary point at the gradient cost $Õ((ε⁻³+δ⁻² ε⁻²+δ⁻⁵) (n1 / 2 ε⁻²+n1 / 2 δ⁻² ε⁻¹+δ⁻³ ε⁻¹+δ⁻⁵+n))$. We demonstrate that our algorithms achieve the best-known optimal convergence guarantees and optimality across a wide range of $ε$ and $δ$ values, providing superior performance under specific smoothness and Hessian-Lipschitz conditions. This work sets a new benchmark in nonconvex optimization, offering robust and scalable solutions for complex stochastic optimization tasks.