Stochastic Cubic Regularization for Fast Nonconvex Optimization

Stochastic Cubic Regularization for Fast Nonconvex Optimization is a Hessian-free (Hessian-vector-product based) stochastic second-order optimization method introduced by Tripuraneni, Stern, Jin, Regier, and Jordan (2018) for minimizing generalonline stochastic nonconvex objectives min_{x in R^d} f(x) = E_{xi ~ D}[f(x; xi)] with ell-Lipschitz gradients and rho-Lipschitz Hessians that finds an epsilon-second-order stationary point (||grad f(x)|| <= epsilon, lambda_min(grad^2 f(x)) >= -sqrt(rho * epsilon)) within O~(epsilon^{-3.5}) total stochastic gradient and stochastic Hessian-vector product evaluations without variance reduction or momentum acceleration (Theorem 1, Corollary 3). At each outer iteration t, Algorithm 1 draws two independent minibatches S_1 of size n_1 = O~(sigma_1^2 / epsilon^2) and S_2 of size n_2 = O~(sigma_2^2 / (rho * epsilon)) so that the averaged gradient g_t and linear Hessian-vector operator B_t[.] concentrate within ||g_t - grad f(x_t)|| <= c_1 epsilon and ||(B_t - grad^2 f(x_t))v|| <= c_2 sqrt(rho * epsilon)||v|| via matrix Bernstein inequalities (Lemma 4), and approximately minimizes the local stochastic third-order cubic submodel tilde{m}(Delta) = Delta^T g_t + (1/2) Delta^T B_t[Delta] + (rho / 6)||Delta||^3 (Equation 7) using a perturbed gradient descent subsolver (Algorithm 3) that takes an analytical Cauchy step Delta = -R_c g_t / ||g_t|| when ||g_t|| >= ell^2 / rho and otherwise runs T(epsilon) = O~(ell / sqrt(rho * epsilon)) gradient descent steps on a sphere-perturbed gradient tilde{g} = g_t + sigma * zeta.