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.

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

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

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

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

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

authors:
Dario Azzimonti
David Ginsbourger
Clément Chevalier
Julien Bect
Yann Richet.

title: Adaptive design of experiments for conservative estimation of excursion sets

authors:
Peter L. Bartlett
Victor Gabillon
Michal Valko.

title: A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption

venue: Proceedings of the 30th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 98), Aurélien Garivier and Satyen Kale (Eds.). PMLR, Chicago, Illinois, 184–206.

authors:
James Bergstra
Rémi Bardenet
Yoshua Bengio
Balázs Kégl.

title: Algorithms for hyperparameter optimization

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

authors:
Clément Bouttier
Tommaso R Cesari
Sébastien Gerchinovitz.

title: Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization

venue: (Feb. 2020). Preprint.

authors:
Stephen Boyd
Lieven Vandenberghe.

title: Convex optimization

venue: Cambridge University Press, Cambridge.

authors:
Sébastien Bubeck
Rémi Munos
Gilles Stoltz
Csaba Szepesvári.

title: X-armed bandits

venue: Journal of Machine Learning Research 12, May (2011), 1655–1695.

authors:
Antonio Cuevas
Ricardo Fraiman
Beatriz Pateiro-López.

title: On statistical properties of sets fulfilling rolling-type conditions

venue: Advances in Applied Probability 44, 2 (2012), 311–329.

authors:
Pierre Hansen
Brigitte Jaumard
S-H Lu.

title: On the number of iterations of Piyavskii’s global optimization algorithm

venue: Mathematics of Operations Research 16, 2 (1991), 334–350.

title: Optimal algorithms for global optimization in case of unknown Lipschitz constant

venue: Journal of Complexity 22, 1 (2006), 50–70.

authors:
Yichun Hu
Nathan Kallus
Xiaojie Mao.

title: Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes

venue: Proceedings of Thirty Third Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 125), Jacob Abernethy and Shivani Agarwal (Eds.). PMLR, Online, 2007–2010.

authors:
Donald R Jones
Matthias Schonlau
William J Welch.

title: Efficient global optimization of expensive black-box functions

venue: Journal of Global optimization 13, 4 (1998), 455–492.

authors:
Robert Kleinberg
Aleksandrs Slivkins
Eli Upfal.

title: Multi-Armed Bandits in Metric Spaces

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

title: Bandits and experts in metric spaces

venue: Journal of the ACM (JACM) 66, 4 (2019), 1–77.

authors:
Tor Lattimore
Csaba Szepesvári.

title: Bandit algorithms

venue: Cambridge University Press, Cambridge. 4https://www.deel.ai/

authors:
Cédric Malherbe
Nicolas Vayatis

title: Global optimization of Lipschitz functions

venue: In Proceedings of the 34th International Conference on Machine Learning, Vol. PMLR 70

title: Optimistic Optimization of a Deterministic Function without the Knowledge of Its Smoothness

venue: Proceedings of the 24th International Conference on Neural Information Processing Systems (Granada, Spain) (NIPS’11). Curran Associates Inc., Red Hook, NY, USA, 783–791.

title: From bandits to Monte-Carlo Tree Search: The optimistic principle applied to optimization and planning

venue: Foundations and Trends in Machine Learning 7, 1 (2014), 1–130.

title: Introductory lectures on convex optimization: A basic course

venue: Vol. 87. Springer Science & Business Media, New York, US.

title: The complexity of the computation of the global extremum in a class of multi-extremum problems

venue: U. S. S. R. Comput. Math. and Math. Phys. 30, 2 (1990), 28–33.

title: An algorithm for finding the absolute extremum of a function

venue: U. S. S. R. Comput. Math. and Math. Phys. 12, 4 (1972), 57–67.

authors:
Yann Richet
Grégory Caplin
Jérôme Crevel
David Ginsbourger
Victor Picheny.

title: Using the efficient global optimization algorithm to assist nuclear criticality safety assessment

venue: Nuclear Science and Engineering 175, 1 (2013), 1–18.

title: A sequential method seeking the global maximum of a function

title: Introduction to Multi-Armed Bandits

venue: Foundations and Trends® in Machine Learning 12, 1-2 (2019), 1–286. https://doi.org/10.1561/2200000068

authors:
Charlie Vanaret
Jean-Baptiste Gotteland
Nicolas Durand
Jean-Marc Alliot.

title: Preventing premature convergence and proving the optimality in evolutionary algorithms

venue: International Conference on Artificial Evolution (Evolution Artificielle). Springer, Springer International Publishing, Cham, 29–40.

title: High-Dimensional Statistics: A Non-Asymptotic Viewpoint

venue: Cambridge University Press, Cambridge, United Kingdom.

