Treatment of Statistical Estimation Problems in Randomized Smoothing for Adversarial Robustness

Authors: václav  voráček
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 18:49:36

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.

Main paper: 
 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 et 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 method1 . We will not cover other certification methods and we refer the reader to the survey Li et al. (2023) instead. We consider the standard task of certified robustness; the goal is to decide if the decision of a classifier F at a particular input x is robust against additive perturbations δ such that ∥δ∥ ≤ r for some norm ∥•∥. Formally, we ask if F (x) = F (x ′ ) whenever ∥x -x ′ ∥ ≤ r.Randomized smoothing is a framework providing state of the art formal guarantees on the adversarial robustness for many datasets. One of its benefits lies in the fact that there are no assumptions on the model, making it possible to readily transfer the methods from defending image classifiers against sparse pixel changes to different modalities; e.g., defending large language models against change of some letters/words/tokens. Randomized smoothing transforms any undefended classifier F : R d → Y by a smoothing distribution φ into a smoothed classifier H φ (x) = arg max y∈Y P δ∼φ F (x + δ) = y for which robustness guarantees exist. We postpone the details for later. During the certification process, we need to estimate the maximum probability of a multinomial distribution from samples as the exact computation is intractable. This statistical estimation problem is the focus of this paper.The main weakness of randomized smoothing is the extensive time required for both prediction and certification, making it troublesome for real-world applications. There is an inherent trade-off between the allowed probability of incorrectly claiming robustness2 (type-1 error, α), the probability of incorrectly claiming non-robustness (type-2 error, β), and the number of samples used n. The standard practice is to set α = 0.001, n = 100 000 and the value of β is then implicit. it might not be the most practically relevant setting since the implicitly set value of β is exponentially small in n when the sample is not close to the threshold. The claim is made precise in Example A.1.The arguably more relevant setting is to set the values of α and β and leave n implicit. This is much more challenging since it is no longer possible to draw the predetermined number of samples and use a favourite concentration inequality. We propose a new certification procedure using confidence sequences to adaptively (and optimally) deciding how many samples to draw addressing the problem.• We introduce a new, strictly better version of Clopper-Pearson confidence intervals for estimating the class probabilities in Subsection 2.1. 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 us 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 a 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 sample-complexity in an 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 (x). We type sequences in bold and denote x :t first t elements of x. We write a ≲ b if there exists a universal constant C > 0 such that a ≤ Cb. If a ≲ b and b ≲ a, then we write a ≍ b. Iverson bracket Φ evaluates to 1 if Φ is true and to 0 otherwise.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 shortcomings of confidence intervals and introduce confidence sequences and provide lower and upper bounds for their performance. We use the confidence sequences in Section 3 where we consider a sequential estimation task. Recalling that H φ (x) = arg max y∈Y h φ (x) y , then for a certain function r : 
