Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Based Gaussian process, this paper develops a zeroth-order optimization algorithm which requires fewer function queries to estimate the gradient than previous zeroth-order methods. Additionally, a so-called dynamic virtual update schemes is incorporated. Theoretically, the proposed method is shown to obtain gradient with exponentially diminishing error; and the convergence result of the algorithm is attained. Empirical studies with synthesized data and real-world data corroborate the theoretical analysis and demonstrated the superior performance of the presented approach over existing zeroth-order optimization approaches.
strength_and_weaknesses: Strength:
1.	A novel algorithm is developed.
2.	The theoretical analysis is solid--- the bound of the gradient error is given, and the convergence rate is obtained.
3.	Empirical results show the proposed algorithm outperforms previous ones by a substantial margin.
Weaknesses:
1.	Related studies on advanced zeroth-order methods that aim to reduce the gradient error or improve query efficiency are not introduced.

clarity,_quality,_novelty_and_reproducibility: The code to reproduce the numerical results is currently unavailable.
summary_of_the_review: 1.	For different problems, is there any guidance for the selection of confidence threshold c. 
2.	More intuitive explanations on why the gradient error decreases at exponential rate are expected.
The code to reproduce the numerical results is currently unavailable.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a zeroth order method that reduces the number of queries made as compared to methods that use finite difference to estimate the gradient. The authors propose using Gaussian Processes to estimate the trajectory of observations, thus giving them access to the gradient at any given point. Given the assumption that the underlying blackbox function is sampled from a gaussian process, the authors prove convergence by showing that the gradient estimation error is non-increasing as the number of queries go up.
strength_and_weaknesses: Strengths

- Clear writing 
- Simple proposed approach

Weaknesses

-  Might have limited novelty 
clarity,_quality,_novelty_and_reproducibility: The paper is clear to read, high in quality, fairly novel, and reproducible.
summary_of_the_review: The paper is clearly written, nicely motivated and well structured. My main concern/question is around the assumption that f is sampled from a GP. How restrictive is this assumption in general? It seems like most heavy lifting in terms of providing a benefit over prior work is due to this assumption, while the algorithm itself is not entirely novel. Would this be an accurate understanding? Can the authors comment a bit more on this? Since the topic is quite far from my area of expertise, I am unable to provide more critical feedback than the above. Having said that, I think the paper makes a solid contribution and the paper is well drafted. Hence, I am leaning towards acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the zeroth-order optimization where the gradient information is infeasible or very expensive to access, and only function values are available. Different from most one or two-point zeroth-order estimation, this paper assumes the function f is sampled from Gaussian process as in Bayesian optimization literature and then develops a trajectory-based zeroth-order method with some posterior information such as mean and covariance functions (both of which are constructed using previous trajectory information). Some error analysis of gradient estimator and convergence of the proposed algorithm are also provided. In experiments, they show that the proposed method admits a better gradient estimation and is more query efficient, compared to some zeroth-order and Bayesian optimization methods. 
strength_and_weaknesses: Pros:

1. Zeroth-order optimization has become an important topic as in many new applications such as adversarial learning, hyperparameter optimization of black-box or complex systems. This paper provides an interesting solution motivated by Bayesian optimization.

2. The presentation is overall good. The proposed method admits feasible mean and covariance function information due to the Gaussian process assumption, which is useful to make the design flexible, e.g., including the so-called virtual updates to improve the query efficiency. The idea is simple and intuitive. 

Cons:

1. The comparison to existing two-point or one-point finite-difference (FD) zeroth-order estimation is not fair, because the proposed method relies on a Gaussian process assumption, whereas existing FD types of methods do not. In my opinion, the authors should provide a more detailed comparison to existing Bayesian optimization based methods, which, however, seems to be quite missing in the current writing. Correct me if I miss anything for the reading. 

2. There are no sufficient algorithmic and theoretical comparison to GP or Bayesian optimization based methods. Only some are found at the end of the appendix. Therefore, the technical novelty of this work is not that clear to me. For example, what is the algorithmic difference compared to existing GP or Bayesian optimization methods? What is the theoretical challenges compared to such studies? Are there any new developments that cannot be handled by existing analysis? These points so far are not that clear to me. In terms of the theoretical analysis (e.g., Theorem 3), is this the first convergence result for GP based optimizer? How does this bound compare to existing GP-based algorithms? What is the best possible tradeoff achieved by $V$ even in this worst-case analysis? It seems Theorem 3 may not be easy to convey this due to the complicated form. 

3. More experiments on the comparison to GP or Bayesian optimization based approaches should be provided. For example, for the non-differentiable metric optimization experiment, why no GP or Bayesian optimization algorithms are included for comparison? 

clarity,_quality,_novelty_and_reproducibility: The quality of this work is overall good, but the clarity and originality need to be improved. 
summary_of_the_review: Overall, I like the approach and the idea of using GP to the zeroth-order optimization, which enables to explore more trajectory-based information to accelerate the convergence. The algorithms seem to be effective in the experiments.  However, the technical and algorithmic novelty is not clear to me. I tend to marginally reject this work, but I am very willing to adjust my score based on other reviewers' comments and the authors' response.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work considers zero-th order optimization through a finite-difference approximation of the gradient. Different from prior works, a technique to incorporate function query history to boost the algorithm performance. Theoretical and experimental analysis confirm the merits of the proposed technique.

The strength of the work is in reducing the number of function queries required to achieve a given sub-optimality, which are established through some interesting analytical insights.

Drawbacks are in a lack of comparison to bandit algorithms and Bayesian optimization techniques, which operate upon a similar premise.
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Accept: poster