Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper addresses the problem of finding stationary points in non-convex settings that are not saddle points (i.e. satisfies second order optimality). It proposes two negative curvature finding (NCF) frameworks that only use zero-order oracles: one offline deterministic and the other online stochastic. The NCF frameworks provide two options of gradient estimation: a coordinate-based estimator and a randomized estimator. The paper then applies this framework to four algorithms and show that these algorithms converge to second-order stationary points. Convergence analysis gives complexity in terms of function queries.
strengths_and_weaknesses: Strengths:
 - Paper is well-written and logically organized. The notation is generally clear and easy to follow.
 - The paper addresses an important topic within optimization: escaping saddle points. 

Weaknesses:
 - No experimental results.
 - Would like clarification on claim that their method turns first-order NCF methods into zero-order NCF methods without increasing the iteration complexity. 
questions: 1. The authors describe situations when gradient calculations are expensive or infeasible (lines 55-56). Are there empirical results that their gradient-free methods outperform existing methods in these situations?
2. Experiments would also help to strengthen the claim that iteration complexity does not significantly increase. It would be good to have empirical results on the accuracy versus number of iterations needed, as well as accuracy versus training time, benchmarked against state of the art methods.
3. CoordEstGrad is calculated by summing across d finite differences calculation (where d is the dimensionality of the problem). This means that there is a dependency on d embedded within CoordEstGrad itself. Is this dependence on d included in the iteration complexity of the framework? For example, Remark 2 says "CoordGradEst has a lower approximation error and thus can reduce the iteration complexity by a fact[or] of d". Does this include the summation within the calculation of CoordGradEst? Similar question for Theorem 4 in the comparison of the complexity of CoordGradEst and that of RandCoordEst: does the O(d/epsilon2) vs O(d2/epsilon2) include the computation of CoordGradEst as well?
4. Some typos/ minor issues
 - Line 30. rho is undefined until line 108. It may be useful to have rho defined earlier.
 - Line 124. Although clear from context, mu is not defined until line 142.
 - Algorithm 1. What is C\_0? And what does ``with proper choice of r'' (line 171) mean? r is a calculated value in the algorithm based on d, C\_0 and sigma.
 -  Algorithm 3. What is C\_1?
 - Line 244. Typo? Should be "factor of d" instead of "fact of d".
5. Because of the similarity to the Neon2 paper, it could be useful to explicitly discuss the paper's contribution beyond what was done in Neon2. For example, which part of the theoretical analysis required different techniques than that used in the Neon2 paper?
limitations: This work does not appear to me to have negative social impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper investigates escaping saddle points of nonconvex problems with zeroth order gradient descent method. A general framework is proposed to capture zeroth-order GD, SGD, and some other closely related algorithms. The main result is the convergence to approximate second order stationarities of these algorithms. The main idea is believed to be inspired by [18] and [47], but the results, to my best knowledge, is novel.
strengths_and_weaknesses: Strength: The problem this paper addresses is well motivated, the writeup is easy to follow, and the novelty and contribution are easy to identified.

Weaknesses: As highlighted in the beginning of the paper, the main technique is to introduce a framework to capture differential ZO methods, but the main article has not focus on this unified framework. Instead of elaborating all the algorithms, the main idea and novelty should have been treated in the main to some extent.


The experimental results should have been presented somewhere in the main article. Reasons of doing this: the main difficulty of using perturbed methods (which have been proven escaping saddle points) is the setting of parameters, the experiments apparently have some hints on the effects of the parameters. Moreover, it is good to see experiments on the Octopus function since it is an important motivation of using any perturbed methods to escape saddle point efficiently instead of using much simpler algorithms like GD (and many first order methods) that has been proven not converging to saddle points either. Brief discussion on these results will make the paper more attractive.

questions: As far as I have understood, a very related former work is [47]. Even the escaping saddle points results holds for algorithms that are not studied in [47], I would like to see the technical challenges of this paper compared to [47]. Part of the difficulty should come from the diversity and complexity of the algorithms considered in this paper, but anything else? I might have missed some points as reading the paper, it would be great if the authors are willing to provide some guidance.
limitations: Considered the choice of hyper parameters and the assumption of Lipschitz Hessian, current experiments is not sufficient for wide application of algorithms.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a zeroth-order negative curvature framework (NCF) that escapes saddle points and converges to a second-order stationary point (SOSP). This framework can be applied to previous zeroth-order algorithms in order to converge to SOSPs. The theoretical results show that ZO-GD achieves similar convergence results to other deterministic ZO methods (with maybe a slightly better dependence on dimension $d$) when $\delta = \mathcal{O}(\sqrt{\epsilon})$. The stochastic results also achieve similar convergence results as other stochastic ZO methods except in the case $\delta = \mathcal{O}(\epsilon^{2/3})$.
strengths_and_weaknesses: To the best of my knowledge, this work seems to be quite novel. I have not seen any zeroth-order NCF methods, especially ones that obtain similar convergence results as its ZO peer methods. This is a big strength, and the literature review is in depth and helpful for the reader.

