Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness
Authors: Vaclav Voracek
Venue: NeurIPS 2024 poster (2024)
Keywords: randomized smoothing
adversarial robustness
confidence interval
confidence sequence
Primary area: safety_in_machine_learning

Abstract: Randomized smoothing is a popular certified defense against adversarial attacks. In its essence, we need to solve a problem of  statistical estimation which is usually very time-consuming since we need to perform numerous (usually $10^5$) forward passes of the classifier for every point to be certified. In this paper, we review the statistical estimation problems for randomized smoothing to find out if the computational burden is necessary.  In particular, we consider the (standard) task of adversarial robustness where we need to decide if a point is robust at a certain radius or not using as few samples as possible while maintaining statistical guarantees.  We present estimation procedures employing confidence sequences enjoying the same statistical guarantees as the standard methods, with the optimal sample complexities for the estimation task and empirically demonstrate their good performance. Additionally, we provide a randomized version of Clopper-Pearson confidence intervals resulting in strictly stronger certificates.

Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness
Václav Voráček
Tübingen Al center, University of Tübingen
vaclav. voracekkumi-tuebingge
Abstract
Randomized smoothing is popular certified defense against adversarial attacks. In its essence, we need to solve problem of statistical estimation which is usually very tine-consuming since we need to perform numerous (usually 10") forward passes of the classifier for every point to be certified. In this paper, we review the statistical estimation problems for randomized smoothing to find out if the computational burden is necessary. In particular, we consider the (standard) task of adversarial robustness where we need to decide a point is robust at a certain radius not using as few samples possible while maintaining statistical guarantees. We present estimation procedures employing confidence sequences enjoying the same statistical guarantees as the standard methods, with the optimal sample complexities for the estimation task and empirically demonstrate their good performance. Additionally, we provide randomized version of Hlopper-Pearson confidence intervals resulting in strictly stronger certificates. The code can be found htttps://gtt httggttthbb.../ com wwworaceeRR_cooo _a________ee___________ seq
We encourage the readers only interested in statistics to start at Subsection 2.1
Introduction
Adversarial robustness: It is well known that a tiny, adversarial, perturbation of the input can change the output of basically any undefended machine learning model (Biggio et al.) 2013 Szegedy jet al., 2014); this is unpleasant and we continue in the mitigation of the problem. There are two main lines of work tackling this problem: (1) Empirical: the standard approach here is to use adversarial
training (Madry et al.] 2018 Goodfellow et al.] 2014) where the model is trained on adversarial examples. This approach does not provide guarantees, only empirical evidence suggesting that the model may be robust. With stronger attacks, we might (yet again) realize it is not the case. (2) Certified: with formal robustness guarantees for the model. We will focus on this, and in particular on randomized smoothing (Lecuyer et al. 2019) which is currently the strongest certification method
We will not cover other certification methods and we refer the reader the survey Li et al. (2023) instead. We consider the standard task of certified robustness; the goal is to decide if the decision of classifier F particular input x is robust against additive perturbations such that ||8|| < r for some norm ||.|]. Formally, we ask if F F(x)
F(x') whenever || a'll <
Randomized smoothing is framework providing state of the art formal guarantees on the adver- sarial robustness for many datasets. One of its benefits lies in the fact that there are no assumptions on the model, making possible readily transfer the methods from defending image classifiers against sparse pixel changes to different modalities; e.g., defending large language models against change of
see leaderboard badeebbrr/ttte///oooortttttttttd http://eeeeeeeeattoooooooodeeeed
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

some letters/words/okenns Randomized smoothing transforms any undefended classifier F R + y by a smoothing distribution yp into a smoothed classifier H (x) = arg max P yl for which robustness guarantees exist. We postpone the details for later. During the certification process, we need to estimate the maximum probability of multinomial distribution from samples as the exact computation is intractable. This statistical estimation problem is the focus of this paper.
The main weakness randomized smoothing is the extensive time required for both prediction and certification, making it troublesome for real- world applications, There is inherent trade-off between the allowed probability of incorrectly claiming robustness (type- error, a), the probability of incorrectly claiming non-robustness (type-2 error, 5), and the number of samples used n. The standard practice is to set a = 0.001, n = 100 000 and the value of is then implicit. might not be the most practically relevant setting since the implicitly small in n when the sample is not close to the threshold. The claim is made precise in Example [A.1
Speed issues:
value of 33 is exponentially
The arguably more relevant setting is to set the values of and 3 and leave implicit. This is much more challenging since no longer possible to draw the predetermined number of samples and use favourite concentration inequality. We propose new certification procedure using confidence sequences to adaptively (and optimally) deciding how many samples to draw addressing the problem.
Contributions:
We introduce a new, strictly better version of Slopper-Pearson confidence intervals for estimating the class probabilities in Subsection 2. The presented interval is optimal, and thus is the ultimate solution to the canonical statistical estimation of randomized smoothing.
We propose new methods for the certification utilizing confidence sequences (instead of confidence intervals) in Subsection 2.2 This allows to draw just enough samples to certify robustness of a point; greatly decreasing the number of samples needed.
We provide a complete theoretical analysis of the proposed certification procedures. In particular, we provide matching (up to constant factor) lower-bounds and upper- bounds for the width of the respective confidence intervals. We invert the bound and show that the certification procedure has the optimal complexxyy in adaptive estimation task.
We provide empirical validation of the proposed methods confirming the theory.
Notation: Bernoulli random variable with mean p is denoted as B(p) and binomial random variable is B(n, p). Random variables are in capitals (X) and the realizations are lowercase (z). We type sequences in bold and denote X. first elements of x. We write a S if there exists a universal constant C > O such that Cb. If a S b and b S a, then we write b. Iverson bracket [+] evaluates to 1 if & is true and to 0 otherwise.
1.1 Paper organization
First, in Section 2 we introduce randomized smoothing, then, in Subsection 2.1 we introduce Clopper-Pearson confidence intervals, show that they are conservative and propose their improved (optimal) randomized version. In Subsection 2.2 we discuss shorteomings of confidence intervals and introduce confidence sequences and provide lower and upper bounds for their performance. We use the confidence sequences in Section and benchmark them sequential estimation task.
2 Randomized Smoothing
As outlined in Introduction, consider classifier F Rd + y and let the class probabilities under additive noise ip be hep (z)y = P + 5) = y]. Denote the highest probability (breaking ties arbitrarily) class in the original point A = arg max (x), and the second- second-highest probability
class B- arg max A hop (z) Let the corresponding probabilities be PA and pB respectively.
Recalling that (x) = arg max h2p (z) then for a certain function r: jo, 112 + R4 we have
x - I'll < r(PA.PB) = Hz(x)) = Hz')))
of input for model at certain radius

---