randomized smoothing: 
 [0, 1] 2 → R + we have ∥x -x ′ ∥ ≤ r(p A , p B ) =⇒ H φ (x) = H φ (x ′ ).This r depends on the smoothing distribution φ and the considered norm. For example, if the considered norm is ℓ 2 and φ is isotropic Gaussian with standard deviation σ, then r(pA , p B ) = σ 2 (Φ -1 (p A ) -Φ -1 (p B ))where Φ -1 is Gaussian quantile function Cohen et al. (2019) . Note that in general, r(•, •) is increasing in the first coordinate and decreasing in the second one. The intuition is that the larger the value of p A at x, the larger it will be also in the neighborhood of x; similarly for p B . It is common in the literature to use the bound p B ≤ 1 -p A and thus certify r(p A , 1 -p A ). 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 randomized smoothing. We consider the abstract framework for randomized smoothing, so the proposed techniques can be used as a drop-in replacement in all randomized smoothing works with a statisticalestimation component (i.e., not in the de-randomized ones such as Levine & Feizi (2021) ). We do not only propose methods that work good empirically, we also provide theoretical analysis suggesting that we solve the problems optimally in certain strong sense. The main focus is on the following two constructs.1. Confidence intervals: A standard component of randomized smoothing pipelines is the Clopper-Pearsons confidence interval. It is known to be conservative3 ; 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 a confidence level 1 -α. 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 if a point is robust at radius r with type-1 (resp. 2) error rates α (resp. β) using as few samples as possible.Overview 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 a crucial decision determined mainly by the threat model with respect to which we want to be robust. For example, if we are after certifying ℓ 1 robustness, we choose a uniform distribution in a d-dimensional ℓ ∞ ball (Lee et al., 2019; Yang et al., 2020) , or better, splitting noise (Levine & Feizi, 2021 ), but we do not go into details here. Alternatively, for p-norms, p ≥ 2 one would usually use a d-dimensional normal distribution Lecuyer et al. (2019) ; Cohen et al. (2019) . The variance of the distribution based on how large perturbations do we allow in our threat model. We refer the reader to Yang et 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) , sparse attack Bojchevski 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 de-randomized smoothing (Levine & Feizi, 2021) ). See also Kumari et al. (2023) for a survey on randomized smoothing containing examples of when the certification is beyond additive ℓ p -norm threat model; even such techniques use the Bernoulli estimation subroutine.We do not have access to the class A probability p A and only have to estimate it from binomial samples; hence, the name randomized smoothing. Because of the randomness, we can only provide probabilistic statements about the robustness of a classifier in the following spirit "with probability at least 1 -α, robust radius is at least r" for a small α, usually 0.001. This failure probability corresponds to the event of overestimating p A 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.Definition 2.1 (Confidence interval for binomials). Let u, v map sample to a real number. They form a (possibly randomized) confidence interval I(x) = [u(x), v(x)] with coverage 1 -α if for any p ∈ [0, 1] it holds that P X∼B(n,p),I (p ∈ I(X)) ≥ 1 -α.We will mainly use one-sided confidence intervals; that is, u(•) = 0 (lower confidence interval) or v(•) = 1 (upper confidence interval). When we will talk about probability of confidence interval containing the parameter, it will be in the sense of its definition, keeping in mind that confidence intervals provide no guarantees post-hoc for any individual estimation.Clearly, if I(x) = [0, 1] regardless of x, it will be a valid confidence interval but rather useless; thus we aim for short intervals. Ideally it would hold for every p that P X (p ̸ ∈ I(X)) = α, 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-Pearson intervals). One sided upper interval is defined as v(x) = 1 andu(x) = inf{p | P(B(n, p) ≥ x) > α}.The lower one is defined as u(x) = 0 andv(x) = sup{p | P(B(n, p) ≤ x) > α}.Amongst the deterministic confidence intervals, they are the shortest possible; however, they are in general conservative. In the binomial case B(n, p), there are only n + 1 possible outcomes; and thus only n + 1 possible confidence intervals suggesting that the actual coverage can be 1 -α only for at most n + 1 values of p. 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 n √ α 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 -α, but will be shorter. Intuitively, we do so by "interpolating" between the deterministic confidence intervals in the spirit of Stevens (1950) .Definition 2.3 (Randomized Clopper-Pearson intervals). Let W be uniform on the interval [0, 1].The randomized one sided upper interval is defined as v r (x) = 1 u r (x) = u ′ r (x, W ) where u ′ r (x, w) = inf{p | P(B(n, p) > x) + wP(B(n, p) = x) > α}. The lower one is defined as u r (x) = 0 and v r (x) = v ′ r (x, W ) where v ′ r (x, w) = sup{p | P(B(n, p) < x) + wP(B(n, p) = x) > α}. Proposition 2.4. Randomized Clopper-Pearson interval (I rCP ) have coverage exactly 1 -α. Furthermore, for any confidence interval I at level 1 -α, and any p ≥ q ∈ [0, 1] it holds thatP X∼B(n,p) (q ∈ I(X)) ≥ P X∼B(n,p) (q ∈ I rCP (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 1 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 p and for certification functions r such that lim p→1 r(p) = ∞, 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 a confidence interval at level 1 -α with n samples be ≍ log(1/α)/n. This way, we hide the dependency on p into ≍. In the full generality, the width of the confidence intervals exhibits many decay regimes between the rates p(1 -p) log(1/α)/n (when np ≫ 1) and log(1/α)/n (when np ≍ 1). Our algorithms capture the correct scaling of the confidence intervals. See Boucheron et al. (2013) and the discussion on Bennett's inequality which captures the correct rates for Bernoulli mean estimation. Limitations of confidence intervals: In order to compute the confidence intervals presented in 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 we do not need all 100 000 samples and after only 10 it would be enough for our purposes because we could already conclude that the point cannot be certified here; thus, we wasted 99 990 samples. ( 2) Alternatively, we could see that even 10 5 samples are not enough, and we need to draw more samples. However, we have already spent our failure budget α, 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 a confidence interval after every received sample such that we control the probability that the true parameter is contained in all the confidence intervals simultaneously.Definition 2.5 (Confidence sequence). Let {u t , v t } ∞ t=1 be mappings from a sequence of observations to a real number. They form a confidence sequence I t (x :t ) = [u t (x :t ), v t (x :t )] for all t ≥ 1 with confidence level 1 -α ifP (p ∈ I t (X :t ), ∀t > 1) ≥ 1 -α for any p ∈ [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, we will have by convention that I t+1 (x :t+1 ) ⊆ I t (x :t ).To simplify presentation, we 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 is straightforward and will not be discussed. 2023). The differences mainly lies in the fact that we are interested in Bernoulli random variables, which allows us to use specialized tools at place, as opposed to the referred works which usually consider bounded random variables. As an analogy to confidence intervals, the previous works construct Bernstein-type inequalities, while we construct a Clopper-Pearson-like bounds. We refer specially to Orabona & Jun (2023) containing more general result which was a great inspiration for us and it also contains a proper literature review on the topic. The construction of confidence sequences based on union bound employs the doubling trick which is widely used in online learning to convert fixed-horizon algorithms to anytime algorithms. In this direction, we refer to Mnih et al. (2008) as the direct predecessor of this work.A natural way how to extend the confidence intervals to confidence sequences is to construct a confidence interval at every time step and use a union bound to control the total failure probability. In the following, we first show that a naive application of this approach is asymptotically suboptimal, and then we provide a way how to construct optimal confidence intervals in a certain strong sense.Intuition on the width of confidence sequences: For any random variable with finite variance, the optimal width of the confidence interval for the mean parameter scales as log(1/α)/t with the increasing number of samples t at confidence level 1 -α Lugosi & Mendelson (2019) . On the other hand, it is well known that the width of the optimal confidence sequence scales as (log(1/α) + log log t)/t as t increases due to the law of iterated logarithms Ledoux & Talagrand (1991) . A naive use of union bound, computing a confidence interval using failure probability at time step t, α t = αc t γ for some c and γ > 1 such that ∞ i=1 α t = α yields a confidence sequence whose width scales as log(1/α t )/t ≈ (log(t) + log(1/α))/t. We cannot choose any monotonous α t schedule decaying slower because even for γ = 1 we still keep the log factor while the sum∞ i=1 δ t diverges.Now consider non-monotonous schedules of α t , two key ideas follows. (1) In order to have the optimal rate log(1/α t ) ≈ log(1/α) + log log t, we need α t ≍ α/ log t. Clearly, if this holds for all t, then ∞ t=1 α t diverges. (2) A confidence interval at time t is also a valid confidence interval for all t ′ > t. Furthermore, if t ′ is not much larger than t, then it may still asymptotically have the optimal width up to a multiplicative constant. Thus, updating the confidence sequence when t is a power of (say) 2 result in the optimal width. This reasoning is formalized in the following theorem.Theorem 2.7. Fix α > 0. Consider a sequenceα t = α k(k+1) if t = 2 k for integer k, 0 otherwise.Then Algorithm 1 produces a confidence sequence at level 1 -α of the following width which is attained in the worst caseε t ≲ log(1/α) + log log(t) twhere ε t is U -L at time t, 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 α t 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 of 2.7 is optimal due to law-of-iterated-logarithm (Ledoux & Talagrand, 1991) and even in the finite sample regime due to Balsubramani (2014) [Theorem 2].A recent alternative approach to confidence sequences is based on a hypothetical betting game. For the illustration, consider a fair sequential game; e.g., sequentially betting on outcomes of a coin. If we guess the outcome correctly, we win the staked amount, otherwise we lose it. If the coin is fair, 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-probability 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 a betting game for every possible mean 0 ≤ p ≤ 1 that would be fair if the true mean is p. 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 a fair game is modeled by martingales4 , sequences of random variables for which, independently of the past, the expected value stays the same.Definition 2.9 (Martingale). A sequence of random variables W 1 , W 2 , . . . is called a martingale if for any integer n > 0, we haveE(|W n |) < ∞ and E(W n+1 |W 1 , . . . , W n ) = W n . If we instead have E(W n+1 |W 1 , . . . , W n ) ≤ W n , then the sequence is called a supermartingale. Algorithm 1 Union-Bound Confidence Sequence T, H, K, L, U ← 0, 0, 0, 0, 1 loop Obtain random x H ← H + x T ← T + 1 if T = 2 K then K ← K + 1 α T ← α/(K(K + 1)) L ← max{L, LowConfInt(H, T, α T )} U ← min{U, UppConfInt(H, T, α T )} end if end loop Algorithm 2 Betting Confidence Sequence LOGQ, T, H, L, U ← 0, 0, 0, 0, 1 loop q ← (H + 1/2)/(T + 1) Obtain random x H ← H + x T ← T + 1 LOGQ ← LOGQ+x log(q)+(1-x) log(1-q) LOGP(p) := H log(p) + (T -H) log(1 -p) I p ← {p|LOGQ -LOGP(p) ≤ log(1/α)} L ← max{L, min I p } U ← min{U, max I p } end loopIn the coin-betting example, W 1 , W 2 , . . . is a martingale where W n represents our wealth after playing the game for n rounds. We stress that W t ≥ 0 for all t > 0. By convention, we will also have W 1 = 1. We further need a time-uniform generalization of Markov's inequality.Proposition 2.10 (Ville's inequality Durrett (2010) ). Let W 1 , W 2 , . . . be a non-negative supermartingale. then for any real a > 0P sup n≥1 W n ≥ a ≤ E [W 1 ] a .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 is 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: Let5 0 < p < 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 of our bet -in 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, we 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 1 -q fraction to tails. It maximizes the expected log-wealth, or equivalently, the expected growth-rate of our wealth and is also known as the Kelly Criterion. This is known to be optimal for the adaptive estimation task, see Wald (1947) under the name sequential-probability-ratio-test (SPRT). One might have expected the optimal criterion to 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 to an eventual bankruptcy 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 or 1 after the first observations, so we go bankrupt whenever the observed sequence contains both outcomes. Thus, we use a "regularized" sample mean and after observing H times heads in a sequence of length T , we estimate q = (H +0.5)/(T +1). This is the MAP estimate of the mean with Beta(1/2, 1/2) prior and is known as Krichevsky-Trofimov estimator (Cesa-Bianchi & Lugosi (2006) Section 9.7), Krichevsky & Trofimov (1981) and is proven to be successful for building confidence sequences beyond the Bernoulli case Orabona & Jun (2023) .Parallel betting games: We have described a betting game for a certain p and a betting strategy. Employing Ville's inequality we can possibly reject the hypothesis that the true sampling distribution follows p. However, we need to run the game for all values of p ∈ [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 p form an interval and we can use binary search twice to find the end-points of the interval. This is a non-trivial result ; on the bottom is the relative suboptimality of the individual methods; i.e., how many times more samples did they request compared to the ideal method. Note log scales on the y-axis. methods: UBnd-CS and Betting-CS are from Algorithm 1 and 2 respectively. Adaptive is from Horváth et al. (2022) . The ideal is the unattainable lower-bound for the two tasks. On the LHS, it is a confidence interval on level 1 -α computed independently at every time step. On the RHS, it is SPRT knowing both p, q which is optimal due to Wald (1947) .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 qt (resp. x t ) be our estimate of q (resp. the coin-toss outcome, for brevity 0/1 corresponds to heads/tails respectively andH = T t=1x t ), then our log-wealth at time T can be written as a function of p.log W T (p) = log T t=1 qt p xt 1 -qt 1 -p 1-xt = T t=1 x t log(q t ) + (1 -x t ) log(1 -qt ) LOGQ -H log(p) -(T -H) log(1 -p) 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 F.Theorem 2.11. Algorithm 2 produces a valid confidence sequence at confidence level 1 -α, where we interpret the interval [L, U ] at iteration T of the algorithm as the confidence interval at time T with width ε at most (which is attained in the worst case):ε t ≲ log(1/α) + log(t) t .This is not asymptotically optimal; still, empirically it performs well, and the same techniques can be used to obtain a confidence sequence that follows law-of-iterated-logarithms Orabona & Jun (2023) .We conclude this subsection by comparing the presented confidence sequences in Figure 2 . 
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 a 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 a certain radius is by far the most common one in the robustness literature. We stress that the comparison of the robustness curves (e.g., as in Figure 1 ) 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 2 ≤ p, q ≤ 1 and only p being known. Receive samples from B(q). 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 α.We identified Horváth et al. (2022) as the most relevant work. They distinguish between samples for which a predetermined radius r can be certified, and the samples for which it cannot. They use s values n 1 < • • • < n s ([10 2 , 10 3 , 10 4 , 1.2 • 10 5 ]) sequentially as the number of samples. They try to certify radius r with n 1 samples; if it fails, then they try n 2 samples etc. They employ Bonferroni correction (union bound) and every sub-certification is allowed to fail with probability only α s . The key differences (details in Appendix C.2.1) to our method are that (1) It always abstains for hard tasks.(2) Splitting the α budget evenly degrades performance for small n. (3) method is only a heuristics. See Figure 5 and Tables 1, 3 , 4. For the empirical comparison.Another relevant work is Chen et al. (2022) . Here, the certification is split in two phases. (1) Mean is crudely estimated. (2) The crude estimate selects the number of samples drawn so that the decrease (either multiplicative or absolute) in the certified radius is heuristically approximately at most a predetermined constant. We note that this heuristic for distributing samples can be made rigorous in a certain sense (see Dagum et al. (1995) ). This is trivial for confidence sequences, as one can stop the estimation only as soon as they short enough and solve the task of Chen et al. (2022) with guarantees (instead of just heuristic). In this sense, we see our methods to be more general. We benchmark this in Table 2 . 2 : We run the confidence sequences until the width is smaller than ε on a (both sided) confidence level 0.999. That way we can certify certain radius knowing that the true probability is at most ε larger. We used the same network as for the ℓ 2 experiment in Table 1 (WideResnet-40 on CIFAR10, σ = 1). We report the average number of samples required over 500 images.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs 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 a short proof sketch to provide intuition. • Inversely, 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 be properly referenced. 
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 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?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. 
broader impact statement: 
 We hope that this paper enlarges the interest in statistical estimation within the ML community. In the binary case, all the failure budget α = 0.001 was spent on controlling the top-1 class probability. In the multiclass setting, we spend λ fraction of the budget in bounding p A and the remaining 1 -λ part on bounding p B . 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 C. The only difference is that now σ = 1.setting, where we certify class A against all the other classes merged in a super class. In that case, the certification is done using the formula r(p A , 1 -pA ), where we have to guarantee that p A ≥ pA at confidence level at least 1 -α. The alternative is to use multiclass certification; here, the certification is done via formula r(p A , pB ) ensuring that p A ≥ pA and p B ≤ pB at the same time at confidence level at least 1 -α. The difference between these two bounds naturally manifests in the regime when p A is small. Strikingly, when p A < 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 to divide the failure budget between the the two estimation procedures. This is usually insignificant. In the ℓ 2 (and thus ℓ ∞ case), the role of α is rather minor, see Cohen et al. (2019) Figure 8 . This is even more pronounced in the ℓ 1 case. Here α plays an 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 to many, we 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 can run one confidence sequence for p A , and another for p B . We do not even need to know p B and we can run it for all of them at the same time. This means, that we run it only for the second most observed class. This second most observed class does 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 a wider confidence interval, so the statistical estimation is still correct.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: In linked repo.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 to a 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, or as supplemental material. 
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, confidence intervals, or statistical significance tests, at 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 run with given experimental conditions). • 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).• It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The total compute is under a 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, or 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] 12. Licenses 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 we used, but not the datasets as it is standard (cifar) Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset'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/model 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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. 
 
 Appendix: C.1 Figure 1 The model in Figure 1 is the pretrained cifar10 model (Exactly the same model/setting from the example in README) of Salman et al. (2019) , https://github.com/Hadisalman/ smoothing-adversarial; in particular, it was ResNet-110 smoothed with Gaussian noise σ = 0.12 for ℓ 2 robustness. We set α = 0.001 as usual and skip every 20 images of the test dataset (using 500 images, as is the standard practice).We were enlarging the sample size by a factor of β = 1.1 between estimations (that is, the condition T = 2 K is replaced by T > β K = 1.1 K and our schedule is α k = 5α/((t + 4)(t + 5)) The method is not sensitive to the choice of hyperparameters, see 5. In fact, the hyperparameters β, γ should be selected based on what is the "interesting" regime. There is an inherent tradeoff between a good asymptotical performance (β, γ ∼ 1) and low-sample performance (β, γ > 1). This is confirmed in γ = 1.05 β =1.1 γ = 1.05 β =1.5 γ = 1.05 β =2 γ = 1.05 β =3 γ = 1.1 β =1.1 γ = 1.1 β =1.5 γ = 1.1 β =2 γ = 1.1 β =3 γ = 1.5 β =1.1 γ = 1.5 β =1.5 γ = 1.5 β =2 γ = 1.5 β =3 γ = 2 β =1.1 γ = 2 β =1.5 γ = 2 β =2 γ = 2 β =3 usedβ(log(1/(γ -1)) + log(1/α) + γ log log β t) t .∞ t=1 1 t γ ≍ 1 γ-1 , α k ≍ α(γ-1) k γand t ≍ β k , then k ≍ log β t. Plugging in these identites in log(αt) t , and remembering that the confidence interval is recomputed only after elarging the sample size by β factor, then for time t, the actual t we use in the formula can be as small as t/β.The method from Horváth et al. (2022) uses a finite collection of values of n = n 1 < • • • < n s for which the confidence intervals are computed. A direct consequence is that the hard examples for which more than n s samples are needed cannot be certified. Additionally, due to Bonferroni correction, with large s, the term log(s/α) appearing in the confidence interval becomes large compared to t for small values of t (compare with the polynomial scaling that we propose where this is not the case). Consider n i = n i 1 , then the width of the confidence interval scales as (not considering the regime when t > n s where the width is constant):n 1 (log s + log 1/α) t .In particular, when we want to have confidence sequence up n s = N samples, then the width becomes s √ N (log s + log 1/α) t and we either pay for the fact that we have large differences between the steps ( √ sN ), or for the fact that we have lot of steps (log(s)) which is detrimental for small values of t.We had WideResNet-40-2 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, noise-augmented training using the same noise as for the certification. We either used Gaussian smoothing for ℓ 2 robustness of uniform in ℓ ∞ box for ℓ 1 robustness.For the certification we used batch size 100 (natural for Horváth et al. (2022) ). For our method, we 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.Proof. We show it for the upper interval, the lower is analogical. First, we note that f (p) = P(B(n, p) ≥ a) is non-decreasing in p for any n, a; Thus, u r (X) ≤ p if and only if P(B(n, p) > x) + wP(B(n, p) = x) > α. Now, we show that P(u r (X) ≤ p) = 1 -α for X ∼ B(n, p). To shorten the notation, let α 1 = P(X ≥ a) and α 2 = P(X > a) for such a that α 1 ≤ α ≤ α 2 . We haveP(u r (X) ≤ p) = P(u r (X) ≤ p | X < a)P(X < a) + P(u r (X) ≤ p | X = a)P(X = a) + P(u r (X) ≤ p | X > a)P(X > a), which we evaluate to P(u r (X) ≤ p) = (1 -α 1 ) + (α 1 -α 2 )P(u r (X) ≤ p | X = a) + 0. We note that given the event X = a, it holds u r (X) ≤ p ⇐⇒ α 2 + W (α 1 -α 2 ) > α, so P(u r (X) ≤ p | X = a) = P(α 2 + W (α 1 -α 2 ) > α) = P W > α-α2 α1-α2 = α1-α α1-α2 . Overall, P(u r (X) ≤ p) = (1 -α 1 ) + (α 1 -α 2 ) α1-α α1-α2 = 1 -α.The second part of the statement follows from Neymann-Pearson lemma. Concretely, we consider the following binary hypothesis testing problem from sample B(n, θ), and we decide if θ = p or θ = q. Both confidence intervals has size α and can be interpreted as binary tests -just return the indicator function of q ∈ I(x). Neymann-Pearson lemma states that the (unique) uniformly most powerful test is the likelihood ratio test, which is implemented by the randomized Clopper-Pearson interval.Proof of Theorem 2.7. First,∞ i=1 α t = ∞ k=1 αk(k+1) = α; thus, by union bound, all the computed confidence intervals are simultaneously correct at confidence level 1 -α. Next we show that the width is as claimed. When t = 2 k , we directly have from Hoeffding's inequalityε ≲ log 1 αt t ≍ log 1 α + log log t t .Otherwise, we would use a confidence interval of some previous t ′ such that t ′ < t < 2t ′ with widthε ≲ log 1 α + log log t ′ t ′ ≍ log 1 α + log log t t ,Noting that Clopper-Pearson's confidence intreval is shorter than Hoeffding's finishes the proof. □ F Proof of Theorem 2.11Proof. First we verify that everything in the algorithm is well defined and the logarithms take positive inputs. Now let W t = exp LOGQ t LOGPt where subscript t denotes iteration of the algorithm. We show that it is a martingale when X ∼ B(p) for 0 < p < 1. In that case, 0.17 ± 0.011s 0.13 ± 0.006s 0.3 ± 0.014s Union bound CS 1 0.2 ± 0.005s 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 ℓ 2 robustness robustness with σ = 1.E X [W t ] = W t-1 E X qt p X 1 -qt 1 -p 1-X = W t-1 p q p + (1 -p) 1 - q 1 -p = W t-If p ∈ {0, 1}, then we would have a deterministic sequence and W t ≤ W t-1 . Thus, W t is a supermartingale. It is also output of the exponential function and so is non-negative. Therefore, the assumptions of Ville's inequality are satisfied and can be applied. Whenever p is excluded from the confidence interval, it happened that LOGQ t -LOGP t ≥ log(1/α), or equivalently, W t ≥ 1/α 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 I p is a sub-level set of a convex function and is 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-Trofimov estimator Cesa-Bianchi & Lugosi (2006) Section 9.7; Krichevsky & Trofimov (1981) . The result then follows from Orabona (2019), Subsection 12.7.We remark that W (x :t ) does not depend on the order of x :t , so we write it as W (h, t); thus, for every T , we can compute what is the minimal number H(T ) needed of observed 1 so that p is outside of the lower-confidence interval. H(T ) is clearly non-decreasing in T ; also, W (h, t) can be easily computed from W (h -1, t) and also from W (h, t -1) using few flops. The whole dynamic programming approach can be summarized in the following scheme:• If W (h, t) ≥ 1 α : H(t) := h, t := t + 1, compute W (h, t + 1) • Else: h := h + 1, compute W (h + 1, t).Both lines are executed in constant time. Also, we start from W (0, 0) and h, t < N + 1. Executing a line, either h or t increases and thus to compute the thresholds for sequence of 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/α. In that case we would just set H(t) = t + 1 and increase t.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a 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 a 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 it 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.see leaderboard https://sokcertifiedrobustness.github.io/leaderboard/ 38th Conference on Neural Information Processing Systems (NeurIPS2024).of an input for a model at a certain radiusSee https://en.wikipedia.org/wiki/Binomial_proportion_confidence_interval.It would be historically accurate to say that martingales actually model fair games.For simplicity of exposition, similar arguments hold when p ∈ {0, 1}. 


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

Reviews: review: paper_summary: paper_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.
Beyond 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.
strength_weakness: strength_weakness: Other suggestions:

Line 118: hence instead of whence

Line 121: event instead of even

Contributions paragraph: Perhaps in the first paragraph mention that your results hold for binomial random variables.
questions: questions: same as weaknesses.
limitations: limitations: same as weaknesses.
paper_summary: paper_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).
strength_weakness: strength_weakness: **Clarity:**
The paper is mostly clear, however some parts could be improved:
- 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
- Section 2.2: I find it confusing that symmetric/asymmetric confidence sequences are discussed before confidence sequences are defined (even informally).
- Line 189: I found this paragraph confusing – I wonder if it could be explained more concretely (with an example) in an appendix.