The theoretical analysis seems to be sound. I was unable to carefully examine all the proofs in the appendix. The paper seems to be only a theoretical contribution, which is fine but experimental results would be a boost to the overall work to show that this method is feasible and effective in practice (more on this later). 

One major issue with this work is its cohesion: I felt that the work seems a bit thrown together. The theoretical results are lengthy, with many theorems/lemmas/corollarys/propositions not including detailed, descriptive, or informative remarks. The theoretical results should be described in a compact and easily digestable manner. In the current state, the results are quite sprawled in Section 4. The same is true for the algorithms. There are no detailed descriptions of Algorithms 4-8. This is problematic. Finally, there is no Conclusion section or any real end of the work. This makes the work feel like a work in progress.

The last issue is with the (lack of) experimental results. Many of the other ZO methods obtain similar convergence results and showcase their performance in practice. It would be beneficial to show if your ZO NCF method can perform better than a ZO random perturbation method. In my opinion this is something that is critically lacking in the current work.

Minor Issue:
1. Is Remark 2 supposed to come after Theorem 4? In the remark, it states that the "dominant term of the function query complexity in Option I is $\mathcal{\tilde{O}(d/\epsilon^2)}$". However, while true in Theorem 4, the dominant term seems to be $\mathcal{\tilde{O}(d/\epsilon^2 \delta^3)}$ in Theorem 3.

Overall, I feel that the development of a ZO-NCF method with rigorous theoretical analysis is a great contribution. However, I believe a lot of work still needs to be done to experimentally backup the convergence claims and make the paper cohesive.

I thank the authors for their submission and am looking forward to their response!

===========================================
Update after author rebuttal:

I had missed the experiments in the appendix, but the authors moved a single experiment into the main section (Section 5). Other experiments remain in the appendix. The authors also did a nice job in cleaning up the presentation of the work. For this, I have bumped up my overall score from a 5 to a 7 and presentation from a 2 to a 3. Great job!

**[R1]** Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Efficiently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32, 2019.
questions: All of my questions are listed in the strengths and weaknesses above.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposed zeroth-order negative curvature finding (NSF) algorithms for both deterministic and stochastic nonconvex minimization problem that finds $\epsilon$-SOSP with the same iteration complexity as the state-of-the-arts for finding $\epsilon$-FOSP, and improved the query complexity of existing algorithms for finding $\epsilon$-SOSP. 
strengths_and_weaknesses: Originality: This work is a novel combination of zero-th order algorithms with NSF algorithms. The related work looks adequate and clear to me. 
	
Quality: The submission is a complete work. The claims are well supported by theorems and experiments. I did not find out where limitations of this work are explicitly mentioned. 
	
Clarity: The introduction is clearly written and well organized. There are many unclear points about algorithms and theorems as shown in my questions. 
	
Significance: The results are important since it demonstrates that the proposed zero-th order algorithms can escape saddle point faster than the previous zero-th order algorithms. 
questions: (1) (Important) Line 5 of Algorithm 4 and Line 4 of Algorithm 7 use $\|\nabla f(x_t)\|\ge\frac{\epsilon}{2}$ while line 4 of Algorithm 5 uses $\|\widehat{\nabla}_{coord}f(x_t)\|\ge\frac{3\epsilon}{4}$, why do they differ? Due to proposition 1, I think you mean CoordGradEst can verify whether $\|\nabla f(x_t)\|\ge\frac{\epsilon}{2}$ with probability $1-p$, so we can always use CoordGradEst as in line 4 of Algorithm 5, yes? If not, the computation of the full gradient $\nabla f(x_t)$ in Algorithm 4 and 7 involves $n$ function queries and thus the complexity should involve $n$, which seems to eliminate the advantage of SGD for large $n$. 
	
(2) (Important) Your Theorems 3 and 4 have probability at least $1-p$. Could you also guarantee that for Theorems 5 and 6 which only have probability at least 2/3 and 3/4 respectively? (e.g. maybe by repeating algorithms multiple times or changing hyper-parameters) How will you accordingly adjust complexity? This is to guarantee that the complexity comparison is fair. 