title: Granulometric smoothing

venue: The Annals of Statistics 25, 6 (1997), 2273–2299.

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

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


summaries: The paper presents an interesting method to create adversarial examples that do not change the class label, but rather flips the confidence in that label.  In other words, the accuracy of the classification system is not changed.  Rather, the idea is that the attack will force a system with well calibrated confidence to become confidently wrong and unconfidently correct rather than the desired behavior of being unconfidently wrong and confidently correct. The overall approach is basically the same as a standard label adversarial attack (i.e., follow the gradient), but at a lower magnitude as not to change the label.  The other minor difference is to determine the direction of the gradient depending on the ground truth label of the test sample.  That is increase confidence if the classification label prediction is incorrect and reduce the confidence otherwise. The paper does include extensive experimentation over various neural network models including uncertainty-aware models such as ensembles, MC dropout and SelectiveNet.

summaries: The paper presents a novel way for adversarial attacks.  This work studies the problem of attacking networks to change their confidence without affecting the accuracy. Such attacks increase the confidence of the network on wrong predictions and decrease the confidence of the networks on correct predictions. Since the accuracy of the network is not the target, this enables the. attacker to use smaller attacks that might not be easily detected. The paper studies both white-box and black-box attacks on different kinds of uncertainty estimation methods including MC-dropout, SelectiveNets, and Ensemble methods. Finally, the paper presents extensive empirical evaluations that support the proposed method.

summaries: Contribute an attack where the DNN is more confident of its incorrect predictions than about its correct ones without having its accuracy reduced. Attacks contributed in the white-box and black-box regime, where the black-box regime here constitutes "the attacker has no knowledge of the target network". Demonstrate minimal perturbations successfully attack existing uncertainty estimation methods.

summaries: This paper presents a novel uncertainty estimation attack technique. Unlike most existing adversarial attacks, which cause incorrect prediction results, this novel attack technique only cripples the network’s capacity for uncertainty estimation. The result is that, after the attack, the DNN is more confident of its incorrect predictions than its correct ones without having its accuracy reduced. Also, as this proposed attack can be accomplished without harming the model’s accuracy, and thus avoid raising suspicion about a possible attack.

summaries: The paper shows that one can manipulate the uncertainty estimation of a neural network without harming its accuracy by perturbing the inputs. To this end, the paper proposes a greedy heuristic to decrease the perturbation size of FGSM until the adversarial example does not flip the original prediction. Experimental results show that the proposed method indeed can increase several uncertainty estimation metrics (i.e., AURC, NLL, and Brier Score) of several types of neural networks regarding the uncertainty, e.g., softmax-based or MC dropout, without reducing their accuracy.

abstractText: Deep neural networks (DNNs) have proven to be powerful predictors and are widely used for various tasks. Credible uncertainty estimation of their predictions, however, is crucial for their deployment in many risk-sensitive applications. In this paper we present a novel and simple attack, which unlike adversarial attacks, does not cause incorrect predictions but instead cripples the network’s capacity for uncertainty estimation. The result is that after the attack, the DNN is more confident of its incorrect predictions than about its correct ones without having its accuracy reduced. We present two versions of the attack. The first scenario focuses on a black-box regime (where the attacker has no knowledge of the target network) and the second scenario attacks a white-box setting. The proposed attack is only required to be of minuscule magnitude for its perturbations to cause severe uncertainty estimation damage, with larger magnitudes resulting in completely unusable uncertainty estimations. We demonstrate successful attacks on three of the most popular uncertainty estimation methods: the vanilla softmax score, Deep Ensembles and MC-Dropout. Additionally, we show an attack on SelectiveNet, the selective classification architecture. We test the proposed attack on several contemporary architectures such as MobileNetV2 and EfficientNetB0, all trained to classify ImageNet.

title: Verification of Forecasts Expressed in Terms of Probability

venue: Monthly Weather Review,

title: An optimum character recognition system using decision functions

venue: IRE Transactions on Electronic Computers, EC-6(4):247–254

authors:
L.P. Cordella
C. De Stefano
F. Tortorella
M. Vento

title: A method for improving classification reliability of multilayer perceptrons

venue: IEEE Transactions on Neural Networks, 6(5):1140–1147

authors:
C. De Stefano
C. Sansone
M. Vento

title: To reject or not to reject: that is the question-an answer in case of neural classifiers

venue: IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 30(1):84–94

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: Imagenet: A large-scale hierarchical image database

venue: 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255

authors:
R. El-Yaniv
Y. Wiener

title: On the foundations of noise-free selective classification

venue: Journal of Machine Learning Research, 11(5)

authors:
Y. Gal
Z. Ghahramani

title: Dropout as a bayesian approximation: Representing model uncertainty in deep learning

