Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers SGD and accelerated GD approaches. While their results are similar to that of Jin et al., they achieve much better iteration dependence on log n: log n for AGD and log^2 n for SGD. 
main_review: Their SGD algorithm also enjoys the property of being a single-loop approach, which allows it to achieve simplicity and reduce a smaller number of hyper-parameters. One of key ideas in the paper is a power SGD-based approach which allows one to efficiently find a direction to escape from a saddle point.

limitations_and_societal_impact: I believe the paper has the following shortcomings:
I’m confused what the authors mean by “single-loop”. Algorithm 6 uses Accelerated Negative Curvature Finding, which introduces a nested loop and has the same problem with hyperparameters.
I think the paper and the main body should be more self-sufficient.For example, Theorem 3 (one of the main results) references Algorithm 6, but the algorithm itself is deferred to appendix. Negative Curvature exploitation from [20] is used, but the motivation behind it is unclear, unless one checks the original paper..
Line 252:  “we can construct the stochastic version of Algorithm 1, as shown in Algorithm 3”. It’s not clear to me why Algorithm 3 is a version of Algorithm 1.

Minor issues:
Line 151 - y_{t, ||} is used everywhere
Line 208 - assumption on < ∇ f, \bar e> should be a part of the statement
I think it would be more convenient if theorems, statements and propositions had the same numeration.
Lemma 2 - I suggest simply saying for “x_{t+1} = x_t - η ∇ f(x_t)”, since the current statement is imprecise.
Lemma 9 - Please remind what G_\perp and G_|| are
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this work, the authors study the escaping saddle points problem for nonconvex optimization. Previously Jin et al. proposed a perturbed accelerated gradient descent (AGD) method which finds $\epsilon$-second-order stationary points in $O(\log^6 n/\epsilon^{1.75})$ number of iterations, where $n$ is the dimension. By utilizing a refined perturbed negative curvature estimator, the authors successfully improves the dependence of dimension from $\log^6 n$ to $\log n$. Experiment results suggest that their algorithm performs well in practice. 
main_review: The main contribution of this work is a robust Hessian power method. Compared with previous approaches such as Jin et al. which estimate the negative curvature direction by a random added perturbation, this work further replaces the random perturbation by the previous estimated direction, which is a more accurate estimate. The idea is neat, the presentation is clear, and the experiments are comprehensive. Here are my additional comments. 

- One of the issues of this work is the so-called ‘robustness’ property. The authors name the ‘robustness’ due to the facts that replacing GD by either SGD or AGD will not prevent the algorithm from finding negative curvature. I find it a bit confusing, since normally I would use the word ‘robustness’ to describe that an algorithm is robust to some adversarial attacks brought by the opponent, which is far away from the meaning in this work. 

- Another issue of this work is the difference between the proposed estimator Algorithm 1 and the Neon 2 estimator proposed by Allen-zhu and Li. It seems that these two estimators utilize the same idea, which is to estimate the negative curvature direction through the Hessian-vector product. However, Algorithm 1 estimates the negative curvature with a single loop with high probability, while Neon 2 needs an additional boosting step to achieve a similar goal. Can the authors elaborate more on the connection and difference between them? 

- Finally, for the stochastic setting, some earlier works [1, 2] proposed algorithms to find second-order stationary points without a nested-loop structure. [3, 4] studied third-order smoothness assumption and show that it can help algorithms find second-order stationary points faster. [5, 6] showed that escaping from saddle points on the low-rank matrix factorization problem is identical to finding the global minima. [7] studied a stochastic variant of the cubic-regularization method and showed a theoretical guarantee. The authors may want to comment on these related works. 

[1] Ge, R., Li, Z., Wang, W., & Wang, X. (2019, June). Stabilized SVRG: Simple variance reduction for nonconvex optimization. In Conference on learning theory (pp. 1394-1448). PMLR.

[2] Li, Z. (2019). SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. arXiv preprint arXiv:1904.09265.

[3] Yu, Y., Xu, P., & Gu, Q. (2018). Third-order smoothness helps: Faster stochastic optimization algorithms for finding local minima. Advances in neural information processing systems. 

[4] Zhou, D., Xu, P., & Gu, Q. (2020). Stochastic nested variance reduction for nonconvex optimization. Journal of machine learning research.

[5] Ge, R., Jin, C., & Zheng, Y. (2017, July). No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning (pp. 1233-1242). PMLR.

[6] Zhang, X., Wang, L., Yu, Y., & Gu, Q. (2018, July). A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery. In International conference on machine learning (pp. 5862-5871). PMLR.

