Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates
Year: 2022

Abstract:
We study the problem of zeroth-order (black-box) optimization of a Lipschitz function f defined on a compact subset X of R, 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 ε. Under a weak assumption on X , this optimal sample complexity is shown to be nearly proportional to the integral ∫ X dx/(max(f)− f(x) + ε) . 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.

text: 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.

heading: 1 Introduction
text: The problem of optimizing a black-box function f with as few evaluations of f as possible arises in many scientific and industrial fields such as computer experiments (Jones et al., 1998; Richet et al., 2013) or automatic selection of hyperparameters in machine learning (Bergstra et al., 2011). 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 a crucial additional requirement (Vanaret et al., 2013). As a concrete example, Azzimonti et al. (2021) describe a black-box function in nuclear engineering whose output is a k-effective multiplication factor, for which a higher value corresponds to a higher nuclear hazard. Certifying the optimization error is a 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 ε-approximate maximizer of a Lipschitz function f of d variables and characterize the optimal number of evaluations of any such function f to achieve this goal. We start by formally defining the setting.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

heading: 1.1 Setting: Zeroth-order Lipschitz Optimization with Error Certificates
text: Let f : X → R be a function on a compact non-empty subset X of Rd and x? ∈ X a maximizer.
Lipschitz assumption. We assume that f is Lipschitz with respect to a norm ‖·‖, that is, there exists L ≥ 0 such that ∣∣f(x)− f(y)∣∣ ≤ L ‖x− y‖ for all x,y ∈ X . Furthermore, we assume such a Lipschitz bound L to be known. Even though the smallest Lipschitz constant Lip(f) := min{L′ ≥ 0 : f is 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, but for most of our results, we will make the following more realistic assumption. Assumption 1. For some known Lipschitz constant L, the function f : X → R belongs to
FL := { g : X → R | g is Lipschitz and Lip(g) < L } . (1)
The Lipschitzness of f implies the weaker property that f(x?)− f(x) ≤ L ‖x? − x‖ for all x ∈ X , sometimes referred to as Lipschitzness around a maximizer x? ∈ X . Although this is not the focus of our work, we will mention when our results hold under this weaker assumption.
Online learning protocol. We study the case in which f is black-box, i.e., except for the a priori knowledge of L, we can only access f by sequentially querying its values at a sequence x1,x2, . . . ∈ X of points of our choice. At every round n ≥ 1, the query point xn can be chosen as a deterministic function of the values f(x1), . . . , f(xn−1) observed so far. At the end of round n, using all the values f(x1), . . . , f(xn), the learner outputs two quantities:
• a recommendation x?n ∈ X , with the goal of minimizing the optimization error (a.k.a. simple regret): max(f)− f(x?n); • an error certificate ξn ≥ 0, with the constraint to correctly upper bound the optimization error for any L-Lipschitz function f : X → R, i.e., so that max(f)− f(x?n) ≤ ξn.
We call certified algorithm any algorithm for choosing such a sequence (xn,x?n, ξn)n≥1.
Our goal is to quantify the smallest number of evaluations of f that certified algorithms need in order to find and certify an approximate maximizer of f at accuracy ε. This objective motivates the following definition. For any accuracy ε > 0, we define the sample complexity (that could also be called query complexity) of a certified algorithm A for an L-Lipschitz function f as
σ(A, f, ε) := inf { n ≥ 1 : ξn ≤ ε } ∈ {1, 2, . . .} ∪ {+∞} . (2)
This corresponds to the first time when we can stop the algorithm while being sure to have an ε-optimal recommendation x?n.

heading: 1.2 Main Contributions and Outline of the Paper
text: 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 ≥ 1, solving a three-decade old open problem raised by Hansen et al. (1991). More precisely, we prove the following instance-dependent upper and lower bounds, which we later state formally in Theorem 3 of Section 4 (see also discussions therein, as well as Propositions 2 and 3 for the limit case L = Lip(f)). Theorem (Informal statement). Under a mild geometric assumption on X , there exists a computationally tractable algorithm A (e.g., c.DOO, Algorithm 1) such that, for some constants Cd, cd > 0 (depending exponentially on the dimension d), any Lipschitz function f ∈ FL (see (1)) and any accuracy ε,
σ(A, f, ε) ≤ Cd ∫ X dx( f(x?)− f(x) + ε
)d , (3) while any certified algorithm A′ must satisfy, for all f ∈ FL, and c ≈ cd(1− Lip(f)/L)d/ log(1/ε),
c ∫ X dx( f(x?)− f(x) + ε
)d ≤ σ(A′, f, ε) . (4) In particular, this result extends to any dimension d ≥ 1 the upper bound proportional to∫ 1
0 dx/(f(x?)− f(x) + ε) that Hansen et al. (1991) derived in dimension d = 1 using arguments
specific to the geometry of the real line.
Detailed contributions and outline of the paper. We make the following contributions.
• As a warmup, we show in Section 2 how to add error certificates to the DOO algorithm (wellknown in the more classical zeroth-order Lipschitz optimization setting without error certificates, see Perevozchikov 1990; Munos 2011). We then upper bound its sample complexity by the quantity SC(f, ε) defined in (5) below. This bound matches a 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 3 we show that, under a mild geometric assumption on X , the complexity measure SC(f, ε) is actually proportional to the integral ∫ X dx/ ( f(x?) − f(x) + ε )d , which implies
(3) above. This extends the bound of Hansen et al. (1991) (d = 1) to any dimension d.
• Finally, in Section 4, we prove the instance-dependent lower bound (4), which differs from traditional worst-case lower bounds in the Lipschitz setting. Our proof relies on a local worstcase analysis that could likely prove useful for other learning tasks.
Some of the proofs are deferred to 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 E).

