Natasha 2 Non-Convex Stochastic Optimization via Swing-by Saddle Points

A stochastic non-convex optimization method (Allen-Zhu 2018) for online or large-scale objectives f(x) = E_i[f_i(x)] with L-Lipschitz gradients and L_2-Lipschitz Hessians that alternates between (1) an online negative-curvature detection phase using Oja's stochastic power/eigenvector method on Hessian-vector differences for T_oja = Theta((L / delta)^2) steps to test whether lambda_min(nabla^2 f(y_k)) <= -delta/2 and if so take a cubic-regularized negative-curvature step y_{k+1} = y_k +- (delta / L_2) v, and (2) a single epoch of proximal variance-reduced stochastic gradient descent (Natasha 1.5, with proximal center penalty sigma * ||x - xhat||_2^2 where sigma = 3 * delta / 2 >= delta) that 'swings by' strict saddle points without getting trapped, achieving an varepsilon-first-order stationary point (E||nabla f(x)||_2 <= varepsilon) in O_tilde(varepsilon^{-3.25}) stochastic gradient evaluations (setting delta = varepsilon^{0.5}) and an (varepsilon, delta)-second-order stationary point in O_tilde(varepsilon^{-3.25} + varepsilon^{-1.5} delta^{-3.5}) stochastic gradient evaluations.