Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper shows convergence to an ε-second-order stationary point for zeroth-order methods. They substantially improve existing bounds, achieving ε^-7/4 dependence on ε and quasi-linear dependence on problem dimension. They present two algorithms: the first algorithm and its analysis are based on the Jin et al’18. The second algorithm, based on the Hessian-vector product idea, substantially improves the logarithmic factors. One of the main component in their analysis is better estimation of discrepancy between the true gradient and its approximation, based on the Lipschitz Hessian property.


strength_and_weaknesses: My main concern about the paper is the lack of explanations:
-- The algorithms should be explained in more details. I’m familiar with Jin et al’18, so I had a good idea what happens in Algorithms 1 and 2. However, while I could parse Algorithm 3, I can’t say I understood what happens there.
-- Similarly, it would be great to explain the choice of parameters (I mean, why their values make sense), especially μ in Theorem 1.
-- Proof outline for Section 3 should be added.

clarity,_quality,_novelty_and_reproducibility: Minor issues:
-- The title of Table 1 should be changed
-- Page 6: “Hessian-vector product estimator in 3.” -> “Equation (3)”.

summary_of_the_review: Solid paper, accept.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work proposes two zeroth-order Nesterov’s accelerated gradient descent based algorithms that can escape saddle points and converge to second order stationary points. The main idea of the work is to use the central finite difference gradient estimator to approximate the gradient. The theoretical results show that the proposed can converge to second-order stationary points with fewer function queries. 

strength_and_weaknesses: Strength 

Overall, the paper is well written and the related work are well cited. The introduction is clearly organized. The derived convergence results match the state-of-the-art one and are faster than previous zeroth-order algorithms for escaping saddle points. Numerical results illustrate the effectiveness of the proposed algorithms.

Weaknesses

1. Since the work focused only on the deterministic optimization, this may restrict the application scenarios of the algorithm. It'd be nice if the authors have further insights for stochastic  optimization as well.

2. The algorithms use $\mathcal{O}(d)$ function evaluations per iteration to enable a high accuracy approximation of the gradient,  which may also not
be practical in realistic applications when the dimension of the problem is large. I wonder if such a gradient estimator is necessary?

3. Since the algorithms are similar to the Jin et al. and Zhang et al., it would be helpful to explain what novel theoretical analysis techniques are used in this work.

4. In theoretical results, the value of parameter $\mu$ is set to be very small, is it the same in the experiment? Since in practice, too mall $\mu$ may cause system error. It would be better for the authors to explain how to choose the parameter u in the experiment.

5. Minor issues:

it seems that $\mathcal{H}_f$ only appear in section 2.4, where is it used?

Algorithm 2 is from Jin et al. 2018, you should add a cite here or delete it and add a footnote.
clarity,_quality,_novelty_and_reproducibility: This paper is well-written, and the techniques are effective and well-supported by the empirical results.
summary_of_the_review: Overall, this is a good paper, and I would recommend an "accept".
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors provide to their knowledge the first two variants of Nesterov's accelerated gradient-free algorithms for escaping saddle points of minimization problem, with comparable convergence rate to their first-order counterparts and smaller oracle complexity compared to prior derivative-free methods for finding second-order stationary points.

strength_and_weaknesses: Pros: This paper studies a significant novel research problem. Theorems and experiments look solid. The presentation looks generally clear, brief and neat. 

Cons: There are some points that need to be clarified, especially those about complexity results, See "Clarity, Quality, Novelty And Reproducibility" for detail. 
clarity,_quality,_novelty_and_reproducibility: Clarity: The contribution looks clear and brief. This paper is generally clear and well organized. Some points need to be clarified as shown below.

(1) What do $c$ and $\Delta_f$ mean at the end of page 4? Though $\Delta_f$ is defined in Theorem 1, it is better to define it at its first appearance. 

(2) At the beginning of Lemma 6, should the second $\widehat{\nabla} f(\mathbf{x}_t)$ be $\nabla f(\mathbf{x}_t)$? 

(3) Just double check, Do Lemmas 3-5 hold almost surely instead of high probability? 

(4) In Theorem 1, by "one of the iterates will be an $\epsilon$-approximate SOSP", do you mean $\mathbf{x}_t$ or $\mathbf{y}_t$? The lemmas seems to imply $\mathbf{x}_t$ but it is better to clarify it in Theorems 1 and 2. 

