Escaping Saddle Points in Constrained Optimization
In this paper, we study the problem of escaping from saddle points in smooth nonconvex optimization problems subject to a convex set C. We propose a generic framework that yields convergence to a second-order stationary point of the problem, if the convex set C is simple for a quadratic objective function. Specifically, our results hold if one can find a ⇢-approximate solution of a quadratic program subject to C in polynomial time, where ⇢ < 1 is a positive constant that depends on the structure of the set C. Under this condition, we show that the sequence of iterates generated by the proposed framework reaches an (✏, )-second order stationary point (SOSP) in at most O(max{✏ 2 , ⇢ 3 3 }) iterations. We further characterize the overall complexity of reaching an SOSP when the convex set C can be written as a set of quadratic constraints and the objective function Hessian has a specific structure over the convex set C. Finally, we extend our results to the stochastic setting and characterize the number of stochastic gradient and Hessian evaluations to reach an (✏, )-SOSP.
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).  The authors clearly introduce the problem and their objectives, while positioning it within the existing literature. My main comment about the introductory section is that this submission claims that it provides ``the first finite-time complexity analysis for reaching an SOSP" of the considered problem. I believe this is not entirely true, considering the following work:  C. Cartis, N. I. M. Gould and Ph. L. Toint, ``Second-Order Optimality and Beyond: Characterization and Evaluation Complexity in Convexly Constrained Nonlinear Optimization", Foundations of Computational Mathematics,  DOI 10.1007/s10208-017-9363-y.  In this reference, the authors derive a bound in $\epsilon^{-3}$, in terms of outer iterations and function/derivatives evaluations, for obtaining a point at which approximate second-order conditions are satisfied. Although their optimality measure differs from that of this submission, I believe it is clear that their method also escapes saddle points and is thus worth mentioning (as mentioned by the authors regarding other references, the cost of solving the subproblem is not explicitly taken into account). Their optimality measure only involves one tolerance, yet one can view their definition of first-order optimality as similar to that of the submission, and I would welcome the authors' comments on this reference.  I would have expected Definitions 2 and 3 to enforce feasibility of the point in addition to the other optimality conditions. In the present submission, this is not a critical issue as all considered iterates are computed so as to be feasible, however I believe adding ``feasible" in these definitions would make more sense, because it does not seem that infeasible points are desirable in the context of this submission. I would like to have the authors' view on this point.  The presentation of the main algorithm and result in Section 3 is in my opinion well conducted. Even though it is clear from the algorithmic process, the authors could have insisted more on the fact that the method can have cheap first-order iterations, which is one of the strengths of this framework. The description of the first-order steps and algorithms in Section 4 is extremely clear.  Section 5 provides an example of the second phase of the algorithm (second-order step) when the constraint set is defined as an intersection of ellipsoids. Using a result from approximation algorithms, the authors show that in that case, it is possible to obtain a solution sufficiently close to the global optimum, thereby enabling the derivation of a complexity bound. Another example for linear constraints is provided in appendix. One might be concerned with the applicability of such results, especially given their dependencies on the problem dimension. Still, the argument appears valid, and the considered cases are among the most commonly encountered.  The last technical section of the submission, Section 6, is concerned with extending the previous results to the case where the gradient and Hessian of the objective are only accessed through stochastic estimates. Using batch gradients and Hessians with appropriate batch sizes, it is possible to obtain complexity guarantees for reaching approximate second-order stationary points with high probability. This extension and the associated algorithmic modifications are very interesting: in particular, the relaxation of the constraint $d_t^\top (u-x_t)=0$ is a key feature of the stochastic method, which is briefly but clearly discussed by the authors. It seems that the condition on Line 3 of Algorithm 2 is also a key difference, about which a comment could have been made. In addition, the first-order-type step is computed at every iteration, probably as a consequence of the stochasticity: this is a key difference in the per-iteration cost of the method, even though it does not impact the complexity analysis. I acknowledge that the authors could not add an extensive discussion due to space constraints, but part of it could have been added as supplementary material.  In a nutshell, I believe the results of the submission to be correct, clearly introduced and motivated. Although I regret the lack of numerical experiments that would have illustrated the applicability of the proposed framework, it is my opinion that this submission can still have an impact on the community, and stimulate further work on algorithms of this form.  Therefore, I will give this submission an overall score of 8.  Additional comments:  a) There are a few minor typos, e.g. "propsoed" line 43.  b) The series of equations on line 523 page 15 is an interesting derivation, but the first lines might need clarification. More precisely, I would like the authors to comment upon the two expectation operators that appear in the first three equalities, and the argument for going from the third equality to the fourth one.  Edit following author feedback:  I thank the authors for providing detailed answers to my comments, and I trust them to incorporate revisions as stated. I agree with the other reviewers' comments regarding the ability of the proposed scheme to escape strict saddle points, but I am confident that this can be addressed by the authors. As a result, I maintain my initial assessment on the submission.