heading: 1.3 Related Works
text: 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 a function 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-order 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).1 In dimension d = 1, Hansen et al. (1991) proved that its sample complexity σ(PS, f, ε) for L-Lipschitz functions f : [0, 1] → R is at most proportional to the integral ∫ 1 0 ( f(x?)− f(x) + ε )−1 dx, 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 appears to be difficult”. Recently, writing Xε := {x ∈ X : max(f) − f(x) ≤ ε} for the set of ε-optimal points, X(a,b] := {x ∈ X : a < max(f)− f(x) ≤ b} for the set of points in between a and b optimal, and N (E, r) for the packing number of a set E at scale r (see Section 1.4), Bouttier et al. (2020, Theorem 2) proved a bound valid in any dimension d ≥ 1 roughly of this form:
SC(f, ε) := N ( Xε, ε
L
) + mε∑ k=1 N ( X(εk,εk−1], εk L ) , (5)
where the number of terms in the sum is mε := ⌈ log2(ε0/ε) ⌉ (with ε0 := L supx,y∈X ‖x− y‖) and the associated scales are given by εmε := ε and εk := ε02 −k for all k ∈ {0, 1, . . . ,mε − 1}.
The equivalence we prove in Section 3 between SC(f, ε) and ∫ X dx/(f(x
?)− f(x) + ε)d solves in particular the question left open by Hansen et al. (1991). The upper bound we prove for the certified DOO algorithm in Section 2 also indicates that the bound SC(f, ε) and the equivalent integral bound can be achieved with a computationally much more tractable algorithm.2 Indeed, the Piyavskii-Shubert algorithm requires at every step n to solve an inner global Lipschitz optimization problem close to the computation of a Voronoi diagram (see discussion in Bouttier et al. 2020, Section 1.1), hence a running time believed to grow as nΩ(d) after n function evaluations. On the contrary, as detailed in Remark 1 (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 .
1For the interested reader who is unfamiliar with this classic algorithm, we added some details in Section D.3 of the Supplementary Material.
2Tractability refers to running time (number of elementary operations) and not number of evaluations of f .
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 bandit) feedback, either with perfect (deterministic) or noisy (stochastic) observations. In the deterministic setting considered here, these papers show that though the number (L/ε)d of evaluations associated to a naive grid search is optimal for worst-case Lipschitz functions (e.g., Thm 1.1.2 by Nesterov 2003), sequential algorithms can approximately optimize more benign functions with a much smaller number of evaluations. Examples of algorithms with such guarantees in the deterministic setting are the branch-and-bound algorithm by Perevozchikov (1990), the DOO algorithm by Munos (2011) 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 Kleinberg et al. (2008, 2019). More examples and references can be found in the textbooks by Munos (2014) and Slivkins (2019).
Note however that, except for the work of Bouttier et al. (2020) mentioned earlier, these bandit optimization papers did not address the problem of certifying the accuracy of the recommendations x?n. Indeed, all bounds are related to a more classical notion of sample complexity, namely, the minimum number of queries made by an algorithm A before outputting an ε-optimal recommendation:
ζ(A, f, ε) := inf{n ≥ 1 : max(f)− f(x?n) ≤ ε} ∈ {1, 2, . . .} ∪ {+∞} . (6)
Though ζ(A, f, ε) is always upper bounded by σ(A, f, ε) defined in (2), these two quantities can differ significantly, as shown by the simple example of constant functions f , for which ζ(A, f, ε) = 1 but σ(A, f, ε) ≈ (L/ε)d since the only way to certify that the output is ε-optimal is essentially to perform a grid-search with step-size roughly ε/L, so as to be sure there is no hidden bump of height more than ε. At a high level, the more “constant” a function is, the easier it is to recommend an ε-optimal point, but the harder it is to certify that such recommendation is actually a good recommendation. See the Supplementary Material (Section E) for a comparison of bounds.
Despite this important difference, the bandit viewpoint (using packing numbers instead of more specific one-dimensional arguments) is key to obtain our multi-dimensional integral characterization.
Comparison with existing lower bounds. Several lower bounds were derived in the bandit Lipschitz optimization setting without error certificates. When rewritten in terms of the accuracy ε and translated into our deterministic setting, the lower bounds of Horn (2006) (when d? = d/2) and of Bubeck et al. (2011) (for any d?) are of the form infA supf∈Gd? ζ(A, f, ε) & (1/ε)
d? , where Gd? 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-dependent lower bound (4) quantifies the minimum number of evaluations to certify an ε-optimal point for each function f ∈ FL. Note that here the certified setting enables to obtain meaningful instance-dependent lower bounds, whereas their non-certified counterparts would be trivial (equal to one). Our proof relies on a local worst-case analysis in the same spirit as for distribution-dependent lower bounds in stochastic multi-armed 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.