(3) (important) The checklist said you have listed limitations. Where are they? 

(4) In the research question in line 87, should not we focus on query complexity instead of iteration complexity? 

(5) Line 130 said "Central Difference vs. Forward Difference (please refer to 131 Appendix B.1)", where is such Appendix B.1? 

(6) Will the small $\mu$ in the denominator cause numerical error? If so, How to avoid that?

(7) I did not fully understand your Algorithms 1 and 2 until I read Theorem 1. I think it better to make the big picture more clear at the beginning of Section 3. For example, you might first describe the goal of NCF problem: to find the the negative curvature direction $v$ at point $x_0$ defined as $v^{\top}\nabla^2 f(x_0)v\le ??$ such that when $x$ is a nearly saddle point, going along this direction $v$ will escape saddle point $x$. Is my understanding correct? Also, do your Algorithms 1 and 2 differ from [4] only in that you use $\mathcal{H}_f(x)v$ instead of $\nabla f(x+v)-\nabla f(x)$ in [4]? You might make this more clear in the paper. 

(8) In line 168, "Note that, although the error bound is poor by ... up to $\mathcal{O}(r^2)$". This sentence seems incomplete since the whole sentence lies in "although". For example, do you mean "although ..., our algorithm only requires function values while [4] requires both function values and gradient values."? Also, it is better to use "poorer" than "poor".
	
(9) In line 6 of Algorithm 2, you might use $\sum_{k=1}^m$ and $f_{i_k}$ to differentiate from $j$ in $z_j$.
	
(10) In line 196, $\lambda_i(M)=-\frac{1}{\ell}\lambda_i\big[\nabla^2 f(x_0)\big]+\big(1-\frac{3\delta}{4\ell}\big)\in [-1,1]$ implies $\lambda_i\big[\nabla^2 f(x_0)\big]\in \big[-\frac{3\delta}{4},2\ell-\frac{3\delta}{4}\big]$, yes?
		
(11) The intuition of Algorithm 3 looks unclear to me. For example, does $T_t(M)\xi$ correspond to $y_t$? How does $x_{t+1}=x_0+y_{t+1}-\mathcal{M}(y_t)$ in line 215 correspond to line 7 of algorithm 3? Also, why not directly applying Algorithms 1 and 2 to the deterministic case ($n=1$) by replacing $\mathcal{H}_{f_i}$ with $\mathcal{H}_f$?  

(12) In Algorithms 4 and 5, the two options can be moved to inside "if" since we do not need to compute them when "else" holds. 

(13) In Proposition 1, does $\mathcal{O}\left(\left(\frac{128 \sigma^{2}}{\epsilon^{2}}+1\right) \log \frac{1}{p}\right)$ mean the batchsize? Also, the statement "$\|\nabla f(x)\|\ge \epsilon/2$ or $\|\nabla f(x)\|\le \epsilon$" always holds. So I wonder: do you actually mean that we can verify whether $\|\nabla f(x)\|\ge \epsilon/2$, and similarly we can verify whether $\|\nabla f(x)\|\le \epsilon$? It is better to make it more clear. 
	
(14) In all the Theorems, do the query complexities mean the number of queries for $f(x)$, or for $f_i(x)$? 
	
(15) Line 3 of Algorithm 7 can be moved into "if $\|\nabla f(x_t)\|\ge \frac{\epsilon}{2}$" since we do not need to compute ZO-SCSG when "else" holds. Also, I think it will be more concise if you remove "for $j=1,...,T$ do" in Algorithm 6 since we only need to run it for 1 epoch. 
 	
(16) You might briefly introduce what is SCSG and SPIDER at the beginning of Sections 4.2 and 4.3. For example, you might say they are variance reduction techniques for non-convex finite-sum problems, and SPIDER has the near-optimal sample complexity, etc. 
 	
(17) In Algorithm 8, line 3 can be moved into "if $w_1\neq \bot$". 

(18) What novel analysis techniques are used in your proof?
limitations: The checklist said you have listed limitations. I did not find them.
review_title: null

Meta-review: metareview: This paper designs new algorithms for finding second order stationary points using only function value queries (0th order information). The main novelty is in designing two approaches for negative curvature finding. The new subroutines can be used in a wide range of algorithms for finding second order stationary points (most using first order information) and result in new 0th order algorithms with reasonable guarantees. The reviewers had some concerns but most are addressed in the response. In general the reviewers agree that this is a solid contribution to nonconvex optimization.
confidence: Certain
Decision: Accept