This r depends on the smoothing distribution & and the considered norm. For example, if the considered norm is l and y is isotropic Gaussian with standard deviation o, then P(P = (pa) - Φ - (p=)) where Φ- is Gaussian quantile function Cohen et al. (201)). Note that in general, r(::-) is increasing in the first coordinate and decreasing in the second one. The intuition that the larger the value of PA at z, the larger it will be also in the neighborhood of æ;; similarly for
PB. It is common in the literature to use the bound pa $ - PA and thus certify r(PA, 1 PA). We
stick to the convention in the paper and discuss the topic in more details in Appendix B
The crux of the paper lies in the statistical estimation problems for random- ized smoothing. We consider the abstract framework for randomized smoothing, so the proposed techniques can be used as drop-in replacement in all randomized smoothing works with statistical- estimation component (i.e., not in the de-randomized ones such as Levine & Feizi (202I). II). We do not only propose methods that work good empirically, we also provide theoretical analysis suggesting that we solve the problems optimally in a certain strong sense. The main focus is on the following two constructs.
Statistical estimation:
1. Confidence intervals: A standard component of randomized smoothing pipelines is the Clopper-Pearsons confidence interval. is known to be conservative thus, the certification procedures are unnecessarily underestimating the certified robustness. We provide the optimal confidence interval for binomial random variables, resolving this issue completely.
2. Confidence sequences: In the standard randomized smoothing practice, we draw a certain, predetermined, number of samples and then we compute the certified radius on confidence level 1 a. We improve on this by allowing for adaptive estimation procedures employing confidence sequences; We demonstrate the performance in the standard task of adversarial robustness, where we want to decide a point is robust at radius r with type-1 (resp. 2) error rates a (resp. 3) using as few samples as possible.
Literature review of randomized smoothing: The most relevant related works are Horváth et al. (2022): Chen et al. (2022) and they are discussed in Section 3 Here we briefly summarize literature relevant to randomized smoothing in general. The choice of the smoothing distribution ( is crucial decision determined mainly by the threat model with respect to which we want to be robust. For example, if we after certifying& l robustness,
choose uniform distribution in d dd-iimnsionaal Lo ball (Lee et al. 2019: Yang et al. 2020). or better, splitting noise (Levine & Feizi (021). but we do not go into details here. Alternatively. ly, for p- n-norms, p 2 2 one would usually normal distribution Lecuyer et al. (2019); Cohen et al.] (2019). The variance of the distribution based how large perturbations do we allow in our threat model. We refer the reader to Yang jet al. (2020) for a broader discussion on the smoothing distributions. It is possible to use methods in the spirit of randomized smoothing to certify other threat models, such as patch attacks Levine & Feizi (2020) and sparse attack [Bocchvski et al. (2020), which can be readily extended to other modalities. Sometimes, the "smoothing" distribution can be made supported on a small, discrete set and then we can evaluate the expectation exactly, yielding deterministic certification (often called
a d dimensioon
de-randomized smoothing (Levine & Feizi (02T)). See also Kumari et al. (2023) for a survey on randomized smoothing containing examples of when the certification is beyond additive f--norm threat model; even such techniques use the Bernoulli estimation subroutine.
2.1 Confidence Intervals
We do not have access to the class A probability PA and only have to estimate from binomial samples; hence, the name randomized smoothing. Because of the randomness, we can only provide probabilistic statements about the robustness of classifier in the following spirit "with probability at least 1 - robust radius is at least r" for a small a, usually 0.001. This failure probability corresponds to the event of overestimating PAA and we control it with the help of confidence intervals.
The standard choice for calculating the upper confidence interval is the Clopper-Pearson interval, sometimes called exact. Regardless of this pseudonym, it is in reality conservative. In this subsection, we introduce the Clopper-Pearson confidence interval for the mean of binomial random variables, demonstrate its limitations and introduce its (better) randomized version.
"See http://wwww..a........./...oooo.
3

---

Definition 2.1 (Confidence interval for binomials), Let u, v map sample to a real number. They form a (possibly randomized) confidence interval (z) [u(x)) v(z)] with coverage a if for any p E [0, 1] it holds that
Px-Bing)) (p E T(X) 2 1 a.
We will mainly use one-sided confidence intervals; that is, u(-) - 0 (lower confidence interval) or v(-) = 1 (upper confidence interval). When will talk about probability of confidence interval containing the parameter, it will be in the frequentist sense, keeping in mind that confidence intervals provide no guarantees post-hoc for any individual estimation.
Clearly, if (xx = [0, 1] regardless of æ, it will be a valid confidence interval but rather useless; thus aim for short intervals. Idcally it would hold for every p that IP (p & [X)) = a. otherwise, some values are included in the confidence intervals unnecessarily often they can be shortened. In the following we introduce the standard Clopper-Pearson confidence intervals Clopper & Pearson (1934).
Definition 2.2 (Clopper-Peatre) Pearson intervals). One sided upper interval is defined as v(x) 1 and
u((>) (z) inf (P p) 2 2) > a}.
The lower one is defined as u(x) = 0 and
v (x) = sup(p P(B(n, p) S xx) > a).
Amongst the deterministic confidence intervals, they are the shortest possible; however, they are in general conservative. In the binomial case B(n,)), there are only + possible outcomes; and thus only n + possible confidence intervals suggesting that the actual coverage can be a only for at most +1 values of The problem strikingly arises for upper confidence interval for large values of p. When we sample from B(n, p), regardless of the outcome, all values larger than Va are contained in the confidence interval. This is a usual problem in the context of randomized smoothing. leading to sharp drops towards the end of robustness curves. We demonstrate this sub-optimality in the first part of Example A.2 We mitigate this problem by introducing randomness into the confidence intervals. They will still have the desired coverage level 1 a, but will be shorter. Intuitively, we do so by "interpolating" between the deterministic confidence intervals in the spirit of Stevens (950)..
Definition 2.3 (Randomized Clopper-Pearson intervals). Let W be uniform on the interval [o, 1]. The randomized one sided upper interval is defined as v. (x) = 1 u, (x) (z, W) where
(2, w) inf {pl P P (2, p) > 2) + wPP (B(n. p) = x) > a).
The lower one is defined as u, (x) 0 and oy (2) (1, W) where
(1, w) sup (B(( p) x) wP (B( = z) a}.
Proposition 2.4. Randomized Clopper-Pearson interval (LecP) have coverage exactly 1 - Fur- thermore, for any confidence interval I at level a, and any p 2 q E [0, 1] it holds that
PP PxxBBlnp) (q E T(X))= 2 P E Lcr(X)).
The proof is in the Appendix D and we remark that the interval can be efficiently found by binary search. Proposition 2.4 implies that the randomized Clopper- Pearson bounds are optimal and all the other confidence intervals for binomial random variables are more conservative. It remains to demonstrate the advantage of the randomized confidence intervals. We refer to Figure | for the comparison of the randomized and deterministic Clopper-Pearson confidence intervals and how they affect the robustness. We note that the most significant difference is towards the high values of and for certification functions such that lim r(p) = oc, such as when smoothing with normal distribution. This explains the common sharp drop by the end of the robustness curve.
Width of confidence intervals: For the simplicity of exposition, let the width of confidence interval at level 1 a with n samples be x /log 1/a)/n. This way, we hide the dependency on p into x. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates /p(1- p) log(1 (gg(1/o) (1/a)/n (when nyp(1 - p) > 1) and log(1/a:// (when np(1 -p) )) x 1). Our algorithms capture the correct scaling of the confidence intervals. See Boucheron et al. (2013) and the discussion on Bennett's 's incquality which captures the correct rates for Bernoulli mean estimation.

---

1.0
0.0010
robust accuracy
0.8
0.6
actual
0.0005
1000
Clopper- Pepperr
n 10000
0.2
Randomized Glopper-Pearson
n 100000
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.1
0.2
0.3
0.4
0.5
robust radius
Figure 1: left: Comparison of coverages of confidence intervals for the mean estimation of (3100, when := 0.001. Note that for > Va 0.93, the coverage 1. right: Comparison of 62- robustness curves with the standard (dashed) or the randomized (solid) Clopper-Pearson bounds CIFAR-10 dataset under the standard setting. The experimental details are in Appendix
2.2 Confidence Sequences
Limitations confidence intervals: In order compute the confidence intervals presented the previous subsection, we need to collect samples and then run an estimation procedure once which brings certain limitations. Consider the following two scenarios: (1) It might be the case that do not need all 100 000 samples and after only 10 it would be enough for our purposes because could already conclude that the point cannot be certified here; thus, we wasted 990 samples. (2) Alternatively, we could see that even 10 samples are not enough, and we need to draw more samples. However, we have already spent our failure budget a, so we cannot even carry another test at all.
This motivates the introduction of confidence sequences. They generalize confidence intervals in the way that they provide confidence interval after every received sample such that we control the probability that the underlying parameter is contained in all the confidence intervals simultaneously.
Definition 2.5 (Confidence sequence). Let {u, et h be mappings from sequence of observations real number. They form confidence sequence (xx,)) [x,(x.)), (x.)) for all with confidence level 1 if
P (p T(X.),, 1)
for any p E [0, 1]. where X is an infinite sequence of Bernoulli random variables B(p).
Remark 2.6. Since we want the estimated parameter to be contained in all the confidence intervals simultaneously, will have by convention that /t+ (2..+1) Ie(x.)).
To simplify presentation, would consider the symmetric ones; i.e., those where we consider the two possible failures when we overestimate or underestimate the mean to be equal. However, they will be constructed from two one-sided bounds, so the generalization straightforward and will not be discussed.
Related work: The construction of confidence sequences based on union bound employs the doubling trick which widely used online learning to convert Exed-horizon algorithms to anytime algorithms. In this direction, we refer to Mnih et al. (2008) as the direct predecessor of this work, where they used similar techniques but did not explicitly construct confidence sequences. In confidence sequence literature, this technique is similar to stitching of Howard et al. (2020). The stitched confidence intervals of Howard et al. (2020) are generally shorter by a small constant factor, but the analysis and generalization become complicated, contrasting with approach.
The construction based on betting is in the spirit Orabona Jun 2023) (the reference contains an excellent survey on the topic). The difference mainly lies in the fact that we are interested in Bernoulli random variables, which allows us use specialized tools at places, as opposed to the referred work, which considers bounded random variables. As an analogy to confidence intervals, the previous work constructed Bernstein-type inequalities, while we constructed Clopper-Pearsee Peaneer-Paroo--liiie bounds. In Ryu & Bhatt (2024), the authors improved over Orabona & Jun (023) in certain aspects the case of (0, 1 -vallue random variables. Notably, in Section 3, they considered the special case {0, 1 -alued random variables and their results greatly overlapping those in Section 2.4
5

---

2.3 Union bound confidence sequence
natural way how to extend the confidence intervals to confidence sequences is to construct a confidence interval at every time step and use union bound to control the total failure probability. In the following, we first show that a naive application of this approach asymptotically suboptimal, and then we provide way how construct optimal confidence intervals in certain strong sense.
Intuition the width of confidence sequences: For any random variable with finite variance, the optimal width of the confidence interval for the mean parameter scales / log(( 1/ with the increasing number of samples t at confidence level the other hand, it is well known that the width of the optimal confidence sequence scales as /(lo(11/ [llog(1/ov] /o) + log log 1)/l (199T). naive use union bound, computing a confidence interval using failure probability at time step 02 ac for some and 7 -1 such that Ei= a4 = a yields confidence sequence whose width scales as Vlog(1/a)) Re (log(()) + log(1/a))/L. We cannot choose any monotonous or schedule decaying slower because even for = 1 we still keep the log factor while the sum Σi= dc diverges.
a Lugosi & Mendelson (2019). On
increases due to the law of iterated logarithms Ledoux & Talagrand
Now consider non- non-monotonous schedules of at, two key ideas follows. (1) In order to have the optimal rate (o,) = log(1/a) + log log we need x a/ log t. Clearly, if this holds for all t, then >x= a₁ diverges. (2) confidence interval at time is also valid confidence interval for all l' >> L. Furthermore, if is not much larger than then it may still asymptotically have the optimal width up to multiplicative constant. Thus, updating the confidence sequence when is a power of (say) 2 result in the optimal width. This reasoning is formalized in the following theorem.
Theorem 2.7. Fix a 0. Consider sequence
it 2 for integer k
k(++T
otherwise.
Then Algorithm 7 produces a confidence sequence at level a of the following width which is attained in the worst case
Et S log(1/a) + log ltg(t)
where E, is - L at time f, and the confidence intervals are randomized Clopper-Pearson intervals.
The proof is in Appendix E. We remark that the statement of Theorem 2.7 prioritizes simplicity over its full generality. The generalization to other schedules of or, from the second bullet point as described in the previous paragraph is routine and described in detail in Appendix C.2
Corollary 2.8. The asymptotic rate 2f is optimal due to haw-offiteruted-llggriite (Ledoux & Talagrand 199]) and even in the finite sample regime due to Balsubramani [Theo)[h 2].
2.4 Confidence sequences based on betting
A recent alternative approach to confidence sequences is based on hypothetical betting game. For the illustration, consider fair sequential game; e.g., sequentially betting on outcomes of a coin. If guess the outcome correctly, in expectation, our wealth stays the same. On the other hand, if the game is not fair and the coin is biased, we can win money. For example, if the true head-probayility is 0.51, we start increasing our wealth in an exponential fashion, see Example A.3] thus, if we win lots of money, we can conclude that the game is not fair. We instantiate betting game for every possible mean 0 S p that would be fair if the true mean is Then we observe samples of the random variable and as soon as we win enough money, we drop that particular p from the confidence sequence. To make things formal, we introduce the necessary concepts from probability theory. The evolution of our wealth throughout fair game is modeled by martingales"] sequences of random variables for which, independently of the past, the expected value stays the same.
win the staked amount, otherwise we lose it. If the coin is fair,
It would be historically accurate say that martingales actually model fair games.

---

Definition 2.9 (Martingale), A sequence of random variables W1, 2,,.. is called martingale if for any integer 0. we have (((,), < oo and have B(Wn+ [W,,- W.) x W,, then the sequence is called a supermartingale.
W,) W,. we instead
Algorithm 1 Union-Boute Bound Confidence Sequence Algorithm 2 Betting Confidence Sequence
i, H,H,K,,U L, + +,,00,,UU 0,0,0,0,1
LOGQ, 6, H1 U + 0,0,0,0,1
loop
loop
Obtain random æ
- (H + 1/2)/(t
+ H
Obtain random
14-+4]
H
if = 2 then
1-t+1
K f K+1
LOGQ + LOGQ + log + (1-x) log(1 - ④)
0₂ 4 ma Low CoowConlt t, at) Low
a/(((K(( 1))
LOGP(p) == H log(p)
H) log(1 p)
Ip + - - log(1/a)}
U min,, UppConfInt(H)) (H, o
L max L, min
end if
U + min max lp
end loop
end loop
In the coin-betting example. W1. W2,... is martingale where Wn, represents our wealth after playing the game for n rounds. We stress that W, 2 0 for all > By convention, we will also have W1 1. We further need a time-un generalization of Markov's 's inequality.
Proposition 2.10 (Ville's inequality Durrett 2010)). Let Wi, W be a non-negative supermartin- gale. then for any real a 0
E [W]]
P sup Wn 2 n21
S
Thus, whenever we play a game and earn a lot, we can with high probability rule out the possibility that the game is fair. So far, this still an abstract framework. We have yet to design the betting game and the betting strategy and describe how to run the infinite number of games.
Betting game: Lef < < 1. Consider a coin-betting game where we win 1/p (resp. 1/(1 p))
multiple of the staked amount if we correctly predicted heads (resp. tails). If the underlying heads probability is p, then regardless our bet- expectation we still have the same amount of money; thus, this game is fair. We identify heads and tails with outcomes 1, 0 respectively.
Betting strategy: We deconstruct the betting strategy into the two sub-tasks: (1) If we know the underlying heads probability, can design the optimal betting strategy for any criterion. (2) Estimate the heads probability. First sub-task: Let p define the betting game from the previous paragraph and q be the true heads probability: Optimally, bet q-fraction of wealth to heads and I fraction to tails. maximizes the expected log-wealth, or equivalently, the expected growth-rate of our wealth and is also known the Kelly Criterion. This is known to be optimal for the adaptive estimation task, see Wald (1947) under the name sequential-probe probability ratiootts- (SPRT). One might have expected the optimal criterion optimize to be the expected wealth; however, the betting strategy maximizing the expected wealth suggest to bet all the money on one of the outcomes. This strategy, however, leads eventual bankruptey almost surely and is not recommended in this context. Second sub-task: A natural choice is to use the running sample mean of the observations as the estimator of q. Unfortunately, this estimator would be either 0 after the first observations, so we go bankrupt whenever the observed sequence contains both outcomes. Thus, we use "regularized" sample mean and after observing I/ times heads in sequence of length t, we estimate q = (Hl + 0.5) (t (t+ This is the MAP estimate of the mean with Beta 1 12, 1/2) prior and is known as Krichevsky-Trofime estimator (Cesa- BiaaaBi & Lugosi| (2006) Section 9.7), Krichevsky Trofimvv (I98I) and is proven to be successful for building confidence sequences beyond the Bernoulii case Orabona & Jun (2023).
Parallel betting games: We have described a betting game for certain p and betting strategy.
Employing Ville's 's inequality we can possibly reject the hypothesis that the true sampling distribution
For simplicity of exposition, similar arguments hold when E {0, 1).
7

---

follows p. However, we need to run the game for all values of E [0, 1] and after every observation report the smallest interval containing all the values of p that were not rejected so far. This is clearly impossible to do explicitly, but it turns out that the non-rejected values of form an interval and we can use binary search twice to find the end-points of the interval. This is non-trivial result and generally does not need to hold for confidence intervals constructed by betting. The first key observations is that the betting strategy does not depend on p. so we can "play the game" just once. The second observation is that the resulting wealth is convex in p. To see why, let d, (resp. Z+) be our estimate of q (resp. the coin-toss outcome, for brevity 1/0 corresponds to heads/tails respectively and = Er= Tr), then our log-wealth at time can be written as a function of p.
log (p(p) log II
1 9- Tr log((r) + (1 - x+) log(1 (-) -H log(p) (1- H) log(1 - p)
gr p
Z7
(1
1 1-
1 -
LoGQ
LoGP(p)
Therefore, at every time-step, we can compute the interval of values of p for which the betting game has not concluded yet and thus form the current confidence interval. The proof is in Appendix
Theorem 2.11. Algorithm producess a valid confidence sequence at confidence level 1 - a, where we interpret the interval [L, U] at iteration T of the algorithm as the confidence interval time I with width at most (which is atlained in the worst case):
log(1/a) + log(t)
Ex S
t.
This is not asympiotically optimal; still, empirically it performs well, and the same techniques can be used to obtain a confidence sequence that follows wwt-off-terated-lggrittte Orabona & Jun (2023). We present a comparison of the confidence sequences in Figure 2 and conclude this subsection by an implementation remark.
Remark 2.12. Wealth (x:;) does not depend on the order of X,,, so we write as W (h, t). meaning wealth after observing heads in the first t tosses. Now, for every time t, we can compute what is the minimal number of observed 1 (heads) (call it Ht)) so that is outside of the lower-confidence interval. H(t is clearly decceascgg in t; also, W(h,t) t)) be easily computed from W(h 1,, t) and from Whh, 1-1) in constant time. The whole dynamic programming approach can be summarized in the following scheme which is repeatedly executed starting from h 0,4
If Wf,,,, 2 : H() == h 1 == + 1, compute Whh,4 1 + 1)
Else: = + compute W W(h + 1,
Both lines are executed in constant time. Also, we start from W(O, 0) and h, < N + Executing a line, either h t increases and thus to compute the thresholds for sequence length up to N, we need to execute at most 2N lines of the scheme. We note that for the simplicity, we did not handle the case when W (h, t) < 1/a. In that case we would just set (tt + and increase t.
3 Experiments
Now we shall provide experimental evidence for the performance of the proposed methods. We benchmark the confidence sequences on the Sequential decision making task, where we try to certify certain radius at given confidence level with as few samples as possible; the definition that follows is general beyond randomized smoothing. We emphasize that this setting of certifying certain radius is by far the most common one the robustness literature. We stress that the comparison of the robustness curves (c.g., as in Figure T is vacuous, since in the adaptive task, we do not spend samples to improve the robustness curves, beyond the certified level.
Definition 3.1 (Sequential decision making task). Let 1 S p.g S 1 and only p being known. Receive samples from B(g). After every sample, either halt and declare that p > q, P < q, or request another sample. The task is to minimize the number of samples while being wrong with frequency at-most

---

10
# samples
10"
width of cont.
10
10
10
10
1.00
10a
Betting CS UBnd-CS
cont. seq:
0.75
suboplimallit
0.50
Ideal
10'
Adaptive
0.25
0.00
10
10
102
10 10f
0.0
0.2
0.4
0.6
0.8 1.0
Figure 2: left: Comparison of widths of confidence sequences for the mean of Bernoulli B(0.1) with = 0.001. The width is on top and the actual confidence sequence on the bottom. In the notation of Algorithms I and 2 the sequence of U L is in the top figure, while both sequences U and L are in the bottom higure. Note the log-scale for t (and width on top). right Instantiation of Task 3.1 The goal is to decide if p 0.91 (vertical magenta line) or not with 0.001. On top the numbers of samples requested for the individual methods averaged over 1000 trials for 51 equally spaced values of p [0, 1]: on the bottom is the relative suboptimality of the individual methods: i.c., how many times more samples did they request compared to the ideal method. Note log scales on the y- ya-i... methods: UBnd-CS and Betting-CS are from Algorithm Tan 2 respectively. Adaptive is from Horváth et al. (2022). The ideal is the unattainable lower- for the two tasks. On the LHS, is confidence interval on level 1 a computed independently every time step. On the RHS, is SPRT knowing both q which is optimal due to Wald 1947).
3.1 Related work
We identified Horváth et al. (2022) as the most relevant work. They distinguish between samples for which predetermined radius can be certified, and the samples for which it cannot. They use values 1i <.. < n, ([10², 10a, 10a, 1.2 10 sequentially as the number of samples. They try to certify radius with nı samples; if it fails, then they try n2 samples etc. They employ Bonferroni correction (union bound) and every sub-certification is allowed to fail with probability only a The key differences (details in Appendix(C.2.1
method that (1) It always abstains for hard tasks. (2) Splitting the a budget evenly degrades performance for small n. (3) method is only a heuristics. See Figure 5 and Tables 1 3
For the empirical comparison.
Another relevant work Chen et al. (2022). Here, the certification split in two phases. (1) Mean crudely estimated. (2) The crude estimate selects the number of samples drawn that the decrease (either multiplicative or absolute) in the certified radius heuristically approximately at most predetermined constant. We note that this heuristic for distributing samples can be made rigorous in certain sense (see Dagum et al. (995)). This is trivial for confidence sequences, as one can stop the estimation only (instead of just heuristic). this sense, we see our methods to be more general. We benchmark this in Table 2
they short enough and solve the task of Chen al. (2022) with guarantees
The works Seferis et al. (2033: Ugare et al. (2024) also address the speed issues of randomized smoothing. however, they are orthogonal to our directions. In particular, Ugare et al. (2024) uses an auxiliary network for which the certification is faster and transfer the certificates to the original model. Seferis et al. (2023) observes that few samples are sufficient for non-trivial certificates.
Conclusion
In this paper, we investigated the statistical estimation procedures related to randomized smoothing and improved them in the following two ways: (1) We have provided strictly stronger version of confidence intervals than the Clopper-Pearson confidence interval. (2) We have developed confidence
sequences for sequential estimation in the framework of randomized smoothing, which will greatly

---

r=0.5
1=1.25
F=2
Adaptive Horváth et al. (022)
1976 41
3593 + 574
4623 + 47
Betting CS
531 + 157
2169 257
2130 + 339
Union bound CS
635 = 157
2557 + 234
2670 + 271
Adaptive Horváth al. 2022)
0.13 0.006s
0.23 0.036s
0.3 4 0.003s
Betting CS
0.05 + 0.012s
0.17 0.019s
0.17 + 0.02s
Union bound CS
0.05 + 0.006s
0.19 + 0.018s
0.21 0.02s
Table I: Comparison of the average number of samples (resp. time) needed to decide if a point is
certifiably robust with given radius. Cifar10, E,, details are in Appendix C.2.1
0.01
0.02
0.03
UB-CS
197 628
49 198
21 513
Betting-CS
199 771
47 215
20 918
Horvath
768 560
94 900
81 080
Table 2: We run the confidence sequences until the width is smaller than on (both sided) confidence
certify certain radius knowing that the true probability is most larger. We used the same network as for the le experiment Table (WideResnet-40 ( on CIFARIO, 1). We report the average number of samples required over 500 images.
level 0.999. That way
reduce the number of samples needed for adaptive estimation tasks. Additionally, we provided matching algorithmic upper bounds with problem lower bounds for the relevant statistical estimation task.
5 Broader Impact Statement
We hope that this paper enlarges the interest in statistical estimation within the ML community,
Acknowledgments
The author was supported by the DFG Cluster of Excellence "Machine Learning New Perspectives for Science", EXC 2064/1, project number 390727645 and is thankful for the support of Open Philanthropy.
References
Balsubramani, A. Sharp finite-time iterated-logarithm martingale concentration. arXiv preprint arXiv:1405.2639, 2014.
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šındić, N., Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. In ECML PKDD, 2013.
Bojchevski, A., Gasteiger, J., and Günnemann, S. Efficient robustness certificates for discrete data: Sparsity- aware randomized smoothing for graphs, images and more. In ICML, 2020.
Boucheron, S., Lugosi, G., and Massart, P. Concentration incqualities. 2013.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Chen, R., Li, J., Yan, J., Li, P., and Sheng, B. Input-specific robustness certification for randomized smoothing. AAAI, 2022.
and Clopper, C. and Pearson, F. S. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 1934.
Cohen, J., Rosenfeld, E.,, and Kolter, Certified adversarial robustness via randomized smoothing. In ICML, 2019.
10

---

Dagum, P., Karp, R., Luby, M., and Ross, S. An optimal algorithm for monte carlo estimation. In FOCS, 1995.
Durrett, R. Probability: Theory and Examples. Cambridge Series in Statistical and Probabilistic Mathematics, 2010.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. JCLR, 2014.
Horväth, M. Z.,, Müller, M. N., Fischer, M., and Vechev, M. Boosting randomized smoothing with variance reduced classifiers. ICLR, 2022.
Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys, 2020.
Krichevsky, R. and Trofimov, V. The performance of universal encoding. IEEE Transactions Information Theory, 1981.
Kumari, A., Bhardwaj. D., Jindal, S., and Gupta, S. Trust, but verify: A survey of randomized smoothing techniques. arXiv preprint arXiv:2312.12608, 2023.
Lecuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. Certified robustness to adversarial examples with differential privacy. In S&P, 2019.
Ledoux, M. and Talagrand, M. The Law of the Iterated Logarithm, pp. 196-234. 1991.
Lee, G.-H., Yuan, Y., Chang, S., and Jaakkola, T. Tight certificates of adversarial robustness for randomly smoothed classifiers. NeurIPS, 2019.
Levine, A. and Feizi, S. (de) randomized smoothing for certifiable defense against patch attacks. NeurIPS, 2020.
Levine, J. and Feizi, S. Improved, deterministic smoothing for & certified robustness. In ICML, 2021.
Li, L., Xie, T., and Li, B. Sok: Certified robustness for deep neural networks. In S&P. IEEE, 2023,
Lugosi, G. and Mendelson, S. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 2019.
Madry, A., Makelov, A., Schmidt, I.., Tsipras, D., and Vladu, A. Towards deep learning models resistant adversarial attacks. In ICLR, 2018.
Mnih, V., Szepesvári, C., and Audibert, J.-Y. Empirical bernstein stopping. In Proceedings of the 25th international conference Machine learming, pp. 672-679, 2008.
Orabona, modern introduction to online learning. arXiv preprint arXiv: 1912. 19221131...11.... 2019.
Orabona, F. and Jun, K.-S Tight concentrations and confidence sequences from the regret of universal portfolio. IEEE Transactions on Information Theory, 2023.
Ryu, J. J. and Bhatt, A. On confidence sequences for bounded random processes via universal gambling strategies. IEEE Transactions Information Theory, 2024.
Ryu, J. and Wornell, G. W. Gambling- confidence sequences for bounded random vectors, 2024. URL //tp///r/vvvvv//a///a/ org/ abw.abb./.22.. 03683
Salman, H., Li, J., Razenshteyn, I,, Zhang. Zhang, H., Bubeck, S., and Yang, G. Provably robust deep learning via adversarially trained smoothed classifiers. In NewrIPS, 2019.
Seferis, E.,, Burton, S., and Kollias, S. Randomized smoothing (almost) in real time? In ICMLw The Many Facets of Preference-Bane Based Learning, 2023.
Stevens, W. L. Fiducial limits of the parameter of discontinuous distribution. Biometrika, 1950.

---

Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. Intriguing properties of neural networks. ICLR, 2014.
Ugare, S., Suresh, T., Banerjee, D., Singh, G., and Misailovic, S, Incremental randomized smoothing certification. In ICLR, 2024.
Voracek, V. and Hein, M. Improving 11-certified robustness via randomized smoothing by leveraging box constraints. International Conference on Machine Learning, 2023.
Wald, A. Sequential analysis. 1947.
Yang, G., Duan, T., Hu, J. E., Salman, H., Razenshteyn, I,, and Li, J. Randomized smoothing of all shapes and sizes, In JCML, 2020.
12

---

0.05
actual
Clopper-Peee Pearson Randomized Clopper-Pearsee
0.025
0.01
0.1
0.224
Figure 3: Actual coverages for (randomized) Clopper-Pearsee confidence intervals for B(2,p).
A Deferred examples
Example A.1. [implicit type-2 error is exponentially small] Let sample from X B(p) to decide the mean smaller or larger than p - e using n = 100 000 samples. We use Hoeffdings" inequality to bound the probability that p is incorrectly estimated be lower than i...
PP
Σ
X; S B[X] -
< 2e-2ne
Considering to be constant, we see that this probability scales e For example, when the true probability is 0.5 and we want to decide it is smaller or larger than 0.4, already 1000 samples make the probability of incorrectly decision to be roughly 2 10-9.
Example A.2. (suboptimality of Clopper-Pearsop confidence interval and optimality of the random- ized one] Recall that the coverage for p the probability that p included in the confidence interval when it is the true parameter and a is the allowed type-1 error and 1 should be the coverage. Con- sider samples from ~ ((2, p) and a 0.05. By definition, the Clopper-Pearson upper intervals are [0, 1]. 00.025, 1). [0.224, 1] for observations x = 0, respectively. Coverage for p 0.224 is 0.95 because the event that p is outside of the confidence interval is (PX e {0, 1)) = - p² x 0.95. 0.1 is P(X {0, 1}) 1 p² 0.99 and for all 0.224 1; see Figure A for the coverages. Now we turn on to the randomized Ktopper-Pearson interval for p 0.5. Recall the definition of the upper interval,
On the other hand, coverage for
(2, w) = in P(B(n, p) > x) + wBP(B(n x) a).
The randomized confidence interval for some value interpolates between the confidence intervals for and + when Thus, when * 2. 0.224 is always in the confidence interval (this happens with probability p² = 0.75. Otherwise, we solve the following for w (because we set 2, 2):
P(B(2,p) > wD = 2) = a 0 + p"u =
= =app².
Thus, p 0.224 is not contained in the randomized confidence interval iff W < a/p² and X 2. Since these random variables are independent, the resulting probability is IPWW < 0.2)P(X = = a/p² p2 a, as desired.
Example A.3 (Exponential increase of wealth for biased coin). For simplicity of exposition assume that the coin falls on head 51 times from 100 tosses. To get a high probability statement straightforward. Let us always bet 0.51 fraction of our money to heads and 0.49 tails (equivalently, just bet 0.02 of the money to the heads). If we win, we win 2% of our money, otherwise we lose 2%. Then, our wealth after 100 tosses will 1.0251 1.02 49 1.04. Thus. every 100 tosses we multiply our wealth by the factor of 1.04 which is the desired exponential function.
B Binary or multiclass certification
Although all the standard benchmarking datasets for randomized smoothing are multiclass (cifar10 and imagenet), the commonly used randomized smoothing certification protocol is for the binary
13

---

multiclass 00000
robust accuracy
0.5
multiclass 2 0.5
multiclass 2 -0.999 binary
0.3
0.2
0.1
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
robust radius
Figure 4: Comparison of the robustness curves for binary and multiclass certification. In the binary case, all the failure budget a 0.001 was spent on controlling the top-1 class probability. In the multiclass setting, we spend À fraction of the budget in bounding pa and the remaining 1 1 part on bounding pn. Note that this has no significant effect. The average certified radius for binary certification is 0.50, while for the multiclass it is 0.61. The experimental details are in Appendix The only difference that now o
setting, where we certify class against all the other classes merged in super class. In that case, the certification is done using the formula r(A.. PA), where we have to guarantee that PA 2 P.a at confidence level at least - a. The alternative to use multiclass certification; here, certification is done via formula rfAA, pn) ensuring that PΛ 2 PA and pn < in at the same time at confidence level at least a. The difference between these two bounds naturally manifests in the regime when PA is small. Strikingly, when PA 0.5, the binary certification approach cannot certify any robustness, while the multiclass one possible can. The cost for the multiclass procedure is only that we have divide the failure budget between the the two estimation procedures. This is usually insignificant. In the l (and thus for case), the role of a is rather minor, see Cohen et al. (2019) Figure 8. This is even more pronounced in the & case. Here a plays absolutely negligible role in the resulting certified radius, see Voracek & Hein (2023), Subsection 2.7 for the discussion and Figures 4. 6. While this might be known many, believe that some readers may benefit from reading this argument. We demonstrate the difference in certification power in Figure 4 This multiclass certification fits in our setting effortlessly. We for pn- We do not even need to know рB and we can run for all of them at the same time. This means, that not need to be the actual runner-up class, but since it was possibly observed more times than the actual runner-up class, it will also provide wider confidence interval, the statistical estimation still correct.
confidence sequence for PA: and another
it only for the second most observed class. This second most observed class does
C Experimental details
C.1 Figure
The model in Figure I is the pretrained cifar10 model (Exactly the same model/setting from the example in README) of Salman et al.] (2019). mmoothingg-advrssarii for lg robustness. We set a 0.001 as usual and skip every 20 images of the test dataset (using 500 images, the standard practice).
in particular, it was Res- smoothed with Gaussian noise 0..1
C.2 Parameters of union bound confidence sequences
We were enlarging the sample size by a factor of B 1.1 between estimations (that is, the condition
2 is replaced by 3K = 1.1 and our schedule ca = 5a/((t + 4)(1 + 5)) The method is not sensitive to the choice of hyperparameters, see 5 In fact, the hyperparameters 83 should be selected based on what is the "interesting" regime. There an inherent tradeoff between a good asymptotical performance (8, 1) and low-sample performance (8, > 1). This is confirmed in
14

---

106
> = 1.05 =111
y = 1.05 #1.5
10$
1.05 -2
7-1.05
8-1.1 -1.11
3-1.5
10*
required samples
7-1.1 -3
-=1.50=1111
0
10a
p=
7-2
10
=12
2=20=2
=
10
used
10
0.0
0.2
0.4
0.6
0.8
1.0
p
Figure Samples needed for the adaptive estimation task as in Figure 2 for different hyperparameters. 3 is the factor by which we enlarge the sample size before computing new confidence interval, is the scaling of a as described in the main text. L.c., k-th estimation will have ag k normalization constant such that k= Clt
pe where e the
a.
Figure The width the confidence interval scales as:
B(log(1/6 1(7 1)) + (og(1/a) + y log log 1)
This is because E
ag ال1=1ه and x 8h, then log Plugging in these
identites in log(ae) and remembering that the confidence interval recomputed only after elarging t the sample size by 3 factor, then for time the actual t we use in the formula can be as small as t/B.
C.2.1 Comparison with Horváth et al. (0022)
The method from Horváth al. (0222) uses a finite collection of values of n. = 71 < n4 for which the confidence intervals are computed. A direct consequence is that the hard examples for which more than n, samples are needed cannot be certified. Additionally, due to Bonferroni correction, with large s, the term log(s/a) appearing in the confidence interval becomes large compared to for small values t (compare with the polynomial scaling that we propose where this not the case). Consider n, ni. then the width of the confidence interval scales as (not considering the regime when > n, where the width is constant):
Ri (log log 1/a)
In particular, when we want to have confidence sequence up n, N samples, then the width becomes
VN s + log 1/a)
t
and we either pay the fact that we have large differences between the steps (VaN), or for the fact that we have lot of steps (log(s)) which is detrimental for small values of t.
15

---

C.3 Details for 13
We had WideResNet-40-22 for CIFAR-10 trained for 120 epochs with SGD and learning rate 0.1, Nesterov momentum 0.9, weight decay 0.0001 and cosine annealing. batch size 64. The loss was the standard, ausse-eugeeeted training using the same noise for the certification. We either used Gaussian smoothing for &2 robustness of uniform in foo box for l robustness.
For the certification used batch size 100 (natural for Horváth al. (2022)) For method, had a mixed batch of data points so the data points for which we have the least amount of samples and are not decided yet are put in the batch.
D Proof of Proposition 2.4
Proof. We show for the upper interval, the lower is analogical. First, we note that f(p)
P(B(n.p) 2 a) is non-decreasing in for any a; Thus, My (x) S p if and only if (B) >
2) + w:P(B((n,)) x) > a. Now, we show that P( (X) S p) 1 a for
[n. p). To
shorten the notation, let 01 = P(X 2 a) and 02 = P(X X a) for such a that a S S 02. We
have
(X) p) = ((, S X < a) <a)
+ { =p|x=o)P((' a)P(X=
+ < a)P(X > a),
which we evaluate to (X) < p) (1 [1-1a)= + (01 a2) < X a) +
We note that given the event X = a. it holds u, p = + W(a1 - a2) > a, so
(X),(X) 1 p X = = P(02 + W(a1 02) > = W 8002
a- Overall,
(X) p) = (1-a)))))) + (a1 - 02) -- = =1-a.
The second part the statement follows from Neymann- Neymann-Pearson lemma. Concretely, we consider the following binary hypothesis testing problem from sample B(n, 0), and we decide if 0 = or 0 g. Both confidence intervals has size a and can be interpreted as binary tests - juutt return the indicator function of q [xx). the likelihood ratio test, which is implemented by the randomized Clopper-Pearsee interval.
Pearson lemma states that the (unique) uniformly most powerful test
E Proof of Theorem 2.7
Proof of Theorem 2.7 First, o k(k+Tj a; thus, by union bound, all the computed confidence intervals are simultaneously correct confidence level 1 a. Next we show that the width as claimed. When t = 2º, we directly have from Hoeffding's 's inequality
log
log + logt
1
Otherwise, we would use a confidence interval of some previous 1' such that L' < < 21' with width
log + log log
log + logtog
t
Noting that Clopper-Pearson 's confidence intreval is shorter than Hoeffding's finishes the proof.
F Proof of Theorem 2.11
Proof. First we verify that everything in the algorithm well defined and the logarithms take positive inputs. Now let W. exp
'LoGO, where subscript & denotes iteration of the algorithm. We show L.GP;
that it is martingale when X ~ B(p) for 0 < p < 1. In that case,
qt
x
1 qt
1 1- = -Wa11- 9 + (1 p) - p = W p
1-x7
Ex [ = Wx-EE
1-P1 p
16

---

r=0.5
1=1.25
F=2
Adaptive Horváth et al. (022)
1976 41
3593 + 574
4623 + 47
Betting CS
531 + 157
2169 257
2130 + 339
Union bound CS
635 = 157
2557 + 234
2670 + 271
Adaptive Horváth al. 2022)
0.13 0.006s
0.23 0.036s
0.3 4 0.003s
Betting CS
0.05 + 0.012s
0.17 + 0.019s
0.17 + 0.02s
Union bound CS
0.05 - 0.006s
0.19 0.018s
0.21 0.02s
r=0.5
r=
r=2
Adaptive Horváth et al.
2022)
4150 523
2266 + 640
4760 E 131
Betting CS
2206 = 150
1665 + 84
3932 + 199
Union bound C
2665 = 78
1674
3717 + 361
Adaptive Horváth et al. 2022)
0.27 + 0.04s
0.15 0.04s
0.3 + 0.009s
Betting CS
0.17 0.011s
0.13 0.006s
0.3 0.014s
Union bound CS
0.2
0.13 + 0.002s
0.28 + 0.02s
Table 3: Comparison of the average number of sample needed to decide if the point is certifiably
robust with given radius in the top. The time needed is on the bottom. The upper table was in the main paper, the bottom one is the exact same experiment but with a retrained model for &g robustness robustness with o
r=55
r=
r=1.5
Adaptive Horváth al. (2022)
423 + 38
3520 = 82
3823 + 127
Betting CS
138 + 28
2680 + 221
3007 + 122
Union bound CS
150 +
2926 + 18
3144 + 347
Adaptive Horväth et al. 2022)
0.04 0.006s
0.23 - 0.006s
0.25 1 0.009s
Betting CS
2
0.19 + 0.002s
0.21 0.017s
0.23 0.01s
Union bound CS
0.016 + 0.006s
0.22 + 0.009s
0.25 0.03s
r=0.5
r=1 4790
1=1.5
Adaptive Horváth al. (2022)
1370 = 596
Betting CS
592 = 94
4055 + 459
5822 + 81
Union bound CS
806 + 113
4327 + 106
5795 + 321
Adaptive Horváth et al. (2022)
0.1 = 0.04s
0.30 0.003s
0.53 0.05s
Betting CS
0.05 0.007s
0.44 + 0.005s
Union bound CS
0.06 + 0.008s
0.33 0.008s
0.44 0.02s
Table 4: Comparison of the average number samples needed to decide if the point is certifiably
robust with given radius in the top. The time needed is the bottom. top and bottom are again the exact same experiment but with a retrained model for ε robustness with 1.
p p E 1). then we would have a deterministic sequence and W, S W,- Thus, W, is a supermartingale. is also output of the exponential function and is non-negative. Therefore, the assumptions of Ville's inequality are satisfied and can be applied. Whenever is excluded from the confidence interval, it happened that LOGQ, LOGP, 2 (og(1/a), or equivalently, W, 2 1/a which can only happen with probability and it is thus a valid confidence sequence. We also recall that in the main text we have shown that 4p a sub-level set of convex function and thus convex and can be efficiently found by binary search. The width of the confidence interval follows from the standard regret bounds for the Krichevsky-Trofie Section 9.7: Kricheicyyvkk & Trofimov (1981). The result then follows from Orabonal (2019), Subsection 12.7. It was also derived in Ryu & Bhatt (2024); see Ryu Wornell (2024) for generalization to vector-valued random variables.
estimator CemaattorCes----i Bianchi & Lugosi| (2006) C
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We promised treatment of statistical estimation problems for randomized smoothing and we delivered them.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: We think we provided fair discussion of the results. For the provided theorems, the assumptions are reasonable. The experiments seem convincing to us.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [Yes]
Justification: We provide proofs in the appendices although the main paper should be enough to understand them.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide details in C However, some of the experiments are heavily dependent on random seed so they are unlikely to be reproduced. The important thing there are not the absolute results, but the relative performance of the methods which should be robust.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-souree models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
19

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
In linked repo.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/publicc/ /usee/uuddd///eeeubbiiiii
Codeeubmiiiie iattuubbiisiiiiii ssisssoicccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
In C. also in the repository.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provided averages over runs and reported standard deviations where appropriate.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
20

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The total compute is under day on a single GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: just yes
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: yes
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
21

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: no need.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the code used, but not the datasets it is standard (cifar)
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
22

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: na
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: na
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: na
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "3UwgY7su9U", "reviewer": "Reviewer_mvjJ", "summary": "They study the task of certified robustness, i.e. they need to decide if a point is robust at a certain radius or not, using as few samples as possible while maintaining statistical guarantees. Their main contribution is utilizing confidence sequences (instead of confidence intervals) that allows them to draw just enough samples to certify robustness of a points which allows them to greatly decrease the number of samples needed. They also show the effectiveness of their approach experimentally.\nBeyond that, they propose a randomized version of Clopper-Pearson confidence intervals for estimating the class probabilities. A standard component of randomized smoothing procedures is the Clopper-Pearsons confidence interval which is known to be conservative. As a result, the certification procedures underestimate the certified robustness. They provide an optimal confidence interval for binomial random variables that resolves this issue.", "questions": "same as weaknesses.", "limitations": "same as weaknesses.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Certainly one of the main issues of Randomized smoothing methods is that they are not practical due to their computational burden, i.e. a lot of samples need to be drawn to decide robustness at a certain radius. Given that, their result seems interesting.", "weaknesses": "Other suggestions:\n\nLine 118: hence instead of whence\n\nLine 121: event instead of even\n\nContributions paragraph: Perhaps in the first paragraph mention that your results hold for binomial random variables.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and typos! We will clarify the binomial case. We are ready to answer any questions if any arise!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wDvYkRce3Q", "reviewer": "Reviewer_NzaR", "summary": "This paper proposes sample-efficient methods for computing probabilistic robustness certificates for randomized smoothing. The proposed methods replace the standard Clopper-Pearson confidence interval on the classifier’s score, with a confidence sequence, thereby allowing the number of samples to be determined adaptively given a radius of certification $r$ and significance level $\\alpha$. Two variants of the method are proposed: one that updates the sequence on a geometric schedule (shown to achieve the asymptotically optimal sample complexity) and another that adopts a betting strategy. The methods are shown to consume 1.5–3 times fewer samples compared to prior work (Horváth et al., 2022).", "questions": "- Does the method apply to the more general formulations of randomized smoothing?\n- Could the method be adapted to estimate the maximum certified radius within some tolerance? This would cover another common use case.", "limitations": "The limitations ought to be discussed more. For example, the experiments only cover one dataset/model, the proposed method only improves sample complexity if the radius is fixed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality:**\nThis paper imports methods from statistics/probability theory, which have not previously been applied in the context of randomized smoothing. The methods appear to be an excellent fit for improving the statistical efficiency (and hence computational efficiency) of randomized smoothing. It’s worth noting that the methods have been adapted, in that the bounds are specialized for Bernoulli random variables (rather than generic bounded random variables). \n\n**Significance:**\nThe computational cost of randomized smoothing is a barrier to adoption, so it’s great to see work in this direction. The proposed algorithms for adaptively determining the sample size is relatively simple to implement which should encourage adoption.\n\n**Quality:**\nThe method is well-motivated. The theory and experiments are generally well-executed, apart from some minor issues outlined below.\n\n**Clarity:**\nThe writing is reasonably clear, apart from some issues discussed below.", "weaknesses": "**Clarity:**\nThe paper is mostly clear, however some parts could be improved:\n- Section 3: Definition 3.1 seems out-of-place: it’s not clear that a generic formulation of sequential decision making is needed, if the experiments focus on randomized smoothing. Section 3.1 includes some discussion of the results, but is labeled “related work”. It would be good to add a few more sentences discussing the results\n- Section 2.2: I find it confusing that symmetric/asymmetric confidence sequences are discussed before confidence sequences are defined (even informally).\n- Line 189: I found this paragraph confusing – I wonder if it could be explained more concretely (with an example) in an appendix.\n\n**Impact:**\n- The formulation of randomized smoothing in Section 2 covers additive smoothing mechanisms, where the certificate is an $\\ell_p$-ball. I suspect the formulation could be generalized to capture non-additive smoothing mechanisms and more general certificate geometries without impacting the validity of the results.\n- The proposed method is not applicable if one wants to estimate the maximum certified radius at an input. I wonder whether the method could be adapted to estimate the maximum certified radius within some tolerance.\n\n**Minor:**\n- line 24: Provide citation for claim that randomized smoothing “is currently the strongest certification method”\n- line 62: “realizations **are** lowercase”\n- line 77: Extraneous closing bracket\n- line 88: “de-randomized” has not been defined yet. Consider defining earlier or providing a citation.\n- line 92: Provide citation for claim that the Clopper-Pearson interval is “well known to be conservative”\n- line 94: In what sense is the confidence interval “optimal”? In terms of coverage?\n- line 121: “even” → “event”\n- line 128: Is the case where u() = 0 an upper confidence interval?\n- Proposition 2.4: Coverage has not been defined for a randomized confidence interval.\n- line 180: Should $\\in$ be $\\subseteq$?\n- line 247: Provide citation for Ville’s inequality\n- Table 1 caption: Delete “of number of samples”\n- line 324: “improved them at places” is ambiguous.\n- line 328: I’m not convinced that we now have a “perfect” understanding of statistical estimation for randomized smoothing. For instance, this paper has not considered the problem of estimating the smoothed classifier’s prediction. It’s possible there may be more sample-efficient ways of estimating the smoothed classifier’s prediction and bounds on the top-2 scores jointly. \n- “We stress out <some statement>” sounds unusual. It would be more natural to say “We stress <some statement>”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your thorough review! We appreciate the insightful comments that will help with the paper. \nIf we satisfactorily answer your questions and reservations, we kindly ask you to consider increasing your score.\n\n## Questions\n\n* **Does it apply to more general formulations of smoothing?**\n\nYes, our methodology can be directly applied to all[1] randomized smoothing works we are aware of as they have the same estimation subroutine. Some examples of such non-additive smoothing are Wasserstein smoothing[2] and Image transformation smoothing[3] and they both use the standard estimation procedure in randomized smoothing due to (Cohen, 2019). We state this explicitly in the paper \n\n[1]: modulo the deterministic ones, where there is no estimation. Additionally, rarely a soft base classifiers are considered instead of hard ones. Here one would need to use e.g., empirical Bernstein bound instead of Clopper-Pearson; alternatively the betting wealth needs to be computed in a different way. \\\n[2]: Levine et al. Wasserstein Smoothing: Certified Robustness against Wasserstein Adversarial Attacks\\\n[3]: Fischer et al. Certified Defense to Image Transformations via Randomized Smoothing\n\n* **Applicability to more general tasks; e.g., estimate the maximum certified radius within some tolerance**\n\nYes, the methods can be directly applied. We run the confidence sequences until a stopping condition is met (in the paper, it was that certain value of $p$ is outside of the confidence sequence). In the proposed task the stopping criterion might be that $r(hi) < r(lo) + \\varepsilon$, where the current confidence interval on the probability is $[lo, hi]$ and $r(p)$ is the radius computed from probability $p$. In the example, we know (at certain confidence) that $r(lo)$ is underestimating the true certified radius and $r(hi)$ is overestimating it; and so when the stopping criterion is met, we return conservative estimate $r(lo)$, but we know that it is at-most $\\varepsilon$ smaller than the true radius. We will include this task in the paper. Please see the enclosed pdf for preliminary results.\n\n## Clarity \nThanks for the pointers, we will fix the problems.\n\n* **Start of setction 2.2**\n\nWe move the content of the first paragraph after the definition 2.5 and the following remark.\n\n* **Section 3, definition 3.1**\n\nWe agree that the section is brief, we will expand it using the extra page. In the paper, we try to strike a balance between the generality (so the results can be readily transfered) and the clarity of the connection to randomized smoothing. We think that the task from Definition 3.1  is natural and we would like to keep it in this form. We agree that the definition might seem to come out of nowhere and we will provide more motivation for it.\n\n* **Paragraph after line 189**   (answer copied for Reviewer xWqy)\n\nThis is a purely technical assumption for the clarity of exposition. This way we can hide the dependency of the width of the confidence interval on $p$ (so the width scales as $n^{-\\frac12}$ and thus simplify the discussion on the width when $np \\asymp 1$ where it exhibits complicated behavior (anything between $n^{-\\frac12}$ and $n^{-1}$) covered in the referred book. We move the discussion in appendix and replace the paragraph in the main text by the following:\n\nFor the simplicity of exposition, let the width of a confidence interval at level $1-\\alpha$ with $n$ samples be $\\asymp \\sqrt{\\log(1/\\alpha)/n}$. This way, we hide the dependency on $p$ into $\\asymp$. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates $\\sqrt{p(1-p)\\log (1/\\alpha)/n} $ (when $np \\gtrsim 1$) and $\\log(1/\\alpha)/n$ (when $np \\asymp 1$).  Our algorithms capture the correct scaling of the confidence intervals. Further discussion is provided in Appendix.\n\n## Minor\nThanks for all the relevant points. We integrate all of them but comment here only one the \"open ended\" ones.\n\n* **In which sense is the randomized interval optimal?**\n\nThey are the shortest possible in expectation. We state it formally in the paper: For any binomial r.v. $X \\sim \\mathcal{B}(n, p)$ and any $q$ (where $p,q$ are probabilities and $n$ is number of samples), $\\mathbb{P}(q \\in CI_{\\text{our}}(X)) \\leq \\mathbb{P}(q \\in CI_{\\text{other}}(X)) $, where $CI_\\text{our}$ is our proposed randomized confidence interval and $CI_\\text{other}$ is any other confidence interval  at the same confidence level as ours, and so our intervals are the shortest one in expectation.\n\n* **Is [0, v(x)] the upper confidence interval?**\n\nWe called it the lower confidence interval since it contains the low values. On the other hand $v(x)$ is the upper bound for the estimated quantity. We are open to rename the interval if it helps the clarity.\n\n* **Definition of coverage for randomized intervals**\n\nWe update the definition so to cover the random intervals. The coverage is the probability of the true parameter appearing in the confidence interval, where the probability is not only over sampling, but also over the randomness of the intervals.\n\n* **Problems with Conclusions**\n\nThanks, we agree. We rewrite it in the following way:\n\nIn this paper, we investigated the statistical estimation procedures related to randomized smoothing and improved them in the following two ways: (1) We have provided a strictly stronger version of confidence intervals than the Clopper-Pearson confidence interval. (2) We have developed confidence sequences for sequential estimation in the framework of randomized smoothing, which will greatly reduce the number of samples needed for adaptive estimation tasks. Additionally, we provided matching algorithmic upper bounds with problem lower bounds for the relevant statistical estimation task.\n\n## Limitations\n\nWe will add Imagenet experiments and with multiple models (we already have multiple models for CIFAR and $\\ell_1, \\ell_2$ tasks.) We will include your proposed task.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "G0t5QhwYPZ", "reviewer": "Reviewer_xWqy", "summary": "This paper presents two statistical innovations on top of standard randomized smoothing. The first is employing a randomized Clopper-Pearson interval (instead of deterministic), which marginally increases the certified radius for a particular number of samples. The second involves improving sample efficiency by leveraging confidence sequences, resulting in a roughly 2x speedup over existing methods.", "questions": "1. Why is the blue line in Figure 1(a) so jagged?\n2. I don't understand the purpose of the bounds mentioned on line 189: \"In the analysis that follows, we assume that the Bernoulli distribution has a success probability satisfying 0 < c < p < C < 1 for some constants c, C, and thus we can hide the dependence on it into ≍.\"\n3. I have trouble understanding the plots in Figure 2. The text of the paper suggests that epsilon is the width, so why is it plotted from 0 to 1 in the bottom left plot? What exactly are these bounds converging to? I feel that these plots are explaining something important but I'm not sure what the experimental setup is here exactly.\n4. The randomized interval in Definition 2.3 only differs from the deterministic interval in the \"knife edge\" case where the binomial distribution is exactly x. I'd expect the contribution from this term to become negligible as the number of samples grows -- why is this not the case in Figure 2b?", "limitations": "The authors do not discuss limitations.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I'm torn on this work -- although it seems to be a technically sound improvement on the SOTA, the method is very involved for a relatively small benefit. The paper could also use some better exposition. I'm curious what other reviewers think.\n\n1. This work leverages interesting statistical techniques to improve upon randomized smoothing, both in terms of certified radius and sample efficiency.\n2. The theory is quite extensive and seems sound (although I have not checked the proofs in detail).\n3. Certified robustness of classifiers is an interesting and topical problem.", "weaknesses": "1. The authors should take care to proofread their work, which has a number of grammatical and structural errors.\n2. The union-bound and betting-based confidence sequences seem to yield very similar results. I am not sure why both need to be included.\n3. The paper flow is somewhat poor and difficult to follow. The authors should revise their manuscript to add better transitions between sections.\n4. The proposed approaches include a great deal of complexity for relatively minimal improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your review. We appreciate the comments and questions that will help improve the clarity of the paper.  We would like to emphasize that the resulting (theoretically grounded) methods are reasonably simple ($\\sim10$ lines of code) and (a heuristic) SotA uses $50\\\\%$ more samples and thus the improvement is significant. Furthermore, we provide lower bounds suggesting that it is impossible to significantly improve the performance estimation tasks.  We are happy to provide further clarifications if needed and we **kindly ask you to consider increasing the score** if you are satisfied with the responses\n\n## Weaknesses\n1. **Grammatical errors**\n\nSorry for this. We are aware of some of them and will try to eliminate them.\n\n2.  **Why are 2 methods included when they perform similarly?**\n\nWe decided to include both methods for two main reasons apart from the completeness: (1) Betting  works better for easy problems while UB is better for the harder ones. (2) We do not only want to propose a method for randomized smoothing. We want the reader to understand the subtleties of the task so they can potentially use this framework in a different context. In certain settings it might be easier to adopt the UB-CS and elsewhere the betting one.\n\n3. **Paper flow is difficult to follow**\n\nWe tried to make the writing as clear as possible and we suspect that some difficulty is inherent due to the technical complexity of the presented topics. We would like to increase the clarity of the paper, could you please share in what parts were difficult to follow?\n\n4.a  **Approaches include a great deal of complexity**\n\nThe derivations of the methods are sometimes involved, but the methods themselves are then rather straightforward to implement. On line 243 (top of page 7) we show both proposed algorithms and they can be implemented in 12 simple lines of pseudocode (Python code would be in almost a 1-to-1 correspondence, invoking library function bisect). Union bound CS is just as complex code as the baseline (Horvath, 2022). \n\n4.b **...for relatively minimal improvement**\n\nWe want to stress that we consider the improvements of our methods to be significant. The SotA method (1) require roughly $50\\\\%$ more samples than our methods, (2) cannot be used in the very large sample regime and (3) is only heuristic \n\nOn the contrary, our method is optimal in a certain sense and is competitive with ideal methods which strictly outperform the best possible methods for this task. Thus, we not only provide an empirically strong method outperforming SotA by $50\\\\%$, but also demonstrate that significant further improvements on this task are impossible.\n\n## Questions\n1. **Why is the blue line in Fig 1 jagged?**\n\nThis is a property of the Copper-Pearson intervals - that we wanted to demonstrate - resulting in them being conservative in general. We discuss it in the paragraph starting at line 138. In Example A.2 (and figure 3) we work out a simple example for B(2,p) using elementary math demonstrating why this behavior occurs. Briefly, in setting of Fig 1a, $p_1=0.912$ and $p_2=0.933$ will **not** be contained in the upper confidence interval only when observing $100$ heads from $100$ tosses. This happens for $p_1$ with probability $\\alpha_1 = 10^{-4}$ and for $p_2$ with probability $\\alpha_2 = 10^{-3}$ which are then points on the jagged blue line.\n\n2. **Why do we assume that there are some constants $c,C$ such that $0 <c <p <C < 1$?** (answer copied for  Reviewer NzaR)\n\nThis is a purely technical assumption for the clarity of exposition. This way we can hide the dependency of the width of the confidence interval on $p$ (so the width scales as $n^{-\\frac12}$ and thus simplify the discussion on the width when $np \\asymp 1$ where it exhibits complicated behavior (anything between $n^{-\\frac12}$ and $n^{-1}$) covered in the referred book. We move the discussion in appendix and replace the paragraph in the main text by the following:\n\nFor the simplicity of exposition, let the width of a confidence interval at level $1-\\alpha$ with $n$ samples be $\\asymp \\sqrt{\\log(1/\\alpha)/n}$. This way, we hide the dependency on $p$ into $\\asymp$. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates $\\sqrt{p(1-p)\\log (1/\\alpha)/n} $ (when $np \\gtrsim 1$) and $\\log(1/\\alpha)/n$ (when $np \\asymp 1$).  Our algorithms capture the correct scaling of the confidence intervals. Further discussion is provided in Appendix.\n \n3. **Understanding Fig 2**\n\nOur bottom-left y axis label might have not been the best choice, we will update both captions on the left by words. In the notation of Algorithm 1,2; in the top-left we plot U_t - L_t, while on bottom-left we plot both U_t and L_t (i.e., top = width of CS, bottom = CS itself). We find the setting to be described exhaustively in the caption, but we needed to keep it short due to space constraints. We will put the following in the caption of the left part: \"In the notation of Algorithms 1,2, the sequence of $U-L$ is in the top figure, while both sequences $U$ and $L$ are in the bottom figure.\" See the enclosed pdf for the new figure.\n\n4. **Why are the gains from randomized CI not diminishing with increasing $n$?**\n\nThe randomized and deterministic CIs are only equal when the realization of a uniform r.v. on the interval [0,1]  is 1 (so almost surely the randomized ones are larger). The difference in widths gets smaller as $n$ grows; however in Fig 1b. we show the certified radii with Gaussian smoothing and so we plot $\\Phi^{-1}(\\underline p)$ ($\\Phi$ is Gaussian CDF). It holds that $\\lim_{p \\to 1} \\Phi^{-1}( p) = \\infty $, so even when the absolute difference between the deterministic and randomized CI lower-bound  of $p$ decreases, the difference between the certified radii roughly stays the same because the growth of $\\Phi^{-1}$  is increasing quickly around $1$. This holds only when $\\underline p \\sim 1$ which is the relevant part of Fig 1b.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their reviews! In general we agree with them. In our understanding, the reviewers agree on the fact that we successfully attacked a well-known limitation of randomized smoothing. Their perceived weaknesses are occasional writing problems - those are easily fixable and do not require significant changes.

In the enclosed pdf we provide updated figure 2. for better clarity. We changed the Y-axis labels on the left part. We also slightly updated caption -  changes are in red.

We also enclose a table with an experiment on a new task as requested by Reviewer NzAR

Meta-review: This paper studies the statistical cost of certification of robustness based on randomized smoothing (RS). The certification step is one of the computational bottlenecks of RS and, as such, providing procedures that can reduce the amount of samples needed to certify a certain level of robustness at a given point is important. The authors provide a testing procedure based on confidence sequences and testing by betting that provides comparable certificates to the alternatives with about half of the needed samples. The manuscript also provides a lower bound demonstrating that further significant improvements in sample complexity will not be possible. There is a consensus among reviewers that this is a solid contribution, and I agree.
Decision: Accept (poster)