Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents tight, instance dependent upper and lower bounds for certifiable zeroth-order Lipschitz function optimization. It was known from prior work that in 1-d, the optimal sample complexity is nearly proportional to the integral $\int_{\mathcal{X}} \frac{\mathrm{d} x}{\max (f) - f (x) + \epsilon}$.  This paper extends this result to dimension $d$, establishing that the DOO algorithm of Perevozchikov 1990 can be made certifiable, achieving the sample complexity $\int_{\mathcal{X}} \frac{\mathrm{d} x}{(\max (f) - f (x) + \epsilon)^d}$.

The sample complexity bound of this algorithm matches that derived by Bouttier et al (2020) for an algorithm of Piyavskii and Shubert. The bound in Bouttier et al, however is provided in terms of covering numbers of the ground set at different error scales.

The main contribution of this paper is to (i) show that the c.DOO algorithm runs in near linear time and (ii) a sample complexity bound with of the same order as that derived by Bouttier et al (ii) To relate this sample complexity bound to the quantity $\int_{\mathcal{X}} \frac{\mathrm{d} x}{(\max (f) - f (x) + \epsilon)^d}$ (iii) establish a lower bound for certifiable algorithms which matches the upper bound up to an order of $(c( 1 - \text{Lip} (f) / L ))^d$ where $L$ is a known upper bound on the Lipschitz constant of the true function.

The authors also complement these results with a sample complexity upper bound of a constant when $L = \text{Lip}(f)$ (i.e. the Lipschitz constant of the function is known) for $d \ge 2$, which surprisingly does not hold for the case of $d=1$.
main_review: While I think the contribution of the paper is interesting, I think that this result should be advertised less as resolving the open problem of finding the number of sample complexity queries of any optimal algorithm. Indeed it should be made more explicit that: (i) the authors relate the sample complexity bound on the PS algorithm established earlier by Bouttier et al, and (ii) show that the DOO algorithm can be made certifiable. I feel like these points are not established clearly in the abstract. I provide my remaining comments below:

* It should be mentioned that the constants c and C in the upper and lower bounds depend exponentially on d and are not absolute constants.

* Theorem 2 of Bouttier et al (2020) proves that the term $S_C (f,\epsilon)$ is an upper bound to the sample complexity for a different algorithm than the one considered in the paper which is less computationally efficient. It might help to clarify this again in the discussion above eq. (5) / in section 2.

* In the intuition for proposition 2, I find it hard to understand how the learner can *find* two points at which the respective values of f are maximally distant. Even given two such points, the general intuition for this result is not clear to me.

* I find it hard to understand the message in propositions 2 and 3. Shouldn’t the certification problem in, say, 2 dimensions be harder than in 1 dimension? One can always embed a 1-d Lipschitz function into 2-d as: $f_2 ( x ) = f_1 ( \langle x , e_1 \rangle )$.

* Is there any intuition as to what to expect in the case when any of the assumptions such as 2 and 3 are relaxed? Is there a fundamental difficulty in the absence of either of these assumptions?
limitations_and_societal_impact: Yes, I believe the authors have. It might help to include some pointers to questions left open in this work in the conclusion section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the instance-dependent sample complexity for zeroth-order optimization of a Lipschitz function f, with the additional constraint that the algorithm must certify the accuracy of the output. The paper provides nearly matching instance-dependent upper and lower bounds for the setting of perfect (deterministic) observation. 

main_review: Overall, I believe this work is a nice complement to the instance-dependent sample complexity of zeroth-order optimization. The presentation is good with clear upper and lower bounds. My main concerns are summarized as below. 

1. I'm confused about the gap in the dependence of dimension $d$ in the upper and lower bounds. Theorem 3 suggests that the constant $c$ in lower bound is $c'(1-Lip(f)/L)^d$, and claims that the results are direct corollary of Theorem 2 and Proposition 1. However, in theorem 2 the constant $c$ has a extra dependence of $2^{-7d}$, which can be huge when the dimension is large and suggests another mismatch of order $2^{-d}$ in the upper and lower bounds. Is there any other technique applied to mitigate this factor in the lower bound? Otherwise, the authors shall state this gap clearly in the introduction and theorem instead of hiding it in the constant $c'$.

2. Based on the dependence of smoothness in the lower bound in Theorem 2, the adaptivity to all range of smoothness seems to be a natural and important question towards fully instance-dependent optimal bound. It is mentioned in line 89 that 'our lower bound suggests that no adaptivity could be possible for certified algorithm'. This is not clear from Proposition 2 and 3, since Proposition 2 seems to suggest that there exists algorithm that can achieve constant sample size when $f$ is exactly $L$-Lipschitz. Could the author elaborate on this point? 