authors:
Y. Geifman
R. El-Yaniv

title: Selective classification for deep neural networks

venue: Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 4885–4894

title: Selectivenet: A deep neural network with an integrated reject option

authors:
Y. Geifman
G. Uziel
R. El-Yaniv

title: Bias-reduced uncertainty estimation for deep neural classifiers

title: Boosting uncertainty estimation for deep neural classifiers

authors:
I.J. Goodfellow
J. Shlens

title: and C

venue: Szegedy. Explaining and harnessing adversarial examples

authors:
K. He
X. Zhang
S. Ren

title: and J

venue: Sun. Deep residual learning for image recognition

authors:
G. Huang
Z. Liu
K.Q. Weinberger

title: Densely connected convolutional networks

authors:
A.-K. Kopetzki
B. Charpentier
D. Zügner
S. Giri

title: and S

venue: Günnemann. Evaluating robustness of predictive uncertainty estimation: Are dirichlet-based models reliable?

title: Learning multiple layers of features from tiny images

venue: Technical report

authors:
A. Kurakin
I. Goodfellow

title: and S

venue: Bengio. Adversarial examples in the physical world

authors:
B. Lakshminarayanan
A. Pritzel
C. Blundell

title: Simple and scalable predictive uncertainty estimation using deep ensembles

authors:
Y. Liu
X. Chen
C. Liu
D. Song

title: Delving into transferable adversarial examples and black-box attacks

title: A practical bayesian framework for backpropagation networks

venue: Neural Comput.,

authors:
A. Madry
A. Makelov
L. Schmidt
D. Tsipras

title: and A

venue: Vladu. Towards deep learning models resistant to adversarial attacks

authors:
N. Tishby
E. Levin
S.A. Solla

title: Consistent inference of probabilities in layered networks: Predictions and generalizations

venue: pages 403–409 vol. 2

title: Bayesian Learning for Neural Network

venue: PhD thesis, Dept. of Computer Science, University of Toronto

authors:
A. Paszke
S. Gross
F. Massa
A. Lerer
J. Bradbury
G. Chanan
T. Killeen
Z. Lin
N. Gimelshein
L. Antiga
A. Desmaison
A. Kopf
E. Yang
Z. DeVito
M. Raison
A. Tejani
S. Chilamkurthy
B. Steiner
L. Fang
J. Bai
S. Chintala

title: Pytorch: An imperative style

venue: high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc.

authors:
M. Sandler
A.G. Howard
M. Zhu
A. Zhmoginov
L. Chen

title: Inverted residuals and linear bottlenecks: Mobile networks for classification

venue: detection and segmentation. CoRR, abs/1801.04381

authors:
K. Simonyan
A. Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings

authors:
C. Szegedy
W. Zaremba
I. Sutskever
J. Bruna
D. Erhan
I. Goodfellow

title: and R

venue: Fergus. Intriguing properties of neural networks

authors:
M. Tan
Q.V. Le

title: Efficientnet: Rethinking model scaling for convolutional neural networks

title: Pytorch image models

heading: 1 Introduction

