Accelerated Gradient and Negative-Curvature Exploitation for Non-Convex Optimization

Accelerated Gradient and Negative-Curvature Exploitation for Non-Convex Optimization is a Hessian-free first-order and Hessian-vector-product optimization framework introduced by Carmon, Duchi, Hinder, and Sidford (2018) for finding epsilon-stationary and second-order stationary points of functions f: R^d -> R with L_1-Lipschitz continuous gradient and L_2-Lipschitz continuous Hessian. The method (`Accelerated-non-convex-method`, Algorithm 1) alternates between two competing subroutines controlled by a curvature threshold alpha = min{L_1, max{epsilon^2 Delta_f^{-1}, sqrt(epsilon L_2)}}: (1) `Negative-curvature-descent` (Section 3.2), which uses accelerated Lanczos/shift-and-invert top-eigenvector steps on M = L_1 I - nabla^2 f(z_j) (Corollary 2.7) in O(sqrt(L_1/alpha) log(d/delta')) Hessian-vector products to either find a negative-curvature direction v_j with v_j^T nabla^2 f(z_j) v_j <= -alpha/2 and step z_{j+1} = z_j - (2|v_j^T nabla^2 f(z_j) v_j|/L_2)*sign(v_j^T grad f(z_j)) v_j (reducing f by at least alpha^3 / (12 L_2^2), Lemma 3.2) or certify lambda_min(nabla^2 f(x_hat_k)) >= -alpha; and (2) `Almost-convex-AGD` (Section 3.1), which adds the radial hinge-squared penalty rho_alpha(x - x_hat_k) = L_1 [||x - x_hat_k|| - alpha/L_2]_+^2 so that f_k(x) = f(x) + rho_alpha(x - x_hat_k) is globally 3*alpha-almost convex and 5*L_1-smooth (Lemma 4.1), and then solves a sequence of 3*alpha-strongly convex proximal subproblems g_j(z) = f_k(z) + 3*alpha*||z - z_j||^2 via Nesterov's accelerated gradient descent (Lemma 3.1). Theorem 4.3 proves that this coupling finds x satisfying ||grad f(x)|| <= epsilon and lambda_min(nabla^2 f(x)) >= -2*sqrt(epsilon L_2) in O_tilde(Delta_f L_1^{1/2} L_2^{1/4} epsilon^{-7/4}) gradient and Hessian-vector product evaluations, strictly improving upon the O(Delta_f L_1 epsilon^{-2}) complexity of gradient descent.