3. The mismatch between one dimension and high dimension is quite interesting. In Proposition 3, the authors suggest that in one dimension, the term $S_c$ is again a valid lower bound. Does this mean that the problem when we know exactly the smoothness of the function in one dimension can be harder than that in high dimension? Does this also imply that there exists algorithm that is adaptive to smoothness in one dimension? It would be great if some intuitive explanation can be added on why the discrepancy between one dimension and high dimension happens.

Besides the concerns mentioned above, I think understanding exactly the instance-dependent optimal zeroth-order optimization is a good contribution. I'm happy to adjust the points accordingly if my questions are resolved. 


***Update based on the author response:
The authors have resolved most of the questions listed above. Although the exponential gap in dimension is still tricky, I acknowledge that this is an open problem left and this work makes a first step towards understanding the instance-dependent optimal zeroth-order optimization in high dimension. I have adjusted my score accordingly.

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduced the Certified DOO algorithm, which is a zero-order method, to find the maximal point of a Lipschitz function on a compact feasible set. The authors also provided the convergence rate of the Certified DOO algorithm and an instance-dependent lower bound for all certified algorithms. And the lower bound matches the upper bound op to a logarithm term. 
main_review: The paper is well-organized. The authors present the Certified DOO algorithm and the upper bound of sample complexity of the Certified DOO algorithm. And the novel technique, which the authors used to prove an instance-dependent lower bound of certified algorithms, could likely follow up to prove other learning settings.  With noticing that the Certified DOO algorithm is highly dependent on the information of the feasible set, there is a question that I am interested in: can we design algorithms without knowing the information of the feasible set $K$ in advance, i.e., the oracle will return $- \infty$ if $x \notin K$. 

Thanks for the authors' nice response. I would like to keep my ratings for this good paper, 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary:   In this paper, the authors consider the problem of finding global solutions
  to a possibly non-convex optimization problem under possibly non-convex
  constraints using only access to function values of the objective function.
  In particular, they focus on certified algorithms, i.e., algorithm that
  together with a solution they also output certificate of the optimality of the
  solution.

  Their main result is an instance optimal bound for any Lipschitz continuous
  functions. In particular if f is a Lipschitz continuous function with unknown
  Lipschitz constant that is less than L, then the number of zero-order queries
  needed to find an $\epsilon$-approximate global optimum together with a
  certificate of optimality is

  $\sigma = \int_{\mathcal{X}} \frac{1}{(f(x^*) - f(x) + \epsilon)^d} dx$

  where $f(x^*)$ is the value of the global optimum and d is the dimensionality
  of the problem. The authors provide both an algorithm and a lower bound that
  is equal to $\sigma$ up to dimension dependent constants. Surprisingly the fact
  that the Lipschitz constant is not exactly known but only upper bounded is
  crucial for the proof of the lower bound.
main_review: Strengths
  ====================

  - The paper resolves an interesting open question from 1991.

  - The problem of finding global optima with zero-order methods is very
  important in many areas, e.g., in hyperparameter tuning.

  - The techniques developed to prove the results are very interesting.

  - The use of the notion of certified algorithms is a very clever way to be
  able to accurate prove lower bounds for this problem.


  Weaknesses - Comments
  ========================

  1. It would be nice to have some better understanding of the expression of
  \sigma. For example, when the domain is [0, 1]^d, a trivial brute force
  algorithm would need (L/\epsilon)^d steps to get a certified
  \epsilon-approximately optimal solution. How is this bound compared to the
  per-instance optimal bound? It is clear that the per-instance bound is
  smaller but is which cases it is significantly smaller? For example if L is
  O(1) are the two bounds of the same order.

  2. The term "constant" in many lemmas and theorems is misleading. In many
  cases the constants C, c, or c' dependent at least exponentially to the
  dimension d of the problem which is a very important parameter. I understand
  that these constants do not dependent on f and \epsilon but d is an important
  parameter as well and the authors should be more careful when they use the
  term constant that has some dependence on d.

  3. The use of the term "sample complexity" is a bit misleading a believe a
  better wording would be "query complexity".

  4. In lines 244-250 it is mentioned that Assumption 4 is satisfied for many
  natural domain sets. Is it satisfied in general for convex sets X or there is
  a counter-example?

  5. In the proof of Theorem 2 in line 302 the notation K is confusing because K
  has been used so far for the expansion of the tree in the algorithm.

  6. The fact that the exact knowledge of the Lipschitzness is fundamental for
  the lower bound is a bit confusing. It is possible that the exact knowledge
  of the Lipschitz constant can be used to get an improved algorithm for any
  function f?


  Summary of Recommendation
  ======================================
  The results provided in this paper seem to be important and significant and
  for this reason I recommend acceptance.


  Post-Rebuttal
  ======================================
  After reading the authors response and the other reviews I keep my score.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studied the problem of zeroth-order Lipschitz optimization, and mainly showed that under mild geometric assumptions and a noise-free zeroth-order oracle, the sample complexity of finding the \varepsilon-optimal point for a function f is of the order $\int dx/(f(x^\star) - f(x) + \varepsilon)^d$ (up to logarithmic factors). More specifically, the main contributions are as follows: 