(5) In Lemma 7, $\lambda_{\min}(\nabla^2 f(\mathbf{x}_t))\le ??$.

(6) In Algorithms 1 and 3, variables like $\mathbf{x}_t$, $\tilde{\mathbf{x}}$ have been assigned multiple times. Is it better to use $\leftarrow$ instead of $=$ for such variables, which includes all the assignment statements in Algorithms 1 and 3? 

Also, do $\mathbf{x}_t$ in Theorem 1 and Lemmas 3-6 refer to its value right after implementing line 4, 6 or 9 of Algorithm 1? Similar issue exists in Section 3.2. You may clarify it in these Lemmas and theorms, or add variables such that each variable is assigned only once?

(7) In Line 15 of Algorithm 3, should the first $\tilde{\mathbf{x}}$ be $(\tilde{\mathbf{x}}, \tilde{\mathbf{x}})$ to match dimensionality? 

(8) In Theorem 2, you could substitute the value of $\delta_0$ into the complexity, since $\delta_0$ relies on $\epsilon, \delta, \rho$. 

(9) The complexities in Theorems 1 and 2 match oracle complexity in the abstract, but the iteration complexity is not found in the theorems. Could you add them? Also, you may say "The total number of function queries (oracle complexity)" in the theorems to be consistent with abstract.

(10) I did not find out the complexity value expressed in $\mathcal{O}$ in the proof of Theorem 1. In the proof of Theorem 2, $T=\widetilde{O}\big(\frac{\Delta_f}{\epsilon^{1.75}}\log d\big)$ does not match the complexity in Theorem 2. Could you explain that? Usually when proving complexity, it is recommended to express the complexity in terms of hyperparameters and then substitute the hyperparameter values. 


Quality: 

This work is complete and generally solid. However, the claim in the abstract that "our methods achieve a comparable convergence rate to their first-order counterparts and have fewer oracle complexity compared to prior derivative-free methods for finding second-order stationary points." is not well supported, unless you compare all these complexities in terms of $\mathcal{O}$, either in the introduction or after Theorems 1 and 2. 

In the experiment, why is RSPI not implemented in Figure 1? 


Novelty:  This work gives positive answer to a novel research problem: can Nesterov's momentum accelerate the convergence of gradient-free methods for finding second-order stationary point? 


Reproducibility: To ensure reproducibility of the experiments, it is better to tell the values used for all the inputs (hyperparameter choices). For example, what are the candidate values in the coarse grid search for $\ell$ and $\rho$? 

Minor comments: 

(1) In the abstract, I think "smaller oracle complexity" is better than "fewer oracle complexity". 

(2) At the beginning of Section 3.1, use "three parts" instead of "three part". 

(3) Use bolded $\mathbf{x}_t$ in line 5 of Algorithm 1.

(4) Line 8-9 of Algorithm 1 could be moved to right before line 6. 

(5) In and right after Lemma 3, you could use "eq. (6)" instead of "(6)". This also applies to equation citations elsewhere.

(6) You could use big { } in Lemma 4. Similarly, use big ( ) on the left side of the centered equation in Lemma 8. 

(7) In Theorem 1 and 2, "query" could be changed into "queries". 

(8) A typo in Theorem 2: "set set".

(9) You could also cite 
Zhang, H., Xiong, H., & Gu, B. (2022). Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients. arXiv preprint arXiv:2210.01496.
summary_of_the_review: Based on "Strength And Weaknesses" above, I recommend borderline accept for this paper. After my major concerns above about the complexities are solved by the authors, I would like to raise my rating.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of escaping from saddle points, a basic problem in nonconvex optimization. Specifically, this paper considers function evaluations, i.e., zero-order inputs, and is able to give algorithms with ~O(1/eps^1.75) iteration complexity and ~O(d/eps^1.75) query complexity. Although this 1/eps^1.75 dependence has been achieved by gradient-descent based methods, this paper is first one to achieve the same dependence for gradient-free methods. Finally, numerical experiments are conducted to corroborate the theory results.
strength_and_weaknesses: From my perspective, this paper has the following strengths:

- This is the first work which gives zeroth-order methods for escaping saddle points with matching eps dependence compared to first-order methods. This is a great contribution to me and significantly improves our understanding of zeroth-order methods.