heading: 1.4 Recurring Notation
text: 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, 2, . . .} by N∗ and let N := N∗ ∪ {0}. For all n ∈ N∗, we denote by [n] the set of the first n integers {1, . . . , n}. We denote the Lebesgue measure of a (Lebesgue-measurable) set E by vol(E) and refer to it simply as its volume. For all ρ > 0 and x ∈ Rd, we denote by Bρ(x) the closed ball with radius ρ centered at x, with respect to the arbitrary norm ‖·‖ that is fixed throughout the paper. We also write Bρ for the ball with radius ρ centered at the origin and denote by vρ its volume.
Lip(f) denotes the smallest Lipschitz constant of our target L-Lipschitz function f : X → R. The set of its ε-optimal points is denoted by Xε := {x ∈ X : max(f)− f(x) ≤ ε}, its complement (i.e., the set of ε-suboptimal points) by X cε , and for all 0 ≤ a < b, the (a, b]-layer (i.e., the set of points that are b-optimal but a-suboptimal) by X(a,b] := X ca ∩ Xb = { x ∈ X : a < f(x?)− f(x) ≤ b } . Since f is L-Lipschitz, every point in X is ε0-optimal, with ε0 defined by ε0 := Lmaxx,y∈X ‖x− y‖. In
other words, Xε0 = X . For this reason, without loss of generality, we will only consider values of accuracy ε smaller than or equal to ε0.
For any bounded set E ⊂ Rd and all r > 0, the r-packing number of E is the largest cardinality of an r-packing of E, that is, N (E, r) := sup { k ∈ N∗ : ∃x1, . . . ,xk ∈ E,mini 6=j ‖xi − xj‖ > r } if E is nonempty, zero otherwise; the r-covering number of E is the smallest cardinality of an r-covering of E, i.e.,M(E, r) := min { k ∈ N∗ : ∃x1, . . . ,xk ∈ Rd,∀x ∈ E,∃i ∈ [k], ‖x− xi‖ ≤ 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, ε)
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(f, ε) defined in Eq. (5). In passing, we slightly improve the packing arguments used by Munos (2011) in the non-certified setting (Supplementary Material, Section E). In Section 4, we will prove that this bound is optimal (up to logarithmic factors) for certified algorithms.
The certified DOO algorithm (c.DOO, Algorithm 1) is defined for a fixed K ∈ N?, by an infinite sequence of subsets of X of the form (Xh,i)h∈N,i=0,...,Kh−1, called cells. For each h ∈ N, the cells Xh,0, . . . , Xh,Kh−1 are non-empty, pairwise disjoint, and their union contains X . The sequence (Xh,i)h∈N,i=0,...,Kh−1 is associated with a K-ary tree in the following way. For any h ∈ N and j ∈ {0, . . . ,Kh − 1}, there exist K distinct i1, . . . , iK ∈ {0, . . . ,Kh+1 − 1} such that Xh+1,i1 , . . . , Xh+1,iK form a partition of Xh,j . We call (h+ 1, i1), . . . , (h+ 1, iK) the children of (h, j). To each cell Xh,i (h ∈ N, i ∈ {0, . . . ,Kh − 1}) is associated a representative xh,i ∈ Xh,i, which can be thought of as the “center” of the cell. We assume that feasible cells have feasible representatives, i.e., that Xh,i ∩ X 6= ∅ implies xh,i ∈ X . The two following assumptions prescribe a sufficiently good behavior of the sequences of cells and representatives.
Assumption 2. There exist two positive constants δ ∈ (0, 1) and R > 0 such that, for any cell Xh,i (h ∈ N, i = 0, . . . ,Kh − 1) and all u,v ∈ Xh,i, it holds that ‖u− v‖ ≤ Rδh. Assumption 3. There exists ν > 0 such that, with δ as in Assumption 2, for any h ∈ N, i = 0, . . . ,Kh − 1, h′ ∈ N, i′ = 0, . . . ,Kh′ − 1, with (h, i) 6= (h′, i′), ‖xh,i − xh′,i′‖ ≥ νδmax(h,h ′).
The classic Assumption 2 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 (2011), yet very easy to satisfy. Indeed, one can prove that for any compact X , it is always possible to find a sequence of cells and representatives satisfying Assumptions 2 and 3. For instance, if X is the unit hypercube [0, 1]d and ‖·‖ is the supremum norm ‖·‖∞, we can define cells by bisection, letting K = 2d, Xh,i be a hypercube of edge-length 2−h, and xh,i be its center (for h ∈ N and i = 0, . . . , 2dh − 1). In this case, Assumptions 2 and 3 are satisfied with R = 1 and δ = ν = 1/2.
Our certified version of the DOO algorithm (c.DOO, Algorithm 1) maintains a set of indices of active cells Ln throughout rounds n. During each iteration k, it selects the index of the most promising active cell (h?, i?) (Line 5) and splits it into its K children L+ (Line 6). Then, it sequentially picks the representatives of the cells corresponding to each of these children (Line 10), observes the value of the target function f at these points (Line 11), recommends the point with the highest observed value of f (Line 12), and outputs a certificate ξn = ( f(xh?,i?) + LRδ h? ) − f(x?n) (Line 13) that is the difference between an upper bound on max(f) and the currently recommended value f(x?n). In the meantime, all children in L+ are added to the set of active indices Ln (Line 9), and the current iteration is concluded by removing (h?, i?) from Ln (Line 14), 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 f ) is driven by the computation of the recommendation x?n ∈ argmaxx∈{x1,...,xn}f(x) (Line 12) and the search of the index of the most promising active cell (h?, i?) ∈ argmax(h,i)∈Ln{f(xh,i) + LRδ
h} (Line 5). The recommendation x?n can be computed sequentially in constant time (by comparing the new value f(xn) with the current maximum). In Line 5, the leaf (h?, i?) to be split at iteration k can be
Algorithm 1: Certified DOO (c.DOO) input: X , L, K, δ, R, cells (Xh,i)h∈N,i=0,...,Kh−1, representatives (xh,i)h∈N,i=0,...,Kh−1 initialization: let n← 1 and L1 ← {(0, 0)}
1 pick the first query point x1 ← x0,0 2 observe the value f(x1) 3 output recommendation x?1 ← x1 and error certificate ξ1 ← LR 4 for iteration k = 1, 2, . . . do 5 let (h?, i?) ∈ argmax(h,i)∈Ln { f(xh,i) + LRδ h }
// ties broken arbitrarily 6 let L+ be the set of the K children of (h?, i?) 7 for each child (h? + 1, j) ∈ L+ of (h?, i?) do 8 if Xh?+1,j ∩ X 6= ∅ then 9 let n← n+ 1 and Ln ← Ln−1 ∪ {(h? + 1, j)}
10 pick the next query point xn ← xh?+1,j 11 observe the value f(xn) 12 output a recommendation x?n ∈ argmaxx∈{x1,...,xn}f(x) 13 output the error certificate ξn ← f(xh?,i?) + LRδh
? − f(x?n) 14 remove (h?, i?) from Ln
computed sequentially in logarithmic time (using a max-heap structure). Therefore, the running time of c.DOO is of order n log(n) in 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 SC(f, ε) introduced in Eq. (5). Proposition 1. If Assumptions 2 and 3 hold, then Algorithm 1 is a certified algorithm and letting ad := 2+K ( 1ν/R≥1 + 1ν/R<1(4R/ν) d ) , its sample complexity satisfies, for all Lipschitz functions f ∈ FL (see (1)) and any accuracy ε ∈ (0, ε0], σ(c.DOO, f, ε) ≤ adSC(f, ε) .
The proof is postponed to Section B of the Supplementary Material and shares some arguments with those of Perevozchikov (1990) and Munos (2011), originally written for the non-certified setting. The key change is to partition the values of f , instead of its domain X at any depth h of the tree (see Munos 2011), when counting the representatives selected at all levels. The idea of using layers X(εi, εi−1] was already present in Kleinberg et al. (2008, 2019) and Bouttier et al. (2020) for more computationally challenging algorithms (see discussion in Section 1.3).
3 Characterization of SC(f, ε)
Earlier, we mentioned that the quantity SC(f, ε) introduced in Eq. (5) upper bounds the sample complexity of several certified algorithms, such as c.DOO or Piyavskii-Shubert. In this section, we provide a characterization of this quantity in terms of a much cleaner and integral expression.
This result is inspired by Hansen et al. (1991), that in dimension d = 1, derive an elegant bound on the sample complexity σ(PS, f, ε) of the certified Piyavskii-Shubert algorithm for any Lipschitz function f and accuracy ε. They proved that σ(PS, f, ε) is upper bounded by ∫ 1 0
dx/(f(x?)− f(x) + ε) up to constants. However, the authors rely heavily on the one-dimensional assumption and the specific form of the Piyavskii-Shubert algorithm in this setting, stating that the task of “Extending the results of this paper to the multivariate case appears to be difficult”. In this section, we show an equivalence between SC(f, ε) 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, σ(PS, f, ε) ≤ SC(f, ε)) solves the long-standing problem raised by Hansen et al. (1991) three decades ago.
To tame the wild spectrum of shapes that compact subsets may have, we will assume that X satisfies the following mild geometric assumption. At a high level, it says that a constant fraction of each (sufficiently small) ball centered at a point in X is included in X . This removes sets containing isolated points or cuspidal corners and, as can be shown quickly, includes most domains that are typically used, such as 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., 2020). Assumption 4. There exist two constants r0 > 0, γ ∈ (0, 1] such that, for any x ∈ X and all r ∈ (0, r0), vol ( Br(x) ∩ X ) ≥ γvr.
Note that, above, γ may implicitly depend on d. For instance if X is an hypercube, then γ is at most 2−d. 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, ε) was defined in (5). Theorem 1. For any Lipschitz function f ∈ FL (see (1)), if Assumption 4 holds with r0 > ε0/2L, γ ∈ (0, 1],3 then there exist cd, Cd > 0 (e.g., cd := 1/v1/L and Cd := 1/(γv1/128L)) such that, for all ε ∈ (0, ε0],
cd ∫ X dx( f(x?)− f(x) + ε )d ≤ SC(f, ε) ≤ Cd ∫ X dx( f(x?)− f(x) + ε
)d . Remark that in Theorem 1, the integral is multiplied by Ld in the two inequalities. This is to compensate for the fact that this integral does not depend on L, while SC(f, ε) scales like Ld for a fixed f as L→∞. Proof. Fix any ε ∈ (0, ε0] and recall that mε := ⌈ log2(ε0/ε) ⌉ , εmε := ε, and for all k ≤ mε − 1, εk := ε02 −k. Partition the domain of integration X into the following mε + 1 sets: the set of ε-optimal points Xε and the mε layers X(εk, εk−1], for k ∈ [mε]. We begin by proving the first inequality:∫
X dx( f(x?)− f(x) + ε )d ≤ vol(Xε)εd + mε∑ k=1
vol ( X(εk, εk−1] ) (εk + ε)d
≤ M ( Xε, εL ) · v1 ( ε L )d εd + mε∑ k=1 M ( X(εk, εk−1], εk L ) · v1 ( εk L )d εdk
≤ v1 Ld
( N ( Xε, ε
L
) + mε∑ k=1 N ( X(εk, εk−1], εk L )) ,
where the first inequality follows by lower bounding f(x?)− f with its infimum on the partition, the second one by dropping ε > 0 from the second denominator and upper bounding the volume of a set with the volume of the balls of a smallest εk/L-cover, and the last one by the fact that covering numbers are always smaller than packing numbers (we recall this known result in the Supplementary Material, Lemma 1, Eq. (8)). This proves the first part of the theorem.
For the second one, we have∫ X dx( f(x?)− f(x) + ε )d ≥ vol(Xε)(ε+ ε)d + mε∑ k=1 vol ( X(εk, εk−1] ) (εk−1 + ε)d
≥ 1 2d vol(Xε) εd + 1 4d mε∑ k=1
vol ( X(εk, εk−1] ) εdk ≥ 1 32d vol(X2ε) εd + mε∑ k=1 vol ( X( 12 εk, 2εk−1] ) εdk−1  ≥ N ( Xε, εL ) vol ( ε 2LB1 )
(32 ε)d/γ + mε∑ k=1
N ( X(εk, εk−1], εk L ) vol ( εk 2LB1 ) (32 εk−1)d/γ
≥ γv1/64LN ( Xε, ε
L
) + γv1/128L mε∑ k=1 N ( X(εk, εk−1], εk L ) ,
where the first inequality follows by upper bounding f(x?)− f with its supremum on the partition, the second one by ε ≤ εk−1 (for all k ∈ [mε + 1]) and εk−1 ≤ 2εk (for all k ∈ [mε]), the third
3We actually prove a stronger result. The first inequality holds more generally for any f that is L-Lipschitz around a maximizer and Lebesgue-measurable, and does not require X to satisfy Assumption 4.
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 X2ε ⊇ X 3
2 ε
and X( 12 εk, 2εk−1] ⊇ X( 12 εk, 32 εk−1] (for all k ∈ [mε]) followed by a relationship between packing numbers and volumes (proved in the Supplementary Material, Proposition 4) that holds under Assumption 4.
4 Optimality of SC(f, ε)
We begin this section by proving an f -dependent lower bound on the sample complexity of certified algorithms that matches the upper bound SC(f, ε) on the sample complexity of the c.DOO algorithm (Proposition 1), up to a log(1/ε) term, a dimension-dependent constant, and the term (1−Lip(f)/L)d. 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, ε). 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-ε accuracy. We recall that mε := ⌈ log2(ε0/ε) ⌉ and that SC(f, ε) was defined in (5). Theorem 2. The sample complexity of any certified algorithm A satisfies
σ(A, f, ε) > c′d(1− Lip(f)/L)d
1 +mε SC(f, ε)
for some constant c′d (that can be taken as c ′ d = 2 −22−7d), any Lipschitz function f ∈ FL (see (1)) and all ε ∈ (0, ε0].
Proof. Fix any f ∈ FL and an accuracy ε ∈ (0, ε0]. We begin by defining the tightest error certificate that a certified algorithm A could return based on its first n observations of f . Formally, errn(A) := sup { max(g)− g(x?n) : g is L-Lipschitz and f(x) = g(x) for all x ∈ {x1, . . . ,xn} } where xi = xi(A, f) and x?i = x ? i (A, f) are the query and recommendation points chosen by A at time i when run on f (to lighten the notation, we omit the explicit dependencies on A and f of xi and x?i ). In particular, max(f)− f(x?n) ≤ errn(A). Based on this quantity, we define a corresponding notion of optimal sample complexity τ as the smallest number of rounds n that the best certified algorithm A′ needs in order to guarantee that errn(A′) ≤ ε. Formally,
τ := min { n ∈ N∗ : infA′ ( errn(A ′) ) ≤ ε } , (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 a recommendation that maximizes the observed values.
Crucially, τ lower bounds the sample complexity σ(A, f, ε) of any certified algorithm A. At a high level, this makes intuitive sense because τ guarantees a weaker property: that the best certificate of the best algorithm is small, while σ(A, f, ε) controls the certificate of the specific algorithm A. We defer a formal proof of this statement to the Supplementary Material, Section D.1.
Since σ(A, f, ε) ≥ τ , to prove the theorem it is sufficient to show that, with c := 2−22−7d(1 − Lip(f)/L)d,
τ > c
1 +mε SC(f, ε) . LetQ := 16L/ ( L−Lip(f) ) . If SC(f, ε)/(1+mε) < 3(8Q)d, then τ ≥ 1 > 3/4 > cSC(f, ε)/(1+ mε). Assume from now on that SC(f, ε)/(1 +mε) ≥ 3(8Q)d. The idea now is to upper bound the sum of 1 +mε packing numbers that define SC(f, ε) in (5) with the largest one multiplied by 1 +mε. This way, SC(f, ε)/(1 +mε) can be controlled by (an upper bound of) the largest summand in SC(f, ε). Let ε̃ be the scale achieving the maximum in (5), that is
ε̃ =
{ ε , if N ( Xε, εL ) ≥ maxi∈{1,...,mε}N ( X(εi, εi−1], εi L ) ,
εi?−1 , otherwise, where i? ∈ argmaxi∈{1,...,mε}N ( X(εi, εi−1], εi L ) .
Since N (Xε, ε/L) ≤ N (Xε, ε/2L) and N ( X(εi, εi−1], εi/L ) ≤ N ( X εi−1 , εi−1/2L ) , we then have SC(f, ε) ≤ (mε + 1)N (Xε̃, ε̃/2L). Let now n ≤ cSC(f, ε)/(1 + mε). We then have n ≤ cN (Xε̃, ε̃/2L). From a known property of packing numbers (Supplementary Material, Lemma 2),
N ( Xε̃, Qε̃L ) ≥ ( 1 8Q )d N ( Xε̃, ε̃2L ) ≥ ( 1 8Q )d SC(f,ε) mε+1 ≥ 3 ,
by our initial assumption. Then we have n ≤ c(8Q)dN (Xε̃, Qε̃/L). Since c(8Q)d = 1/4, we thus obtain n ≤ N (Xε̃, Qε̃/L)− 2. Consider a certified algorithm A for L-Lipschitz functions. Fix a (Qε̃/L)-packing x̃1, . . . , x̃N of Xε̃ with cardinality N = N (Xε̃, Qε̃/L). Then the open balls of centers x̃1, . . . , x̃N and radius Qε̃/2L are disjoint and two of them, with centers, say, x̃1 and x̃2, do not contain any of the points x1, . . . ,xn queried by A when it is run on f . Let, for x ∈ X ,
gε̃(x) := ( 8ε̃− 16LQ ‖x− x̃1‖ ) I { x ∈ X ∩BQε̃/2L(x̃1) } .
Then gε̃(x) is 16L/Q = L− Lip(f) Lipschitz. Hence f + gε̃ and f − gε̃ are L-Lipschitz. Note that f , f + gε̃ and f − gε̃ coincide on the points x1, . . . ,xn that A queries when it is run on f . As a consequence, A queries the same points and returns the same recommendation x?n when it is run on any of the three functions f , f + gε̃, and f − gε̃. Consider first the case x?n ∈ B(x̃1, Qε̃/4L). Then, we have, by definition of gε̃ and the fact that x̃2 ∈ Xε̃, f(x̃2)− gε̃(x̃2)− f(x?n) + gε̃(x?n) ≥ −ε̃+ 8ε̃− 16LQ Qε̃ 4L = 3ε̃.
Now consider the case x?n /∈ B(x̃1, Qε̃/4L). Then, we have, by definition of gε̃ and the fact that x̃1 ∈ Xε̃, f(x̃1) + gε̃(x̃1)− f(x?n)− gε̃(x?n) ≥ −ε̃+ 8ε̃− 8ε̃+ 16LQ Qε̃ 4L = 3ε̃.
Therefore, in both cases errn(A) ≥ 3ε̃ > ε. Repeating the same construction from any other certified algorithm A′, we obtain that infA′ ( errn(A ′) ) > ε. Since this has been shown for any n ≤ cSC(f, ε)/(1 +mε), by definition of τ we can conclude that τ > cSC(f, ε)/(1 +mε).
Putting together Proposition 1 and Theorem 2 shows that the sample complexity of c.DOO applied to any Lipschitz function f ∈ FL is of order SC(f, ε) and no certified algorithm A can do better, not even if A knows f exactly. This is a 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-pathological sets X , combining Proposition 1 and Theorem 2 with Theorem 1 gives the following near-tight characterization of the optimal sample complexity of certified algorithms. Theorem 3. Let L > 0 and suppose that Assumption 4 holds with r0 > ε0/2L. Then, there exist two constants cd, Cd > 0 such that, for all Lipschitz functions f ∈ FL and any accuracy ε ∈ (0, ε0], the optimal sample complexity of any certified algorithm A satisfies
cd ( 1− Lip(f)L )d 1 + ⌈ log2(ε0/ε) ⌉ ∫ X dx( f(x?)− f(x) + ε
)d ≤ infA σ(A, f, ε) ≤ σ(c.DOO, f, ε) ≤ Cd ∫ X dx( f(x?)− f(x) + ε
)d . For example, one can take cd = L d 4·27dv1 and Cd = ( 2 +K ( 1ν/R≥1 + 1ν/R<1(4R/ν) d )) (128L)d v1γ .
The boundary case L = Lip(f). The previous results show that, for any function f whose best Lipschitz constant Lip(f) is bounded away from L, the quantity SC(f, ε) (or the equivalent integral bound) characterizes the optimal sample complexity up to log terms and dimension-dependent constants. For the sake of completeness, we now discuss the boundary case in which L = Lip(f), i.e., 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 Lip(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, ε) nearly characterizes the optimal sample complexity even when L = Lip(f), as shown below. The proof is deferred to Section D.2 of the Supplementary Material.
Proposition 2. If d = 1, let c = 2−8/3. Then, the sample complexity of any certified algorithm A satisfies, for any L-Lipschitz function f and all ε ∈ (0, ε0], σ(A, f, ε) > cSC(f, ε)/(1 +mε).
In contrast, in dimension d ≥ 2, there are examples of functions f with Lip(f) = L for which the optimal sample complexity is much smaller than SC(f, ε). 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 f in only two rounds, while SC(f, ε) grows polynomially in 1/ε. The proof is deferred to Section D.3 of the Supplementary Material, together with a refresher on PS. Proposition 3. Let d ≥ 2,X := B1, and ‖·‖ be a norm. The certified Piyavskii-Shubert algorithm PS with initial guess x1 := 0 is a certified algorithm satisfying, for the L-Lipschitz function f := L ‖·‖ and any ε ∈ (0, ε0), σ(PS, f, ε) = 2 cd/εd−1 ≤ SC(f, ε), for some constant cd > 0.
Note that the same upper bound of 2 could be proved in dimension d = 1 for f(x) = L|x|, but in this case, SC(f, ε)/(1 +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 f such that Lip(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 SC(f, ε) remains the right quantity for functions for which∣∣f(x)− f(y)∣∣/ ‖x− y‖ is close to Lip(f) only far away from the set of maximizers.

heading: 5 Conclusions and Open Problems
text: Contributions. We studied the sample complexity of certified zeroth-order Lipschitz optimization. We first showed that the sample complexity of the computationally tractable c.DOO algorithm scales with the quantity SC(f, ε) introduced in Eq. (5) (Proposition 1). We then characterized this quantity in terms of the integral expression ∫ X dx/(max(f)− f(x) + ε)
d (Theorem 1), solving as a corollary a long-standing open problem in Hansen et al. (1991). Finally we proved an instance-dependent lower bound (Theorem 2) showing that this integral characterizes (up to log factors) the optimal sample complexity of certified zeroth-order Lipschitz optimization in any dimensions d ≥ 1 whenever the smallest Lipschitz constant of f is not known exactly by the algorithm (Theorem 3).
Limitations and open problems. There are some interesting directions that would be worth investigating in the future but we did not cover in this paper. First, even if the results of Section 2 could be easily extended to pseudo-metric spaces as in Munos (2014) and related works, our other results are finite-dimensional and exploit the normed space structure.
Second, our lower and upper bounds involve constants (with respect to f and ε) that depend exponentially 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 L = Lip(f), for which characterizing the optimal sample complexity is still open in dimensions d ≥ 2. A third question is related to the general notion of adaptivity to smoothness (e.g., Munos 2011; Bartlett et al. 2019). Note that when no upper bound L on Lip(f) is available, it is in general not possible to issue a finite certificate ξn satisfying max(f) − f(x?n) ≤ ξn for any f (as arbitrarily steep bumps can be added to f ). Hence, while having some upper bound L is necessary for certified optimization, a natural question is whether L could be much larger than Lip(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 L→∞, the lower bound on σ(A, f, ε) is of order SC(f, ε)/ log(1/ε) and SC(f, ε) grows like Ld. It would thus be interesting to see 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 observations 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 f (Bubeck et al., 2011; Kleinberg et al., 2019). We expect the modified integral ∫ X dx/(max(f)− f(x) + ε)
d+2 to play a role for this, where our intuition for the “+2” is that to see an ε-big gap through the variance, the learner has to draw roughly ε−2 samples.
Acknowledgments and Disclosure of Funding
The work of Tommaso Cesari and Sébastien Gerchinovitz has benefitted from the AI Interdisciplinary Institute ANITI, which is funded by the French “Investing for the Future – PIA3” program under the Grant agreement ANR-19-P3IA-0004. Sébastien Gerchinovitz gratefully acknowledges the support of the DEEL project4. This work benefited from the support of the project BOLD from the French national research agency (ANR).

Review summaries:
  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.

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. 

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 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. 

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$.