Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
Authors: Francois Bachoc
Tommaso Cesari
Sébastien Gerchinovitz
Venue: NeurIPS 2021 Poster (2021)
Keywords: Lipschitz optimization
packing bound
function-dependent bound
Piyavskii-Shubert algorithm

Abstract: We study the problem of zeroth-order (black-box) optimization of a Lipschitz function $f$ defined on a compact subset $\mathcal{X}$ of $\mathbb{R}^d$, with the additional constraint that algorithms must certify the accuracy of their recommendations. We characterize the optimal number of evaluations of any Lipschitz function $f$ to find and certify an approximate maximizer of $f$ at accuracy $\varepsilon$. Under a weak assumption on $\mathcal{X}$, this optimal sample complexity is shown to be nearly proportional to the integral $\int_{\mathcal{X}} \mathrm{d}\boldsymbol{x}/( \max(f) - f(\boldsymbol{x}) + \varepsilon )^d$. This result, which was only (and partially) known in dimension $d=1$, solves an open problem dating back to 1991. In terms of techniques, our upper bound relies on a packing bound by Bouttier et al. (2020) for the Piyavskii-Shubert algorithm that we link to the above integral. We also show that a certified version of the computationally tractable DOO algorithm matches these packing and integral bounds. Our instance-dependent lower bound differs from traditional worst-case lower bounds in the Lipschitz setting and relies on a local worst-case analysis that could likely prove useful for other learning tasks.

Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
François Bachoc
Institut de Mathématiques de Toulouse & University Paul Sabatier
francois bachocemath. univ-toulouse.
Tommaso Cesari
Toulouse School of Economics
Sébastien Gerchinovitz
IRT Saint Exupéry Institut de Mathématiques de Toulouse
sebastien ien..iiee..... geteeiinngggreeeeee... www.hinnooviii ie teseerrt-saiie petrrrtssnnttttppeee com
Abstract
We study the problem of zeroth-order (black-box) optimization of Lipschitz function defined on compact subset X' of RRd, with the additional constraint that algorithms must certify the accuracy of their recommendations. We characterize the optimal number of evaluations of any Lipschitz function f to find and certify an approximate maximizer of f at accuracy c. Under a weak assumption on X, this optimal sample complexity is shown to be nearly proportional to the integral f(x) + +e)d This result, which was only (and partially) known
Jx dæ dd=(mmax(f) in dimension d 1, solves an open problem dating back to 1991 In terms of techniques, our upper bound relics on a packing bound by Bouttier et al. (020) for the Piyavskii-Shubert Shubert algorithm that we link to the above integral. We also show that certified version of the computationally tractable DOO algorithm matches these packing and integral bounds. Our instance-dependent lower bound differs from traditional worst-case lower bounds in the Lipschitz setting and relies on a local worst-case analysis that could likely prove useful for other learning tasks.
Introduction
The problem of optimizing black-box function ff with as few evaluations of f as possible arises in many scientific and industrial fields such as computer experiments (Jones al. [9988 Richet et 2013) automatic selection of hyperparameters in machine learning (Bergstra et al. [201]). For safety-critical applications, e.g., in aircraft or nuclear engineering, using sample-efficient methods is not enough. Certifying the accuracy of the output of the optimization method can be crucial additional requirement (Vanaret al.) (013).
concrete example, Azzimonti et al. (22T)) describe black-box function in nuclear engincering whose output a k-effective multiplication factor, for which a higher value corresponds to a higher nuclear hazard. Certifying the optimization error is way to certify the worst-case k-effective factor, which may be required by safety authorities.
In this paper, we formally study the problem of finding and certifying an e-approximate maximizer of Lipschitz function f of d variables and characterize the optimal number of evaluations of any such function achieve this goal. We start by formally defining the setting.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 Setting: Zeroth-order Lipschitz Optimization with Error Certificates
Let f:
X + R be a function on a compact non-empty subset X' of R and x" E X a maximizer.
Lipschitz assumption. We assume that f is Lipschitz with respect to a norm II-II, that is, there exists L 2 such that (x)) - f(y) I I. || yll for all æ. y E X. Furthermore, we assume such Lipschitz bound L to be known. Even though the smallest Lipschitz constant Lip(f) := min > 0: f L'-Lipschitz is well defined mathematically, it is rarely known exactly in practical black-box problems. As a theoretical curiosity, we will briefly discuss the case L Lip(f) (i.e.. when the best Lipschitz constant of the unknown black-box function f is known exactly) in Section 4 of our results, we will make the following more realistic assumption.
but for most
Assumption 1. For some known Lipschitz constant L, the function f: X - R belongs to
(1) The Lipschitzness of f implies the weaker property that f(x** f(x) - =| æl for all x E X. sometimes referred to as Lipschitzness around maximizer x² X. Although this is not the focus of our work, we will mention when our results hold under this weaker assumption.
F=: {g: X' - R o is Lipschitz and Lip(g) < [.]
Online learning protocol. We study the case in which f is black-box, i.e., except for the priori knowledge of L, we can only access by sequentially querying its values sequence 21, .2.... E X' of points of our choice. At every round n 2 1, the query point H, can be chosen as a deterministic function of the values / .)...,, [(xxn1 observed so far. At the end round n, using all the values / (æI)...... (.r.), the learner outputs two quantities:
recommendation x² E XX with the goal of minimizing the optimizattion error (a.k.a. simple regrer): max(f) - f=²;;;
error certificate &n 2 O, with the constraint to correctly upper bound the optimization error for any L-Lipschitz function f: X + I, i.c., so that max(f) (f) f(x,,, S Ex.
We call certified algorithm any algorithm for choosing such a sequence (In, Ex)x111
Our goal is to quantify the smallest number of evaluations of f that certified algorithms need in order find and certify an approximate maximizer of f at accuracy s. This objective motivates the following definition. For any accuracy >> 0, we define the sample complexity (that could also be called query complexity) of certified algorithm A for an I.-Lipschitz function f as
(A, == ini n 2 1 &n I } E {1,2,... . (+x)).
(2)
This corresponds to the first time when can stop the algorithm while being sure to have e-optimal recommendation x;
1.2 Main Contributions and Outline of the Paper
The main result of this paper is a tight characterization (up to a log factor) of the optimal sample complexity of certified algorithms in any dimension d 2 solving three-decade old open problem raised by Hansen et al.) 1991). More precisely, we prove the following instance-depender upper and lower bounds, which we later state formally Theorem of Section 4 (see also discussions therein, as well as Propositions 2 and for the limit case L = Lip(f)).
Theorem (Informal statement). Under mild geometric assumption on X, there exists a computa- tionally tractable algorithm A (e.g., c.DOO, Algorithm [ such that, for some constants Ca Ca > 0 (depending exponentially the dimension d), any Lipschitz function f E FL (see ( and any accuracy e,
dæ
o(As,ss) SCa (f(x*) - f(x) + e)²
while any certified algorithm A' must satisfy. all f E Fi, and Re call - (iLL-Lpp))//)/oogl/l log([/e)
S (f(x:)) - f(x)) In particular, this result extends any dimension d > the upper bound proportional to So dx/(f((>*) - f(x) + 8) that Hansen al. (1991 derived in dimension using arguments specific to the geometry of the real line.
dx
0 (A',
(4)

---

Detailed contributions and outline of the paper. We make the following contributions.
As a warmup, we show in Section how to add error certificates to the DOO algorithm (well- known in the more classical zeroth-order Lipschitz optimization setting without emror certificates, see [Perevozchkkov 1990; Munos] M We then upper bound its sample complexity by the quantity Sc(J,)) defined (5) below. This bound matches recent bound derived by Bouttier (et al. (2020) for a computationally much more expensive algorithm. In passing, we also slightly improve the packing arguments that Munos (2011) used in the non-certified setting.
In Section we show that, under a mild geometric assumption on X, the complexity measure Sc(J.e) is actually proportional to the integral fzd (f(xx) - far) + +e)" " which implies
33 above. This extends the bound of Hansen et (191 (d = 1) to any dimension
Finally, in Section 4 we prove the instance-dependent lower bound { which differs from traditional worst-case lower bounds in the Lipschitz setting. Our proof relies local worst-
case analysis that could likely prove useful for other learning tasks.
Some of the proof's are deferred the Supplementary Material, where we also recall useful results on packing and covering numbers (Section A as well as provide a slightly improved sample complexity bound on the DOO algorithm in the more classical non-certified setting (Section)
1.3 Related Works
We detail below some connections with the global optimization and the bandit optimization literatures.
Zeroth-order Lipschitz optimization with error certificates. The problem of optimizing func- tion with error certificates has been studied in different settings over the past decades. For instance, in convex optimization, an example of error certificate is given by the duality gap between primal and dual feasible points (see, e.g., Boyd and Vandenberghe 2004).
In our setting, namely, global zeroth- Lipschitz optimization with error certificates, most of the attention seems to have been on the very natural (yet computationally expensive) algorithm introduced by Piyavskii 1972) and Shubert 1972) In dimension d = 1. Hansen et al. 1991) proved that its sample complexity o (PS, for L-Lipschitz functions f: [0, 1J R is at most proportional to the integral So (f(x*) f(x) +
dr, and left the question of extending the results to arbitrary dimensions open, stating that the task of "Extending the results of this paper to the multivariate case
e) +))
appears to be difficulf". Recently, writing Xe == {xc E X max((f) f(x) S e) for the set of E-optimal points, &( == {æ E X': a < max(f) ) f(x) S b} for the set of points in between a and optimal, and N/E, r) for the packing number of set E at scale r (see Section I.4), Bouttier et al. (2020 Theorem 2) proved a bound valid in any dimension d 2 roughly of this form:
me
So(f.e) == N (Xer 5
Σ k=1
N (Meu.en-I):
EK L
(5)
where the number of terms in the sum is m. := Toog (with eo = -.sup a. yex ||00 yll and the associated scales are given by Em, and Eg == 6o2 i for all & E (0.1...... m 1}.
The equivalence we prove in Section between Sc(f.e) and f dx/(f(x²) f(x) + =) solves in particular the question left open Hansen et al.] (1991). The upper bound we prove for the certified DOO algorithm in Section 2 also indicates that the bound (c(f,e and the equivalent integral bound can be achieved with a computationally much more tractable algorithm Indeed, the Piyavskii-Shude algorithm requires at every step to solve an inner global Lipschitz optimization problem close to the computation of a Voronoi diagram (see discussion in Bouttier al. [2200] Section 1.1). hence a running time believed to grow as (dd() after n function evaluations. On the contrary, as detailed in Remark I (Section 2), the running time of our certified version of the DOO algorithm is only of the order of n log(n) after n of evaluations of f.
For the interested reader who unfamiliar with this classic algorithm, we added some details in Section D.3 of the Supplementary Material. Tractability refers running time (number of elementary operations) and not number of evaluations of f.
3

---

Connections with the bandit optimization literature: upper bounds. Our work is also strongly connected to the bandit optimization literature, in which multiple authors studied the global Lipschitz optimization problem with zeroth-order (or hundit) feedback, either with perfect (deterministic) or noisy (stochastic) observations. In the deterministic setting considered here, these papers show that though the number (I./))² of evaluations associated to naive grid search is optimal for worst-case Lipschitz functions (e.g.. Thm 1.1.2 by Nesterov 2003), sequential algorithms can approximately opti- mize more benign functions with much smaller number of evaluations. Examples of algorithms with such guarantees in the deterministic setting are the branch-and-bour
algorithm by Perrevozhiikov (1990), the DOO algorithm by Munos 12011) or the LIPO algorithm by Malherbe and Vayatis| (2017).
Examples of algorithms in the stochastic setting are the HOO algorithm by Bubeck et al. (2011) or the (generic yet computationally challenging) Zooming algorithm by bleiibbrr al. (2008 2019).
More examples and references can be found in the texthooks by Munos (2014) and Slivkins (2019)
Note however that, except for the work of Bouttier et al.] (2000) mentioned earlier, these bandit optimization papers did not address the problem of certifying the accuracy of the recommendations x Indeed, all bounds are related to more classical notion of sample complexity, namely, the minimum number of queries made by an algorithm A before outputting an s-optimal recommendation:
((A, f,e = in 21 1 max(s) - f(x,,) S e) E (1,2....) [+oo]
(6)
Though C(A, e) is always upper bounded by o f) defined in (2). these two quantities can differ significantly, as shown by the simple example of constant functions f. for which ((A. but oAA, e) (L/e)² since the only way to certify that the output is e-optimal is essentially to perform a grid-search with step-size roughly e/ so as to be sure there is no hidden bump of height more than e. At a high level, the more "constant" function is, the easier it is to recommend an e-optimal point, but the harder it is to certify that such recommendation is actually a good recommendation. See the Supplemenaary Material (Section B for a comparison of bounds.
Despite this important difference, the bandit viewpoint (using packing numbers instead of more specific dreedimennional arguments) is key to obtain our culti-dimennsioal integral characterization.
Comparison with existing lower bounds. Several lower bounds were derived in the bandit Lips- chitz optimization setting without error certificates. When rewritten terms of the accuracy e and translated into our deterministic setting, the lower bounds of Horn 2006) (when d' = d/2) and of Bubeck et al. 12011) (for any d²) are of the form inf sup seg.. f,e) 2 (L/E)d* where Ga- is The subset of L-Lipschitz functions with near-optimality dimension at most d+. These are worst-case (minimax) lower bounds.
On the contrary, our instance- deetedeeddeeeneent lower bound (4) quantifies the minimum number of eval- uations to certify an E-optimal point for each function J E FL. Note that here the certified setting enables to obtain meaningful instance-dependent lower bounds, whereas their non-certified counter- parts would be trivial (equal to one). Our proof relies on a local worst-case analysis in the same spirit as for ceeributiio-dependen lower bounds stochastic multi- bandits (see, e.g., Theorem 16.2 in Lattimore and Szepesvári 2020), yet for continuous instead of finite action sets. We believe this lower bound technique should prove useful for other learning tasks.
1.4 Recurring Notation
This short section contains a summary of all the notation that we use in the paper and can be used by the reader for easy referencing. We denote the set of positive integers (1, by No and let N : No U {0). For all n E N+, , we denote by [n] the set of the first n integers {I,....n)) .... We denote the Lebesgue measure of TLebesgue-massrrabee its volume. For all > 0 and x E Rd, we denote by (x) the closed ball with radius P centered at æ, with respect to the arbitrary norm ||-I| that fixed throughout the paper. We also write B, for the ball with radius p centered at the origin and denote by up its volume.
set E by vol(E) and refer to it simply as
Lip(J) denotes the smallest Lipschitz constant of target L-Lipsshitz function f: X + R. The set of its s-optimal points is denoted by X; := {o E X : max(f) - f()) < <E}, its complement (i.e., the set of e-suboptimal points) by X and for all 0 < a < b, the (a, bj-layer (i.e., the set of points that are b-optimal but a-suboptimal) by Ma.s) == X n X6 = (x E X a f(x*) f(x) I b). Since f is L-Lipschitz, every point in X is En-optimal, with so defined by so == L maxe || yll. In

---

other words, Xeo = X. For this reason, without loss of generality, we will only consider values of accuracy smaller than or equal to Eg-
For any bounded set F c Id and all r > O. the r-packing number of E is the largest cardinality of an r-packing of E., that is, rF), == sup E EN -ar,...... -................. 2% E, minizy ||z; æ;j > r] if E is nonempty, zero otherwise; the r-covering number of E is the smallest cardinality of an r-covering of E, i... MME,r) == min f N' 3x1, :......,; 2t. Rd Vo E, 3i E [k], æiil - r if E is nonempty, zero otherwise. Well-known and useful properties of packing (and covering) numbers are recalled in Section A of the Supplementary Material.
2 Warmup: Certified DOO Has Sample Complexity Sc(f,E)
In this section, we start by adapting the well-known DOO algorithm (Perevozchikov 1990: Munos 2011) to the certified setting. We then bound its sample complexity by the quantity Sc(J, e) defined in Eq. (5) In passing, we slightly improve the packing arguments used by |Muos| (2011 in the non-certified setting (Supplementary Material, Section E). In Section 4 is optimal (up to logarithmic factors) for certified algorithms.
we will prove that this bound
The certified DOO algorithm (c.DOO. Algorithm D is defined for fixed K E N by an infi- nite sequence of subsets of X of the form the cells Xi.,,..., ~ are non-empty, pairwise disjoint, and their union contains X. The sequence . is associated with a K-ary tree in the following way. For any E N and j E {O...., K* - 1}. there exist K distinct i1...., , E {o..... "o0.....KKK. Kh+1 -} such that XA+1,111 X 1nt form a partition of Xn.j- We call (h + 1,41), -.... (h + 1, the children of (). To each cell XA.; (h E i, (0...., K 1)) is associated representative Th,; E Xn,i. which can be thought of as the "center" of the cell. We assume that feasible cells have feasible representatives, i.e., that Xn,5 nX + Ø implies In,i X. The two following assumptions prescribe a sufficiently good behavior of the sequences of cells and representatives.
called cells. For each h E N,
Assumption 2. There exist two positive constants ō E (0. 1) and R > 0 such that, for any cell X (h E N. i = 0, O,...,K* Kh Assumption 3. There exists > 0 such that, with 8 in Assumption 2 for any h N. i= 0, O,..., K - e 1' = 0, K* 1, with (h, i) F (h', i'), || DNe 2 v)max(h,)')
1) and all u, E Xn... it holds that || vil I Rō
The classic Assumption is simply stating that diameters of cells decrease geometrically with the depth of the tree. Assumption 3] which is key for our improved analysis, is slightly stronger than the corresponding one in Munos (20TT), yet very easy to satisfy. Indeed, one can prove that for any compact X. it is always possible to find sequence of cells and representatives satisfying Assumptions 2 and 3 For instance, if X is the unit hypercube [0, 1]d and ||-I| is the supremum norm I1- we define cells by bisection, letting K 2d Xx,, be hypercube of edge-length 2 2-A, and 2h. be its center (for h N and = 0, ..... 2dh 1). In this case, Assumptions 2 and are satisfied with R == and 5 = V = 1/2.
Our certified version of the DOO algorithm (c.DOO, Algorithm maintains a set of indices of active cells E,, throughout rounds n. During each iteration k, it selects the index of the most promising active cell (f* (Line 5 and splits it into its K children L4 (Line 6). Then, it sequentially picks the representatives of the cells corresponding to each of these children (Line TO). observes the value of the target function f at these points (Line T.p recommends the point with the highest observed value of (Line 12). and outputs a certificate En = (f(m=).,.) + T.R5**) (ax;) (Line 13) that is the difference between an upper bound on max(f) and the currently recommended value [(;,), ). In the meantime, all children L4 are added the set of active indices L, (Line (.) and the current iteration is concluded by removing (h", ;i²) from L, (Line now that it has been replaced by its refinement L..
Remark 1. The running-time of c. DOO (ignoring the cost of calling the function 1] is driven by the computation of the recommendation at, E setei.x.eee........ ((r) (Line (2) and the search of the index of the most promising active cell (it,t)) E argmax((..)ee) { (Znn))) LR8 (Line 5 The recomnendation at can be computed sequentially in constant time (by comparing the new value f(x)) with the current maximum). In Line 5 the leaf (h' it) to be split at iteration & can be
5

---

Algorithm 1: Certified DOO (c.DOO)
input: X, K. R. cells (Xn,))eN, Kh represetttte (........ initialization: let 4- and L1 f ((0,0)
pick the first query point æ1 <- 20,0
observe the value f(z1)
output recommendation æ < æ and error certificate & LR
for iteration k 1, do
5 let (h","*) E argmax(h.))Ec. (f( + LRØ"} // ties broken arbitrarily let L_ be the set of the K children of (h",i") for each child (h* + 1. L+ of (1" do
if K1. n & then
9
let n +- n n and Ln + Ln-1 U ((hh" + +,1))
10
pick the next query point < #h++1. observe the value f(x,)
11
output recommendation x; argmax (m f(x) output the error certificate En +- f(xn),)) + LR8" - -f(x))
13
14
remove (h", (*) from Ln
computed sequentially in logarithmic time (using max-heap structure), Therefore, the rumning time c.DDOO of order n log(n) the number n of evaluations of the function f.
The next proposition shows that the sample complexity (see (2) of the certified DOO algorithm is upper bounded (up to constants) by the instance-dependent quantity So(f, E) introduced in Eq. (). Proposition 1. If Assumptions 2 and 3 hold, then Algorithm is a certified algorithm and letting a. = 2+K (1./R21 + 11//es ) (d) its sample complexity satisfies, for all functionns
FL (see ① and any accuracy E E0,
(cc.DO0,f.e) aaSolf.E).
The proof is postponed to Section B of the Supplementary Material and shares some arguments with those of Perevozchiiko (990) and Munos (2011), originally written for the non-certine non-certified setting. The key change is partition the values of f. instead of its domain X' at any depth h of the tree (see MenoM 2011). when counting the representatives selected at all levels. The idea of using layers X 1| was already present in Kleinberg al. (2008 (019) and Bouttier al. (2200) for more computationally challenging algorithms (see discussion in Section 1.30
Characterization of Ec
Earlier, we mentioned that the quantity Sc(S,e) e) introduced in Eq. (5) upper bounds the sample complexity of several certified algorithms, such as c.OOO or Piyavski-Shubert. In this section, we provide characterization of this quantity in terms of much cleaner and integral expression.
This result is inspired by Hansen et al. (199I). that in dimension d = 1, derive an elegant bound on the sample complexity ar (PS, of the certified Piyavskii Shubert algorithm for any Lipschitz function and accuracy 8. They proved that a (PS, f,e) is upper bounded by f dx/(f(x*)) - f()) + up to constants. However, the authors rely heavily on the one-dimensional assumption and the specific form of the Piyavskii-Shube of this paper the multivariate case appears to be difficult". In this section, show equivalence between $c(f,e) and this type of integral bound in any dimension d. Putting this together with a recent result of Bouttier et al. (2020) (which proves that up to constants, o oPSS f,e) < Sc(f,)) solves the mtan-itanding problem raised by Hansen et al. (1991) three decades ago.
algorithm this setting, stating that the task of "Extending the results
To tame the wild spectrum of shapes that compact subsets may have, we will assume that X' satisfies following mild geometric assumption. At a high level, it says that a constant fraction of each (sufficiently small) ball centered at point in X' is included in X. This removes sets containing isolated points or cuspidal corners and, can be shown quickly, includes most domains that are typically used, such finite unions of convex sets with non-empty interiors. This natural assumption

---

is weaker than the classic rolling ball assumption from the statistics literature (Cuevas et al. 2012 Walther 1997) and has already been proved useful in the past (Hu et al.) (020).
Assumption 4. There exist two constants To 0.7 (0,1) such that, for any x X and all r E (0, vol (x) nx) 2 y'---
Note that, above, 7 may implicitly depend on For instance if X' an hypercube, then y is at most 2-4. We can now state the main result of this section. Its proof relies on some additional technical results that are deferred to the Supplementary Material. Recall that Sc(f,e) e) was defined (5)
Theorem 1. For any Lipschitz function E Fr. (see T if Afssmpption Sirmmpttoonnholll holds with To Eo/2L,
(0, then there exist Ca, Ca > (e-g- Ca == 1/wx/2 and C2 == 1/ 1/(701/12LL) such that, for all
E E E0,
cd J/x (f(x)) ((x) + E)
dæ
S ec(s,e) S Co CaL (f(x*) ((x) +)
dæ
Remark that in Theorem [ the integral is multiplied by L in the two inequalities. This is to compensate for the fact that this integral does not depend on L, while Sc(f, E) scales like L for a fixed f as L oc.
Proof. Fix any E E (0, and recall that m. == [Tog(<s//e]]= Em, == E, and for all S m 1, EK := E02 K Partition the domain of integration A' into the following m. + 1 sets: the set of e-optimal points X₂ and the my layers Xise, 5x 11. for E [mz]. We begin by proving the first inequality:
Jx (f(x*) - f(x) 2)
dæ
vol(X)) ed
me vol(K(e., ca-1))
(Ek te
M(Xe, +) U1 (+))
M(Men. se-il: 7) 1i (#))
ed
Ek
N K5.
+ Σ -
6
N M (MEL. L ))
Ck
La
k=1
where the first inequality follows by lower bounding [xx)) f with its infimum on the partition, the second one by dropping
from the second denominator and upper bounding the volume of set with the volume of the balls of a smallest es/ r./r-cover, and the last one by the fact that covering numbers are always smaller than packing numbers (we recall this known result the Supplementary Material, Lemma Eq. )) This proves the first part of the theorem.
For the second one, we have
Jx (f(x*)-((z)) +5)
dx
2 vol(Xe)
me vol(& (())))))))))
(E e)d
(Ek-1 + EEd
k=1
2 1 vol(d'))
vol(X sm-1l)
1
vol(
vol (K 26k-.l) ch_1
+ 1d k=
2d
ed
ct
32d
ed
Amml
N (Ke, {)) vol
27.
me
NV (M sk-1): +t) vol
2L B1)
(32E) //7
(32
k=1
me
2 2 (xer ( 701/1225
Σ V (KEr,
EK L
where the first inequality follows by upper bounding f(x') f with its supremum on the partition, the second one by & < E (for all l E [me + 1]) and Ek-1 1 2 (for all & E [me]), the third
We actually prove a stronger result. The first inequality holds more generally for any f that is L-Lipschitz around maximizer and aabesgue-messurane and does not require X' to satisfy Assumption
7

---

one by lower bounding the sum of disjoint layers with that of overlapping ones (proved in the Supplementary Material, Lemma 3). and the fourth one by the elementary inclusions X2r xg
and X atte 2=x-1] 2 (tet. ] (for all k E [m²]) followed by a relationship between packing numbers and volumes (proved in the Supplementary Material, Proposition 4 that holds under Assumption
4 Optimality of F)
We begin this section by proving f-dependent lower bound the sample complexity of certified algorithms that matches the upper bound Sc(f, ) on the sample complexity of the c. cOOOO algorithm (Proposition []. up to a lo/(1/s) term, dimension-dependent constant, and the term (1-Lip(f)/
The proof of this result differs from those of traditional worst-case lower bounds. The idea is to build a local worst-case analysis, introducing a weaker notion of sample complexity that is smaller than (A, f.E). Then we further lower bound this quantity by finding adversarial perturbations of the target function f with the following opposing properties. First, these perturbations have to be similar enough to f so that running A on them would return the same recommendations for sufficiently many rounds. Second, they have to be different enough from f so that enough rounds have to pass before being able to certify sub-E accuracy. We recall that m, == [logg(c//e) and that (c(f&) was defined in (5).
Theorem 2. The sample complexity of any certified algorithm A satisfies
a o(A,f,)) La(1 Tip(f)/T) So(f.E)
1 my
for some constant dg (that can be taken as c/ 2-222- ?d), any Lipschitt f FL (see I and all ε E (0, Eo].
Proof. Fix any f E FL and an accuracy E Eo]. We begin by defining the tightest error certificate that a certified algorithm A could return based on its first n observations of f. Formally,
err, (A) = sup mmxx(g) - g(xx))= g is I--Lipschitz and ((x) = g(x)) for all x E {2 F.,. }
where x; = x,,A, f) and x; = (A, f) are the query and recommendation points chosen by A at time when on f (to lighten the notation, we omit the explicit dependencies on A and f of x; and ). In particular, max(f) - fxx; ) S (A). Based on this quantity, we define a corresponding notion of optimal sample complexity
the smallest number of rounds that the best certified algorithm A' needs in order to guarantee that erI,,(A') I E. Formally,
7 = min(n E : inf (err,, S <e}
(7)
where the infimum is over all certified algorithms A'. It is immediate to prove that is finite, by considering an algorithm that queries a dense sequence of points (independently of the observed function values) and outputs recommendation that maximizes the observed values.
Crucially, T lower bounds the sample complexity o (A,, f. of any certified algorithm A. At a high level, this makes intuitive sense because T guarantees a weaker property: that the best certificate of the best algorithm is small, while (A, f,e) controls the certificate of the specific algorithm A. We defer formal proof of this statement to the Supplementary Material, Section D.I.
Since (A, f,e) 2 T, to prove the theorem it is sufficient to show that, with == 2- 7d(1 Lip(S)/L)
c Sc(S,e)
1 m
Let := : 16L If St m.). Assume from now on that Sc(f.e)/(L m²) 2 3(S))d.
3(8Q) then T 2 1> 12 (1c
The idea now is to upper bound the sum of + m. packing numbers that define ec in (5) with the largest one multiplied by 1 + mg. This way, Sc(f, [) (m)) can be controlled by (an upper bound of) the largest summand in E). Let é be the scale achieving the maximum in (5), that is
if (Xe, {) 2 max.g( N (Ket, em1)) 4)
é 11-1, otherwise, where i* E argmax,e N (e 4)
8

---

Since NV (Ke, E/L) (X, e/2L) and (Ke,, a 1): E\LL) S <N e.-1, Ex-1/2L), we then
have ff < (m, + 1)W (X', E/2L). Let now n S = + me). We then have n < cN (Ng, E/2L). From a known property of packing numbers (Supplementary Material, Lemma 2
23, by our initial assumption. Then we have n S ((8Q) (Ng, QE/L.) Since c(8Q) = 1/4, we thus obtain N (Zg, Q)/L)- - 2.
N A 9
N (Ke, 21. 2 (2
Sc((E) m1+1
8Q
Consider a certified algorithm A for L-Lipschitz functions. Fix a (QE/ ã ...... N of X3 with cardinality N = -N (Kg, QE/L). Then the open balls of centers .1..... NN and radius QE/2L are disjoint and two of them, with centers, say, TΙ and T2, do not contain any of the points T1..... In queried by A when it is run on f. Let, for x E X.
g=(x)= == ( 16L
Q I
=1 T1ll) E X n (a)))
Then (x) is 16L/Q- L Lip(f) Lipschitz. Hence f + Ie and f 9s are L-Lipschitz. Note that f. f + IE and f 9: coincide on the points ZI..... In that A queries when it is run on f. As a consequence, A queries the same points and returns the same recommendation a, when it is run on any of the three functions f. + gz. and f 9e.
Consider first the case xt E (i) QE/4L). Then, we have, by definition of gs and the fact that i E X2, f( ge (22) f(xx,) + (=(x)) 2 - 8ě
16L QE
3
Q 4f.
Now consider the x; & B QE/4L). Then, we have, by definition of ge and the fact that 3n E Xgg, [()) + g= / (az;, yF (x)) 2 - 85 85
+
161. Q
38. Q 4L.
Therefore, in both cases err, (A) 3 > E. Repeating the same construction from any other
certified algorithm A', obtain that inf v (err,
Since this has been shown for any
cSc(f, + m2), by definition of we can conclude that cSc(f.))((1+ m.). O
Putting together Proposition [ and Theorem 2 shows that the sample complexity of c.OOO applied
to any Lipschitz function f E Fr, is of order Sc(f,)) and no certified algorithm A can do better, not even if A knows I exactly. This is striking difference with the classical non-certified setting in which the best algorithm for each fixed function f has trivially sample complexity 1. In particular, for non-pant non-pathological sets X. combining Proposition [ and Theorem 2 with Theorem [ gives the following near-tight tight characterization of the optimal sample complexity of certified algorithms.
Theorem 3. Let L > O and suppose that Assumption holds with ro > s0/21. Then, there exist two constants ca, Ca >> 0 such that, for all Lipschitz functions I E Fr, and any accuracy s E (0,Eo). the optimal sample complexity of any certified algorithm A satisfies
L ca 1 Lip(f)) [1
1+ log2(E0/E)] 1x (f(x*) - f(x) + +e)
dæ
S inf (info(A, A
dx S socc.DO,, S C. (f(x*) - f(x) + f(x)+
+)
1aa For example, one can take ca 4.2'
and C. = c2= K (1n//211 + +
( (1281.*
V17
The boundary case I, = Lip(S). The previous results show that, for any function / whose best Lipschitz constant Lip(f) is bounded away from L. the quantity Sc(f.e) (or the equivalent integral bound) characterizes the optimal sample complexity up to log terms and dimensioon-eependen constants. For the sake of completeness, we now discuss the boundary case in which L = Lip(f), i.., when the best Lipschitz constant of the target function is known exactly by the algorithm. As we mentioned earlier, this case is not of great relevance in practice, as one can hardly think of a scenario in which f is unknown but the learner has somehow perfect knowledge of its smallest Lipschitz constant (f.( It could, however, be of some theoretical interest.
Next we show an interesting difference between dimensions d = 1 and d > 2. In dimension one, Sc(f,e) e) nearly characterizes the optimal sample complexity even when L, Tip(S), as shown below. The proof is deferred to Section D.2 of the Supplementary Material.

---

Proposition 2. - satisfies, for any L-Lipschitz,uunttin f and all E (0, a f,e) > cfc(f.=)/ + m.).
= 1, let c 2-8/3. Then, the sample complexity of any certified algorithm A
In contrast, in dimension d 2 2, there are examples of functions f with Lip(J) - L for which the optimal sample complexity is much smaller than e)) In the proposition below, the fact that Lip(f) = L, the specific shape of f, and the specific initialization point enable the learner to find and certify a maximizer of only two rounds. while Sc(f.e grows polynomially in 1/e. The proof is deferred to Section D.3 of the Supplementary Material, together with refresher on PS.
Proposition 3. Let d 2 2, X = B1, and be a norm. The certified Sryavskki-hhuber algorithm PS with initial guess 1 == 0 is certified algorithm satisfying, for the I.-Lipschitz function f == T. I1-1l and any E (0, Eo). a (PS, f.e) = 2 < ca/e S Sc(ffe), for some constant > 0.
Note that the same upper bound of could be proved in dimension d = for f(x) T.aae,, but in this case, Sc(f, e)/ + m,) is of constant order. There is therefore no contradiction with Proposition 2
Also, remark that Proposition 3 does not solve the question of characterizing the optimal sample complexity for any such that Lf)(f) = L. We conjecture that the drastic improvement in the sample complexity shown in the specific example above is not possible for all other functions f with Lip(f) = L. For instance, we believe that Se (f,fe E) remains the right quantity for functions for which [f(x) - /())// || yl close to Lip(f) only far away from the set of maximizers.
5 Conclusions and Open Problems
Contributions. We studied the sample complexity of certified zeroth-order Lipschitz optimization. We first showed that the sample complexity of the computationally tractable c. c.O algorithm scales with the quantity Sc(f, E) introduced in Eq. 55) (Proposition Ib. We then characterized this quantity
solving as corollary a Long-standing open problem in Hansen et al. 1991). Finally we proved an iistance-depende lower bound (Theorem 2 showing that this integral characterizes (up to log factors) the optimal sample complexity of certified zeroth-order Lipschitz optimization any dimensions smallest Lipschitz constant of J is not known exactly by the algorithm (Theorem 3
in terms of the integral expression Xx dx/ daz/(man (max (f) f(x) + æ) (Theorem
whenever the
Limitations and open problems. There some interesting directions that would be worth investi- gating in the future but we did not cover in this paper. First, even if the results of Section could be casily extended to pseudo-metric spaces as in Munos| (2014) and related works, our other results are finite-dimensional and exploit the normed space structure.
2
Second, our lower and upper bounds involve constants (with respect and E) that depend exponen- tially on d. Although the dependency in d was intentionally not optimized here, it would be beneficial to obtain tighter constants. However, we believe that removing the exponential dependency in d altogether, while keeping the same level of generality as this paper, would be very challenging, if at all possible. There is also room for improvement in the specific (and unrealistic) case I. = Lip(J), for which characterizing the optimal sample complexity is still open in dimensions 2 2.
A third question is related to the general notion of adaptivity to smoothness (e.g., Munos 2011 Bartleti ct al. 2019). Note that when no upper bound L on Lip(f) f) is available, it is in general not possible to issue finite certificate En satisfying max(f) fxxt) < &, for any f (as arbitrarily steep bumps can be added to f). Hence, while having some upper bound L is necessary for certified optimization, natural question is whether L could be much larger than Lip(f) (f) without penalizing significantly the sample complexity. Theorem 2 provides a negative answer since, for a fixed f for which x* is in the interior of X, when I, oc, the lower bound af [A, f)) e) is of order Sc(J, log(1 /e) and Sf(f,)) grows like Ld. It would thus be interesting to whether a relaxed version of certification would make sense for cases when only a very coarse upper bound L on Lip(f) is known.
Finally, it would also be interesting to see if, using randomized algorithms (still with exact observa- tions of f) and weakening the notion of certification (requiring it to hold only with some prescribed probability), smaller upper bounds could be obtained. Also, an important question is to quantify the sample complexity increase yielded by having only noisy observations of ʃ (Bubeck et al., 201
Kleinberg et al. 2019). We expect the modified integral Jxx dar (m//mmx)))) f(z) + 2) 2 to play role for this, where our intuition for the "42" is that to see an é-big gap through the variance, the learner has to draw roughly =2 samples.
10

---

Acknowledgments and Disclosure of Funding
The work of Tommaso Cesari and Sébastien Gerchinovitz has benefitted from the Al Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future PIA3" program under the Grant agreement ANR-19-P3IA- of the DEEL projec This work benefited from the support of the project BOLD from the French national research agency (ANR).
Sébastien Gerchinovitz gratefully acknowledges the support
References
Dario Azzimonti, David Ginsbourger, Clément Chevalier, Julien Bect, and Yann Richet. 2021. Adaptive design of experiments for conservative estimation of excursion sets. Technometrics 63, 1 (2021), 13-26.
Peter L. Bartlett, Victor Gabillon, and Michal Valko. 2019. A simple parameter-free and adaptive approach to optimization under minimal local smoothness assumption. Proceedings of the 30th International Conference on Algorithmic Learning Theory (P (Proceedings of Machine Learning Research, Vol. 98), Aurélien Garivier and Satyen Kale (Eds.). PMIR, Chicago, Illinois, 184-206.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011. Algorithms for hyper- parameter optimization. In 25th annual conference on neural information processing systems (NIPS 2011). Vol. 24. Neural Information Processing Systems Foundation, Neural Information Processing Systems Foundation, Granada, Spain, 2546-2554,
Clément Bouttier, Tommaso R Cesari, and Sébastien Gerchinovitz. 2020. Regret analysis of the Piyavskii-Shuhert algorithm for global Lipschitz optimization. (Feb. 2020). Preprint.
Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge University Press, Cambridge.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. 2011. X-armed bandits. Journal of Machine Learning Research 12, May (2011), 1655-1695.
Antonio Cuevas, Ricardo Fraiman, and Beatriz Pateiro-López. 2012. On statistical properties of sets fulfilling rolling-type conditions. Advances in Applied Probability 44, 2 (2012), 311-329.
Pierre Hansen, Brigitte Jaumard, and S-H Lu. 1991. On the number of iterations of Piyavskii's global optimization algorithm. Mathematics of Operations Research 16, (1991), 334-350.
Matthias Horn. 2006. Optimal algorithms for global optimization in case of unknown Lipschitz constant. Journal of Complexity 22, (2006), 50-70.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. 2020. Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes. In Proceedings of Thirty Third Conference on Learning Theory (Proeedinggs of Machine Learning Research, Vol. 125), Jacob Abernethy and Shivani Agarwal (Eds.). PMLR, Online, 2007-2010.
Donald R Jones, Matthias Schonlau, and William J Welch. 1998. Efficient global optimization of expensive black-box functions. Journal of Global optimization 13, 4 (1998), 455-492
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. 2008. Multi-Armed Bandits in Metric Spaces. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (Victoria, British Columbia, Canada) (STOC '08), Association for Computing Machinery, New York, NY, USA, 681-690.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. 2019. Bandits and experts in metric spaces. Journal of the ACM (JACM) 66, 4 (2019), 1-77.
Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press, Cam- bridge.
https::/ www. deel. aieel.ii/

---

Cédric Malherbe and Nicolas Vayatis. 2017. Global optimization of Lipschitz functions. In Pro- ceedings of the 34th International Conference on Machine Learning, Vol. PMLR 70. JMgR. Sydney, NSW, Australia, 2314-2323.
Rémi Munos. 2011. Optimistic Optimization of a Deterministic Function without the Knowledge of Its Smoothness. Proceedings of the 24th International Conference on Neural Information Processing Systems (Granada, Spain) (NIPS' 11). Curran Associates Inc., Red Hook, NY, USA, 783-791.
Rémi Munos. 2014. From bandits to Monte-Carie Tree Search: The optimistic principle applied to optimization and planning. Foundations and Trends Machine Learning 7, (2014), 1-130.
Yurii Nesterov. 2003. Introductory lectures on convex optimization: basic course. Vol. 87, Springer Science & Business Media, New York, US.
A.G. Perevozchikov. 1990. The complexity of the computation of the global extremum in a class of multi-extremum problems. U. S. R. Comput. Math. and Math. Phys. 30, 2 (1990), 28-33.
S.A. Piyavskii. 1972.
algorithm for finding the absolute extremum of a function. U. S. S. Comput. Math. and Math. Phys. 12, 4 (1972),57
Yann Richet, Grégory Caplin, Jérôme Crevel, David Ginsbourger, and Victor Picheny. 2013, Using the efficient global optimization algorithm to assist nuclear criticality safety assessment. Nuclear Science and Engineering 175, (2013), 1-18.
Bruno O Shubert. 1972. A sequential method seeking the global maximum of a function. SIAM J. Numer. Anal. 9, 3 (1972), 379-388.
Aleksandrs Slivkins. 2019. Introduction to Multi-Armed Bandits. Foundations and Trends@) in http:///0o...o11..155..22222
Machine Learning 12, 1-2 (2019), 1-286.
Charlie Vanaret, Caan-Bap Gotteland, Nicolas Durand, and Jean-Mare Alliot. 2013. Preventing premature convergence and proving the optimality in evolutionary algorithms. In International Con- ference on Artificial Evolution (Evolution Artificielle. Springer, Springer International Publishing. Cham, 29-40.
Martin J. Wainwright. 2019. figh-Diimesiooal Statisties: A Non-Asymptotic Viewpoint. Cambridge University Press, Cambridge, United Kingdom.
Guenther Walther. 1997. Granulometric smoothing. The Annals of Statistics 25, 6 2273-2299.
2279229,
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The outline in Section 1.2 provides pointers where the claimed contributions of the paper are provided.
(b) Did you describe the limitations of your work? [Yes] In particular, the conclusion discusses limitations and open problems.
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] This is a theoretical/foundation work that adds to the theory and methodology of optimization. As for any such contributions, the positive or negative societal impact will depend on the application case. We do not promote any harmful use of this theory, but expand on the existing knowledge.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] See previous question.
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All our results explicitly refer to their required assumptions. Some general assumptions that hold throughout the paper are also stated in the introduction.
12

---

(b) Did you include complete proofs of all theoretical results? [Yes] Some technical details are deferred to the Supplementary Material.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A] We did not ran experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We did not use existing assets (code, data or models) nor cure/release new assets (code, data or models).
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] We did not use crowdsourcing nor conducted research with human subjects.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "m7SRTZwxyiN", "reviewer": "Reviewer_QEpC", "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: \n\n1. 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). \n\n2. 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. \n\n3. 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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nIf 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. \n\nSome additional comments: \n\n1. 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. \n\n2. 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. \n\n3. 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. \n\n4. Line 66-68: check for language issues. \n\nPost-rebuttal feedback:\n\nThanks 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "U4gAqh2zVbV", "reviewer": "Reviewer_FGKi", "summary": "  In this paper, the authors consider the problem of finding global solutions\n  to a possibly non-convex optimization problem under possibly non-convex\n  constraints using only access to function values of the objective function.\n  In particular, they focus on certified algorithms, i.e., algorithm that\n  together with a solution they also output certificate of the optimality of the\n  solution.\n\n  Their main result is an instance optimal bound for any Lipschitz continuous\n  functions. In particular if f is a Lipschitz continuous function with unknown\n  Lipschitz constant that is less than L, then the number of zero-order queries\n  needed to find an $\\epsilon$-approximate global optimum together with a\n  certificate of optimality is\n\n  $\\sigma = \\int_{\\mathcal{X}} \\frac{1}{(f(x^*) - f(x) + \\epsilon)^d} dx$\n\n  where $f(x^*)$ is the value of the global optimum and d is the dimensionality\n  of the problem. The authors provide both an algorithm and a lower bound that\n  is equal to $\\sigma$ up to dimension dependent constants. Surprisingly the fact\n  that the Lipschitz constant is not exactly known but only upper bounded is\n  crucial for the proof of the lower bound.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n  ====================\n\n  - The paper resolves an interesting open question from 1991.\n\n  - The problem of finding global optima with zero-order methods is very\n  important in many areas, e.g., in hyperparameter tuning.\n\n  - The techniques developed to prove the results are very interesting.\n\n  - The use of the notion of certified algorithms is a very clever way to be\n  able to accurate prove lower bounds for this problem.\n\n\n  Weaknesses - Comments\n  ========================\n\n  1. It would be nice to have some better understanding of the expression of\n  \\sigma. For example, when the domain is [0, 1]^d, a trivial brute force\n  algorithm would need (L/\\epsilon)^d steps to get a certified\n  \\epsilon-approximately optimal solution. How is this bound compared to the\n  per-instance optimal bound? It is clear that the per-instance bound is\n  smaller but is which cases it is significantly smaller? For example if L is\n  O(1) are the two bounds of the same order.\n\n  2. The term \"constant\" in many lemmas and theorems is misleading. In many\n  cases the constants C, c, or c' dependent at least exponentially to the\n  dimension d of the problem which is a very important parameter. I understand\n  that these constants do not dependent on f and \\epsilon but d is an important\n  parameter as well and the authors should be more careful when they use the\n  term constant that has some dependence on d.\n\n  3. The use of the term \"sample complexity\" is a bit misleading a believe a\n  better wording would be \"query complexity\".\n\n  4. In lines 244-250 it is mentioned that Assumption 4 is satisfied for many\n  natural domain sets. Is it satisfied in general for convex sets X or there is\n  a counter-example?\n\n  5. In the proof of Theorem 2 in line 302 the notation K is confusing because K\n  has been used so far for the expansion of the tree in the algorithm.\n\n  6. The fact that the exact knowledge of the Lipschitzness is fundamental for\n  the lower bound is a bit confusing. It is possible that the exact knowledge\n  of the Lipschitz constant can be used to get an improved algorithm for any\n  function f?\n\n\n  Summary of Recommendation\n  ======================================\n  The results provided in this paper seem to be important and significant and\n  for this reason I recommend acceptance.\n\n\n  Post-Rebuttal\n  ======================================\n  After reading the authors response and the other reviews I keep my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "G6eSf6OQ0z1", "reviewer": "Reviewer_6ukK", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nOn 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:\n$$\n\\mathcal{N} (\\mathcal{X}\\_\\epsilon, \\epsilon / L) + \\sum\\_{k = 1}^{m\\_\\epsilon} \\mathcal{N} (\\mathcal{X}\\_{(\\epsilon\\_k, \\epsilon\\_{k - 1}]}, \\epsilon\\_k / L)\n$$\nwhere $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:\n\\begin{equation*}\n    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}\n\\end{equation*}\nproviding 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. \n\nOverall, 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. \n\n**************************** POST REBUTTAL ADJUSTMENTS ****************************\n\nAfter 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Fx3nH8W9cao", "reviewer": "Reviewer_wYFu", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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$. \n\nThanks for the authors' nice response. I would like to keep my ratings for this good paper, ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "about 8 hours. "}, "extra_text": {}}, {"review_id": "9OzAD6ZnIDM", "reviewer": "Reviewer_TJAZ", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality: 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.\n\nClarity: 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.\n\nSignificance: 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "-qZt-k5Jgr", "reviewer": "Reviewer_Ri1i", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\n1. 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'$.\n\n2. 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? \n\n3. 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.\n\nBesides 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. \n\n\n***Update based on the author response:\nThe 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "-cemEFnjnJV", "reviewer": "Reviewer_8oRd", "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}$.\n\nThe 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.\n\nThe 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.\n\nThe 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$.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n* 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.\n\n* 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.\n\n* 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.\n\n* 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 )$.\n\n* 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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"ethical_concerns": "None to the best of my knowledge.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)