text:
Deep neural networks (DNNs) show great and improving performance in a wide variety of application domains including computer vision and natural language processing. Successful deployment of these models, however, is critically dependent on providing effective uncertainty estimation for their predictions, or employing some kind of selective prediction [8].
In the context of classification, practical and well-known uncertainty estimation techniques include: (1) the classification prediction’s softmax score [3, 4], which quantifies the embedding margin between an instance to the decision boundary; (2) MC-Dropout [7], which is argued to proxy Bayesian networks [22, 20, 23]; (3) Deep Ensembles [18], which have shown state-of-the-art results in various estimation settings; and (4) SelectiveNet [9], which learns to estimate uncertainty in a way that produces optimal risk for a specific desired coverage.
In this paper we show that all these well-known uncertainty estimation techniques are vulnerable to a new and different type of attack that can completely destroy their usefulness and that works in both black-box (where the attacker can only query the attacked model for predicted labels and has no knowledge of the model itself) and white-box (the attacker has complete knowledge about the attacked model) settings. While standard adversarial attacks target model accuracy, the proposed attack is designed to keep accuracy performance intact and refrains from changing the original classification predictions made by the attacked model. We call our method ACE: Attack on Confidence Estimation. To demonstrate the relevance of our findings, we test ACE on modern architectures, such
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
as MobileNetV2 [25], EfficientNet-B0 [28], as well as on standard baselines such as ResNet50 [13], DenseNet161 [14] and VGG16 [26]. Our attacks are focused on the task of ImageNet classification [5]. Figure 1 conceptually illustrates how ACE works. Consider a classifier for cats vs. dogs that
uses its prediction’s softmax score as its uncertainty estimation measurement. An end user asks the model to classify several images, and output only the ones in which it has the most confidence. Since softmax quantifies the margin from an instance to the decision boundary, we visualize it on a 2D plane where the instances’ distance to the decision boundary reflect their softmax score. In the example shown in Figure 1, the classifier was mistaken about one image of a dog, classifying it as a cat, but fortunately its confidence in this prediction is the lowest among its predictions. A malicious attacker targeting the images in which the model has the most confidence would want to increase the confidence in the mislabeled instance by pushing it away from the decision boundary, and decrease the confidence in the correctly labeled instances by pushing them closer to the decision boundary.
Our attack, however, can be accomplished without harming the model’s accuracy, and thus avoid raising suspicion about a possible attack. Even if the mislabeled dog is assigned more confidence than only a single correctly predicted image, ACE will undermine the model’s uncertainty estimation performance, since based on its estimation measurements, it cannot offer its newly least-confident (and correct) instance without offering the now more-confident mislabeled dog. It will either have to exclude both from the predictions it returns, reducing its coverage and its usefulness to the user, or include both and return predictions with mistakes, increasing its risk.
ACE, unlike adversarial attacks, creates damage even with small magnitudes of perturbations, befitting even an attacker with very limited resources (see Section 5). This benefit is inherent in our goal, which is different from standard adversarial attacks: adversarial attacks seek to move the attacked instance across the model’s decision boundary, and thus require the magnitude of the perturbations it causes to be sufficiently large to allow this. Our objective is to simply move the correctly and incorrectly predicted instances, relative to one another within the boundaries, which requires a less powerful “nudge”. Figure 2 exemplifies such an attack on EfficientNet, showing how the model would be more confident of binoculars being a tank than a correctly-labeled tank. Figure 6 shows the Risk-Coverage (RC) curve (see Section 3 for an explanation of RC curves) for EfficientNet under our attack, and that for the strongest attack tested (in terms of perturbation magnitude, which is still a very small amount), approximately 20% of the model’s most confident predictions were wrong.
Uncertainty attacks are in general conceptually different than adversarial attacks. Consider a scenario of a debt landing company using machine learning to decide whether to approve or disapprove loans to its clients. An interesting example is: lendbuzz.com. Such a company operates by granting loans to highly probable non-defaulting applicants achieving the highest confidence according to their predictive model. The choice of rejection threshold must depend on uncertainty estimation (in accordance with the company’s risk tolerance). A malicious attacker might attempt to influence this company to grant loans to the maximal amount of defaulting applicants to increase its odds to go
bankrupt. Aware of this risk, the company tries to defend itself in various ways. Two obvious options are: (1) Monitor their model’s accuracy. if it drops significantly it might point to an adversarial attack. Since normal adversarial attacks harms accuracy significantly, it will alarm such monitors. ACE does not harm accuracy, and therefore will not. (2) Subscribe to AI firewall services like those given by professional parties such as robustintelligence.com. Since standard adversarial attacks generate instances that cross the decision boundary, they require a relatively large epsilon that is easier to detect relative to those required by ACE. Even if the standard adversarial attack bypassed detection, the crossing adversarial instance they generated may have a very high uncertainty estimate due to its proximity to the decision boundary.
While a similar attack was already considered in the context of OOD detection with Dirichletbased uncertainty models [15], the present paper is the first to offer an algorithm to attack only the uncertainty estimation of any model employing any of the most common uncertainty estimation techniques in both black-box and white-box settings.

heading: 2 Related work