**Impact:**
- 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.
- 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.

**Minor:**
- line 24: Provide citation for claim that randomized smoothing “is currently the strongest certification method”
- line 62: “realizations **are** lowercase”
- line 77: Extraneous closing bracket
- line 88: “de-randomized” has not been defined yet. Consider defining earlier or providing a citation.
- line 92: Provide citation for claim that the Clopper-Pearson interval is “well known to be conservative”
- line 94: In what sense is the confidence interval “optimal”? In terms of coverage?
- line 121: “even” → “event”
- line 128: Is the case where u() = 0 an upper confidence interval?
- Proposition 2.4: Coverage has not been defined for a randomized confidence interval.
- line 180: Should $\in$ be $\subseteq$?
- line 247: Provide citation for Ville’s inequality
- Table 1 caption: Delete “of number of samples”
- line 324: “improved them at places” is ambiguous.
- 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. 
- “We stress out <some statement>” sounds unusual. It would be more natural to say “We stress <some statement>”.
questions: questions: - Does the method apply to the more general formulations of randomized smoothing?
- Could the method be adapted to estimate the maximum certified radius within some tolerance? This would cover another common use case.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The authors should take care to proofread their work, which has a number of grammatical and structural errors.
2. The union-bound and betting-based confidence sequences seem to yield very similar results. I am not sure why both need to be included.
3. The paper flow is somewhat poor and difficult to follow. The authors should revise their manuscript to add better transitions between sections.
4. The proposed approaches include a great deal of complexity for relatively minimal improvement.
questions: questions: 1. Why is the blue line in Figure 1(a) so jagged?
2. 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 ≍."
3. 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.
4. 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: limitations: The authors do not discuss limitations.

