NEON2: Finding Local Minima via First-Order Oracles
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its theoretical performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.
This paper provides a way to turn algorithms that find a first-order stationary point (i.e. gradient norm is bounded by a constant) to algorithms that find a second-order stationary point (a.k.a. approximate local minima). The definition of a second order stationary point is that the gradient norm at the point is bounded by a constant AND the smallest eigenvalue of the Hessian is at least a negative number (but with small magnitude).  The main contribution here is that the proposed approach avoids Hessian or Hessian-vector product computations. It just needs (stochastic) gradient information, which is a significant contribution. Previous works need Hessian-vector products for computing the eigenvector that corresponds to the most negative eigenvalue of the Hessian; it is recognized that the negative curvature can be exploited to decrease the objective value even when the gradient norm is small.  In this paper the authors provide two methods to replace the Hessian-vector product computations. One for the offline setting, which is that setting that the convergence rate depends on number of samples n. The other for the online setting, which is the setting that the convergence rate does not depend on $n$, as $n$ can be infinite. Theoretical guarantees on both offline setting and online setting are provided.  I enjoy reading the paper. The analysis looks correct and sound, though I didn't have time to read them in details. One concern is that the complexity result in this paper may not be the state-of-the-art. "SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator" might have a better rate. Yet, I understand that the paper is put on arxiv after this submission. It is unfair to compare them. Still, I suggest the authors to briefly mention it in the next version.  (p.s. It seems like SPIDER has a state-of-the-art rate in finding a first order stationary point. The authors of SPIDER follow the nice tricks proposed in this paper to exploit the negative curvature and turn it to an approximate local-minimum finding one. So, the papers are actually complementary.)