Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper provides a convergence analysis of a class of prior-guided zeroth-order (ZO) optimization algorithms and gives a prior-guided variant of the accelerated random search (ARS) algorithm. 
Contribution:
1. Provides a complete convergence on some prior-guided zeroth-order optimization algorithms.
2. Provides a prior-guided variant of the ARS algorithm.
main_review: Strengths:
1. The presentation of the convergence analysis is very nice, very well-written, and easy to follow. It is shown through the analysis that a good prior is one with a larger correlation with the gradient which is intuitively true.
2. The prior-guided ARS is a good addition to the class of prior-guided ZO algorithms. In addition, the new algorithm performs well on some convex functions.

Weaknesses:
1. It seems the analysis is just writing down traditional analysis of ZO algorithms with some quantities waiting to be instantiated to specific forms for different algorithms. I do not really see any unexpected new insights distilled from the analysis.
2. The proposed prior-guided ARS seems does not to perform well on black-bok attacks which is a key application to ZO algorithms in machine learning. This limited the impact of the paper.


limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the performance of zeroth order optimization algorithms where gradient estimation uses prior information. They provide a bound on the convergence analysis for such prior guided algorithms in terms of expected alignment of the gradient estimates to the true gradient. They use this framework to study historical priors and show that such a prior may counter the effects of using a sub-optimal learning rate. They also provide a new accelerated random search algorithm that incorporates prior information. 
main_review: This paper studies an important and interesting problem. Their insights into the performance of the historical prior are useful. The paper is clearly written and well organized. 
My concerns with this paper are as follows:
- the difference between the bounds in the convex and strongly convex case are not well highlighted or discussed. Moreover, zeroth order algorithms are not typically applied to only convex functions so some discussion on possible extensions or the difficulty of should be included in this work. 
- while the bounds are used to study historical priors, it would benefit to work to either study other examples of priors or to demonstrate why their bounds in terms of the expected correlation between the prior and the true gradient are useful for other priors. Can we expect that such bounds are easy to compute for other priors? 
limitations_and_societal_impact: The paper does address the limitation of using the directional gradient oracle.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies the problem of zeroth-order optimization in a deterministic setting, where the exact function values at each point can be observed but the gradient of the function is not accessible. The main approach for solving such problems is first to estimate the gradient of the function and then apply a gradient method by plugging in this estimator instead of the gradient. The main goal of this work is to provide convergence guarantee for prior guided zeroth order algorithms.

Assumptions on the objective function: The objective function is (strongly) convex and smooth.

Approach: Since the paper assumes a deterministic setting, at each step by two function evaluations and choosing a small enough perturbation term, roughly they can observe the gradient of the function towards any arbitrary direction (page 3, equation 1). Also, they assume that at each step they can observe $q$ random directions of the gradient, which are given priorly (or they estimate them by $2q$ additional function evaluations). Then, they take advantage of these $q$ given directions and $g_{I}$s to construct $g_t$, where $g_t$ is the gradient estimator at step $t$, and $I<t$. 

Contributions: Their results in Theorems 3 and 4 outline the convergence guarantees and robustness to the learning rate.
main_review: Before the authors' responses, some parts were not clear to me. They provide useful justification and clear the misunderstanding. I edited the review and raised my score. 

1. Theoretical claims are well supported. 
2. The technical aspects are well written. Also, in the appendix, they tried to cover the most general cases, which was quite nice.
3. I encourage the authors to discuss the computational cost of Gram-Schmidt procedure diagonalization.
4. Their results provide intuition about the practical success of History based algorithms and outline the robustness of History-PRGF against the choices of learning rate. 
5. The authors also provide convergence analysis for an accelerated greedy method, which is outlined in Theorem 5. 
limitations_and_societal_impact: The authors briefly discuss the limitations of their work. I also pointed out some, in the Main Review section.

Since the paper is quite technical, I except no direct social impact at this point.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work analyzes the convergence rates of several existing prior guided zero order optimization methods. The zero order methods studied use statistical methods to provide an estimate of the function gradient using only function evaluations. This works studies the trade offs between gradient estimation accuracy and function evaluations as well as the effect of learning rate selection for the various estimates. This work also proposes a prior guided version of accelerated random search and studies its convergence. All algorithms studied are then numerically compared on benchmark functions as well as black box adversarial attacks. 
main_review: The authors here focus on the effects of history dependent gradient estimates on zero order optimization.  The setting studied here is challenging because gradient estimates themselves are not statistically independent. This requires significant modifications to the standard convergence arguments and to the derived bounds that the authors clearly explain.  To the best of my knowledge, the technical arguments used here are novel.

The authors also try to explain the empirical success of history based gradient estimators. The authors prove that convergence can be accelerated by using previous gradient information when a suboptimal learning rate is used, which is in agreement with past empirical findings. I found this insight very helpful and relevant given that learning rate selection remains more art than science even for first order methods. 

Finally, the analysis of the prior guided version of Accelerated Random Search method requires  even more work as additional quantities beyond directional derivatives need to be estimated. The experiments showcase that the prior guided algorithms can be more efficient than their simpler counterparts. I believe that this work both explains the success of existing works but can also have standalone theoretical and practical impact.

I acknowledge the authors' responses to all reviewers. I believe the additions proposed by the authors will make the submission stronger so I continue to be in favor of accepting this submission.
limitations_and_societal_impact: Limitations and negative social impact are adequately discussed.
review_title: null

Meta-review: While there were some initial concerns from the reviewers, these were all clearly resolved following the author rebuttal, with the reviewers in question acknowledging the depth and clarity of the responses.  The reviewers are now in agreement that this paper is a valuable addition to the literature on zero-order optimization, and is suitable for publication at NeurIPS.  I do not have any specific reviewer points to highlight here, but I do ask that the authors carefully consider all of the reviewer comments when forming the camera-ready version.
Decision: Accept (Poster)