text:
The most common and well-known approach to estimate uncertainty in DNNs for classification is using softmax at the last layer. Its values correspond to the distance from the decision boundary, with high values indicating high confidence in the prediction. The first ones to suggest this approach using DNNs were [3, 4].
Lakshminarayanan et al. [18] showed that an ensemble consisting of several trained DNN models gives reliable uncertainty estimates. For classification tasks, the estimates are obtained by calculating a mean softmax score over the ensemble. This approach was shown to outperform the softmax response on CIFAR-10, CIFAR-100, SVHN and ImageNet [11].
Motivated by Bayesian reasoning, Gal and Ghahramani [7] proposed Monte-Carlo dropout (MCDropout) as a way of estimating uncertainty in DNNs. At test time, for regression tasks this technique estimates uncertainty using variance statistics on several dropout-enabled forward passes. In classification, the mean softmax score of these passes is calculated, and then a predictive entropy score is calculated to be used as the final uncertainty estimate.
Geifman and El-Yaniv [9] introduced SelectiveNet, an architecture with a suitable loss function and optimization procedure that trains to minimize the risk for a specific required coverage. The SelectiveNet architecture can utilize any DNN as its backbone, and constructs three prediction heads on top of it – one of which is used solely for training, and the other two for prediction and rejection.
SelectiveNet incorporates a soft “reject option” into its training process, allowing it to invest all its resources to achieve an optimal risk for its specific coverage objective. It was shown to achieve state-of-the-art results on several datasets for deep selective classification across many different coverage rates.
The area under the risk-coverage curve (AURC) metric was defined in [10] for quantifying the quality of uncertainty scores. This metric is motivated from a selective classification perspective: given a model, and using any uncertainty score for that model, an RC curve can be generated to indicate what the resulting risk (y-axis) would be for any percentage of coverage (x-axis). AURC is then defined to be the area under this curve. More details and an example are provided in Section 3.
Turning to adversarial attacks, one of the first adversarial examples was presented by Szegedy et al. [27]. They showed how small, barely perceptible perturbations of the input to a CNN, crafted by using the box-constrained L-BFGS (Limited-Memory Broyden-Fletcher-Goldfarb-Shanno) algorithm, could alter the DNN’s classification. Goodfellow et al. [12] developed a more efficient way to craft adversarial examples, called the fast gradient sign method (FGSM), requiring only a single backward pass of the network. Formally, with being a fixed magnitude for the image perturbation, y being the true label and a given loss function, the FGSM adversarial example is simply x̃ = x+ · sign(∇xloss(f(x), y)). Liu et al. [19] demonstrated that crafting transferable adversarial examples (examples fooling multiple models, possibly of different architectures) for black-box attacks is especially challenging when targeting specific labels. The authors showed that using an ensemble results in highly transferable adversarial examples. The knowledge required for this method to create non-targeted attacks is only the ground-truth label and the attacked model’s predicted label for targeted attacks.

heading: 3 Problem setup

