Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors provide a best-iterate convergence rate for a zeroth-order optimization with constant number of function evaluations per iteration which can escape saddle points efficiently in order to compute a second-order stationary point. 
strength_and_weaknesses: In order to understand if the model is really interesting, I would like to ask a model where waiting to get d samples can not be done and it is crucial to have some small progress at every round because it improves some regret quantity. Additionally, the authors claimed that adding constantly isotropic noise instead of sporadically is better, because the algorithm of Flokas et al (the optimal one in combination iteration x samples) has to check the gradient if it is small. This is wrong, by looking the referred algorithm, it examines the ''approximate gradient'', which will be used for the descent (so we have access to that for free).

I am wondering, if the authors start to add a noise adaptive, if they will achieve better rate of convergence.
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well-written as far as the maths BUT I strongly believe that the authors should add prelude paragraphs in the appendices to keep intuitions. Giving repetitively examples before or after the statements would only benefit the algorithm.

Quality: It involves technical machinery well established last decade in non-convex optimization. The probabilistic machinery had some independent interest

Novelty: In my opinion, the most interesting tool is the derivation of a potential which includes the constant addition of noise in such a detailed form. It is indeed interesting the ability to have even some non-negligible progress with constant number of samples per round. (However, I am not convinced that this is the case...Can the authors elaborate more about that?)
summary_of_the_review: My honest goal is to observe the discussion, since I am not convinced about the importance of the model.
To be more precise, why someone should not just wait to get d estimates to approximate grad with finite differences, since the final iterations \times samples = complexity would be the same, or even better
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the zeroth-order optimization of black-box functions. Due to the unavailability of gradients, gradient estimations are used. The paper proposes an algorithm as follows: at each iteration, it uses only $2m$, where $1 \le m \le d$ and $d$ is the input dimension, to approximate gradients. Then it adds an isotropic perturbation to the gradient estimate in order to escape from saddle points. The authors show that their algorithm can find $\epsilon$ second-order stationary points using only $tidle{\mathcal O} (d\/epsilon^2.5)$ function evaluations. The idea of their convergence analysis is based on that of Jin et al. (2019a) with non-trivial modifications. If the gradient estimate is large, they show that the function can decrease even with only $2m$ evaluations at every iteration. If the current point is near saddle points, they show that there is a constant probability of making the function value decrease.    


strength_and_weaknesses: Strengths:
- The paper addresses an important problem of the zeroth-order optimization. 
- The theoretical results are novel and interesting: even with 2 samples to estimate the gradient instead of $d$ samples as in existing works, we still find the $\epsilon$ second-order stationary points after $tidle{\mathcal O} (d\/epsilon^2.5)$ function evaluations. This result is valuable for the high-dimensional optimization problem.
- The approach is based on existing works but provides some new techniques.

Weaknesses:
- Although the number of evaluations to estimate gradient is reduced from $\mathcal O(d)$ to $2m$, however, the number of evaluations for convergence guarantees increases compared to existing works. Overall, it seems that their work has no progress compared to existing works. Therefore, the parameter $m$ can be considered as a trading coefficient between the number of samples to estimate gradients and the performance of the optimization. 
- The paper is so long to estimate. I've checked some proof for the case when the gradient is large, but could not check all proofs.  
 
clarity,_quality,_novelty_and_reproducibility: The paper is well written. The techniques used in this paper can be valuable. 
summary_of_the_review: I am toward accepting this paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this manuscript, the authors generalize the well-known idea of adding perturbation to avoid converging to the saddle points in nonconvex optimization, to the zeroth-order setting in which only function evaluations are available. They also provide convergence analysis of their zeroth-order perturbed gradient method and show that to finding an $\epsilon$ second-order stationary point, it requires at most ${\cal O}(d/\epsilon^{2.5})$ number of function evaluations.
strength_and_weaknesses: It's interesting to provide analysis of zeroth-order methods in escaping from the saddle points without estimating the Hessian matrix. However, as mentioned in the manuscript, this problem has been already studied in the literature and a sample complexity of ${\cal O}(d/\epsilon^{2})$ has been provided. The authors argue that the major limitation of obtaining this complexity bound is to compute ${\cal \Omega }(d)$ per iteration. However, this is not very convincing and the proposed complexity bound in this manuscript is worse than that of the existing methods. 
clarity,_quality,_novelty_and_reproducibility: The problem is not new in the literature and the complexity results in this manuscript is new only in a limited setting. Moreover, the authors have only founded on the deterministic case. 
summary_of_the_review: The results are new only in a limited regime and the existing results outperform the presented ones in the manuscript in most settings.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes zeroth-order perturbed gradient descent algorithm which is the first zeroth order algorithm to the authors' knowledge that finds second-order stationary point with only $2m$ function evaluations per iteration for any $m\in [1,d]$ ($d$ is the dimensionality), in contrast to $\Omega(d)$ per iteration in previous similar algorithms. The total number of function evaluations is $\widetilde{\mathcal{O}}(d\epsilon^{-2.5})$. New proof techniques are used to deal with small batchsize $2m$ and large variance without subGaussianity assumption. 
strength_and_weaknesses: Pros: Both the achievement in $2m$ function evaluations per iteration and the techniques to deal with small batchsize $2m$ and large variance without subGaussianity assumption look novel. The overall structure and main contribution of this paper look very clear. 

Cons: The advantage of the proposed algorithm is not well supported as I elaborated in "**(my major concern)**" below. The proof intuition could be more direct and brief before diving into technical details, as I elaborated in "**(my second major concern)**" below. 
clarity,_quality,_novelty_and_reproducibility: **Clarity:**