1. The authors proposed a certified DOO algorithm which could provide an error certification at each step, and achieves a sample complexity provided by the sum of packing numbers S_C(f,\varepsilon), a quantity already proposed in Bouttier et al. (2020). 

2. Under a mild geometric assumption, the quantity S_C(f,\varepsilon) is bounded by the integral from both above and below, thereby proving the upper bound. 

3. For the instance-dependent lower bound, the authors used a simple perturbation idea to reduce to a proper packing number: if the packing number of some shell is too large, then there must be points not queried by the algorithm, and a local perturbation of the functions around the non-queried points made the certification break down. 
main_review: Overall this is a nice paper and I enjoyed reading it. This paper provides a complete characterization for the instance-dependent complexity of zeroth-order Lipschitz optimization, solving a long-standing conjecture for over 30 years. 

If I have to list some weaknesses, perhaps the main weakness is that the current paper may owe a lot to Bouttier et al. (2020) which obtained the crucial quantity S_C(f,\varepsilon). Based on this quantity the remaining steps are actually not so hard, including its relationship to the integral, and the lower bound argument. Therefore, I suggest the authors to discuss more on the importance of error certification, as well as the main novelty/difference/challenge in the current DOO algorithm compared with the previous ones. This would make the contribution of the current paper more convincing. 

Some additional comments: 

1. Perhaps it would be nice to add that error certification makes the instance-dependent complexity meaningful. Without error certification, the complexity lower bound must be in a local minimax sense instead of strictly pointwise. 

2. In the lower bound, does any result change if the points could be queried randomly? The pigeonhole principle always becomes a little bit shaky to apply when things are not deterministic. Some discussions would be appreciated. 

3. Also, if the oracle is actually noisy, do the authors have any intuition/evidence whether the sample complexity is roughly the same, or changes dramatically? Some discussions would also be appreciated. 

4. Line 66-68: check for language issues. 

Post-rebuttal feedback:

Thanks to the authors for the detailed response. Please add the discussions on the random query model and noisy oracles if space permits. I am happy to keep my score and recommend acceptance. 
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the complexity of certifiable zeroth-order optimization of Lipschitz functions. Formally, given oracle access to evaluations of a $L$-Lipschitz function $f$ over a known compact domain $\mathcal{X}$ and an error parameter, $\epsilon > 0$, the goal is to find a point $\hat{x}$ satisfying $f (\hat{x}) \geq \max_x f (x) - \epsilon$ making as few oracle queries as possible. The paper characterizes the optimal oracle complexity of the problem in an instance dependent sense where the number of queries made to the oracle depend on the behavior of the particular function. Concretely, they show that the number of queries that necessarily must be made to the oracle is $\int_{\mathcal{X}} d \mathbf{x} / (\max(f) - f(\mathbf{x})  + \epsilon)^d$ up to constant factors depending (exponentially) on the dimension.
main_review: The paper studies the complexity of certifiable zeroth-order optimization of Lipschitz functions. Formally, given oracle access to evaluations of a $L$-Lipschitz function $f$ over a known compact domain $\mathcal{X}$ and an error parameter, $\epsilon > 0$, the goal is to find a point $\hat{x}$ satisfying $f (\hat{x}) \geq \max_x f (x) - \epsilon$ making as few oracle queries as possible. The paper characterizes the optimal oracle complexity of the problem in an instance dependent sense where the number of queries made to the oracle depend on the behavior of the particular function. Concretely, they show that the number of queries that necessarily must be made to the oracle is $\int_{\mathcal{X}} d \mathbf{x} / (\max(f) - f(\mathbf{x})  + \epsilon)^d$ up to constant factors depending (exponentially) on the dimension. The right notion of complexity in the instance dependent setting is a little tricky as the optimal algorithm in the instance dependent setting would be one that simply outputs the optimizer of the particular function in question. However, if one additionally imposes the requirement of certification which is essentially that the algorithm must output a correct answer for \emph{any} Lipschitz function over $\mathcal{X}$, one obtains nontrivial bounds. 