text:
Let X be the image space and Y be the label space. Let P (X ,Y) be an unknown distribution over X × Y . A model f is a prediction function f : X → Y , and its predicted label for an image x is denoted by ŷf (x). The model’s true risk w.r.t. P is R(f |P ) = EP (X ,Y)[`(f(x), y)], where ` : Y × Y → R+ is a given loss function, for example, 0/1 loss for classification. Given a labeled training set Sm = {(xi, yi)}mi=1 ⊆ (X × Y), sampled i.i.d. from P (X ,Y), the empirical risk of the model f is r̂(f |Sm) , 1m ∑m i=1 `(f(xi), yi).
For a given model f , following [10], we define a confidence score function κ(x, ŷ|f), where x ∈ X , and ŷ ∈ Y is the model’s prediction for x. The function κ should quantify confidence in the prediction of ŷ for the input x, based on signals from the model f . This function should induce a partial order over points in X , and is not required to distinguish between points with the same score. For example, for any classification model f with softmax at its last layer, the vanilla confidence score is its softmax response values: κ(x, ŷ|f) , f(x)ŷ . Note that we are not concerned with the values of the confidence function; moreover, they do not have to possess any probabilistic interpretation. They can be any value in R. An optimal κ for a given classification model f and 0/1 loss should hold for every two instances with their ground truth, (x1, y1) ∼ P (X ,Y) and (x2, y2) ∼ P (X ,Y):
κ(x1, ŷf (x1)|f) ≤ κ(x2, ŷf (x2)|f) ⇐⇒ PrP [ŷf (x2) 6= y2] ≤ PrP [ŷf (x1) 6= y1]
so that κ truly is monotone with respect to the loss.
In practice, DNN end users often calibrate a threshold over the κ used (whether it is a softmax one or an MC-dropout one, etc.) to get the desired coverage over the inference inputs exceeding this threshold, and give special treatment to the rest (such as consulting an expert or abstaining entirely from giving a prediction). A natural way to evaluate the performance of a κ in such settings is from a selective model perspective. A selective model f [6, 2] uses a selection function g : X → {0, 1} to serve as a binary selector for f , enabling it to abstain from giving predictions for certain inputs. g can be defined by a threshold θ on the values of a κ function such that gθ(x|κ, f) = 1[κ(x, ŷf (x)|f) > θ]. The performance of a selective model is measured using coverage and risk, where coverage, defined as φ(f, g) = EP [g(x)], is the probability mass of the non-rejected instances in X . The selective risk of the selective model (f, g) is defined as R(f, g) , EP [`(f(x),y)g(x)]φ(f,g) . These quantities can be evaluated empirically over a finite labeled
set Sm, with the empirical coverage defined as φ̂(f, g|Sm) = 1m ∑m i=1 g(xi), and the empirical
selective risk defined as r̂(f, g|Sm) , 1 m
∑m i=1 `(f(xi),yi)g(xi)
φ̂(f,g|Sm) . The risk-coverage curve (RC curve)
is a curve showing the selective risk as a function of coverage, measured on some chosen test set. Figure 3 shows an example of such a curve. The RC curve could be used to evaluate a confidence score function κ over all its possible thresholds (such that the threshold is determined to produce the matching coverage in the graph). A useful scalar to quantify κ’s performance is to consider all possible coverages, by calculating the area under its RC curve (AURC) [11], which is simply the mean selective risk.

heading: 4 How to attack uncertainty estimation

text:
Attacking the uncertainty estimation “capacity” of a model is essentially sabotaging the partial order induced by its confidence score κ, for example, by forcing κ to assign low confidence scores to correct predictions, and high confidence scores to incorrect predictions (an even more refined attack, discussed in Section 6, is to completely reverse the partial order, which could be useful when the loss used is not 0/1). An adversarial example that specifically targets uncertainty estimation can be crafted by finding a minimal perturbation for an input x, such that x̃ = x+ would cause κ to produce a bad (in terms of selective risk) partial order on its inputs without changing the model’s accuracy. The most harmful attack on κ for a model f should hold for every two adversarial instances with their ground truth:
κ(x̃1, ŷf (x̃1)|f) ≤ κ(x̃2, ŷf (x̃2)|f) ⇐⇒ PrP [ŷf (x̃1) 6= y1] ≤ PrP [ŷf (x̃2) 6= y2].
Figure 5 shows such a hypothetical worse-case RC curve scenario, in which all of its incorrectly predicted instances are assigned more confidence than its correctly predicted ones. An end user setting a threshold to get a coverage of 0.22 over inputs would suffer a 100% error rate. An RC curve of our proposed attack showing similar actual damage can be observed in Figure 6.
The restriction of not changing the model’s accuracy allows an attacker to only harm the uncertainty estimation without attracting suspicion by causing a higher error rate for the model. This constraint underscores the fact that it is not necessary to change the model’s predictions in order to harm its capacity to estimate uncertainty. This restriction could be lifted based on the goal of the attack (if, for example, the attacker does not mind that the attacked model’s accuracy is being reduced).
This type of attack also enjoys two benefits unique to it and not shared with common adversarial attacks: Firstly, the perturbations needed for this type of attack are inherently smaller than those needed for most adversarial attacks. Perturbations with too large magnitudes could cause the crafted example to cross the decision boundary and thus harm the model’s accuracy (violating our restriction). Secondly, its success is not binary: The goal of most adversarial attacks is to push an input over the decision boundary. If the perturbation magnitude was insufficient to do that, the attack has failed. In
our approach, the attack is partially successful even if it causes a single incorrect prediction to get a higher confidence score than a correct one, with the magnitude of the perturbations only contributing to the potency of the attack (creating a worse partial order and creating a larger confidence gap, numerically, between the correct and incorrect samples).
Algorithm 1 Attack on Confidence Estimation 1: function ACE(f, f̂ , κ, x, y, , decay,max_iterations) 2: η ← sign(∇xκ(x, ŷf (x)|f̂)) . κ is calculated with f̂ on the label predicted by f 3: for i < max_iterations do 4: if ŷf (x) == y then . f is correct, decrease confidence for x 5: x̃← x− · η 6: else . f is incorrect, increase confidence for x 7: x̃← x+ · η 8: if ŷf (x̃) == ŷf (x) then 9: return x̃ . label is unchanged so accuracy will be unharmed 10: else 11: ← · decay 12: return x . insufficient max_iterations & too big Algorithm’s arguments: f is the attacked model, f̂ is the proxy for f , κ is the confidence scoring function, x is the input, y is the true label, is the initial magnitude of the perturbation, decay is the rate at which decreases when the attack changes the input’s prediction and max_iterations is the number of decrease steps.
Algorithm 1 summarizes the general template for our proposed attack, dubbed ‘ACE’ (Attack on Confidence Estimation). In black-box settings, the proxy f̂ for the attacked model f is an ensemble of models not consisting of f itself (with ŷf (x) requiring a query to f to obtain its label for the input x), and in white-box settings, f̂ = f . The derivative of κ w.r.t. x, in the case of the softmax score, is the derivative of the y prediction component of f̂ w.r.t. to the input x, where y = yf (x). We show in our white-box experiments that attacking the softmax score specifically is sometimes preferable, even if the κ used is not the softmax score, which is why we target the softmax score in black-box settings. We speculate that this is due to the fact that softmax allows us a direct “handle” on the prediction’s margin in cases where κ does not (for example, in Section 5.4 we show that targeting the selector head of SelectiveNet that is used for rejection is less effective than targeting its softmax score).
While the scope of this paper is classification, future work could modify ACE for regression tasks, in which the uncertainty is often measured by the variance of several outputs made by the model (e.g., the variance of outputs provided by an ensemble of DNNs). A simple conversion of this algorithm could, for example, define any instance with a loss above some threshold (such as the median loss on some validation set) as an “incorrect prediction” and loss values below the threshold as “correct predictions”. The κ being attacked would be the variance of the outputs, causing an increase in
variance for the inputs for which the model had a low loss, and a decrease in variance for inputs for which the model had a high loss.
A weakness of ACE for conducting large scale attacks is that knowledge of the ground truths for the instances it attacks is required, which might be difficult to obtain. Some attackers, however, could have a good proxy of the ground truths, such as a different model capable of making accurate predictions. Alternatively, the attacker might not care at all about the ground truths and would like only to increase the confidence for certain types of labels and decrease the confidence for other types regardless of their truthfulness (i.e., causing a loan company to have a very high confidence for the label approving the granting of a loan and a very low confidence for the label disapproving loans, thus increasing the chance for it to go bankrupt).

heading: 5 Experiments

text: We evaluate the potency of ACE using several metrics: AURC (×103), Negative Log-likelihood (NLL) and Brier score [1] commonly used for uncertainty estimation in DNNs, and defined in Appendix A. We test several architectures on the ImageNet [5] validation set (which contains 50,000 images), implemented and pretrained by PyTorch [24], with the exception of EfficientNetB0, which was implemented and pretrained by [29]. We test ACE in black-box settings using three values for : 0.0005, 0.005 and 0.05 (with RGB intensity values between 0 and 1). We follow [19] in using an ensemble to craft the adversarial examples, in our case consisting of ten ResNet50 models trained on ImageNet. For “easier” white-box settings we test ACE with even smaller values: 0.00005, 0.0005 and 0.005. To the best of our knowledge, some of our tested values were never used by standard adversarial attacks. Due to ACE refraining from changing the originally predicted labels and decreasing iteratively if needed, the effective values selected by ACE are smaller and noted in the results (as “Effective ”). In all of our experiments, we set the hyperparameters arbitrarily: decay = 0.5,max_iterations = 15. We did not try to optimize these, and we expect the algorithm to reach better results with a smaller decay if we also increase max_iterations (since it would find bigger values that could be used without changing the predictions).

heading: 5.1 Attacking softmax uncertainty

text:
Table 1 shows the results of using ACE for different values of under black-box settings. Note that for larger values of , the effective is about half the size, meaning that even fewer resources are sufficient for a very harmful attack. Under attack by ACE with = 0.05, the AURC is 3.5 − 6.5 times worse, and both the NLL and Brier score have worsened by about 100%, meaning that the uncertainty estimation of the model is devastated while the accuracy is left unharmed – just as ACE intended. The RC curves included in Appendix B.3 provide an important insight the metrics cannot: while on average, larger values harm uncertainty estimation more, sometimes for larger coverages, a smaller is more harmful. For example, the selective risk for VGG16 above coverage 0.6 is higher for = 0.005 than it is for = 0.05 (indicated by the purple curve being under the blue curve). This artifact may either be inherent to such black-box attacks, or it may be due to many attacked instances losing their “adversarial trajectory” by taking overly large steps, and could be fixed with an iterative version of ACE further discussed in Section 6. Figure 6 shows an RC curve for EfficientNetB0 with ACE under white-box settings (the legend presents the different values for ). Results for the even more potent white-box setting and its RC curves are included in Appendix B.1. In Appendix B.2 we
evaluate ACE with an adversarially trained model. These results suggest that standard adversarial training does not provide significant robustness against ACE.

heading: 5.2 Attacking deep ensemble uncertainty

text:
Table 2 shows the results of using ACE under black-box settings. We evaluate two different kinds of ensemble proxies to attack an ensemble of ResNet50: (1) an ensemble proxy of foreign architectures
(EfficientNet, MobileNetV2 and VGG), (2) an ensemble proxy consisting of ResNet50 models matching the victim models. While ACE harms the ensemble in both scenarios, it is clearly stronger when using a matching ensemble. In the resulting RC curve, which is included in Appendix C.2, we can make the same observation we did when attacking softmax: for large coverages, a smaller causes greater damage to the selective risk (using a ResNet50 proxy for example, the selective risk for any coverage above 0.45 is slightly higher for = 0.005 than it is for = 0.05). For white-box settings, we test ACE using ensembles of different sizes consisting of ResNet50 models trained on ImageNet. Appendix C.1 shows the results of these experiments, from which we observe that for = 0.005, the AURC degrades about eightfold. An interesting observation is that the bigger the ensemble, the more resilient it is to ACE, and even the smallest ensemble is more resilient than a single ResNet50 model (in both black-box and white-box settings). Note that since the scope of this paper does not include explicit attempts to enhance these techniques’ resiliency to our attack, we have not used adversarial training for the ensemble as was suggested by [18] (which was found to improve uncertainty estimation). We did not want to give a perceived advantage to Deep Ensembles over other techniques in this respect, and as the results show, Deep Ensembles are more resilient even without adversarial training.

heading: 5.3 Attacking Monte Carlo dropout

text: We test ACE on MC-Dropout using predictive entropy as its confidence score. We first experiment with ACE under white-box settings and test two methods of attack: an indirect method, in which ACE targets the softmax score of a single dropout-disabled forward pass, and a direct method, in which ACE targets the predictive entropy produced from N dropout-enabled forward passes. In both methods, the model’s confidence in the prediction is calculated by predictive entropy over N forward passes with dropout enabled. From the results presented in Appendix D.1, we can observe that while for small values the direct method is slightly more harmful, for bigger values the indirect softmax method is significantly more harmful and on par with results of attacking those models when their κ is softmax instead of being calculated by MC-Dropout. These results lead us to conclude that for most purposes, an indirect softmax attack could be more harmful than a direct attack on the predictive entropy used by MC-Dropout. Using this knowledge, we attack MC-Dropout in black-box settings identically to how we attacked softmax: by using an ensemble as a proxy and attacking its softmax score, without using dropout at all. Observing Table 3 for the results, we notice that for black-box settings, MC-Dropout seems somewhat more resilient compared to using softmax as κ for these same models. The number of forward passes made by the models do not seem to affect ACE’s effectiveness. The RC curves for the black-box settings are provided in Appendix D.2.

heading: 5.4 Attacking SelectiveNet

text:
Finally, we test ACE under white-box settings attacking SelectiveNet using two different architectures for its backbone, namely ResNet18 and VGG16, both trained on CIFAR-10 [16]. The confidence score is given by the selector head of SelectiveNet, which was trained to be used for a specific
coverage. Since the model is trained to give predictions with an optimal selective risk for the coverage for which they were optimized, the selective risk at that coverage is the most relevant metric by which to measure the performance of a SelectiveNet model. The paper that introduced SelectiveNet [9] emphasized the need to calibrate SelectiveNet’s trained coverage to fit the desired empirical coverage. For fairness and to reach flawless calibration, we train the models to fit a trained coverage of 0.7, but evaluate the selective risk according to the model’s true empirical coverage on the test set (as observed without any attack). For example, the empirical coverage of SelectiveNet with ResNet18 as its backbone on the test set is 0.648, and the selective risk we show in Table 4 is the model’s risk for that exact coverage. As additional metrics, we also provide the AURC, NLL and Brier score (even though they do not reflect the true goal of the network in this context). We consider a direct
attack on the model’s selector head and an indirect attack via the model’s softmax score. In both cases the final confidence score is measured using the selector head. As seen in the results in Table 4, an indirect attack by softmax seems more harmful than a direct one. For example, for SelectiveNet with a VGG16 backbone, the error over the not “rejected” instances is 0.67%, but it is 7.72% for directly (selector) crafted adversarial instances ( = 0.005) and 8.29% for indirectly (softmax) crafted adversarial instances ( = 0.005). For context, we include in Appendix E ACE results on standard (not selective) architectures trained on CIFAR-10 with the confidence score being the softmax score.

heading: 6 Concluding Remarks

text:
We have presented a novel attack on uncertainty estimation, capable of causing significant damage with even small values of (compared to standard adversarial attacks) and without changing the model’s original predictions. This attack severely harms some of the most popular techniques for estimating uncertainty. We can think of several ways in which the attack could be further improved: First is optimizing the perturbations in an iterative process, similar to how BIM [17] or PGD [21] take FGSM steps iteratively. This may not only increase ACE’s potency, but may also fix the artifacts of larger values of leading to a lower selective risk than smaller values (observed in Sections 5.1 and 5.2). This might also have the added benefit of using more of the resources that were allocated to the attack, thus increasing the effective . Low ratios of Effective such as observed from our results mean unspent resources for the attack.
The results of this attack also teach us that some methods are more resilient than others. We hope that this work will encourage efforts to examine the resiliency of other and new uncertainty estimation methods, as well as creating defense mechanisms or detection techniques for them. Finally, in the case of none-0/1 loss functions, an attack on uncertainty estimation might need to completely reverse the partial order observed by the model, which would capture the gaps in uncertainty between two correct instances or between two incorrect instances. Such an attack could be used for regression tasks as well, more naturally than our suggested simple conversion of ACE, discussed in Section 4.

heading: Acknowledgments

text: This research was partially supported by the Israel Science Foundation, grant No. 710/18.

title: Disrupting Deep Uncertainty Estimation Without Harming Accuracy