The overall structure and main contribution of this paper look very clear. 

**(My second major concern)** I scanned Section 3 and felt it very hard to fully understand the intuition. I believe that the technique is novel and correct, and that the authors have devoted much time and energy to outline the proof intuition. Is it possible to write 1-2 paragraphs at the beginning of Sections 3.1 and 3.2 to briefly sketch the proof with no equation or only a few core equations, so that we can more easily understand how the function value decrease OR $||\nabla f(x_t)||$, $\lambda_{\min}[\nabla^2 f(x_t)]$ are bounded for large and small gradients? I think that's perhaps not easy but worth trying. 

Also, what is $\tau'$ in Lemma 1? It's recommended to define each new notion and notation at its first appearance. 

The citation of [1] misses "In Advances in neural information processing systems". 

[1] Vlatakis-Gkaragkounis, E. V., Flokas, L., and Piliouras, G. (2019). Efficiently avoiding saddle points with zero order methods: No gradients required. In Advances in neural information processing systems, 32.

**Quality:**

**(My major concern)** The advantage of the proposed algorithm in only $2m$ (batchsize) function evaluations per iteration is theoretically proved. I think this is probably a practical advantage. However, practical advantage needs to be supported by experiments. Also, the authors acknowledged the larger dependence of their total number of function evaluations on $\epsilon$ than that in [1], which further theoretically undermines the advantage of the proposed algorithm, since the total number of function evaluations is more important in the overall efficiency. To well support the advantage, I suggest to do **either of the following two**.

(1) Add experiments to compare with at least the zeroth order algorithms that find second-order stationary points, in terms of CPU time or total number of function evaluations. Hopefully the proposed algorithm can outperform in most cases. 

(2) Improve the proof to reduce the total number of function evaluations to at most that of [1]. You might carefully compare your proof with [1] to see where the additional $\epsilon^{-0.5}$ is imported. 

Also, what is your advantage compared with [2]? You could cite [2]. 

[2] Zhang, H., Xiong, H. and Gu, B. (2022). Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients. ArXiv:2210.01496.


**Novelty:**

Both the achievement in $2m$ function evaluations per iteration and the techniques to deal with small batchsize $2m$ and large variance without subGaussianity assumption look novel. 


**Reproducibility:**

Not applicable as there is no experiment. 


**Minor comments:**

(1) In the second paragraph of Introduction, you might say "several earlier works on stochastic gradient methods (Jin et al., 2017; 2018)" to correspond to "stochastic gradient methods" at the beginning of the third paragraph. 

(2) In Lemma 3, should $j\ne 2$ be $j\ge 2$? 
summary_of_the_review: Both the achievement in $2m$ function evaluations per iteration and the techniques to deal with small batchsize $2m$ and large variance without subGaussianity assumption look novel. The overall structure and main contribution of this paper look very clear. However, since the advantage of the proposed algorithm is not well supported, as I elaborated in "**(my major concern)**" above, I recommend borderline rejection. I would like to raise my rating if the authors can solve my major concern by either adding experiment or improving the total complexity as I elaborated in "**(my major concern)**" above.
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., zeroth-order inputs, and furthermore only 2m function evaluations are allowed in each iteration. Under such a setting, the authors give an algorithm with iteration complexity ~O(d/eps^2.5*m). 
strength_and_weaknesses: From my perspective, the most notable strength of this paper is that it is the first work on escaping from saddle points that can use fewer than d evaluation queries in each iteration. This is very much novel because first-order methods and previous zeroth-order methods essentially all use (approximate) gradient information, and it is impressive that escaping saddle points can be achieved by using few than d evaluation queries. It’s also veery nice that there is an explicit relationship between the number of function evaluations per iteration and the overall iteration complexity, expressed by m.

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

- I feel that the authors should probably give more explanations about why the current method can only achieve 1/eps^2.5 in terms of eps, and why it cannot reach 1/eps^2 (GD) or 1/eps^1.75 (AGD) at the moment. In particular, discussions about how this 2.5 is formed and the difference compared to those exponents in GD-based methods will be very helpful. Is it mainly due to having difficulty in the large-gradient scenario or when we are near saddle points (improve or localize)?

- There is no numerical experiment in this paper. I think writing a code for Algorithm 1 should not be difficult since it simply takes Gaussian samples and there is only 2m evaluations in each iteration. The paper would be stronger if there are numerical results that corroborate the theoretical findings.

- A typo throughout the paper: In a few places, zero-order should be zeroth-order (just imagine that we never say one-order but always first-order).

At last, I have a suggestion to the authors: It seems that the authors are mainly treating the 2m evaluations as m batches of two-point evaluations. Is it possible to consider fewer batches but more points in each batch? The observation is that Eq. (1) in Definition 3 is simply a first-order central-difference method. 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 using fewer than d function evaluations for escaping from saddle points using zeroth-order methods. Reproducibility is not applied because this work is purely theoretical.
summary_of_the_review: Overall, I think this is a novel work in studying zeroth-order methods for escaping from saddle points, and it could be nice to see this paper at ICLR 2023. Nevertheless, since the result has relatively large power of 1/eps and numerical experiments are absent, it also makes sense for this work to improve further and save for future conferences/journals.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors use a (batch-based) zero-th order gradient estimates to show avoidance results for non-convex minimization problems. 

The obtained sample complexity is worse than the state-of-the-art and does not involve stochastic gradient estimates though the authors use added isotropic noise as a tool for avoidance. 


justification_for_why_not_higher_score: The work does not improve existing results and uses a batch setting, which is not needed in practice.
Decision: Reject