Perturbed Gradient Descent for Escaping Saddle Points in Hessian-Lipschitz Optimization

Perturbed Gradient Descent for Escaping Saddle Points in Hessian-Lipschitz Optimization is a purely first-order non-convex optimization algorithm and geometric saddle-escape theory introduced by Jin, Ge, Netrapalli, Kakade, and Jordan (2017) for l-gradient-Lipschitz (||grad f(x_1) - grad f(x_2)|| <= l ||x_1 - x_2||) and rho-Hessian-Lipschitz (||grad^2 f(x_1) - grad^2 f(x_2)|| <= rho ||x_1 - x_2||) objectives f: R^d -> R. Whenever the gradient norm satisfies ||grad f(x_t)|| <= g_thres and at least t_thres steps have elapsed since the previous perturbation, Algorithm 1 adds a single isotropic uniform perturbation xi_t ~ Unif(B_0(r)) of radius r = tilde{Theta}(epsilon / l) and continues standard gradient descent x_{t+1} = x_t - eta grad f(x_t) with step size eta = tilde{Theta}(1 / l). By bounding the stuck region X_stuck subseteq B_{tilde{x}}(r) via a two-sequence coupling lemma (Lemma 15 and Lemma 17) showing that along the minimum-eigenvalue direction e_1 of grad^2 f(tilde{x}) (with lambda_min(grad^2 f(tilde{x})) <= -sqrt(rho epsilon)) the stuck set has width at most delta * r / sqrt(d) along e_1 (forming a 'thin pancake' of volume fraction at most delta), Theorem 3 proves that Perturbed Gradient Descent finds an epsilon-second-order stationary point (||grad f(x)|| <= epsilon and lambda_min(grad^2 f(x)) >= -sqrt(rho epsilon)) in O(l (f(x_0) - f^*) / epsilon^2 * log^4(d l Delta_f / (epsilon^2 delta))) gradient evaluations, matching unperturbed gradient descent's first-order complexity up to polylogarithmic factors without computing or inverting any Hessians.