- Two algorithms are proposed to achieve the result of ~O(1/eps^1.75) iteration complexity and ~O(d/eps^1.75) query complexity. The second one based on negative curvature finding only has one logarithmic term in d.
 
- The theory results are corroborated by numerical experiments on two instances: cubic regularization and quartic functions. Codes are also provided in the supplementary material.

Nevertheless, the paper may still have space to improve from the following aspects:

- It would be very helpful if the authors can illustrate more on the practical cases where both escaping from saddle points is a vital problem and we have to use zeroth-order methods instead of first-order methods. In the introduction, the authors mentioned the situations where the calculation of explicit gradients is expensive or even infeasible, such as black-box adversarial attack on deep neural networks. This is still a bit vague to me; would be helpful to explain how we have the function evaluation access in such problems.

- The writing in this paper is a bit sloppy in general and has space to further polish. From a relatively superficial reading, I can already spot the following glitches:

- - Second paragraph in Page 1: non-convex problem 1 -> non-convex problem (1). This also applies to a few following places.

- - Third paragraph in Page 1: O(1/eps^2) -> Theta(1/eps^2) (Here, the authors are talking about the optimality of gradient descent, so a lower bound or tight bound should be reflected here.)

- - Second half of Page 2: proposed a first-order Negative curvature finding framework -> … negative (should be small letter instead of capital letter here)

- - End of Page 2: with fewer function query complexity -> with smaller function query complexity, or with fewer function queries

- - Beginning of Page 3, second bullet point in contributions: Due to the efficiency of the negative curvature finding for finding the most negative curvature direction near a saddle. We further study -> …, we further study (currently, the first sentence is not complete)

- - Beginning of Page 4: By the property Hessian Lipschitz -> By the Hessian-Lipschitz property 

- - Middle of Page 5: The second part of the Algorithm 1 is the Nesterov’s accelerated gradient descent steps with its gradients estimated by 2 -> … with its gradients estimated by Eq. (2) (otherwise it reads like the gradient is estimated by the value 2)

- - Page 5, after Eq. (6): Specifically, when 6 doesn’t hold -> Specifically, when Eq. (6) does not hold (in formal English writing, abbreviations are supposed to be open). Same change shall be applied to the statement of Lemma 3: when 6 does not holds -> when Eq. (6) does not hold

In addition, I also have a couple of questions for the authors:

- It would be helpful to give detailed comparison between Algorithm 1 and Algorithm 3. Algorithm 1 gives slightly worse query complexity results (extra poly-log d overhead); so why is this of general interest over Algorithm 3?

- In Eq. (2) in Section 2.3, a central difference coordinate-wise gradient estimator is applied. In fact, in numerical analysis, higher-order central difference formulae have been studied, see for instance Li https://www.sciencedirect.com/science/article/pii/S0377042704006454?via%3Dihub It would be of general interest to discuss whether using a higher-order central difference formula could further improve the results.
clarity,_quality,_novelty_and_reproducibility: From my perspective, the clarity and quality of this paper is in general good, though the paper still has space to improve as I mentioned above. Novelty is excellent -- this is the first paper proving the 1/eps^1.75 convergence rate for escaping from saddle points using zeroth-order methods, matching that of first-order methods. Reproducibility is also excellent -- theoretical results are stated with detailed proofs and the numerical experiments are provided with codes and detailed explanations.
summary_of_the_review: Overall, I think this is a novel and outstanding work in studying zeroth-order methods for escaping from saddle points, and I’m happy to recommend acceptance for ICLR 2023. Nevertheless, the paper still has space to improve as mentioned above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper gives efficient gradient free algorithms for finding approximate second order stationary points. The running time and query complexity bounds are very strong and they significantly improved over previous results. The proof technique is also novel and interesting. Reviewers agreed that this is a strong result, with some suggestions on clarify and presentation. The author response has addressed most of the concerns. Overall this is a solid result in nonconvex optimization.
justification_for_why_not_higher_score: It's somewhere between a spotlight and oral, I'm not sure which way it should go.
justification_for_why_not_lower_score: The paper gets almost tight guarantees for gradient free nonconvex optimization I think it deserves at least a spotlight.
Decision: Accept: notable-top-25%