Perturbed Accelerated Gradient Descent with Negative-Curvature Reset for Escaping Saddle Points

Perturbed Accelerated Gradient Descent with Negative-Curvature Reset for Escaping Saddle Points (PAGD) is a single-loop, Hessian-free momentum optimization algorithm introduced by Jin, Netrapalli, and Jordan (2018) for minimizing ell-smooth, rho-Hessian-Lipschitz nonconvex functions f : R^d -> R that finds an epsilon-second-order stationary point (||grad f(x)|| <= epsilon and lambda_min(grad^2 f(x)) >= -sqrt(rho * epsilon)) in O~((ell^{1/2} rho^{1/4} (f(x_0) - f^*) / epsilon^{7/4}) log^6(d ell Delta_f / (rho epsilon delta))) gradient evaluations (Theorem 3), strictly improving upon the O~(epsilon^{-2}) complexity of Perturbed Gradient Descent without requiring nested proximal loops or Hessian-vector products. PAGD (Algorithm 2) augments Nesterov's accelerated gradient descent (y_t = x_t + (1 - theta) v_t, x_{t+1} = y_t - eta grad f(y_t), v_{t+1} = x_{t+1} - x_t with eta = 1 / (4 ell) and momentum parameter theta = 1 / (4 sqrt(kappa)) where kappa = ell / sqrt(rho * epsilon)) with two mechanisms: (1) uniform ball perturbation x_t <- x_t + xi_t (xi_t ~ Unif(B_0(r))) whenever ||grad f(x_t)|| <= epsilon and no perturbation occurred in the last T = O~(sqrt(kappa)) steps, and (2) Negative Curvature Exploitation (NCE, Algorithm 3) triggered whenever f(x_t) <= f(y_t) + <grad f(y_t), x_t - y_t> - (gamma / 2)||x_t - y_t||^2 (with gamma = theta^2 / eta), which resets momentum v_{t+1} = 0 and either stays at x_t if ||v_t|| >= s = gamma / (4 rho) or steps to argmin_{x in {x_t +/- s v_t / ||v_t||}} f(x) if ||v_t|| < s. Progress is certified via a computable discrete Hamiltonian E_t = f(x_t) + ||v_t||^2 / (2 eta) (Equation 1) that monotonically decreases on every mild-nonconvexity AGD step (Lemma 4) and every NCE step (Lemma 5), together with an improve-or-localize bound sum_{tau=t+1}^{t+T} ||x_tau - x_{tau-1}||^2 <= (2 eta / theta)(E_t - E_{t+T}) (Corollary 6).