Reviews: Escaping Saddle Points in Constrained Optimization

In this submission, the authors propose an algorithm for nonconvex optimization under convex constraints. The method aims at escaping saddle points and converging to second-order stationary points. The main idea of the submission lies in exploiting the structure of the convex constraint set so as to find an approximate solution to quadratic programs over this set in polynomial time. By combining this oracle with a first-order iteration such as conditional gradient or projected gradient, the authors are able to guarantee that their algorithm will converge towards an (\epsilon,\gamma) -Second-Order Stationary Point (SOSP), i. e. a point at which first and second-order necessary conditions are approximately satisfied, respectively to \epsilon and \gamma tolerances. In addition to addressing a topic of increasing interest in the community of NIPS (escaping saddle points in nonconvex optimization), this submission also touches complexity aspects that are of general interest in theoretical computer science (NP-hardness and approximation algorithms).