[7] Zhou, D., Xu, P., & Gu, Q. (2018, July). Stochastic variance-reduced cubic regularized Newton methods. In International Conference on Machine Learning (pp. 5990-5999). PMLR.




limitations_and_societal_impact: The authors discussed the limitations and there is no negative societal impact about this work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper provides an improved method for computing stationary points of nonconvex functions. The authors give an algorithm which, given an $L$-smooth $\rho$-Hessian Lipschitz nonconvex function $f$, computes an $(O(\epsilon), O(\sqrt{\rho \epsilon}))$-second order stationary point of $f$ using $O(\eps^{-7/4} \log n)$ gradient computations of $f$. This matches the $\epsilon$ dependence  achieved by several previous works in the area (for example [6,7,20]) but  improves the dependence on $\log n$, where $n$ is the dimension, by polynomial factors. The algorithm is also of similar simplicity to the previous state-of-the-art method given in [20], and combines the perturbed AGD framework given there with some clever observations to achieve the result.
main_review: All algorithms in this line of work combine accelerated gradient descent with a mechanism to exploit negative curvature in the objective. The main contribution of this work is a clever interpretation of perturbed gradient descent itself as a curvature exploitation routine: this significantly simplifies the algorithm and allows their approach to obtain results for stochastic gradient oracles as well.  

The analysis of the algorithm is relatively straightforward and easy to follow. The proof of the negative curvature exploitation routine seems fully correct to me, and in my brief skim I did not see any issues with the combination of this with the acceleration framework of [20]. The paper does a good job motivating the negative curvature detection idea-- the algorithm the authors propose is both the simplest and fastest algorithm in the literature for finding stationary points of nonconvex functions. 
limitations_and_societal_impact: While the result obtained is nice and of obvious practical importance, the analysis of acceleration seems to be heavily borrowed from [20], outside of the clever improvement to the negative curvature exploitation. In addition, the experiments only benchmark solution quality and iteration complexity against an unaccelerated method (PGD from [19])-- it would be interesting to see if the claimed iteration complexity translates to [20]. My score is borderline between a 7 and an 8 for these reasons: I would be happy to raise my evaluation if these concerns are addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors propose a simple gradient-based algorithm for a smooth function. And it outputs an \epsilon-approximate second-order stationary point with the complexity O(\log n/\epsilon^1.75), which is polynomially better in terms of log(n) and matches their complexities in terms of 1/\epsilon. 
main_review: This paper is technically sound, and the experiments also seem convincing. However, this paper requires some improvements.
1.	The main contribution of this paper is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve a polynomial speedup in log(n) compared to the perturbed gradient descent methods. However, the authors should add some comparisons with existing works based on negative curvature descent such as [26] and [R1] in both theory and practical.
2.	The author should explain the main differences between the proposed algorithm and the related works [26] and [R1].

3.	In the experiment section, the compared algorithms are too few. Can the authors provide more comparisons to other advanced optimization algorithms?

4.	The experiments are done only for the special non-convex functions, and the authors should provide more results for more general non-convex fucntions.
5.	In Line 165, it may be \alpha_t=\|y_{t,\|}\|/\|y_t\| instead of \alpha_t=\|y\|_{t,\|}/\|y_t\|.

[R1] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, Tianbao Yang.  Adaptive Negative Curvature Descent with Applications in Non-convex Optimization.  NeurIPS 2018
limitations_and_societal_impact: 1.	The main contribution of this paper is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve a polynomial speedup in log(n) compared to the perturbed gradient descent methods. However, the authors should add some comparisons with existing works based on negative curvature descent such as [26] and [R1] in both theory and practical.
2.	The author should explain the main differences between the proposed algorithm and the related works [26] and [R1].

3.	In the experiment section, the compared algorithms are too few. Can the authors provide more comparisons to other advanced optimization algorithms?

4.	The experiments are done only for the special non-convex functions, and the authors should provide more results for more general non-convex fucntions.
5.	In Line 165, it may be \alpha_t=\|y_{t,\|}\|/\|y_t\| instead of \alpha_t=\|y\|_{t,\|}/\|y_t\|.

[R1] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, Tianbao Yang.  Adaptive Negative Curvature Descent with Applications in Non-convex Optimization.  NeurIPS 2018

----------after feedback---------------  

The authors address my comments well, so I increased my score.
review_title: null

Meta-review: ​​This paper proposes a robust Hessian power method to find negative curvature direction, based on which (stochastic) gradient descent can find the local minima with improved gradient complexity (the improvement is in the poly-log dependence in the problem dimension $n$). All the reviewers are in strong support of this paper.  I, therefore, recommend acceptance.
Decision: Accept (Poster)