Comments: comment: Thanks!
I went through other reviews and responses. Due to the computational cost of RS it is hard to adopt them, and they show an empirical method outperforming SotA by 50% reduction in samples. But it is true that RS is very expensive and it is not clear that 50% reduction in the number of samples is good enough. Furthermore, they show lower bounds that significant further improvements on this task are impossible. I believe the contribution is sufficient enough for acceptance.
Thanks a lot! 

If you think that RS is impractical at this stage, then you can see our paper as a negative result, since our lower bounds prevent significant improvements for the considered task.

On the other hand, we provide an adaptive estimation procedure that can be used for virtually any task related to randomized smoothing estimation and we can draw samples one-by-one.

Thanks again for your review, we will add the commas.
Thank you to the reviewers for their clarifications. I'm raising my score to a 5, but am still not confident on this paper. Mostly I'm not sure that a 50% reduction in samples is significant, as randomized smoothing is very far from being practical in any sense without an order-of-magnitude conceptual breakthrough. This seems unlikely given that these approaches have been explored for a few years now.

While this paper doesn't particularly excite me, perhaps the AC's tastes are different in this regard.

Also as a small note: I recommend adding periods after all inline subsections (e.g., after "Related Work" in line 181).
Thank you! We will remark it.
The authors' responses to my two questions have clarified that the proposed methods have broad applicability in randomized smoothing. I have therefore increased my score for "Contribution" and the overall rating.

> Yes, our methodology can be directly applied to all[1] randomized smoothing works we are aware of as they have the same estimation subroutine. ... We state this explicitly in the paper.

This was not clear to me from reading the paper. In section 2, randomized smoothing is formulated for additive noise and metric balls induced by a norm. Perhaps the authors could include a remark that this more limited formulation is used for ease of exposition, noting that the methods apply more generally as discussed in the response above.