Paper deep dive
Multi-scale Diffusion Denoised Smoothing
Jongheon Jeong, Jinwoo Shin
Models: ViT-B/16
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/12/2026, 5:49:10 PM
Summary
The paper introduces 'Multi-scale Diffusion Denoised Smoothing', a method to improve the trade-off between certified robustness and accuracy in randomized smoothing. It utilizes a cascaded inference pipeline that adaptively selects smoothing factors and proposes a fine-tuning objective for diffusion models to reduce over-confidence and improve calibration.
Entities (6)
Relation Signals (3)
Diffusion Model → evaluatedon → CIFAR-10
confidence 95% · In our experiments, we evaluate our proposed schemes on CIFAR-10
Multi-scale Diffusion Denoised Smoothing → improves → Certified Robustness
confidence 95% · the proposed multi-scale smoothing scheme combined with diffusion fine-tuning enables strong certified robustness
Cascaded Randomized Smoothing → utilizes → Diffusion Model
confidence 92% · which can be efficiently implemented with a single diffusion model.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Along with recent diffusion models, randomized smoothing has become one of a few tangible approaches that offers adversarial robustness to models at scale, e.g., those of large pre-trained models. Specifically, one can perform randomized smoothing on any classifier via a simple "denoise-and-classify" pipeline, so-called denoised smoothing, given that an accurate denoiser is available - such as diffusion model. In this paper, we present scalable methods to address the current trade-off between certified robustness and accuracy in denoised smoothing. Our key idea is to "selectively" apply smoothing among multiple noise scales, coined multi-scale smoothing, which can be efficiently implemented with a single diffusion model. This approach also suggests a new objective to compare the collective robustness of multi-scale smoothed classifiers, and questions which representation of diffusion model would maximize the objective. To address this, we propose to further fine-tune diffusion model (a) to perform consistent denoising whenever the original image is recoverable, but (b) to generate rather diverse outputs otherwise. Our experiments show that the proposed multi-scale smoothing scheme combined with diffusion fine-tuning enables strong certified robustness available with high noise level while maintaining its accuracy close to non-smoothed classifiers.
Tags
Links
Trouble viewing inline? Open PDF directly →
Full Text
94,784 characters extracted from source content.
Expand or collapse full text
Multi-scale Diffusion Denoised Smoothing Jongheon JeongJinwoo Shin Korea Advanced Institute of Science and Technology (KAIST) Daejeon, South Korea jongheonj, jinwoos@kaist.ac.kr Abstract Along with recent diffusion models, randomized smoothing has become one of a few tangible approaches that offers adversarial robustness to models at scale, e.g., those of large pre-trained models. Specifically, one can perform randomized smoothing on any classifier via a simple “denoise-and-classify” pipeline, so-called denoised smoothing, given that an accurate denoiser is available – such as diffusion model. In this paper, we present scalable methods to address the current trade-off between certified robustness and accuracy in denoised smoothing. Our key idea is to “selectively” apply smoothing among multiple noise scales, coinedmulti-scale smoothing, which can be efficiently implemented with a single diffusion model. This approach also suggests a new objective to compare thecollectiverobustness of multi-scale smoothed classifiers, and questions which representation of diffusion model would maximize the objective. To address this, we propose to further fine- tune diffusion model (a) to perform consistent denoising whenever the original image is recoverable, but (b) to generate rather diverse outputs otherwise. Our experiments show that the proposed multi-scale smoothing scheme, combined with diffusion fine-tuning, not only allows strong certified robustness at high noise scales but also maintains accuracy close to non-smoothed classifiers. Code is available at https://github.com/jh-jeong/smoothing-multiscale. 1 Introduction Arguably, one of the important lessons in modern deep learning is the effectiveness of massive data and model scaling [38,74], which enabled many breakthroughs in recent years [8,53,55,7]. Even with the largest amount of data available on the web and computational budgets, however, the worst-casebehaviors of deep learning models are still challenging to regularize. For example, large language models often leak private information in training data [10], and one can completely fool superhuman-level Go agents with few meaningless moves [40]. Such unintentional behaviors can be of critical concerns in deploying deep learning into real-world systems, and the risk has been increasing as the capability of deep learning continues to expand. In this context,adversarial robustness[61,9] has been a seemingly-close milestone towards reliable deep learning. Specifically, neural networks are even fragile to small, “imperceptible” scales of noise when it comes to the worst-case, and consequently there have been many efforts to obtain neural networks that are robust to such noise [47,3,75,15,65]. Although it is a reasonable premise that we humans have an inherent mechanism to correct against adversarial examples [21,26], yet so far the threat still persists in the context of deep learning,e.g., even in recent large vision-language models [48], and is known as hard to avoid without a significant reduction in model performance [66, 64]. Randomized smoothing[41,15], the focus in this paper, is currently one of a few techniques that has been successful in obtaining adversarial robustness from neural networks. Specifically, it constructs a smoothed classifierby taking a majority vote from a “base” classifier,e.g., a neural network, over random Gaussian input noise. The technique is notable for itsprovableguarantees on adversarial 37th Conference on Neural Information Processing Systems (NeurIPS 2023). arXiv:2310.16779v3 [cs.LG] 27 Oct 2023 (a) Cascaded smoothing(b) Diffusion calibration Figure 1: An overview of the proposed approaches, (a)cascaded randomized smoothing(Section 3.2 and (b)diffusion calibration(Section 3.3) to attain a better trade-off between accuracy and certified robustness in randomized smoothing, upon on the recentdiffusion denoised smoothingscheme [11]. robustness,i.e., it is acertified defense[44], and its scalability to arbitrary model architectures. For example, it was the first certified defense that could offer adversarial robustness on ImageNet [56]. The scalablity of randomized smoothing has further expanded by Salman et al.[58], which observed that randomized smoothing can be applied to any pre-trained classifiers by prepending a denoiser model, dubbeddenoised smoothing. Combined with the recentdiffusion-based models[31], denoised smoothing could provide the current state-of-the-arts inℓ 2 -certified robustness [11, 69, 44]. Despite its desirable properties, randomized smoothing in practice is also at odds with model accuracy [15], similarly to other defenses [47,76], which makes it burdening to be applied in the real-world. For example, the variance of Gaussian noise, orsmoothing factor, is currently a crucial hyperparameter to increase certified robustness at the cost of accuracy. The fundamental trade-off between accuracy and adversarial robustness has been well-evidenced in the literature [66,75,64], but it has been relatively under-explored whether they may or may not be applicable in the context of randomized smoothing. For example, Tramèr et al.[64]demonstrate that pursuingε-uniform adversarial robustness in neural networks may increase their vulnerability againstinvariance attacks,i.e., some semantics-altering perturbations possible inside theε-ball: yet, it is still unclear whether such a vulnerability would be inevitable at non-uniformly robust models such as smoothed classifiers. In attempt to understand the accuracy-robustness trade-off in randomized smoothing, efforts have been made to increase the certified robustness a given smoothed classifier can provide,e.g., through a better training method [58,73,35–37]. For example, Salman et al.[57]have employed adversarial training [47] in the context of randomized smoothing, and Jeong and Shin[35]have proposed to train a classifier with consistency regularization. Motivated by the trade-off among different smoothing factors, some works have alternatively proposed to perform smoothing withinput-dependentfactors [1,13,67]: unfortunately, subsequent works [60,36] have later shown that such schemes do not provide valid robustness certificates, reflecting its brittleness in overcoming the trade-off. Contribution.In this paper, we develop a practical method to overcome the current frontier of accuracy-robustness trade-off in randomized smoothing, particularly upon the architectural benefits that the recentdiffusion denoised smoothing[11] can offer. Specifically, we first propose to aggregate multiple smoothed classifiers of different smoothing factors to obtain their collective robustness (see Figure 1(a)), which leverages the scale-free nature of diffusion denoised smoothing. In this way, the model can decide which smoothed classifier to use for each input, maintaining the overall accuracy. Next, we fine-tune a diffusion model for randomized smoothing through the “denoise-and-classify” pipeline (see Figure 1(b)), as an efficient alternative of the full fine-tuning of (potentially larger) pre- trained classifiers. Here, we identify theover-confidenceof diffusion models,e.g., to a specific class given certain backgrounds, as a major challenge towards accurate-yet-robust randomized smoothing, and design a regularization objective to mitigate the issue. In our experiments, we evaluate our proposed schemes on CIFAR-10 [39] and ImageNet [56], two of standard benchmarks for certifiedℓ 2 -robustness, particularly considering practical scenarios of applying diffusion denoised smoothing to large pre-trained models such as CLIP [53]. Overall, the 2 results consistently highlight that (a) the proposed multi-scale smoothing scheme upon the recent diffusion denoised smoothing [11] can significantly improve the accuracy of smoothed inferences while maintaining their certified robustness at larger radii, and (b) our fine-tuning scheme of diffusion models can additively improve the results - not only in certified robustness but also in accuracy - by simply replacing the denoiser model without any further adaptation. For example, we could improve certifications from a diffusion denoised smoothing based classifier by30.6%→72.5%in clean accuracy, while also improving its certified robustness atε= 2.0by12.6%→14.1%. We observe that the collective robustness from our proposed multi-scale smoothing does not always correspond to their individual certified robustness, which has been a major evaluation in the literature, but rather to their “calibration” across models: which opens up a new direction to pursue for a practical use of randomized smoothing. 2 Preliminaries Adversarial robustness and randomized smoothing.For a given classifierf:X → Y, where x∈ X ⊆R d andy∈ Y:=1,·,K,adversarial robustnessrefers to the behavior offin making consistent predictions at theworst-caseperturbations under semantic-preserving restrictions. Specifically, for samples from a data distribution(x,y)∼p data (x,y), it requiresf(x+δ) =y foreveryperturbationδthat a threat model defines,e.g., anℓ 2 -ball∥δ∥ 2 ≤ε. One of ways to quantify adversarial robustness is to measure the followingaverage minimum-distanceof adversarial perturbations [9],i.e.,R(f;p data ) :=E (x,y)∼p data min f(x ′ )̸=y ||x ′ −x|| 2 . The essential challenge in achieving adversarial robustness stems from that evaluating this (and further optimizing on it) is usually infeasible.Randomized smoothing[41,15] bypasses this difficulty by constructing a new classifier ˆ ffromfinstead of lettingfto directly model the robustness: specifically, it transforms the base classifierfwith a certainsmoothing measure, where in this paper we focus on the case of Gaussian distributionsN(0,σ 2 I): ˆ f(x) := arg max c∈Y P δ∼N(0,σ 2 I) [f(x+δ) =c].(1) Then, the robustness of ˆ fat(x,y), namelyR( ˆ f;x,y), can be lower-bounded in terms of thecertified radiusR( ˆ f,x,y),e.g., Cohen et al.[15]showed that the following bound holds, which is tight for ℓ 2 -adversarial threat models: R( ˆ f;x,y)≥σ·Φ −1 (p ˆ f (x,y)) =:R( ˆ f,x,y),wherep ˆ f (x,y) :=P δ [f(x+δ) =y],(2) provided that ˆ f(x) =y, otherwiseR( ˆ f;x,y) := 0. 1 Here, we remark that the formula for certified radius is essentially a function ofp ˆ f , which is theaccuracyoff(x+δ)overδ. Denoised smoothing.Essentially, randomized smoothing requiresfto make accurate classification of Gaussian-corrupted inputs. A possible design offin this regard is to concatenate a Gaussian denoiser, saydenoise(·), with any standard classifierf std , so-calleddenoised smoothing[58]: f(x+δ) :=f std (denoise(x+δ)).(3) Under this design, an ideal denoiserdenoise(·)should “accurately” recoverxfromx+δ,i.e., denoise(x+δ)≈x(in terms of their semantics to perform classification) with high probability of δ∼N(0,σ 2 I). Denoised smoothing offers a more scalable framework for randomized smoothing, considering that (a) standard classifiers (rather than those specialized to Gaussian noise) are nowadays easier to obtain in the paradigm of large pre-trained models, and (b) the recent developments in diffusion models [31] has supplied denoisers strong enough for the framework. In particular, Lee[42] has firstly explored the connection between diffusion models and randomized smoothing; Carlini et al.[11]has further observed that latest diffusion models combined with a pre-trained classifier provides a state-of-the-art design of randomized smoothing. Diffusion models.In principle,diffusion models[59,31] aims to generate a given data distribution p data (x)via an iterative denoising process from a Gaussian noise ˆ x T ∼ N(0,T 2 I)for a certain T >0. Specifically, it first assumes the following diffusion process which mapsp data toN(0,T 2 I): dx t =μ(x t ,t)dt+σ(t)dw t , wheret∈[0,T], andw t denotes the standard Brownian motion. Based 1 Φdenotes the cumulative distribution function ofN(0,1 2 ). 3 on this, diffusion models first train ascore models φ (x,t)≈∇logp t (x)via score matching [34], and use the model to solve the probabilistic flow from ˆ x T ∼N(0,T 2 I)tox 0 for sampling. The score estimators φ (x,t)is often parametrized by adenoiserD(x;σ(t))in practice,viz.,∇logp t (x) = (D(x;σ(t))−x)/σ(t) 2 , which establishes its close relationship with denoised smoothing. 3 Method Consider a classification task fromXtoYwhere training dataD=(x i ,y i ) ∼p data (x,y)is available, and letf:X →Ybe a classifier. We denote ˆ f σ to be the smoothed classifier offwith respect to the smoothing factorσ >0, as defined by(1). In this work, we aim to better understand how theaccuracy-robustness trade-offof ˆ f σ occurs, with a particular consideration of the recent denoised smoothing scheme. Generally speaking, the trade-off implies the following: for a given model, there exists a sample that the model gets “wrong” as it is optimized for (adversarial) robustness on another sample. In this respect, we start by taking a closer look at what it means by a model gets wrong, particularly when it is from randomized smoothing. 3.1 Over-smoothing and over-confidence in randomized smoothing Consider a smoothed classifier ˆ f σ , and suppose there exists a sample(x,y)where ˆ f σ makes an error: i.e., ˆ f σ (x)̸=y . Our intuition here is to separate possible scenarios of ˆ f σ (x) making an error into two distinct cases, based on theprediction confidenceof ˆ f σ (x). Specifically, we define theconfidenceof a smoothed classifier ˆ f σ atxbased on the definition of randomized smoothing (1) and (2): p ˆ f σ (x) := max y p ˆ f σ (x,y) = max y P δ∼N(0,σ 2 I) [f(x+δ) =y].(4) Intuitively, this notion of “smoothed” confidence measures howconsistentthe base classifierfis in classifyingx+δover Gaussian noiseδ∼N(0,σ 2 I). In cases whenfis modeled by denoised smoothing, achieving high confidence requires the denoiserDto accurately “bounce-back” a given noisy imagex+δinto one that falls into classywith high probability overδ. Given a smoothed confidencep:=p ˆ f σ (x), we propose to distinguish two cases of model errors, which are both peculiar to randomized smoothing, by considering a certain thresholdp 0 onp. Namely, we interpret an error of ˆ f σ atxeither as (a)p≤p 0 : the model isover-smoothing, or (b)p > p 0 : the model is having anover-confidenceon the input: 1.Over-smoothing (p≤p 0 ):On one hand, it is unavoidable that the mutual information I(x+δ;y)between input and its class label absolutely decrease from smoothing with larger varianceσ 2 , although using largerσcan increase the maximum certifiable radius of ˆ f σ in practice (2). Here, a “well-calibrated” smoothed classifier should output a prediction close to the uniform distribution acrossY, leading to a low prediction confidence. In terms of denoised smoothing, the expectation is clearer: asx+δgets closer to the pure Gaussian noise, the denoiserD should generate more diverse outputs hence inYas well. Essentially, this corresponds to an accuracy-robustness trade-off from choosing a specificσfor a given (e.g., information-theoretic) capacity of data. 2.Over-confidence (p > p 0 ):On the other hand, it is also possible for a model ˆ f σ to be incorrect but with ahigh confidence. Compared to the over-smoothing case, this scenario rather signals a “miscalibration” and corresponds to a trade-off frommodel biases: even across smoothed models with a fixedσ, the balance between accuracy and robustness can be different depending on how each model assigns robustness in its decision boundary per-sample basis. When viewed in terms of denoised smoothing, this occurrence can reveal an implicit bias of the denoiser functionD, e.g., that of diffusion models. For example, a denoiser might be trained to adapt to some spurious cues in training data,e.g., their backgrounds, as also illustrated in Figure 1(b). In the subsequent sections, Section 3.2 and 3.3, we introduce two methods to exhibit better accuracy- robustness trade-off in randomized smoothing, each of which focuses on the individual scenarios of over-smoothing and over-confidence, respectively. Specifically, Section 3.2 proposes to use a cascaded inferenceof multiple smoothed classifiers across different smoothing factors to mitigate the limit of using a single smoothing factor. Next, in Section 3.3, we propose to calibrate diffusion models to reduce its over-confidence particularly in denoised smoothing. 4 3.2 Cascaded randomized smoothing To overcome the trade-off between accuracy and certified robustness fromover-smoothing,i.e., from choosing a specificσ, we propose to combinemultiplesmoothed classifiers with differentσ’s. In a nutshell, we design a pipeline of smoothed inferences that each input (possibly with different noise resilience) can adaptively select which model to use for its prediction. Here, the primary challenge is to make it “correct”, so that the proposed pipeline does not break the existing statistical guarantees on certified robustness that each smoothed classifier makes. Specifically, we now assumeKdistinct smoothing factors, say0< σ 1 <·< σ K , and their corresponding smoothed classifiers off, namely ˆ f σ 1 ,·, ˆ f σ K . For a given inputx, our desiderata is (a) to maximize robustness certification atxbased on the smoothed inferences available from the individual models, sayp ˆ f σ 1 (x),·,p ˆ f σ K (x) , while (b) minimizing the access to each of the models those require a separate Monte Calro integration in practice. In these respects, we propose a simple “predict-or-abstain” policy, coinedcascaded randomized smoothing: 2 casc(x; ˆ f σ i K i=1 ) := ˆ f σ K (x)ifp ˆ f σ K (x)> p 0 , casc(x; ˆ f σ i K−1 i=1 )ifp ˆ f σ K (x)≤p 0 andK >1, ABSTAINotherwise, (5) whereABSTAIN/∈ Ydenotes an artificial class to indicate “undecidable”. Intuitively, the pipeline starts from computing ˆ f σ K (x) , the model with highestσ, but takes its output only if its (smoothed) confidencep ˆ f σ K (x)exceeds a certain thresholdp 0 : 3 otherwise, it tries a smaller noise scale, say σ K−1 and so on, applying the same abstention policy ofp ˆ f σ (x)≤p 0 . In this way, it can early-stop the computation at higherσif it is confident enough, so it can maintain higher certified robustness, while avoiding unnecessary accesses to other models of smallerσ. Next, we ask whether this pipeline can indeed provide a robustness certification:i.e., how much one can ensurecasc(x+δ) =casc(x)in its neighborhoodδ. Theorem 3.1 below shows that one can indeed enjoy the most certified radius from ˆ f σ k wherecasc(x) =: ˆyhalts, as long as the preceding models are either keep abstaining or outputˆyoverδ: 4 Theorem 3.1.Let ˆ f σ 1 ,·, ˆ f σ K :X → Y be smoothed classifiers with0< σ 1 <·< σ K . Supposecasc(x; ˆ f σ i K i=1 ) =: ˆy∈Yhalts at ˆ f σ k for somek. Consider anypandp i,c ∈[0,1]that satisfy the following:(a)p≤p ˆ f σ k (x,ˆy) , and(b)p k ′ ,c ≥p ˆ f σ k ′ (x,c) fork ′ > kandc∈Y. Then, it holds thatcasc(x+δ; ˆ f σ i K i=1 ) = ˆyfor any∥δ∥< R, where: R:= min σ k ·Φ −1 p ,min y̸=ˆy k ′ >k σ k ′ ·Φ −1 1− p k ′ ,y .(6) Overall, the proposed multi-scale smoothing scheme (and Theorem 3.1) raise the importance of “abstaining well” in randomized smoothing: if a smoothed classifier can perfectly detect and abstain its potential errors, one could overcome the trade-off between accuracy and certified robustness by joining a more accurate model afterward. The option to abstain in randomized smoothing was originally adopted to make its statistical guarantees correct in practice. Here, we extend this usage to also rule out less-confident predictions for a more conservative decision making. As discussed in Section 3.1, now theover-confidencebecomes a major challenge in this matter:e.g., such samples can potentially bypass the abstention policy of cascaded smoothing, which motivates our fine-tuning scheme presented in Section 3.3. Certification.We implement our proposed cascaded smoothing to make “statistically consistent” predictions across different noise samples, considering a certainsignificance levelα(e.g.,α= 0.001): in a similar fashion as Cohen et al.[15]. Roughly speaking, for a given inputx, it makes predictions only when the(1−α)-confidence interval ofp ˆ f (x) does not overlap withp 0 uponni.i.d.noise samples (otherwise it abstains). The more details can be found in Appendix D.2. 2 We also discuss several other possible (and more sophisticated) designs in Appendix E. 3 In our experiments, we simply usep 0 = 0.5for allσ’s. See Appendix C.3 for an ablation study withp 0 . 4 The proof of Theorem 3.1 is provided in Appendix D.1. 5 3.3 Calibrating diffusion models through smoothing Next, we move on to theover-confidenceissue in randomized smoothing:viz., ˆ f σ often makes errors with a high confidence to wrong classes. We propose to fine-tune a given ˆ f σ to make ratherdiverse outputs when it misclassifies,i.e., towards a more “calibrated” ˆ f σ . By doing so, we aim to cast the issue of over-confidence as that ofover-smoothing: which can be easier to handle in practice,e.g., by abstaining. In this work, we particularly focus on fine-tuning only thedenoiser modelDin the context of denoised smoothing,i.e.,f:=f std ◦Dfor a standard classifierf std : this offers a more scalable approach to improve certified robustness of pre-trained models, given that fine-tuning the entire classifier model in denoised smoothing can be computationally prohibitive in practice. Specifically, given a base classifierf:=f std ◦Dand training dataD, we aim to fine-tuneDto improve the certified robustness of ˆ f σ . To this end, we leverage theconfidenceinformation of the backbone classifierf std fairly assuming it as an “oracle” - which became somewhat reasonable given the recent off-the-shelf models available - and apply different losses depending on the confidence information per-sample basis. We propose two losses in this matter: (a)Brier lossfor either correct or under-confident samples, and (b)anti-consistency lossfor incorrect, over-confident samples. Brier loss.For a given training sample(x,y), we adopt the Brier (or “squared”) loss [6] to regularize the denoiser functionDto promote the confidence off std (D(x+δ))towardsy, which can be beneficial to increase the smoothed confidencep ˆ f σ (x)that impacts the certified robustness atx. Compared to the cross-entropy (or “log”) loss, a more widely-used form in such purpose, we observe that the Brier loss can be favorable in such fine-tuning ofDthroughf std , in a sense that the loss is less prone to “over-optimize” the confidence at values closer to 1. Here, an important detail is that we do not apply the regularization to incorrect-yet-confident samples: i.e., wheneverf std (D(x+δ))̸=yandp std (δ) := max c F std,c (D(x+δ))> p 0 , whereF std is the soft prediction off std . This corresponds to the case whenD(x+δ)rather outputs a “realistic” off-class sample, which will be handled by the anti-consistency loss we propose. Overall, we have: L Brier (x,y) :=E δ [1[ˆy δ =yorp std (δ)≤p 0 ]·∥F std (D(x+δ))−e y ∥ 2 ],(7) where we denoteˆy δ :=f(x+δ)ande y is they-th unit vector inR |Y| . Anti-consistency loss.On the other hand, the anti-consistency loss aims to detect whether the sample is over-confident, and penalizes it accordingly. The challenge here is that identifying over-confidence in a smoothed classifier requires checking forp ˆ f σ (x)> p 0 (4) , which can be infeasible during training. We instead propose a simpler condition to this end, which only takes two independent Gaussian noise, sayδ 1 ,δ 2 ∼N(0,σ 2 I). Specifically, we identify(x,y)as over-confident whenever (a)ˆy 1 :=f(x+δ 1 )andˆy 2 :=f(x+δ 2 )match, while (b) they are incorrect,i.e.,ˆy 1 ̸=y. Intuitively, such a case signals that the denoiserDis often making a complete flip to the semantics ofx+δ (see Figure 1(b) for an example), which we aim to penalize. A care should be taken, however, considering the possibility thatD(x+δ)indeed generates an in-distribution sample that falls into a different class: in this case, penalizing it may result in a decreased robustness of that sample. In these respects, our design of anti-consistency loss forces the two samples simply to have different predictions, by keeping at least one prediction as the original, while penalizing the counterpart. Denotingp 1 :=F std (D(x+δ 1 ))andp 2 :=F std (D(x+δ 2 )), we again apply the squared loss on p 1 andp 2 to implement the loss design, as the following: L AC (x,y) :=1[ˆy 1 = ˆy 2 andˆy 1 ̸=y]·(∥p 1 −sg(p 1 )∥ 2 +∥p 2 ∥ 2 ),(8) wheresg(·)denotes the stopping gradient operation. Overall objective.Combining the two proposed losses,i.e., the Brier loss and anti-consistency loss, defines a new regularization objective to add upon any pre-training objective for the denoiserD: L(D) :=L Denoiser +λ·(L Brier +α·L AC ),(9) whereλ,α >0are hyperparameters. Here,αdenotes the relative strength ofL AC overL Brier in its regularization. 5 Remark that increasingαwould give more penalty on over-confident samples, which would lead the model to make more abstentions: therefore, this results in an increased accuracy particularly in cascaded smoothing (Section 3.2). 5 In our experiments, we simply useα= 1unless otherwise specified. 6 Carlini et al. (σ=0.25) Carlini et al. (σ=0.50) Carlini et al. (σ=1.00) + Cascading (ours) Certified accuracy 0 0.2 0.4 0.6 0.8 1.0 Radius 0123 (a) CIFAR-10 Carlini et al. (σ=0.25) Carlini et al. (σ=0.50) Carlini et al. (σ=1.00) + Cascading (ours) Certified accuracy 0 0.2 0.4 0.6 0.8 1.0 Radius 0123 (b) ImageNet Figure 2: Comparison of certified test accuracy with Carlini et al. [11] on the effectiveness of cascaded smoothing. Gaussian Consistency Carlini et al. (2023) + Calibration (ours) Certified accuracy 0 0.2 0.4 0.6 0.8 1.0 Radius 0123 Figure 3: Comparison of certi- fied test accuracy on CIFAR-10 atσ∈0.25,0.50,1.00. Table 1: Comparison of (a) certified accuracy, (b) empricial accuracy, and (c) average certified radius (ACR) on CIFAR-10. We set our result bold-faced whenever it achieves the best upon baselines. CIFAR-10, ViT-B/16@224Empirical accuracy (%)Certified accuracy atε(%) σTrainingC10C10-C10.10.00.51.01.52.0ACR 0.25 Gaussian [15]92.788.376.787.055.30.479 Consistency [35]89.584.767.684.960.70.517 Carlini et al. [11]92.888.867.689.559.80.527 + Calibration (ours)94.589.469.290.361.90.535 0.50 Gaussian [15]87.481.871.069.945.924.46.00.543 Consistency [35]80.775.059.667.749.231.213.10.617 Carlini et al. [11]88.884.964.375.350.631.014.30.646 + Calibration (ours)88.684.263.775.153.332.515.30.664 (0.25-0.50)+ Cascading (ours)92.589.178.585.153.332.914.90.680 1.00 Gaussian [15]75.672.468.342.227.916.99.04.00.426 Consistency [35]65.861.353.643.131.122.314.68.70.513 Carlini et al. [11]87.383.273.048.632.521.911.86.40.530 + Calibration (ours)83.379.360.952.636.724.916.18.80.577 (0.25-1.00)+ Cascading (ours)90.186.974.579.640.525.016.28.80.645 4 Experiments We verify the effectiveness of our proposed schemes, (a)cascaded smoothingand (b)diffusion calibration, mainly on CIFAR-10 [39] and ImageNet [56]: two standard datasets for an evaluation of certifiedℓ 2 -robustness. We provide the detailed experimental setups,e.g., training, datasets, hyperparameters, computes,etc., in Appendix B. Baselines.Our evaluation mainly compares withdiffusion denoised smoothing[11], the current state-of-the-art methodology in randomized smoothing. We additionally compare with two other training baselines from the literature, by considering models with the same classifier architecture but without the denoising step of Carlini et al.[11]. Specifically, we consider (a)Gaussian training[15], which trains a classifier with Gaussian augmentation; and (b)Consistency[35], which additionally regularizes the variance of predictions over Gaussian noise in training. We select the baselines assuming practical scenarios where the training cost of the classifier side is crucial: other existing methods for smoothed classifiers often require much more costs,e.g.,8times over Gaussian [57,73]. Setups.We follow Carlini et al.[11]for the choice of diffusion models: specifically, we use the 50M-parameter32×32diffusion model from Nichol and Dhariwal[52]for CIFAR-10, and the 552M- parameter256×256unconditional model from Dhariwal and Nichol[18]for ImageNet. For the classifier side, we use ViT-B/16 [63] pre-trained via CLIP [53] throughout our experiments. For uses we fine-tune the model on each of CIFAR-10 and ImageNet via FT-CLIP [19], resulting in classifiers that achieve 98.1% and 85.2% in top-1 accuracy on CIFAR-10 and ImageNet, respectively. Following the prior works, we mainly considerσ∈0.25,0.50,1.00for smoothing in our experiments. Evaluation metrics.We consider two popular metrics in the literature when evaluating certified robustness of smoothed classifiers: (a) theapproximate certified test accuracyatr: the fraction of the test set which CERTIFY[15] classifies correctly with the radius larger thanrwithout abstaining, 7 Table 2: Comparison of (a) certified accuracy, (b) empricial accuracy, and (c) average certified radius (ACR) on ImageNet. We set our result bold-faced whenever it achieves the best upon baselines. ImageNet, ViT-B/16@224Empirical accuracy (%)Certified accuracy atε(%) TrainingσIN-1KIN-RIN-A0.00.51.01.52.0ACR Carlini et al. [11]0.2580.969.335.378.861.40.517 Carlini et al. [11]0.5079.567.532.365.852.238.623.60.703 + Cascading (ours)(0.25-0.50)83.569.641.375.052.639.022.80.720 + Calibration (ours)(0.25-0.50)83.869.841.776.654.639.823.00.743 Carlini et al. [11]1.0077.264.332.030.625.820.617.012.60.538 + Cascading (ours)(0.25-1.00)82.669.840.569.042.426.619.014.60.752 + Calibration (ours)(0.25-1.00)83.269.540.872.544.027.519.914.10.775 and (b) theaverage certified radius(ACR) [73]: the average of certified radii on the test setD test while assigning incorrect samples as 0:viz.,ACR := 1 |D test | P (x,y)∈D test [CR(f,σ,x)·1 ˆ f(x)=y ] , whereCR(·)denotes the certified radius thatCERTIFYreturns. Throughout our experiments, we use n= 10,000noise samples to certify robustness for both CIFAR-10 and ImageNet. We follow [15] for the other hyperparameters to runCERTIFY, namely byn 0 = 100, andα= 0.001. In addition to certified accuracy, we also compare theempirical accuracyof smoothed classifiers. Here, we define empirical accuracy by the fraction of test samples those are either (a) certifiably correct, or (b) abstained but correct in thecleanclassifier: which can be a natural alternative especially at denoised smoothing. For this comparison, we usen= 100to evaluate empirical accuracy. Unlike the evaluation of Carlini et al.[11], however, we do not compare cascaded smoothing with theenvelop accuracy curveover multiple smoothed classifiers atσ∈0.25,0.50,1.00: although the envelope curve can be a succinct proxy to compare methods, it can be somewhat misleading and unfair to compare the curve directly with an individual smoothed classifier. This is because the curve does not really construct a concrete classifier on its own: it additionally assumes that each test sample has prior knowledge on the value ofσ∈0.25,0.5,1.0to apply, which is itself challenging to infer. This is indeed what our proposal of cascaded smoothing addresses. 4.1 Results Cascaded smoothing.Figure 2 visualizes the effect of cascaded smoothing we propose in the plots of certified accuracy, and the detailed results are summarized in Table 1 and 2 as “+ Cascading”. Overall, we observe that the certified robustness that cascaded smoothing offers can be highly desirable over the considered single-scale smoothed classifiers. Compared to the single-scale classifiers at highest σ,e.g.,σ= 1.0in Table 1 and 2, our cascaded classifiers acrossσ∈0.25,0.50,1.00absolutely improve the certified accuracy at all the range ofεby incorporating more accurate predictions from classifiers,e.g., of lowerσ∈ 0.25,0.50. On the opposite side,e.g., compared to Carlini et al. [11]atσ= 0.25, the cascaded classifiers provide competitive certified clean accuracy (ε= 0), e.g., 89.5%vs.85.1% on CIFAR-10, while being capable of offering a wider range of robustness certificates. Those considerations are indeed reflected quantitatively in terms of the improvements in ACRs. The existing gaps in the clean accuracy are in principle due to the errors in higher-σclassifiers: i.e., a better calibration, to let them better abstain, could potentially reduce the gaps. Diffusion calibration.Next, we evaluate the effectiveness of our proposed diffusion fine-tuning scheme: “+ Calibration” in Table 1 and 2 report the results on CIFAR-10 and ImageNet, respectively, and Figure 3 plots the CIFAR-10 results for each ofσ∈0.25,0.50,1.00. Overall, on both CIFAR- 10 and ImageNet, we observe that the proposed fine-tuning scheme coulduniformlyimprove certified accuracy across the range considered, even including the clean accuracy. This confirms that the tuning could essentially improve the accuracy-robustness trade-off rather than simply moving along itself. As provided in Table 3, we remark that simply pursuing only the Brier loss(7)may achieve a better ACR in overall, but with a decreased accuracy: it is the role of the anti-consistency loss(8)to balance between the two, consequently to achieve a better trade-off afterwards. Empirical accuracy.In practical scenarios of adopting smoothed classifiers for inference, it is up to users to decide how to deal with the “abstained” inputs. Here, we consider a possible candidate of simply outputting thestandardprediction instead for such inputs: in this way, the output could be noted as an “uncertified” prediction, while possibly being more accurate,e.g., for in-distribution 8 Table 3: Comparison of ACR and certified accuracy of cascaded smooth classifiers on CIFAR-10 over different training and ablations. We useσ∈0.25,0.5,1.0for cascaded smoothing. Bold and underline indicate the best and runner-up, respectively. Model reported in Table 1 is marked as grey. Cascaded,σ∈0.25,0.5,1.0Certified accuracy atε(%) TrainingACR0.000.250.500.751.001.251.501.75 Gaussian [15]0.47070.746.931.723.716.812.49.26.5 Consistency [35]0.54857.642.732.326.322.418.114.611.1 Carlini et al. [11]0.57980.552.837.428.021.716.811.88.5 + Cross-entropy0.60577.952.839.629.122.218.713.59.5 + Brier loss0.66677.655.741.732.726.821.716.311.9 + Anti-consist.(α= 1.0)0.64579.653.540.531.225.020.116.211.4 + Anti-consist.(α= 2.0)0.62580.154.639.230.624.018.514.59.9 + Anti-consist.(α= 1.0)0.56683.955.1 37.825.819.814.511.58.1 Table 4: Comparison of ACR and certified accuracy (%) on CIFAR-10 across two fine-tuning schemes:diffu- sionfine-tuning (“Diff.”; ours) andclassifierfine-tuning (“Class.”) [11]. We useσ= 0.5for this experiment. Fine-tuningCertified accuracy atε(%) Diff.Class.ACR0.000.250.500.751.001.25 ✗0.63975.362.050.639.331.022.9 ✓✗0.66475.164.153.342.132.525.0 ✗✓0.66476.064.752.742.132.424.4 ✓0.67375.264.753.543.832.525.8 Table 5: Comparison of model error rates on CIFAR-10 decomposed into (a) over-smoothing (p≤p 0 ) and (b) over- confidence (p > p 0 ), also with ACR. Error rates (%,↓) Model (σ= 1.0)p≤p 0 p > p 0 ACR (↑) Carlini et al. [11]43.87.60.498 Cascading5.014.50.579 + Anti-consist.4.711.40.566 + Brier loss3.616.80.645 inputs. Specifically, in Table 1 and 2, we consider a fixed standard classifier of CLIP-finetuned ViT-B/16 on CIFAR-10 (or ImageNet), and compare the empirical accuracy of smoothed classifiers on CIFAR-10, -10-C [27] and -10.1 [54] (or ImageNet, -R [28], and -A [30]). Overall, the results show that our smoothed models could consistently outperform even in terms of empirical accuracy while maintaining high certified accuracy,i.e., they abstain only when necessary. We additionally observe in Appendix C.2 that the empirical accuracy of our smoothed model can be further improved by considering an “ensemble” with the clean classifier:e.g., the ensemble improves the accuracy of our cascaded classifier (σ∈0.25,0.5) on CIFAR-10-C by88.8%→95.0%, even outperforming the accuracy of the standard classifier of93.4%. 4.2 Ablation study In Table 3, we compare our result with other training baselines as well as some ablations for a component-wise analysis, particularly focusing on their performance in cascaded smoothing across σ∈ 0.25,0.50,1.00on CIFAR-10. Here, we highlight several remarks from the results, and provide the more detailed study,e.g., the effect ofp 0 (5), in Appendix C.3. Cascading from other training.“Gaussian” and “Consistency” in Table 3 report the certified robustness of cascaded classifiers where each of single-scale models is individually trained by the method. Even while their (certified) clean accuracy ofσ= 0.25models are competitive with those of denoising-based models, their collective accuracy significantly degraded after cascading, and interestingly the drop is much more significant on “Consistency”, although it did provide more robustness at largerε. Essentially, for a high clean accuracy in cascaded smoothing the individual classifiers should make consistent predictions although their confidence may differ: the results imply that individual training of classifiers, without a shared denoiser, may break this consistency. This supports an architectural benefit of denoised smoothing for a use as cascaded smoothing. Cross-entropyvs.Brier.“+ Cross-entropy” in Table 3 considers an ablation of the Brier loss(7) where the loss is replaced by the standard cross-entropy: although it indeed improves ACR compared to Carlini et al.[11]and achieves the similar clean accuracy with “+ Brier loss”, its gain in overall certified robustness is significantly inferior to that of Brier loss as also reflected in the worse ACR. The superiority of the “squared” loss instead of the “log” loss suggests that it may not be necessary to optimize the confidence of individual denoised image toward a value strictly close to 1, which is reasonable considering the severity of noise usually considered for randomized smoothing. 9 Anti-consistency loss.The results marked as “+ Anti-consist.” in Table 3, on the other hand, validates the effectiveness of the anti-consistency loss(8). Compared to “+ Brier loss”, which is equivalent to the case whenα= 0.0in(9), we observe that adding anti-consistency results in a slight decrease in ACR but with an increase in clean accuracy. The increased accuracy of cascaded smoothing indicates that the fine-tuning could successfully reduce over-confidence, and this tendency continues at largerα= 2.0. Even with the decrease in ACR over the Brier loss, the overall ACRs attained are still superior to others, confirming the effectiveness of our proposed loss in total (9). Classifier fine-tuning.In Table 4, we compare our proposed diffusion fine-tuning (Section 3.3) with another possible scheme ofclassifierfine-tuning, of which the effectiveness has been shown by Carlini et al.[11]. Overall, we observe that fine-tuning both classifiers and denoiser can bring their complementary effects to improve denoised smoothing in ACR, and the diffusion fine-tuning itself could obtain a comparable gain to the classifier fine-tuning. The (somewhat counter-intuitive) effectiveness of diffusion fine-tuning confirms that denoising process can be also biased as well as classifiers to make over-confident errors. We further remark two aspects where classifier fine-tuning can be less practical, especially when it comes with the cascaded smoothing pipeline we propose: (a)To perform cascaded smoothing at multiple noise scales, classifier fine-tuning would require separate runs of training for optimal models per scale, also resulting in multiple different models to load - which can be less scalable in terms of memory efficiency. (b)In a wider context of denoised smoothing, the classifier part is often assumed to be a model at scale, even covering cases when it is a “black-box” model,e.g., public APIs. Classifier fine-tuning, in such cases, can become prohibitive or even impossible. With respect to (a) and (b), denoiser fine-tuning we propose offers a more efficient inference archi- tecture: it can handle multiple noise scales jointly with a single diffusion model, while also being applicable to the extreme scenario when the classifier model is black-box. Over-smoothing and over-confidence.As proposed in Section 3.1, errors from smoothed classifiers can be decomposed into two:i.e.,p≤p 0 for over-smoothing, andp > p 0 over-confidence, respec- tively. In Table 5, we further report a detailed breakdown of the model errors on CIFAR-10, assuming σ= 1.0. Overall, we observe that over-smoothing can be the major source of errors especially at such a high noise level, and our proposed cascading dramatically reduces the error. Although we find cascading could increase over-confidence from accumulating errors through multiple inferences, our diffusion fine-tuning could alleviate the errors jointly reducing the over-smoothing as well. 5 Conclusion and Discussion Randomized smoothing has been traditionally viewed as a somewhat less-practical approach, perhaps due to its cost in inference time and impact on accuracy. In another perspective, to our knowledge, it is currently one of a few existing approaches that is prominent in pursuingadversarial robustness at scale,e.g., in a paradigm where training cost scales faster than computing power. This work aims to make randomized smoothing more practical, particularly concerning on scalable scenarios of robustifying large pre-trained classifiers. We believe our proposals in this respect,i.e.,cascaded smoothinganddiffusion calibration, can be a useful step towards building safer AI-based systems. Limitation.A practical downside of randomized smoothing is in its increased inference cost, mainly from the majority voting procedure per inference. Our method also essentially possesses this practical bottleneck, and the proposed multi-scale smoothing scheme may further increase the cost from taking multiple smoothed inferences. Yet, we note that randomized smoothing itself is equipped with many practical axes to reduce its inference cost by compensating with abstention: for example, one can reduce the number of noise samples,e.g., ton= 100. It would be an important future direction to explore practices for a better trade-off between the inference cost and robustness of smoothed classifiers, which could eventually open up a feasible way to obtain adversarial robustness at scale. Broader impact.Deploying deep learning based systems into the real-world, especially when they are of security-concerned [12,72], poses risks for both companies and customers, and we researchers are responsible to make this technology more reliable through research towardsAI safety[2,29]. Adversarial robustness, that we focus on in this work, is one of the central parts of this direction, but one should also recognize that adversarial robustness is still a bare minimum requirement for reliable deep learning. The future research should also explore more diverse notions of AI Safety to establish a realistic sense of security for practitioners,e.g., monitoring and alignment research, to name a few. 10 Acknowledgments and Disclosure of Funding This work was partly supported by Center for Applied Research in Artificial Intelligence (CARAI) grant funded by Defense Acquisition Program Administration (DAPA) and Agency for Defense Development (ADD) (UD230017TD), and by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)). We are grateful to the Center for AI Safety (CAIS) for generously providing compute resources that supported a significant portion of the experiments conducted in this work. We thank Kyuyoung Kim and Sihyun Yu for the proofreading of our manuscript, and Kyungmin Lee for the initial discussions. We also thank the anonymous reviewers for their valuable comments to improve our manuscript. References [1]Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem. Data dependent randomized smoothing. InUncertainty in Artificial Intelligence, pages 64–74. PMLR, 2022. [2]Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in AI safety.arXiv preprint arXiv:1606.06565, 2016. [3] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. InProceedings of the 35th International Conference on Machine Learning, volume 80 ofProceedings of Machine Learning Research, pages 274–283, Stock- holmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR. URLhttp://proceedings.mlr.press/ v80/athalye18a.html. [4]Mislav Balunovic and Martin Vechev. Adversarial training and provable defenses: Bridging the gap. In International Conference on Learning Representations, 2020. URLhttps://openreview.net/forum? id=SJxSDxrKDr. [5] Carlo Bonferroni. Teoria statistica delle classi e calcolo delle probabilita.Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commericiali di Firenze, 8:3–62, 1936. [6] Glenn W Brier. Verification of forecasts expressed in terms of probability.Monthly weather review, 78(1): 1–3, 1950. [7]Anthony Brohan, Yevgen Chebotar, Chelsea Finn, Karol Hausman, Alexander Herzog, Daniel Ho, Julian Ibarz, Alex Irpan, Eric Jang, Ryan Julian, et al. Do as I can, not as I say: Grounding language in robotic affordances. In6th Annual Conference on Robot Learning, 2022. [8]Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. InAdvances in Neural Information Processing Systems, volume 33, pages 1877–1901, 2020. [9] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, and Aleksander Madry.On evaluating adversarial robustness.arXiv preprint arXiv:1902.06705, 2019. [10]Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. In30th USENIX Security Symposium, pages 2633–2650, 2021. [11]Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter. (Certified!!) adversarial robustness for free! InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=JLg5aHHv7j. [12]Rich Caruana, Yin Lou, Johannes Gehrke, Paul Koch, Marc Sturm, and Noemie Elhadad. Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission. InProceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1721–1730, 2015. [13] Chen Chen, Kezhi Kong, Peihong Yu, Juan Luque, Tom Goldstein, and Furong Huang. Insta-RS: Instance- wise randomized smoothing for improved robustness and accuracy.arXiv preprint arXiv:2103.04436, 2021. [14]Charles J Clopper and Egon S Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial.Biometrika, 26(4):404–413, 1934. 11 [15]Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors,Proceedings of the 36th In- ternational Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Re- search, pages 1310–1320, Long Beach, California, USA, 09–15 Jun 2019. PMLR.URLhttp: //proceedings.mlr.press/v97/cohen19c.html. [16]Francesco Croce and Matthias Hein. Provable robustness against all adversariall p -perturbations forp≥1. InInternational Conference on Learning Representations, 2020. [17] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. RobustBench: a standardized adversarial robustness benchmark.arXiv preprint arXiv:2010.09670, 2020. [18]Prafulla Dhariwal and Alexander Nichol.Diffusion models beat GANs on image synthesis.In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors,Ad- vances in Neural Information Processing Systems, volume 34, pages 8780–8794. Curran Asso- ciates, Inc., 2021. URLhttps://proceedings.neurips.c/paper_files/paper/2021/file/ 49ad23d1ec9fa4bd8d77d02681df5cfa-Paper.pdf. [19] Xiaoyi Dong, Jianmin Bao, Ting Zhang, Dongdong Chen, Gu Shuyang, Weiming Zhang, Lu Yuan, Dong Chen, Fang Wen, and Nenghai Yu. CLIP itself is a strong fine-tuner: Achieving 85.7% and 88.0% top-1 accuracy with ViT-B and ViT-L on ImageNet.arXiv preprint arXiv:2212.06138, 2022. [20]Francisco Eiras, Motasem Alfarra, M. Pawan Kumar, Philip H. S. Torr, Puneet K. Dokania, Bernard Ghanem, and Adel Bibi. ANCER: Anisotropic certification via sample-wise volume maximization, 2021. [21] Gamaleldin Elsayed, Shreya Shankar, Brian Cheung, Nicolas Papernot, Alexey Kurakin, Ian Goodfellow, and Jascha Sohl-Dickstein. Adversarial examples that fool both computer vision and time-limited humans. Advances in Neural Information Processing Systems, 31, 2018. [22]Marc Fischer, Maximilian Baader, and Martin Vechev. Certified defense to image transformations via randomized smoothing.Advances in Neural information processing systems, 33:8404–8417, 2020. [23] Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. InIEEE Symposium on Security and Privacy, 2018. [24]Leo A Goodman. On simultaneous confidence intervals for multinomial proportions.Technometrics, 7(2): 247–254, 1965. [25]Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. InIEEE/CVF International Conference on Computer Vision, pages 4842–4851, 2019. [26]Chong Guo, Michael Lee, Guillaume Leclerc, Joel Dapello, Yug Rao, Aleksander Madry, and James Dicarlo. Adversarially trained neural representations are already as robust as biological neural representations. In International Conference on Machine Learning, pages 8072–8081. PMLR, 2022. [27]Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. InInternational Conference on Learning Representations, 2019. URLhttps:// openreview.net/forum?id=HJz6tiCqYm. [28]Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: A critical analysis of out-of-distribution generalization. InProceedings of the IEEE/CVF International Conference on Computer Vision, pages 8340–8349, October 2021. [29] Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in ML safety. arXiv preprint arXiv:2109.13916, 2021. [30]Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15262–15271, June 2021. [31]Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models.Advances in Neural Information Processing Systems, 33:6840–6851, 2020. 12 [32]Miklós Z. Horváth, Mark Niklas Mueller, Marc Fischer, and Martin Vechev. Boosting randomized smoothing with variance reduced classifiers. InInternational Conference on Learning Representations, 2022. URLhttps://openreview.net/forum?id=mHu2vIds_-b. [33]Miklós Z. Horváth, Mark Niklas Müller, Marc Fischer, and Martin Vechev. Robust and accurate – compositional architectures for randomized smoothing. InICLR 2022 Workshop on Socially Responsible Machine Learning, 2022. [34]Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005. [35]Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, 33:10558–10570, 2020. [36]Jongheon Jeong, Sejun Park, Minkyu Kim, Heung-Chang Lee, Doguk Kim, and Jinwoo Shin. SmoothMix: Training confidence-calibrated smoothed classifiers for certified robustness. InAdvances in Neural Information Processing Systems, 2021. URLhttps://openreview.net/forum?id=nlEQMVBD359. [37]Jongheon Jeong, Seojin Kim, and Jinwoo Shin. Confidence-aware training of smoothed classifiers for certified robustness. InProceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8005–8013, 2023. doi: 10.1609/aaai.v37i7.25968. URLhttps://ojs.aaai.org/index.php/AAAI/ article/view/25968. [38] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020. [39]Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Department of Computer Science, University of Toronto, 2009. [40]Li-Cheng Lan, Huan Zhang, Ti-Rong Wu, Meng-Yu Tsai, I-Chen Wu, and Cho-Jui Hsieh. Are AlphaZero- like agents robust to adversarial perturbations? In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors,Advances in Neural Information Processing Systems, 2022. URLhttps: //openreview.net/forum?id=yZ_JlZaOCzv. [41] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In2019 IEEE Symposium on Security and Privacy (SP), pages 656–672. IEEE, 2019. [42]Kyungmin Lee. Provable defense by denoised smoothing with learned score function. InICLR Workshop on Security and Safety in Machine Learning Systems, 2021. [43]Alexander J Levine and Soheil Feizi. Improved, deterministic smoothing forl 1 certified robustness. In International Conference on Machine Learning, pages 6254–6264. PMLR, 2021. [44] Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li. SoK: Certified robustness for deep neural networks.arXiv preprint arXiv:2009.04131, 2020. [45]Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li. Double sampling randomized smoothing. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors,Proceedings of the 39th International Conference on Machine Learning, volume 162 ofProceedings of Machine Learning Research, pages 13163–13208. PMLR, 17–23 Jul 2022. URLhttps://proceedings.mlr. press/v162/li22a.html. [46]Chizhou Liu, Yunzhen Feng, Ranran Wang, and Bin Dong. Enhancing certified robustness via smoothed weighted ensembling, 2020. [47]Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. InInternational Conference on Learning Representations, 2018. URLhttps://openreview.net/forum?id=rJzIBfZAb. [48] Chengzhi Mao, Scott Geng, Junfeng Yang, Xin Wang, and Carl Vondrick. Understanding zero-shot adversarial robustness for large-scale models. InInternational Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=P4bXCawRi5J. [49]Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. InInternational Conference on Machine Learning, volume 80, pages 3578–3586, 10–15 Jul 2018. URLhttp://proceedings.mlr.press/v80/mirman18b.html. 13 [50]Jeet Mohapatra, Ching-Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. Higher- order certification for randomized smoothing.Advances in Neural Information Processing Systems, 33: 4501–4511, 2020. [51]Mark Niklas Mueller, Mislav Balunovic, and Martin Vechev. Certify or predict: Boosting certified robustness with compositional architectures. InInternational Conference on Learning Representations, 2021. URLhttps://openreview.net/forum?id=USCNapootw. [52] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 8162–8171. PMLR, 18–24 Jul 2021. URLhttps://proceedings.mlr.press/v139/nichol21a.html. [53] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. InInternational Conference on Machine Learning, pages 8748–8763. PMLR, 2021. [54] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do CIFAR-10 classifiers generalize to CIFAR-10?, 2018. [55] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High-resolution image synthesis with latent diffusion models. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10684–10695, 2022. [56] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge.International Journal of Computer Vision, 115(3):211–252, 2015. doi: 10.1007/s11263-015-0816-y. [57] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. InAdvances in Neural Information Processing Systems 32, pages 11289–11300. Curran Associates, Inc., 2019. [58] Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers.Advances in Neural Information Processing Systems, 33:21945–21957, 2020. [59]Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. InInternational Conference on Machine Learning, pages 2256–2265. PMLR, 2015. [60]Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann. Intriguing properties of input-dependent randomized smoothing. InProceedings of the 39th International Conference on Machine Learning, volume 162 ofProceedings of Machine Learning Research, pages 20697–20743. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/sukeni-k22a.html. [61]Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2014. [62] Antonio Torralba, Rob Fergus, and William T. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition.IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11):1958–1970, 2008. doi: 10.1109/TPAMI.2008.128. [63] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou. Training data-efficient image transformers & distillation through attention. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 10347–10357. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/touvron21a.html. [64] Florian Tramèr, Jens Behrmann, Nicholas Carlini, Nicolas Papernot, and Jörn-Henrik Jacobsen. Fundamen- tal tradeoffs between invariance and sensitivity to adversarial perturbations. InInternational Conference on Machine Learning, pages 9561–9571. PMLR, 2020. [65]Florian Tramèr, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. InAdvances in Neural Information Processing Systems, volume 33, 2020. 14 [66]Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robust- ness may be at odds with accuracy. InInternational Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=SyxAb30cY7. [67]Lei Wang, Runtian Zhai, Di He, Liwei Wang, and Li Jian. Pretrain-to-finetune adversarial training via sample-wise randomized smoothing, 2021. URLhttps://openreview.net/forum?id=Te1aZ2myPIu. [68]Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. InInternational Conference on Machine Learning, volume 80, pages 5286–5295, 10–15 Jul 2018. URLhttp://proceedings.mlr.press/v80/wong18a.html. [69]Chaowei Xiao, Zhongzhu Chen, Kun Jin, Jiongxiao Wang, Weili Nie, Mingyan Liu, Anima Anandkumar, Bo Li, and Dawn Song. DensePure: Understanding diffusion models for adversarial robustness. InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview. net/forum?id=p7hvOJ6Gq0i. [70]Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. InInternational Conference on Machine Learning, pages 10693–10705. PMLR, 2020. [71]Zhuolin Yang, Linyi Li, Xiaojun Xu, Bhavya Kailkhura, Tao Xie, and Bo Li. On the certified robustness for ensemble models and beyond. InInternational Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=tUa4REjGjTf. [72]Ekim Yurtsever, Jacob Lambert, Alexander Carballo, and Kazuya Takeda. A survey of autonomous driving: Common practices and emerging technologies.IEEE Access, 8:58443–58469, 2020. [73]Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. MACER: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2020. URLhttps://openreview.net/forum? id=rJx1Na4Fwr. [74]Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling Vision Transformers. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12104– 12113, 2022. [75]Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. InProceedings of the 36th In- ternational Conference on Machine Learning, volume 97 ofProceedings of Machine Learning Re- search, pages 7472–7482, Long Beach, California, USA, 09–15 Jun 2019. PMLR.URLhttp: //proceedings.mlr.press/v97/zhang19p.html. [76]Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho- Jui Hsieh. Towards stable and efficient training of verifiably robust neural networks. InInternational Con- ference on Learning Representations, 2020. URLhttps://openreview.net/forum?id=Skxuk1rFwB. [77]Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. General cutting planes for bound-propagation-based neural network verification. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors,Advances in Neural Information Processing Systems, 2022. URLhttps://openreview.net/forum?id=5haAJAcofjc. 15 A Related Work In the context of aggregating multiple smoothed classifiers, several works have previously explored on ensembling smoothed classifiers of the same noise scale [46,32,71], in attempt to boost their certified robustness. Our proposed multi-scale framework for randomized smoothing considers a different setup of aggregating smoothed classifiers of different noise scales, with a novel motivation of addressing the current accuracy-robustness trade-off in randomized smoothing. More in this respect, Mueller et al.[51]have considered a selective inference scheme between a “certification” network (for robustness) and a “core” network (for accuracy), and Horváth et al.[33]have adapted the framework into randomized smoothing. Our approach explores an orthogonal direction, and can be viewed as directly improving the “certification” network here: in this way, we could offer improvements not only in empirical but also incertifiedaccuracy as a result. Independently to our method, there have been approaches to further tighten the certified lower-bound that randomized smoothing guarantees [50,70,43,45,69]. Mohapatra et al.[50]have shown that higher-order information of smoothed classifiers,e.g., its gradient on inputs, can tighten the certification of Gaussian-smoothed classifiers, beyond that only utilizes the zeroth-order information of smoothed confidence. In the context of denoised smoothing [58,11], Xiao et al.[69]have recently proposed a multi-step, multi-round scheme for diffusion models to improve accuracy of denoising at randomized smoothing. Such approaches could be also incorporated to our method to further improve certification. Along with the developments of randomized smoothing, there have been also other attempts in certifying deep neural networks against adversarial examples [23,68,49,25,76,16,4,77], where a more extensive survey on the field can be found in Li et al. [44]. B Experimental Details B.1 Datasets CIFAR-10[39] consist of 60,000 images of size 32×32 pixels, 50,000 for training and 10,000 for testing. Each of the images is labeled to one of 10 classes, and the number of data per class is set evenly,i.e., 6,000 images per each class. By default, we do not apply any data augmentation but the input normalization with mean[0.5,0.5,0.5]and standard deviation[0.5,0.5,0.5], following the standard training configurations of diffusion models. The full dataset can be downloaded at https://w.cs.toronto.edu/~kriz/cifar.html. CIFAR-10-C[27] are collections of 75 replicas of the CIFAR-10 test datasets (of size 10,000), which consists of 15 different types of common corruptions each of which contains 5 levels of corruption severities. Specifically, the datasets includes the following corruption types: (a)noise: Gaussian, shot, and impulse noise; (b)blur: defocus, glass, motion, zoom; (c)weather: snow, frost, fog, bright; and (d)digital: contrast, elastic, pixel, JPEG compression. In our experiments, we evaluate test errors on CIFAR-10-C for models trained on the “clean” CIFAR-10 datasets, where the error values are averaged across different corruption types per severity level. The full datasets can be downloaded at https://github.com/hendrycks/robustness. CIFAR-10.1[54] is a reproduction of the CIFAR-10 test set that are separately collected from Tiny Images dataset [62]. The dataset consists of 2,000 samples for testing, and designed to minimize distribution shift relative to the original CIFAR-10 dataset in their data creation pipelines. The full dataset can be downloaded athttps://github.com/modestyachts/CIFAR-10.1, where we use the “v6” version for our experiments among those given in the repository. ImageNet[56], also known as ILSVRC 2012 classification dataset, consists of 1.2 million high- resolution training images and 50,000 validation images, which are labeled with 1,000 classes. As a data pre-processing step, we apply a 256×256 center cropping for both training and testing images after re-scaling the images to have 256 in their shorter edges, making it compatible with the pre- processing of ADM [18], the backbone diffusion model. Similarly to CIFAR-10, all the images are normalized with mean[0.5,0.5,0.5]and standard deviation[0.5,0.5,0.5]. A link for downloading the full dataset can be found inhttp://image-net.org/download. ImageNet-R[28] consists of 30,000 images of various artistic renditions for 200 (out of 1,000) ImageNet classes:e.g., art, cartoons, deviantart, graffiti, embroidery, graphics, origami, paintings, patterns, plastic objects, plush objects, sculptures, sketches, tattoos, toys, video game renditions, 16 and so on. To perform an evaluation of ImageNet classifiers on this dataset, we apply masking on classifier logits for the 800 classes those are not in ImageNet-R. The full dataset can be downloaded athttps://github.com/hendrycks/imagenet-r. ImageNet-A[30] consists of 7,500 images of 200 ImageNet classes those are “adversarially” filtered, by collecting natural images that causes wrong predictions from a pre-trained ResNet-50 model. To perform an evaluation of ImageNet classifiers on this dataset, we apply masking on classifier logits for the 800 classes those are not in ImageNet-A. The full dataset can be downloaded at https://github.com/hendrycks/natural-adv-examples. B.2 Training CLIP fine-tuning.We follow the training configuration suggested by FT-CLIP [19] in fine- tuning the CLIP ViT-B/16@224 model, where the full script is specified athttps://github.com/ LightDXY/FT-CLIP. The same configuration is applied to all the datasets considered for fine-tuning, namely CIFAR-10, ImageNet, and Gaussian-corrupted versions of CIFAR-10 (for baselines such as “Gaussian” and “Consistency”), which can be done by resizing the datasets into224×224as a data pre-processing. We fine-tune all these tested models for 50 epochs on each of the considered datasets. Diffusion fine-tuning.Similarly to the CLIP fine-tuning, we follow the training details given by Nichol and Dhariwal[52]in fine-tuning diffusion models, which are specified inhttps://github. com/openai/improved-diffusion. More concretely, here we fine-tune each pre-trained diffusion model by “resuming” the training following its configuration, but with an added regularization term we propose upon the original training loss. We use the 50M-parameter32×32diffusion model from Nichol and Dhariwal[52]for CIFAR-10, 6 and the 552M-parameter256×256unconditional model from Dhariwal and Nichol[18]for ImageNet 7 to initialize each fine-tuning run. We fine-tune each model for 50K training steps, using batch size 128 and 64 for CIFAR-10 and ImageNet, respectively. B.3 Hyperparameters Unless otherwise noted, we usep 0 = 0.5forcascaded smoothingthroughout our experiments. We mainly consider two configurations of cascaded smoothing: (a)σ∈ 0.25,0.50,1.00, and (b) σ∈0.25,0.50, each of which denoted as “(0.25-1.00)” and “(0.25-0.50)” in tables, respectively. Fordiffusion calibration, on the other hand, we useα= 1.0by default. We useλ= 0.01on CIFAR-10 andλ= 0.005on ImageNet, unless noted: we halve the regularization strengthλ on ImageNet considering its batch size used in the fine-tuning,i.e., 128 (for CIFAR-10)vs.64 (for ImageNet). In other words, we followλ= 0.01·(batch_size/128). Among the baselines considered, “Consistency” [35] requires two hyperparameters: the coefficient for the consistency termηand the entropy termγ. Following those considered by Jeong and Shin[35], we fixγ= 0.5 andη= 5.0throughout our experiments. B.4 Computing infrastructure Overall, we conduct our experiments with a cluster of 8 NVIDIA V100 32GB GPUs and 8 instances of a single NVIDIA A100 80GB GPU. All the CIFAR-10 experiments are run on a single NVIDIA A100 80GB GPU, including both the diffusion fine-tuning and the smoothed inference procedures. For the ImageNet experiments, we use 8 NVIDIA V100 32GB GPUs per run. In our computing environment, it takese.g.,∼10 seconds and∼5 minutes per image (we usen= 10,000for each inference) to perform a single pass of smoothed inference on CIFAR-10 and ImageNet, respectively. For a single run of fine-tuning diffusion models, we observe∼1.5 days of training cost on CIFAR-10 with a single NVIDIA A100 80GB GPU, and that of∼4 days on ImageNet using a cluster of 8 NVIDIA V100 32GB GPUs, to run 50K training steps. At inference time, our proposed cascaded smoothing may introduce an extra computational overhead as the cost for the increased accuracy,i.e., from taking multiple times of smoothed inferences. Nevertheless, remark that the actual overhead per input in practice can be different depending on the early-stopping result of cascaded smoothing. For example, in our experiments, we observe that 6 https://github.com/openai/improved-diffusion 7 https://github.com/openai/guided-diffusion 17 Carlini et al. (2023) IDRS (E[σ] ≈0.263) Ours (σ∈0.2, 0.25, 0.3) Ours (σ∈0.25, 0.5) Certified accuracy 0 0.2 0.4 0.6 0.8 1.0 Radius 00.51.01.5 Figure 4: Comparison of certified test accu- racy with (a) Carlini et al.[11]atσ= 0.25, (b)Input-Dependent Randomized Smoothing (IDRS) proposed by Súkeník et al.[60]. For (b), we adopt the per-sampleσvalues of CIFAR-10 test set of Súkeník et al. [60]. p 0 = 0.5 p 0 = 0.6 p 0 = 0.7 p 0 = 0.8 p 0 = 0.9 0 0.2 0.4 0.6 σ x ABSTAIN0.250.501.00 Figure 5: Comparison of histograms acrossp 0 ∈ [0.5,1.0)on the distribution ofσ’s where each of CIFAR-10 test samples halts from cascaded smooth- ing. Each of smoothed inferences is performed with n= 10,000noise samples andα= 0.001. the average inference time to process the CIFAR-10 test set via cascaded smoothing is only∼1.5× compared to standard (single-scale) smoothed inferences, even consideringσ∈0.25,0.5,1.0. C Additional Results C.1 Comparison with input-dependent smoothing In a sense that the proposed cascaded smoothing results in different smoothing factorsσper-sample basis, our approach can be also viewed in the context ofinput-dependent randomized smoothing [1,67,13,20], a line of attempts to improve certified robustness by applying different smoothing factorσconditioned on input. From being more flexible in assigningσ, however, these approaches commonly require more assumptions for their certification, making them hard to compare directly upon the standard evaluation protocol,e.g., that we considered in our experiments. For example, Súkeník et al.[60]have proved that such a scheme of freely assigningσdoes not provide valid robustness certificates in the standard protocol, and [1,20] in response have suggested to further assume that all the previous test samples during evaluation can be memorized to predict future samples, which can affect the practical relevance of the overall evaluation protocol. To address the issue, Súkeník et al.[60]have also proposed a fix of [1] to discard its test-time dependency, by assuming a more strict restriction on the variation ofσ. Nevertheless, they also report that the benefit of input-dependentσthen becomes quite limited, supporting the challenging nature of input-dependent smoothing. As shown in Figure 4 that additionally compares our method with [60], we indeed confirm that cascaded smoothing offers significantly wider robustness certificates with a better accuracy trade-off. This is unprecedented to the best of our knowledge, which could be achieved from our completely new approach of data-dependent smoothing:i.e., by combining multiple smoothed classifiers through abstention, moving away from the previous attempts that are focused on obtaining a single-step smoothing. C.2 Clean ensemble for empirical accuracy In this appendix, we demonstrate that predictions from smoothed classifiers can not only useful to obtain adversarial robustness, but also to improve out-of-distribution robustness ofcleanclassifiers, which suggests a new way to utilize randomized smoothing. Specifically, consider a smoothed classifier ˆ f , and its smoothed confidences atx, sayp ˆ f (y|x)fory∈Y. Next, we consider prediction confidences of a “clean” prediction, namelyp f (y|x). Remark thatp f (y|x)can be interpreted in terms oflogits, namelylogp f (x|y), of a neural network based modelfas follows: p f (y|x) = p f (x,y) p f (x) = p(y)·p f (x|y) P y∈Y p f (x,y) .(10) Note that the priorp(y)is usually assumed to be the uniform distributionU(Y). Here, we consider a variant of this prediction, by replacing the priorp(y)by amixtureofp(y)and asmoothed prediction 18 Table 6: Comparison of per-corruption empirical accuracy of clean (“FT-CLIP”) and smoothed classifiers (Others) on CIFAR-10-C. For each corruption type, we report accuracy averaged over 5 levels of severity, and for each level we use 1,000 uniform subsamples to compute the accuracy. MethodCleanGaussianShotImpulseDefocusGlassMotionZoomSnowFrostFogBrightnessContrastElasticPixelateJPEGAVG FT-CLIP [19]98.183.788.796.496.885.795.096.196.196.097.097.897.594.791.088.593.4 Carlini et al. [11]88.885.886.988.787.383.686.886.085.283.678.987.875.785.486.485.884.9 + Casc. + Calib.92.589.090.191.590.787.389.690.789.989.486.091.181.289.790.489.389.1 + Clean prior98.090.993.096.596.889.995.296.396.296.696.897.797.495.394.291.695.0 Table 7: Comparison of empirical accuracy and certified accuracy of cascaded smooth classifiers on CIFAR-10 across ablations onλ. We useσ∈0.25,0.5,1.0for cascaded smoothing. CIFAR-10EmpiricalCertified accuracy atε(%) SetupsClean0.000.250.500.751.001.251.501.75 λ= 0.001 α= 1.084.179.954.439.630.924.218.913.99.3 α= 2.084.380.753.938.929.723.918.713.09.6 α= 4.085.180.952.839.129.523.217.312.49.4 α= 8.086.181.553.238.529.022.017.113.08.8 λ= 0.01 α= 1.082.979.653.540.531.225.020.116.211.4 α= 2.084.880.154.639.230.624.018.514.59.9 α= 4.085.180.453.639.129.522.817.813.19.5 α= 8.086.181.554.539.027.721.417.312.98.8 λ= 0.1 α= 1.080.877.253.939.931.424.820.115.511.6 α= 2.082.778.053.939.930.724.119.815.111.1 α= 4.082.178.352.639.130.122.617.413.710.0 α= 8.083.778.251.136.928.022.317.913.19.1 Table 8: Comparison of empirical accuracy and certified accuracy of cascaded smooth classifiers on CIFAR-10 across ablations onp 0 . We useσ∈0.25,0.5,1.0for cascaded smoothing. CIFAR-10EmpiricalCertified accuracy atε(%) SetupsClean0.000.250.500.751.001.251.501.75 p 0 = 0.5084.881.152.837.227.921.716.811.88.5 p 0 = 0.5587.982.653.535.626.919.814.010.17.1 p 0 = 0.6090.783.952.734.523.916.911.98.36.4 p 0 = 0.6592.583.452.134.022.614.49.87.05.5 p 0 = 0.7094.183.052.631.619.212.28.26.34.7 p 0 = 0.7595.281.952.229.116.59.56.75.23.7 p 0 = 0.8096.079.547.625.014.08.05.94.62.4 p 0 = 0.8596.676.345.022.812.57.14.72.82.2 p 0 = 0.9097.272.142.520.011.74.62.81.91.0 p 0 = 0.9597.865.538.616.77.22.21.70.70.0 p(ˆy) :=p ˆ f (y|x): in this way, one could use ˆ f(x) as an additional prior to refine the clean confidence in cases when the two sources of confidence do not match. More specifically, we consider: logp f (ˆy|x) := logp β ˆ f (y|x) + logp f (x|y) +C,where(11) logp β ˆ f (y|x) := (1−β)·logp ˆ f (y|x) +β·p(y).(12) whereCdenotes the normalizing constant, andβ >0is a hyperparameter which we fix asβ= 0.1 in our experiment. In Table 6, we compare the accuracy of the proposed inference with the accuracy of standard classifiers derived from FT-CLIP [19] fine-tuned on CIFAR-10: overall, we observe that this “ensemble” of clean prediction with cascaded smoothed predictions could improve the corruption accuracy of FT-CLIP on CIFAR-10-C, namely by93.4%→95.0%, while maintaining its clean accuracy. The gain can be considered significant in a sense that the baseline accuracy of93.4%is already at the state-of-the-art level,e.g., according to RobustBench [17]. 19 Critical σ 0 0.5 1.0 1.5 2.0 CIFAR-10 Classes PlaneCarBirdCatDeerDogFrogHorseShipTruck Figure 6: Comparison of per-class histograms ofcriticalσ: the minimum value ofσfor each input where the smoothed confidence at true class falls below0.5. We use the whole CIFAR-10 training samples for the analysis. Each image is smoothed withn= 1,000samples of Gaussian noise, while iteratingσwithin the rangeσ∈[0.0,2.0]. Images with criticalσlarger than2.0are truncated. C.3 Ablation study Effect ofλ.In Table 7, we jointly ablate the effect of tuningλ∈ 0.001,0.01,0.1upon the choices ofα∈ 1.0,2.0,4.0,8.0, by comparing its certified accuracy of cascaded smoothing as well as their empirical accuracy on CIFAR-10 test set. Overall, we observe that increasingλhas an effect of improving robustness at large radii, with a slight decrease in the clean accuracy as well as the empirical accuracy, where using higherαcould compensate this at some extent. Although we generally observe effectiveness of the proposed regularization for a wide range ofλ, using higher values ofλ,e.g.,λ= 0.1, often affects the base diffusion model and results in a degradation in accuracy without a significant gain in its certified robustness. Effect ofp 0 .Table 8, on the other hand, reports the effect ofp 0 we introduced for cascaded smoothing. Recall that we usep 0 = 0.5throughout our experiments by default. We observe that using a bit of higher values ofp 0 ,e.g.,p 0 = 0.6could be beneficial to improve the clean accuracy of cascaded smoothing, at the cost of robustness at larger radii: for example, it improves the certified accuracy atr= 0.0by81.1→83.9. The overall certified robustness starts to decrease asp 0 further increases, due to its effect of increasing abstention rate. One could still observe the consistent improvement in the empirical accuracy asp 0 increases,i.e., by also considering abstain as a valid prediction,i.e., using high values ofp 0 could be useful in certain scenarios. We think a more detailed choice ofp 0 perσcan further boost the performance of cascaded smoothing, which is potentially an important practical consideration. Criticalσ.Although it is not required for cascaded smoothing to guarantee the stability of smoothed confidences acrossσ(e.g., outside of0.25,0.5,1.0in our experiments), we observe that smoothed confidences from denoised smoothing usually interpolate smoothly between differentσ’s, at least for the diffusion denoised smoothing pipeline. In this respect, we consider a new concept ofcriticalσ for each sample, by measuring the threshold ofσwhere its confidence goes belowp 0 = 0.5. Figure 6 examines this measure on CIFAR-10 training samples and plots its distribution for each class as histograms. Interestingly, we observe that the distributions are often significantly biased,e.g., the “Ship” class among CIFAR-10 classes relatively obtains much higher criticalσ- possibly due to its peculiar background of,e.g., ocean. Per-σdistribution from cascading.To further verify that per-sampleσ’s from cascaded smoothing are diverse enough to achieve better robustness-accuracy trade-off, we examine in Figure 5 the actual histograms of the resultingσ∈ ABSTAIN,0.25,0.50,1.00on CIFAR-10, also varying p 0 ∈0.5,0.6,0.7,0.8,0.9. Overall, we observe that (a) the distributions ofσ x indeed widely cover the total range ofσfor everyp 0 ’s considered, and (b) using higherp 0 can further improve diversity of the distribution while its chance to be abstained can be also increased. D Technical Details D.1 Proof of Theorem 3.1 Our proof is based on the fact that any smoothed classifier ˆ f composed withΦ −1 (·)is always Lipschitz-continuous, which is shown by Salman et al. [57]: 20 Lemma D.1(followed by Salman et al.[57]).LetΦ(a) := 1 √ 2π R a −∞ exp − 1 2 s 2 ds be the cu- mulative distribution function of standard Gaussian. For any functionf:R d →[0,1], the map x7→σ·Φ −1 (p ˆ f σ (x))is 1-Lipschitz for anyσ >0. Given Lemma D.1, the robustness certificate by Cohen et al.[15]in (2) (of the main text) can be viewed as computing the region ofp ˆ f σ (x+δ;y)>0.5 ,i.e., where it is guaranteed to returnyover other (binary) smoothed classifiersp ˆ f σ (x+δ;y ′ )ofy̸=y ′ . In general, as in our proposedcascaded smoothing, one can consider a more “strict” region defined byp ˆ f σ (x+δ;y)> p 0 for somep 0 ≥0.5. Here, the region corresponds to a policy that ˆ f σ abstains wheneverp ˆ f σ (x)≤p 0 . Accordingly, the certified radius one can obtain from this policy becomes: R p 0 ( ˆ f σ ;x,y) :=σ· Φ −1 (p ˆ f σ (x,y))−Φ −1 (p 0 ) .(13) With this notation, we restate Theorem 3.1 into a tighter form to show, which do not consider neither pnorpupon the knowledge ofp ˆ f σ k and implies Theorem 3.1 as a consequence: Theorem 3.1 (restated).Let ˆ f σ 1 ,·, ˆ f σ K :X → Ybe smoothed classifiers with0< σ 1 < ·< σ K . Supposecasc(x; ˆ f σ i K i=1 ) =: ˆy∈ Yhalts at ˆ f σ k for somek. Then, it holds that casc(x+δ; ˆ f σ i K i=1 ) = ˆyfor∥δ∥< R, where: R:= min n R p 0 ( ˆ f σ k ;x,ˆy),R − o ,andR − := min y̸=ˆy k ′ >k n min n 0,−R p 0 ( ˆ f σ k ′ ;x,y) o .(14) Proof.By the definition ofcasc(x), one can ensurecasc(x+δ) = ˆyif the following holds: (a) ˆ f σ k (x+δ) = ˆywithp ˆ f σ k (x+δ,ˆy)> p 0 , and (b)p ˆ f σ k ′ (x+δ)< p 0 or ˆ f σ k ′ (x+δ) = ˆy, for everyk ′ =k+ 1,·,K. Remark that the condition (a) is satisfied byδwithin∥δ∥< R p 0 ( ˆ f σ k ;x,ˆy) . Specifically, one can consider the “certifiable” region ofδat ˆ f σ k as follows: R k =δ∈X:∥δ∥< R p 0 ( ˆ f σ k ;x,ˆy).(15) For the condition (b), on the other hand, note that the condition is equivalent to that: (b ′ )p ˆ f σ k ′ (x+δ;y)< p 0 fory̸= ˆy, and for everyk ′ =k+ 1,·,K. Fixk ′ ∈k+ 1,·,K . From the Lipschitzedness ofx7→σ·Φ −1 (p ˆ f σ (x;y)) by Lemma D.1, it is clear to show thatδ’s inside the following regionR k ′ satisfies (b ′ ): R k ′ = \ y̸=ˆy n δ∈X:∥δ∥<min n 0,−R p 0 ( ˆ f σ k ′ ;x,y) o (16) = δ∈X:∥δ∥<min y̸=ˆy n min n 0,−R p 0 ( ˆ f σ k ′ ;x,y) o .(17) Lastly, the result is followed by considering the intersection ofR k ’s which represent a certifiable region wherecasc(x+δ; ˆ f σ i K i=1 ) = ˆy: R:=R k ∩(∩ k ′ ≥k+1 R k ′ ) =δ∈X:∥δ∥< R.(18) Once we have the restated version of Theorem 3.1 above, the original statement follows from an observation that the new radius by introducing eitherporp, sayR, always lower-boundsRof the above:i.e.,R≤Rfor any choices ofpandp, thus certifiable for the region as well. 21 D.2 Certification and prediction For practical uses of cascaded smoothing, where the exact values ofp ˆ f σ k (x,y)are not available, one has to estimate the smoothed confidence values as per Theorem 3.1,i.e., by properly lower-bound (or upper-bound) the confidence values. More concretely, one is required to obtain (a)p ˆ f σ k (x)at the halting stagek, and (b)p ˆ f σ k ′ (x,y)fork ′ =k+ 1,·,Kandy∈Y. For both estimations, we use Monte Carlo algorithm withni.i.d.Gaussian samples, sayδ i , and perform a majority voting acrossf σ (x+δ i )to obtain a histogram onYofntrials: (a)To estimate a lower-boundp ˆ f σ k (x), we follow the statistical procedure by Cohen et al. [15], namelyCERTIFY(n,n 0 ,α), which additionally takes two hyper-parametersn 0 andα: here,n 0 denotes the number of samples to initially make a guess to estimate a smoothed prediction, andαis the significance level of the Clopper-Pearson confidence interval [14]. Concretely, it setsp ˆ f σ k as the lower confidence level ofp ˆ f σ k with coverage1−α. (b) Forp ˆ f σ k ′ (x,y), on the other hand, we first obtain voting counts fromnGaussian trials, say c (σ k ′ ) x , and adopt Goodman confidence interval to bound multinomial proportions [24] with the significance levelα. Specifically, one can setp ˆ f σ k ′ (x,y) fory∈Yby the(1−α)-upper level of the (multinomial) confidence interval. This can be implemented by using,e.g., multinomial_proportions_confintof thestatsmodelslibrary. We make an additional treatment on the significance levelα: unless the pipeline halts at the first stageK, cascaded smoothing makes a(K−k+ 1)-consecutive testing of confidence intervals to make a prediction. In attempt to maintain the overall significance level of this prediction asα, one can apply the Bonferroni correction [5] on the significance level of individual testing, specifically by considering α (K−k+1) as the adjusted significance level (instead of usingα) at the stagek. E Other Possible Designs In this appendix, we present two alternative designs of multi-scale randomized smoothing we have also considered other thancascaded smoothingproposed in the main text. Specifically, here we additionally propose two different policies of aggregating multiple smoothed classifiers, each of which dubbed as the (a)max-radius policy, and (b)focal smoothing, respectively. Overall, both design do provide valid certified guarantees combining the accuracy-robustness trade-offs across multiple smoothing factors, often attaining a better robustness even compared to cascaded smoothing whenn, the number of noise samples, is large enough. The common drawback in the both approaches here, however, is the necessity to access every smoothed confidence, which can be crucial in practice in both terms of efficiency and accuracy. Specifically, for givenKsmoothed classifiers, this implies the exactK-times increase in the inference cost, which makes it much costly on average compared to cascaded smoothing. The need to access and compare withKsmoothed confidence in practice also demands more accurate estimations of the confidence values to avoid abstaining. For example, these approaches can significantly degrade the certified accuracy in practice wherencannot be large unlike the certification phase: which again makes our cascaded smoothing more favorable over the approaches presented here. E.1 Max-radius policy ConsiderKsmoothed classifiers, say ˆ f σ 1 ,·, ˆ f σ K :X → Y , where0< σ 1 <·< σ K . The max-radiuspolicy, saymaxR(·), can be another simple policy one can consider for given ˆ f σ i : maxR(x; ˆ f σ i K i=1 ) := ˆ f σ ∗ (x), whereσ ∗ := arg max σ i σ i ·Φ −1 p ˆ f σ i (x) .(19) Again, given the Lipschitzedness associated with the smoothed confidencesp ˆ f σ (x,y), it is easy to check the following robustness certificate formaxR(x; ˆ f σ i K i=1 ): 22 Theorem E.1.Let ˆ f σ 1 ,·, ˆ f σ K :X → Ybe smoothed classifiers with0< σ 1 <·< σ K . If maxR(x; ˆ f σ i K i=1 ) =: ˆy∈Y, it holds thatmaxR(x+δ; ˆ f σ i K i=1 ) = ˆyfor∥δ∥< R, where: R:= 1 2 · σ ∗ ·Φ −1 p ˆ f σ ∗ (x) −max y̸=ˆy i=1,·,K σ i ·Φ −1 p ˆ f σ i (x;y) .(20) Remark that the certified radius given by (20) recovers the guarantee of Cohen et al. [15] ifK= 1. E.2 Focal smoothing In this method, coinedfocal smoothing, we take a somewhat different approach to achieve multi-scale smoothing. Here, now we assume two different levels of smoothing factor, sayσ 0 > σ 1 >0, and consider inputs that contains noise withspatially differentmagnitudes. Specifically, we consider a binary maskM∈0,1 d and an input corrupted by the following: focal(x,M;σ 0 ,σ 1 ) :=x+ (σ 0 ·(1−M) +σ 1 ·M)⊙ε,(21) where⊙denotes the element-wise product andε∼N(0,I). In this way, each of corrupted input ˆ x gets a “hint” to recover the original content ofxby observing a less-corrupted region marked byM. Randomized smoothing over suchanisotropicnoise has been recently studied [22,20]: in a nutshell, smoothing over noises specified by(21)could produce anellipsoid-shapedcertified region with two axes of lengthσ 0 Φ −1 (p)andσ 1 Φ −1 (p)for its smoothed confidencep, respectively. In terms of certified radius, however, this implies that one can still certify only the region limited by the shorter axes (of lengthσ 1 Φ −1 (p)). It turns out that such a limitation can be avoided by considering an “ensemble” ofKmultiple orthogonal masks, sayM 1 ,·,M K , so that the shorter axes of ellipsoids from the masks do not overlap each other. Specifically, we observe the following: Theorem E.2.LetM 1 ,·,M K ∈0,1 d beKorthogonal masks andσ 0 > σ 1 >0be smoothing factors, andp k (x)be the smoothed confidence from inputs corrupted byfocal(x,M k ;σ 0 ,σ 1 ), for a given binary classifierf k :R d →[0,1]. Defineˆp:= 1 K P k p k , and supposeˆp(x)>0.5. Then, it is certified thatˆp(x+δ)>0.5for∥δ∥< R b ∗ , whereb ∗ is the solution of the following optimization: minimize b R b := 1 K X k a k √ t 2 b k + 1 subject to X k b k = 1, b k ≥0, k= 1,2,·,K, (22) wherea k :=σ 0 Φ −1 (p k )fork= 1,·,K, andt 2 := σ 2 0 σ 2 1 −1 . In Algorithm 1, we propose an efficient 1-dimensional grid-search based optimization to solve (22), based on observations given as Lemma E.3 and E.4: each of which identifies the condition ofb k when it attains either the maximum value or zero, respectively. By solving the optimization, one could obtain a certified radiusRthat the aggregated smoothing can guarantee consistent prediction. Lemma E.3.Consider the constrained optimization(22)with respect tob= (b 1 ,·,b K ). Let M a :=m∈[K] :a m = max k a k andb ∗ be an optimal solution of(22). Then, it holds that b ∗ m =b ∗ m ′ >0for anym,m ′ ∈M a . Proof.First, we show that there exists at least onem∈M a whereb ∗ m is nonzero,i.e.,b ∗ m >0. Suppose the contrary,i.e.,b ∗ k = 0for allk∈M a . Denote the corresponding objective value asR ∗ . Given the condition P k b k = 1, there always existsi /∈Mwhereb i >0. Now, consider swapping the allocations ofb m andb i for somem∈M a and denote the corresponding objective valueR ′ . 23 Algorithm 1Focal smoothing: A grid-search based optimization of (22) Require:a k >0,k= 1,2,...,K, toleranceε >0 Ensure:optimal budget assignmentb ∗ , certified radiusR ∗ 1: Find the maximum valuea max = max k a k 2: Identify the index setMsuch thata k =a max fork∈M 3: Set a grid of values forb m in the interval(0,1]. 4:foreach grid value ofb m do 5:fork= 1,2,...,Kdo 6:ifk /∈Mthen 7:b k ←0ifa k ≤ a m (t 2 b m +1) 3/2 else 1 t 2 a k a m 2/3 (t 2 b m + 1)−1 8:end if 9:end for 10:if| P K k=1 b k −1|≤εthen 11:R← 1 K P K k=1 a k √ t 2 b k +1 12:Updateb ∗ k ,R ∗ ←b k ,RifR < R ∗ 13:end if 14:end for Then, we have: R ′ −R ∗ = 1 K a k p t 2 b j + 1 + a j √ t 2 b k + 1 − a k √ t 2 b k + 1 − a j p t 2 b j + 1 ! = 1 K a k 1 p t 2 b j + 1 − 1 √ t 2 b k + 1 ! +a j 1 √ t 2 b k + 1 − 1 p t 2 b j + 1 !! < 1 K a k 1 p t 2 b j + 1 − 1 √ t 2 b k + 1 ! +a k 1 √ t 2 b k + 1 − 1 p t 2 b j + 1 !! = 0, (23) given thata k > a j and 1 √ t 2 b j +1 < 1 √ t 2 b k +1 = 1. This meansR ′ < R ∗ , contradicting the optimality of the initial solutionb ∗ withb k = 0for allk∈M a . Thus, there must exist at least oneb ∗ m >0 for somem∈M a . Next, we showb ∗ m =b ∗ m ′ for anym,m ′ ∈M a . Suppose there exist suchm,m ′ ∈M a where b ∗ m ̸=b ∗ m ′ . Due to the symmetry, one can construct another optimal allocationb ′ by swapping the two allocationsb ∗ m andb ∗ m ′ , as it does not affect the optimality. Now consider another allocation ̄ b by averaging the two allocations: ̄ b m = ̄ b m ′ = b ∗ m +b ∗ m ′ 2 .(24) Let the corresponding objective value ̄ R. Note thatRis strictly convex, which it implies that ̄ R < R ∗ , contradicting the optimality of the initial solutionb ∗ . Thus, it holdsb ∗ m =b ∗ m ′ for any m,m ′ ∈M a . Lemma E.4.Consider the constrained optimization(22)withb ∗ as an optimal solution. Denote B:=b ∗ m =b ∗ m ′ >0for allm,m ′ ∈M a . Then,b ∗ k = 0if and only ifa k ≤ A (t 2 B+1) 3/2 . Proof. Supposeb ∗ k = 0. From the Karush–Kuhn–Tucker (KKT) stationarity condition, we have −a k t 2 K +λ−μ k = 0 . Sinceλ,μ k ≥0, we obtainλ≥ a k t 2 K . Now, consider the stationarity condition form∈M:− At 2 K( √ t 2 B+1) 3 +λ= 0 . Substituting the lower bound forλ, we have a k ≤ A (t 2 B+1) 3/2 . Conversely, supposea k ≤ A (t 2 B+1) 3/2 . Then,b ∗ k >0contradict to thatb ∗ k = 1 t 2 a k A 2/3 (t 2 B+ 1)−1 ≤0, henceb ∗ k = 0. 24