On a technical level, there seem to be two main technical contributions in the paper. Firstly, noting that a modification of the Deterministic Optimistic Optimization algorithm by Munos (2011) obtains a sample complexity of:
$$
\mathcal{N} (\mathcal{X}\_\epsilon, \epsilon / L) + \sum\_{k = 1}^{m\_\epsilon} \mathcal{N} (\mathcal{X}\_{(\epsilon\_k, \epsilon\_{k - 1}]}, \epsilon\_k / L)
$$
where $m_\epsilon = \log \epsilon_0 / \epsilon$, $\epsilon_k = \epsilon_0 2^{-k}$,  $\epsilon_0 = \max_{x,y \in \mathcal{X}} L \lVert x - y \rVert$, $\mathcal{X}\_\epsilon = \{x \in \mathcal{X}: f(x) \geq \max (f) - \epsilon \}$, $\mathcal{X}\_{(a, b]} = \{x \in \mathcal{X}: a < \max(f) - f(x) \leq b\}$ and $\mathcal{N} (\mathcal{A}, \gamma)$ denotes a $\gamma$-packing number of $\mathcal{A}$, they show that under reasonable assumptions on $\mathcal{X}$, the integral is a dimension-dependent constant factor approximation of the integral characterizing the optimal upper and lower bounds. Secondly, they show any certified algorithm must incur an oracle complexity of:
\begin{equation*}
    c \int_{\mathcal{X}} \frac{d \mathbf{x}}{(\max(f) - f(\mathbf{x}) + \epsilon)^d} \text{ where } c = c' \frac{(1 - \mathrm{Lip} (f) / L)^d}{1 + m_\epsilon}
\end{equation*}
providing some justification on why $1 - \mathrm{Lip} (f) / L$ factor in the lower bound may be inherent. In proving the lower bound, they show that any algorithm making fewer than the number characterized by the lower bound for some function $f$ must make an error on a related function $f'$ constructed by perturbing $f$ using a precisely constructed bump function around a close-to-optimal point of $f$. The construction itself is fairly intuitive but yields near-optimal results. 

Overall, the paper makes progress on a natural question relating to a fundamental problem that is of interest to the NeurIPS community. The proofs themselves are quite natural and intuitive though one small caveat is that the assumption on $\mathcal{X}$ (Assumption 4) while seemingly reasonable is a little difficult to reason about. Additional exposition on the types of sets for which it may (or may not) hold would be quite helpful. 

**************************** POST REBUTTAL ADJUSTMENTS ****************************

After reviewing the authors response, I am convinced of the technical quality of the results in the paper and the assumptions underlying them. I will retain my recommendation to accept the paper.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work gives nearly tight upper/lower bounds for the sample complexity of optimizing any lipschitz function using zeroth-order oracles with certification. They prove the sample complexity is proportional to the integral of  $1/(\max(f)-f(x)+\epsilon)^d$ up to a $\log \epsilon$ factor, which is instance-dependent.
main_review: Originality: This paper considers the version of zeroth-order lipschitz optimization with certification. Considering certification is novel, but its motivation needs further justification. For example, is the goal of certification only to certify the $\epsilon$-optimal point, or to certify $every$ point generated by the algorithm? If we only want to provide certification for the $\epsilon$-optimal point, then bandit optimization algorithms can do as well by simply picking the best point played in hindsight after playing enough rounds. The goal to certify the output of the algorithm generated in every round, in the contrary, seems extravagant since we don't care about certification when the output is far away from optimal.

Quality: It's not too surprising that one can get instance-dependent bounds, since certification essentially requires 'exploring every corner of $X$' at a high level. My main concern is on the constant $c$ and its dependence on $d$. Roughly speaking, $c$ is the product of two terms, where the first is $L^d/v_1$ and the second is $(1-Lip(f)/L)^d$. The second term is exponentially small (in $d$), which is problematic (it hurts the tightness of the upper bound) even if $d$ is seen as a constant. The first term is either exponentially large or exponentially small in $d$, depending on whether $L$ is above a constant threshold. This seems unnatural as one can easily scale the funtion to be $l$-lipschitz for arbitrary $l$, and finding an $\epsilon l/L$-optimal point will suffice. Moreover, $\gamma$ isn't completely independent of $d$ either, because the value of $\gamma$ would be not mild at all for large $d$ whereas the same value might be mild for low dimension.

Clarity: This paper is overall well-written, except that the end of Section 4 ($L=Lip(f)$ case) should be written in a separate section with more details. Adding proof sketches instead of putting technical proofs in the maintext would improve readability.

Significance: This work solves an existing open problem. Though whether the proposed algorithm could be useful in practice is unclear, it's of importance from a theoretical perspective.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: This paper considers the zeroth-order optimization problem with error certificates for Lipschitz functions. It generalized existing work to higher dimensions and showed that the algorithm is certifiable. The technical contribution is solid. I am happy to recommend acceptance, but I also note that the reviewers have pointed out that the technical novelty is limited in the sense that it owes a lot to Bouttier et al. (2020) which obtained the crucial quantity S_C(f,\varepsilon). 
Decision: Accept (Poster)