Diffusion Models are Certifiably Robust Classifiers
Authors: Huanran Chen
Yinpeng Dong
Shitong Shao
Zhongkai Hao
Xiao Yang
Hang Su
Jun Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: certified robustness
diffusion classifier
adversarial robustness
Primary area: safety_in_machine_learning
TL;DR: We derive the certified radius and Lipschitz constant for diffusion classifiers. We also generalize diffusion classifiers to classify noisy data.

Abstract: Generative learning, recognized for its effective modeling of data distributions, offers inherent advantages in handling out-of-distribution instances, especially for enhancing robustness to adversarial attacks. Among these, diffusion classifiers, utilizing powerful diffusion models, have demonstrated superior empirical robustness. However, a comprehensive theoretical understanding of their robustness is still lacking, raising concerns about their vulnerability to stronger future attacks. In this study, we prove that diffusion classifiers possess $O(1)$ Lipschitzness, and establish their certified robustness, demonstrating their inherent resilience. To achieve non-constant Lipschitzness, thereby obtaining much tighter certified robustness, we generalize diffusion classifiers to classify Gaussian-corrupted data. This involves deriving the evidence lower bounds (ELBOs) for these distributions, approximating the likelihood using the ELBO, and calculating classification probabilities via Bayes' theorem. Experimental results show the superior certified robustness of these Noised Diffusion Classifiers (NDCs). Notably, we achieve over 80\% and 70\% certified robustness on CIFAR-10 under adversarial perturbations with \(\ell_2\) norms less than 0.25 and 0.5, respectively, using a single off-the-shelf diffusion model without any additional data.

Diffusion Models are Certifiably Robust Classifiers
Huanran Chen 1.2 Yinpeng Dong SShitong Shao' Zhongkai Hao', Xiao Yang', Hang Su Jun Zhu' 1.2+
Jun DDept. of Comp. Sci. and Tech., Institute for AI, Tsinghua-Bon Bosch Joint ML Center, THBI Lab
BNRist Center, Tsinghua University, Beijing, 100084, China RRealAI
Zhhngguanccun Laboratory, Beijing, China huanran. chw.ranncce@@oolloo...o com {dongyinpeng, des2j @mail tsinghua. edu.
Abstract
Generative learning, recognized for its effective modeling of data distributions, offers inherent advantages in handling out-of-distribution instances, especially for enhancing robustness adversarial attacks. Among these, diffusion classifiers, uti- lizing powerful diffusion models, have demonstrated superior empirical robustness. However, comprehensive theoretical understanding of their robustness is still lacking, raising concerns about their vulnerability to stronger future attacks. In this study, we prove that diffusion classifiers possess (1)) Lipschitzness, and establish their certified robustness, demonstrating their inherent resilience. To achieve non- constant Lipschitzness, thereby obtaining much tighter certified robustness, we generalize diffusion classifiers to classify muussiannccorupped data. This involves deriving the evidence lower bounds (ELBOs) for these distributions, approximating the likelihood using the ELBO, and calculating classification probabilities via Bayes' theorem. Experimental results show the superior certified robustness these Noised Diffusion Classifiers (NDCs). Notably, we achieve over 80% and 70% certified robustness on CIFAR- 10 under adversarial perturbations with & norms less than 0.25 and 0.5, respectively, using single off-the-shelf diffusion model without any additional data.
1 Introduction
Despite the unprecedented success of discriminative learning [32 22 ial examples, which are generated by imposing human-imperceptible perturbations natural exam- ples but can mislead target models into making erroneous predictions 44 8) To improve the robust- ness of discriminative learning, numerous defense techniques have been developed (2 B5 27 34). However, since discriminative models are directly trained for specific tasks, they often find shortcuts in the objective function, exhibiting non-robust nature 77 36]. For example, adversarial training exhibits poor generalization against unseen threat models [45 34 and purification-basee methods typically cannot completely remove adversarial perturbations, leaving subsequent discriminative
they are vulnerable to adversar-
classifiers still affected by these perturbations [ 25 15).
On the contrary, generative learning is tasked with modeling the entire data distribution, which offers degree of inherent robustness without any adversarial training (53 9 As the current state- of-the-art generative approach, diffusion models provide a more accurate estimation of the score function across the entire data space. Thus, they have been effectively utilized as generative classifiers for robust classification, known diffusion classifiers (26) 5] Specifically, they calculate the classification probability ply(x) x p(xly)p(V)) through Bayes' theorem and approximate the log likelihood log p(xly) via the evidence lower bound (ELBO). This method establishes connection between robust classification and the fast-growing field of pre-trained generative models. Although
"The corresponding Author.
Code is available at https: :ettps://gitee //githuu..b.... hww.://aaaaaeeeee//aiaiiiiisiiia
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

promising, there is still a lack of rigorous theoretical analysis, raising questions about whether their robustness overestimated and whether they will be vulnerable to (potentially) stronger future adaptive attacks. In this work, we use theoretical tools to derive the certified robustness of diffusion classifiers, fundamentally address these concerns, and gain a deeper understanding of their robustness.
We begin by analyzing the smoothness of diffusion classifiers through the derivation of their Lip- schitzness. We prove that diffusion classifiers possess an O(1) Lipschitz constant, demonstrating their inherent robustness. This allows us to certify the robust radius of diffusion classifiers by di- viding the gap between predictions on the correct class and the incorrect class by their Lipschitz constant. Although we obtain a non-trivial certified radius, it could be much tighter if we could derive non-constant Lipschitzness (i.e., the Lipschitzness each point). Randomized smoothing [6] (8). a well-researched technique, allows us to obtain tighter Lipschitzness based on the output at each point. However, randomized smoothing requires the base classifier (e.g., diffusion classifiers) to process -aursian-corruptedd data x,, where is the noise level. To address this, we generalize diffu- sion classifiers to calculate ply x-) by estimating log p(x- (y) using its ELBO and then calculating p(y]x, x,) using Bayes' theorem. We named these generalized diffusion classifiers as Noised Diffusion Classifiers. Hence, the core problem becomes deriving the ELBO for noisy data.
Naturally, we conceive to generalize the ELBO in Sohl-Dickstein et al. A1 and Kingma et al. 17 to T + O, naming the corresponding diffusion classifier the Exact Posterior Noised Diffusion Classifier (EPNDC). EPNDC achieves state-of- oate-oof-hhe-rr certified robustness among methods that do not use extra data. Surprisingly, we discover that one can calculate the expectation or ensemble of this ELBO without any additional computational overhead. This finding allows us to design new diffusion classifier that functions as an ensemble of EPNDC but does not require extra computational cost. We refer to this enhanced diffusion classifier as the Approximated Posterior Noised Diffusion Classifier (APNDC). Towards the end of this paper, we reduce the time complexity of diffusion classifiers by significantly decreasing variance through the use of the same noisy samples for all classes and by proposing a search algorithm to narrow down the candidate classes for the diffusion classifier.
Experimental results substantiate the superior performance of our methods. Notably, we achieve 82.2%. 70.7%, and 54.5% Eg radii of 0.25, 0.5. and 0.75, respectively. on the CIFAR-10 10 dataset. These results surpass the previous state-of-the-as [47] by absolute margins of 5.6%, 6. 1.1 and 4.1% 1% in the corresponding categories. Additionally, our approach registers clean accuracy of 91 91.2%, outperforming Xiao et al. 47 by 3.6%. Moreover, our time complexity reduction techniques decrease the computational burden by factor of 10 on CIFAR- 10 and by factor of 1000 on ImageNet, without compromising certified robustness. Furthermore, not only highlights the tangible benefits of our theoretical advancements but also provides valuable insights into several evidence lower bounds and the inherent robustness of diffusion classifiers.
comparative analysis with heuristic methods
The contributions of this paper are summarized as follows:
We derive the Lipschitz constant and certified lower bound for diffusion classifiers, demon- strating their inherent provable robustness.
We generalize diffusion classifiers classify noisy data, enabling us derive non-constant Lipschitzness and
certified robustness.
We propose a variance reduction technique that greatly reduces time complexity without compromising certified robustness.
2 Background
2.1 Diffusion Models
For simplicity in derivation, we introduce a general formulation that covers various diffusion models. In Appendix A.8 we show that common models, such as Ho et al. [[I] Song et al. [42], Kingma
et al. [17 and Karras et al. [16], can be transformed to align with our definition.
Given x := X [0, 1 with a data distribution (xx)). the forward diffusion process incrementally introduces Gaussian noise to the data distribution, resulting in continuous sequence of distributions (g(x;) ;= (xxx)) by:
g(x,)= = (xxs))((x(xx)dd5
(1)
2

---

XLDO
Likellbood
Claeeter
Smonthed Prnnction
Cerilfied Radics
Approsinaa
UC
plg
Sager Theasos
Randomiiood Shwwrbiin
Berl1))
Approsaiiant
Los p(x, s)
s(xly Fepximilplatxii
R
((os (6a))
Riseed
Eaoemebee
Rundomited
Bx,(15)
Apyronsimaty
pips..)
Sasoothing
sixl, Bepxoulpllpxee!
R (+-1))))- (050)))
Frg(8)
Figure 1: Illustration of our theoretical contributions. We derive the Lipschitz constant and the corresponding certified radius for diffusion classifiers B] Additionally, we introduce two novel evidence lower bounds, which are used to approximate the log likelihood. These lower bounds are then employed to construct classifiers based Bayes' theorem. By applying randomized smoothing to these classifiers, we derive their certified robust radii.
where (x)) = (x,; Xo, I)), i.e., x, = O1C,6 (O, I]. Typically, oe monotonically
increases with f, establishing one-to-one mappings t(a) from f and (t) from a. Additionally, oT is large enough that q(XT) is approximately an isotropic Gaussian distribution. Given p Pe
as the parameterized reverse distribution with prior p(xT) = (xT;; O, of. the diffusion process used to synthesize real data is defined as Markov chain with learned Gaussian distributions [1] 42):
T
p(xo.) = p(x)) II p(xx-1xx)))
(2)
t=1
In this work, we parameterize the reverse Gaussian distribution (xx)) using a neural network he (g(x,,t)
p(x-11 = -N t), 0f(0it1 - - I).
oit1 (o - o1) o2-1x1
(3)
(x( t)
of The parameter is usually trained by optimizing the evidence lower bound (ELBO) on the log likelihood 41
T
(xxo( 2
Σ
Ee
o.) -xol2l + C1,
1=1
where w, 0 is the weight of the loss at time step and C1 is constant. Similarly, the 2:4
conditional diffusion model p(x;-1l Xx, 8) is parameterized by ha (x,x Te, y). A similar lower bound on conditional log likelihood
log logr(xolv)
Σ Ec (wx]lho(((,0,,,)) xol22] + +C,
(5)
where C' another constant.
2.2 Diffusion Classifiers
Diffusion classifier B 5 26 DC(.) [0,1] RK is a generative classifier that uses a single
off-the-shelf diffusion model for robust classification. first approximates the conditional likelihood log p())X)) via conditional ELBO (i.c., using ELBO as logit), and then calculates the class probability p(y|xo xp) x p(xaly) through Bayes' theorem, with the assumption that p(y) a uniform prior:
DC(xo)y = exp( DT Σt Ee [w (w///a/ (xt, ot. v) xo xol
Eg exp (- DI Ex E. [we] hx oe, 0) X x
(6)
exp (log p(xuly))
p(xulv)p(e)
2 Eg exp (log pl (o))
E ((xxo0))(()) p(ulxo).
3

---

In other words, it utilizes the ELBO of each conditional likelihood log p(y (x)) as the logit of each class. This classifier achieves state-of-the-arr empirical robustness across several types of threat models and can generalize unseen attacks as it does not require training on adversarial examples 3 However, there is still lacking a rigorous theoretical analysis, leaving questions about whether they will be vulnerable to (potentially) future stronger adaptive attacks.
2.3 Randomized Smoothing
20 is a model-agnostic technique designed to establish a lower bound of robustness against adversarial examples. It is scalable to large networks and datasets and achieves state-of-the-ar performance in certified robustness [48). This approach constructs smoothed classifier by averaging the output of base classifier over Gaussian noise. Owing the Lipschitz continuity of this classifier, it remains stable within a certain perturbation range, thereby ensuring certified robustness.
Randomized smoothing 22
6
48
Formally, given a classifier f: [0. 1 - RK that takes a D-dimensional input x and predicts class probabilities over K classes, the y-th output of the smoothed classifier g is:
g(xo)y P( arg max fxx + o+ .)g y), &E(1.....K)
where E -N( I) is Gaussian noise and o, is the noise level. Let Φ 1 denote the inverse function of the standard Gaussian CDF. Salman et al. 38] prove that c (xx) is a. -Liischhiz However, the exact computation of (xxo) is infeasible due to the challenge of calculating the expectation in high-dimensional space. Practically, one usually estimates a lower bound PA of g(xo)y and an upper bound pB of maX&4y gxxo) using the Clopper-Peanse Pearson lemma, and then calculates the lower bound of the certified robust radius R for class y
R = Or (pA)
(PA) $ (pB))
(8)
Typically, the existing classifiers are trained to classify images in clean distribution g(x)). However, the imput distribution in Eq. (7) is x(x,) = f (xx0) (xx, (x) dxx.. Due to the distribution discrepancy, g(xo) constructed by classifiers trained on clean distribution g(xo) exhibits low accuracy on g(x,). Due to this issue, we cannot directly incorporate the diffusion classifier (3] with randomized smooth- ing. In this paper, we propose a new category of diffusion classifiers, that can directly calculate p(y)x+) via off-the-shelf diffusion model.
To handle Gaussian-corrupee data, early work [6
38) trains new classifiers on g(x;) but is not
applicable to pre-trained models. Orthogonal to our work, there is also some recent work on using denoiser for certified robustness [39 46), and some of them choose diffusion model as denoiser (2] 47 52]. They first denoise x, ((x,), followed by off-the-shelf discriminative classifier for classifying the denoised image. However, the efficacy such an algorithm is largely constrained by the performance of the discriminative classifier.
3 Methodology
In this section, we first derive an upper bound of the Lipschitz constant in Sec. 3.1 difficulty in deriving a tighter Lipschitzness for such a mathematical form, we propose two variants of Noised Diffusion Classifiers (NDCs), and integrate them with randomized smoothing to obtain tighter robust radius, as detailed in Sec. 3.2 and Sec, 3.3 Finally, we propose several techniques in Sec. 3.4 to reduce time complexity and enhance scalability for large datasets.
Due to the
3.1 The Lipschitzness of Diffusion Classifiers
We observe that the logits can be decomposed as
1 Σr= W, [[ or) - xollē] of diffusion classifier in Eq. 6
DT
T
Wi (Ee [| ox), + ||xol13 - 2E, [ho (xe, o.) xo)
DT

---

Algorithm EPNDC
1: Require: A pre- trained diffusion model ha, a noisy input image x., noisy level T.
2: for to K - 1 do
f to Io do
4: Calculate the analytical form of Eggxe xx [xc] by: (o of be -
of-1 -0?
Calculate the analytical form of Ep(x: (2441))) [Xe] by: (0f+) (e
5:
end for Calculate the lower bound log p(x, (0) of log p(x. (t) using w/"
224 -0? 2(r2
( (+1--))) by:
C-++ W6 Botxees [ll (M44 [Xe] (ppeeleee () [x+]]]
end for 9: Approximate po (ulx+) by Eg exp (log Pa(x, 19]*
8:
(log (x(x)l
and Return: ÿ = arg maxy po (o(vxx)).
Given that EEg (xe, ox) [1]] and E. [x,, 0z) are smoothed by Gaussian noise and lie within the range [o, 1j2, they satisfy the Lipschitz condition [38]. Consequently, the logits of diffusion classifiers should satisfy a Lipschitz condition. Thus, it can be inferred that the entire diffusion classifier is robust and possesses certain robust radius.
We derive an upper bound for the Lipchitz constant of diffusion classifiers in the following theorem:
Theorem 3.1. The upper bound of Lipschitz constant of diffusion classifier is given by:
T
DDC(x + 8), - DC((x)n) S
Wt
VD 118112
2
(10)
2/2
o.
If one can get lower bound pA for DC(xa)y and a upper bound pn for maxgty DC(x))g (e.g.. probabilistic bound by Bernstein inequality (301), the lower bound of certified radius for diffusion classifier can be obtained:
(PA PB)
RDC = (2/VDD 2//T) E we/Or
(1))
Proof. (Sketch; details in Appendix A. Employing similar methodology that used by Salman et al. (38), we derive the gradient of the diffusion classifier. Since the gradient norm neural
network is unbounded, we transfer the target of the gradient operator from the neural network to the
Gaussian density function, so that we can bound the gradient norm and the Lipschitz constant. O
As demonstrated in Theorem 3.1 the Lipschitz constant of diffusion classifiers is nearly identical to that in the "weak law" of randomized smoothing (See Appendix [A.3] or Lemma in Salman et al. (38). This constant is small and independent of the dimension D. indicating the inherent robustness of diffusion classifiers. However, similar to the weak law of randomized smoothing, such certified robustness has limitations because it assumes the maximum Lipschitz condition is satisfied throughout the entire perturbation path, i.e., it assumes the equality always holds in (X f(x),l I < T.|x- Xedvll2 when f has Lipschitz constant L. As result, the equality also holds in fXadvv 2 f(x), - L||x Xadvll2 ||2 and f(xadv) S f(x), + L|| Xadvlla 2l2 for maxg/y (x) To guarantee the prediction is unchanged (i.e., f (Xado) y Z (XLavv)) its requires the perturbation ||x Xadul|2 must be less than zz.
To be specific, under the weak law randomized smoothing, it is impossible to achieve a certified radius greater than 1.253. According to Eq. (II), a certified radius greater than 0.39 is unattainable, and empirically, the average certified radius achieved is only 0.156 (refer to Appendix C.3). This is significantly lower than the empirical robustness upper bound obtained through adaptive attacks as reported in Chen et al. 3
On the other hand, the "strong law" of randomized smoothing (See Eq. 8 or Lemma 2 in Salman et al. 388 can yield a non-constant Lipschitzness, leading to more precise robust radius, with the upper bound of the certified radius potentially being infinite. Therefore, in the subsequent sections, we aim to combine diffusion classifier with randomized smoothing to achieve a tighter certified radius, thus thoroughly explore its robustness.
5

---

Algorithm 2 APNDC
1: Require: A pre-tram trainddnd diffusion model ha, a noisy input image x., noisy level T.
2: for 0 to K 1 do
Calculate the lower bound log p(x, (y) log (x+ (v) by:
Ei We (ollhoo(x,, (x, σx) - (x., Je+1, v)ll where Wi 0411-08
end for
exp (x(x
5: Approximate (o(x)x)) by Eg exp Pa(x,
Return: y = arg maxy po ())x
3.2 Exact Posterior Noised Diffusion Classifier
As explained in Sec. 2.3 randomized smoothing constructs smoothed classifier y from given base classifier f by aggregating votes over Gaussian-corrupted data. This process necessitates that the base classifier
classify data from the noisy distribution g(x+). However, the diffusion classifier in Chen et al. 3 is limited to classifying data solely from g(xo). Therefore, in this section, we generalize the diffusion classifier to enable the classification of images from q(x;) ) for any given
Similar to Chen et al. 3], our fundamental idea involves deriving the ELBO for log p(x, ly) and subsequently calculating p(y[x,) using the estimated log p(x+lu) via Bayes' theorem. Drawing inspiration from Ho et al. [11], we derive a similar ELBO for log p(x,), ), as elaborated in the following theorem (the conditional ELBO is similar to unconditional one, see Appendix [A.4] for details):
Theorem 3.2. (Proof in Appendices A.4 and A.5 The ELBO of log ((x,) is given by:
T
logp(x+)
w/
(T)
Ex(x, (x..)) [x]]1 Cz.
(12)
where
X1+1 q(x(41|xx), Eytxe Met1 x.) (ot of)x, (0î o xx,+1
02f1 o7
(13)
0i.1 -
(o - 0(41) + 02x111
w/? 2(0 - (0) - ot)² Epoxi nixe)
oi
Remark 3.3. Notice that the summation of KL divergence in the ELBO of log p(x,) starts from + and ends at T, while that of log p(xo) starts from Besides, the posterior is ( xx+1, instead of q(x: Xo).
Remark 3.4. When T = O, this result degrades to the diffusion training loss 0++1 ||xo h(x 0++1)l 2|2 consistent with Kingma et al. 17 and Karras et al. [16].
Due to the page width limit, we only present the unconditional ELBO in the main text. We can get the conditional ELBO by adding y to the condition. Using the conditional ELBOs approximation pgls by)
for log likelihood (i.e., using ELBBO as logits), one can calculate p(y)x>) = Σ, clos pgtk- NT for classification. We name this algorithm as Exact Posterior Noised Diffusion Classifier (EPNDC), as demonstrated in Algorithm T
Although this classifier achieves non-trivial certified robustness, still has limitations. For instance, we cannot theoretically determine the optimal weight w/(") (see Appendix C.2 for details). Addi- tionally, the time complexity is high. In the next section, we propose new diffusion classifier called the Approximated Posterior Noised Diffusion Classifier (APNDC), which addresses these problems and acts like an ensemble of EPNDC so that greatly enhanced certified robustness without any computational overhead.
3.3 Approximated Posterior Noised Diffusion Classifier
Greatly inspired by Song al. 42 and Meng et al. 31 we propose approximate the posterior in a similar manner:
g(xx|x++11 q(x, XxX1/ Xy, Xo ho 1x,,,, oT)) x q(x, Xx+1, hg(x,,
(14)

---

Table 1: Certified accuracy at CIFAR-10 test set. The clean accuracy for each smoothed model is in the parentheses. The certified accuracy for each cell is from Xiao et 47 same as the results from their respective papers. Carlini et al. 2 and Xiao et al. 47 use ImageNet-21k as extra data.
Certified Accuracy at (%)
Method
Off-the-shelf
Extra data
0.25
0.5
0.75
1.0
PixeIDP
23
X
(71.0)
(.4.0)
RS
6
X
X
(75.0) 61.0
(75.0) 43.0
(65.0)
32.0
23.0
SmoothAdy
38
(82.0) 68.0
(70.0)
(68.0)
(6..0)
Consistency
13
68.8
58..
48.59)
(52.3)
MACER
50
(81 (8100)14 71.0
59.0
(06.0) 16.0
(8..0)
Boosting
(8..4)70.6
(7..6152.4 67.48)
(73.0) 38.8
SmoothMix
14
(77. 67..
(77.1)
(74.2)47.7
37.2
Denoised
39
(72:0) 56.0
(02.0)41.0
(82.0)28.0
(44.0) 19.0
Lee
2
6-)0
(-)
(-)28.0
(-)
Carlini
(8,.0)
56..
(68.0)
(74.2)31.0
DensePure 47
(87 (97.6)66 76,6
(87 (87.6)
(73.6)37.4 (87.6)50.4
DiftPure+DC (baseline, ours)
X
(87.6) 68.8
(37.5)53.1
(87.6)41.2
(78.4)25.6
EPNDC (T" 100, ours)
(89. 77.4
60.0
(74.8)24.4 (89.1)
APNDC (T" = 100, ours)
(89.5) 80.7
(8,8
(76.2)35.2 (8.8
APNDC (T" 1000, ours)
(01.2)
70.7
(4.52)
(77-3)38.2
As result, the KI. divergence can be simplified using this approximation:
DKL
(g(x Xx+1, )lpp) (x (x)xx++)) s (g Xx+1, Xu = (x)xx
0t [h(x,, 0.) h(x, 1(xx41)0++1111 C3.
(15)
Intriguingly, Eq.
15 is the ELBO of B (x0= logg i.e.
T
(x (o logp; (8,)] C1 Σ (x
0z) - xo xol1)]. (16)
Therefore,
the ELBO in Eq. (16) a approximation for log p(x,) (i.e., employing the EL- BOs of this expected log likelihood as the logits), and calculate the class probabilities through Bayes' theorem. We name this method as Approximated Posterior Noised Diffusion Classifier (APNDC), as shown in Algorithm 2
APNDC is functionally equivalent to ensemble of EPNDC, it calculates the ELBO of Eg(2, (x, [log] (= which corresponds to the expected log (og,((x+l)) ly). This nearly-free ensemble can be executed with only one more forward pass of UNet to compute ha(x,, For detailed explanations, please refer to Appendix A.7
Remark 3.5. From heuristic standpoint, one might consider first employing a diffusion model for denoising (named DiffPure by Nie et al. [34)). followed by using a diffusion classifier for classification. This approach differs from our method, where we calculate the diffusion loss only from 7 + T, and the noisy samples x, are obtained by adding noise to x, instead of Xy. In Table we demonstrate that our APNDC method significantly outperforms this heuristic approach (DiffPureDDC).
3.4 Time Complexity Reduction
Variance reduction.
The main computational effort in our approach is dedicated to calculating
the evidence lower bound for each class. This involves computing the sum of reconstruction
losses. For instance, in DC, the reconstruction loss is ||x, - hg (x11)11 In EPNDC, it is
||Exxx/xx11xx 1.x.) [x.] Ep(x||x: [x,]1lž. and APNDC, the loss is | 0.) 110--hhxxss ( 0t+1, Il with the summation carried out over I. Chen et al. 33 attempt to reduce the time complexity by
only calculating the reconstruction loss at certain timesteps. However, this approach proves ineffec-
tive. We identify that the primary reason for this failure is the large variance in the reconstruction

---

Table 2: Certified accuracy at ImageNet-64464. The clean accuracy is in the parentheses.
Certified Accuracy at At (%)
Method
Off-the-shelf
Extra data
0.25
0.5
0.75
1.0
RS 6
x
X
(7.3
(37.0) 26.6
20.9
(87.0)
SmoothAdy
38
X
x
(44.4)37.4
24.9
(1.17)
17.0
Consistency
(6.9
(1.56)
(6.64) (4.00)26.0
MACER 50
(46.3)27.1 (5.73)35.7
(46.3) 15.6
(3.3
Carlini 2
X
(41.1)37.5
(39.4)30.7
(4.64)
(39. (39.4)21.7
DensePure 47
(37.7)35.4
29.3
(37.7)26.0
18.6
APNDC (Sift-and-Refine, ours)
X
(64.4) 46.3
38.3
35,2
(48.
loss, necessitating sufficient calculations for convergence. To address this, we propose an effective variance reduction technique that uses identical input samples across all categories each timestep. In other words, use the same X, for different classes. This approach significantly reduces the difference in prediction difficulty among various classes, allowing for a more equitable calculation of the reconstruction loss for each class. As shown in Figure 2(a) we can utilize much smaller number of timesteps, such as 8, without sacrificing accuracy, thereby substantially reducing time complexity.
Selt-and-refing algorithm. The time complexity of these diffusion classifiers is proportional to the number of classes. presenting significant obstacle for their application in datasets with numerous classes. Chen et al. [3] suggest the use of multi-head diffusion to address this issue. However, this approach requires training an additional diffusion model, leading to extra computational overhead. In our work, we focus solely on employing single aff-the-shed diffusion model to construct certifiably robust classifier. To tackle the aforementioned challenge, we propose -ift-and-refine algorithm. The core idea is to swiftly reduce the number of classes, thereby limiting our focus to manageable subset of classes. We provide more detailed analysis in Algorithm
Experiment
we evaluate the certified robustness of our method on two 19 and ImageNet [37], selecting a subset of 512 images from each. We adhere to the certified robustness pipeline established by Cohen et al. [6] although our method potentially offers tighter certified bound, as demonstrated in Appendix A.3] To make a fair comparison with previous studies, we also select o, {0.25, 0.5, 1.0} for certification (thus 7 is determined) and use EDM [16] our diffusion models. For re-clarification the hyper-pparane pprrmmerree and additional experiments (including ablation studies on diffusion checkpoints and time complexity comparison), please refer to Appendix B
Following previous studies 2 47 52
standard datasets, CIFAR- 10
4.1 Results on CIFAR-10
Experimental settings. Due to computational constraints, we employ a sample size of N = 10, 000 to estimate PA- The number of function evaluations (NFEs) for each image in our method is O(N T"" K), amounting to 10 for T' = 100 and 10 for T' 1000 since K = 10 in this dataset. In contrast, the NFEs for the previous state-of-thh oftthe--rtttt method 47 are 4 10 which is four times higher than our method when 7" is 100. It is important to highlight that our sample size N is 10 times smaller than those baselines in (Table T. potentially placing our method a significant disadvantage, especially for large dr.
Experimental results. As shown in Table [ our method, utilizing an off-the-shelf model without the need for extra data, significantly outperforms all previous methods at smaller values of e (0.25, 0.5]. Notably, surpasses all previous methods on clean accuracy, and exceeds the previous state-of-the-an method (47 by 5.6% at 0.25 and 6.1% 1% at 0.5. Even with larger values of c, our method attains performance levels comparable to existing approaches. This is particularly noteworthy considering our constrained setting of N 10, 000, substantially smaller than the
N = 100, 000 used in prior works. Considering that the community randomized smoothing employs hypothesis tests to establish a probabilistic upper bound of the smoothed function, with consistent type-one error rates, our method encounters significant disadvantages. This is particularly the case since, with equivalent accuracy noisy data, certified robustness is monotonically

---

1.0
90
(2h22)
(5)
Curiite Accuracy
8.8
APNBC (ser))
Ceniifed Asturacy
0.5
APNDC
6.6
0.4
50
0.4
DC Char (382))
0.2
0.2
16
32
64
128
256
512
1000
0.0
0.3
0.6
0.9
1.2
1.5
0.00
0.25
0.50
0.75
1,50
Radius
Radius
(a)
T"
(b) R in CIFAR-I0
(c) R in ImageNet
Figure 2: (a) The accuracy (%) CIFAR-10 dataset with time complexity reduction technique in Chen et 3 and ours. (b, e) The upper envelop of certified radii of different methods.
increasing function with respect to sample size N. However, we still achieve competitive performance despite its inherent sample size disadvantage.
4.2 Results on ImageNet
Experimental settings. We conduct experiments on ImageNet64x64 due to the absence of con- ditional diffusion models for 256x256 resolution. Due to computational constraints, we employ sample size of N = 1000, 10 times smaller than all other works in Table We use the Sift-and-Refin algorithm to improve the efficiency.
Experimental results. As demonstrated in Table and Figure 2[c) our method, only employing a single off aff-the-shelf diffusion model without requiring extra data, significantly outperforms previous training-bace based and training-free approaches. In contrast, diffusion- purification methods, when applied with small CNNs and no extra data, do maintain their superiority over training-based approaches. It is noteworthy that our experiments are conducted with only one-tenth of the sample size typically used previous works. This success on large dataset like ImageNet64x64 underscores the scalability of diffusion classifiers in handling extensive datasets with a larger number of classes.
4.3 Discussions
Comparison with heuristic methods. From a heuristic standpoint, one might consider initially using diffusion model for denoising, followed by a diffusion classifier for classification. As shown in Table [ this heuristic approach outperforms nearly prior off- the-l and no-extra-data baselines. However, the methods derived through our theoretical analysis significantly surpass this heuristic strategy. This outcome underscores the practical impact of our theoretical contributions.
Trivial performance of EPNDC. Although EPNDC exhibits non-trivial improvements compared to previous methods, it still lags significantly behind APNDC. There
main reasons for this gap. First, as extensively discussed in Appendix C.2, the weight in EPNDC is not optimal, and we cannot theoretically determine the optimal weight. Additionally, APNDC is equivalent an ensemble of EPNDC, which may contribute to its superior performance compared to EPNDC.
C.22
Explanation of Eq. IT. Eq. (1)) is extremely similar to the weak law of randomized smoothing. When o, is larger, it could potentially have a larger certified radius, but the input images will be more noisy and hard classify. This trade-off is quite similar to the role of ar in randomized smoothing. However, there are two key differences. First, the inputs to the network contain different levels of noisy images, which means the network could clean images, less noisy images, and very noisy images, hence could make more accurate predictions. Besides, the trade-off parameter 2i allowing users some freedom to select different noise levels and balance them by w. We observe that this is the common feature of such denoising and reconstructing classifiers. We anticipate this observation will aid the community in developing more robust and certifiable defenses.

---

Conclusion
In this work, we conduct a comprehensive analysis the robustness of diffusion classifiers. We establish their non-trivial Lipschizzness, a key factor underlying their remarkable empirical robustness. Furthermore, we extend the capabilities of diffusion classifiers to classify noisy data at any noise level by deriving the evidence lower bounds for noisy data distributions. This advancement enable us to combine the diffusion classifiers with randomized smoothing, leading to a tighter certified radius. Experimental results demonstrate substantial improvements in certified robustness and time complexity. We hope that our findings contribute to deeper understanding of diffusion classifiers in the context of adversarial robustness and help alleviate concerns regarding their robustness.
Acknowledgement
This work was supported by NSFC Projects (Nos.. 62076147, 92370124, 62350080, 92248303, 62276149, 62061 136001), BNRist (BNR2022RC0006), Tsinghua Institute for Guo Qiang, and the High Performance Computing Center, Tsinghua University. Zhu was also supported by the XPlorer Prize. Y. Dong was also supported by the China National Postdoctoral Program for Innovative Talents and Shuimu Tsinghua Scholar Program.
References
[1] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, pages 274-283, 2018.
[2] Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter. (certified!!) adversarial robustness for free! In International Conference on Learning Representations, 2023.
[3] Huanran Chen, Yinpeng Dong, Zhengyi Wang, Xiao Yang, Chengqi Duan, Hang Su, and Jun Zhu. Robust classification via a single diffusion model. In Forty-first International Conference on Machine Learning, 2024.
[4] Huanran Chen, Yichi Zhang, Yinpeng Dong, Xiao Yang, Hang Su, and Jun Zhu. Rethinking model ensemble in transfer-based adversarial attacks. In The Twelfth International Conference on Learning Representations, 2024.
[5] Kevin Clark and Priyank Jaini. Text-to-image diffusion models are zero-shot classifiers. arXiv preprint arXiv:2303. 15233, 2023.
[6] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310-1320, 2019.
[7] Robert Geirhos, förn-Henrie Jacobsen, Claudio Michaelis, Richard Zemel, Wieland Brendel, Matthias Bethge, and Felix A Wichmann. Shortcut learning in deep neural networks. Nature Machine Intelligence, pages 665-673, 2020.
[8] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. In International Conference on Learning Representations, 2015.
[9] Will Grathwohl, Kuan-Chieh Wang, Joern-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky. Your classifier is secretly an energy based model and you should treat it like one. In International Conference on Learning Representations, 2019.
[10] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 150300230 2015.
[11] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, pages 6840-6851, 2020.
10

---

[12] Miklós Z Horváth, Mark Niklas Mueller, Mare Fischer, and Martin Vechev. Boosting random- ized smoothing with variance reduced classifiers. International Conference on Learning Representations, 2021.
[13] Jongheon Jeong and Jinwoo Shin. Consistency regularization for certified robustness of smoothed classifiers. Advances in Neural Information Processing Systems, pages 10558-10570, 2020.
[14] Jongheon Jeong, Sejun Park, Minkyu Kim, Heung-Chang Lee, Do-Guk Kim, and Jinwoo Shin. Smoothmix: Training confidence-calibrate smoothed classifiers for certified robustness. In Advances in Neural Information Processing Systems, pages 30153-30168 2021.
[15] Mintong Kang, Dawn Song, and Bo Li. Diffattack: Evasion attacks against diffusion- adversarial purification. Advances Neural Information Processing Systems, 36, 2024.
[16] Tero Karras, Miia Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion-based generative models. Advances in Neural Information Processing Systems, pages 26565-26577, 2022.
[17] Diederik Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. Advances in Neural Information Processing Systems, pages 21696-21707, 2021.
[18] Diederik P Kingma and Ruiqi Gao. Understanding the diffusion objective as a weighted integral of elbos. arXiv preprint arXiv:2303.0088 00044, 2023.
[19] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[20] Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi. Curse of dimensionality on randomized smoothing for certifiable robustness. In International Conference on Machine Learning, pages 5458-5467, 2020.
[21] Langley. Crafting papers on machine learning. In Pat Langley, editor, Proceedings of the 17th International Conference on Machine Learning (ICMI. 2000), pages 1207-1216, Stanford, CA, 2000. Morgan Kaufmann.
[22] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 444, 2015.
[23] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE symposium on security and privacy, pages 656-672, 2019.
[24] Kyungmin Lee. Provable defense by denoised smoothing with learned score function. In ICLR Workshop on Security and Safety in Machine Learning Systems, 2021.
[25] Minjong Lee and Dongwoo Kim. Robust evaluation of deffusiio-baseee adversarial purification. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 134-144,
2023.
[26] Alexander C Li, Mihir Prabhudesai, Shivam Duggal, Ellis Brown, and Deepak Pathak. Your diffusion model is secretly a zero-shot classifier. arXiv preprint arXiv:2303. 2023.
[27] Fangzhou Liao, Ming Liang, Yinpeng Dong, Tianyu Pang. Xiaolin Hu, and Jun Zhu. Defense against adversarial attacks using high-level representation guided denoiser. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1778-1787, 2018.
[28] Cheng Lu, Kaiwen Zheng, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu. Maximum likelihood training for score-based diffusion odes by high order denoising score matching. In International Conference Machine Learning, pages 14429-14460. PMLR, 2022.
[29] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.

---

[30] Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint 7xXiv:0977.3740, 2009.
[31] Chenlin Meng, Yutong He, Yang Song, Jiaming Song, Jiajun Wu, Jun-Yan Zhu, and Stefano Ermon. Sdedit: Guided image synthesis and editing with stochastic differential equations. In International Conference on Learning Representations, 2021.
[32] Andrew Y Ng and Michael I Jordan. On discriminative vs. generative classifiers: a comparison of logistic regression and naive bayes. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, pages 841-845 2001.
[33] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabílistic models. In International Conference on Machine Learning, pages 8162-811 8171, 2021.
[34] Weili Nie, Brandon Guo, Yujia Huang. Chaowei Xiao, Arash Vahdat, and Animashree Anand- kumar. Diffusion models for adversarial purification. In International Conference on Machine Learning, pages 16805-16827, 2022.
[35] Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2103.01946, 2021.
[36] Joshua Robinson, Li Sun, Ke Yu, Kayhan Batmanghelich, Stefanie Jegelka, and Suvrit Sra. Can contrastive learning avoid shorteut solutions? Advances in neural information processing systems, pages 4974 4986, 2021.
[37] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115(3):211225) 252, 2015.
[38] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
[39] Hadi Salman, Mingjie Sun, Greg Yang, Ashish Kapoor, and J Zico Kolter. Denoised smoothing: provable defense for pretrained classifiers. In Advances Neural Information Processing Systems, pages 21945-21957, 2020.
[40] Shitong Shao, Xu Dai, Shouyi Yin, Lujun Li, Huanran Chen, and Yang Hu. Catch-up distillation: You only need to train once for accelerating sampling. arXiv preprint vrXiv:2305.10766 2023.
[41] Jascha Sohl- Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. International Conference on Machine Learning, pages 2256-2263 2015.
[42] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021.
[43] Yang Song, Prafulla Dhariwal, Mark Chen, and Ilya Sutskever. Consistency models. arXiv preprint arXiv:2303.01469 2023.
[44] Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
[45] Florian Tramèr and Dan Bonch. Adversarial training and robustness for multiple perturbations. In Proceedings the 33rd International Conference on Neural Information Processing Systems, pages 5866-5876 2019.
[46] QuanLin Wa, Hang Ye, Yuntian Gu, Huishuai Zhang, Liwei Wang, and Di He. Denoising masked autoencoders help robust classification. The Eleventh International Conference on Learning Representations, 2022.
12

---

[47] Chaowei Xiao, Zhongzhu Chen, Kun Jin, Jiongxiao Wang, Weili Nie, Mingyan Liu, Anima Anandkumar, Bo Li, and Dawn Song. Densepure: Understanding diffusion models for adversar- ial robustness. In International Conference on Learning Representations, 2023.
[48] Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705, 2020.
[49] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016, pages 17.1-87.12, 2016.
[50] Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsich, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. In International Conference on Learning Representations, 2019.
[51] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and aceuracy. International Conference on Machine Learning, pages 7472-7482, 2019.
[52] Jiawei Zhang, Zhongzhu Chen, Huan Zhang, Chaowei Xiao, and Bo Li. {DiffSmooth): Certifiably robust learning via diffusion models and local smoothing. In 32nd USENIX Security Symposium, pages 4787-480 2023.
[53] Roland S Zimmermann, Lukas Schotr, Yang Song, Benjamin Adric Dunn, and David A Klindt. Score-based generative classifiers. In NewrIPS 2021 Workshop on Deep Generative Models and Downstream Applications, 2021.
13

---

APPENDIX
Appendix organization:
Appendix A
Proofs.
Assumptions and Lemmas.
A.2
Lipschitz Constant of Diffusion Classifiers.
A.3
Stronger Randomized Smoothing When Possess Lipschitzness.
A.4 4
ELBO of log px()) in EPNDC.
5
The Analytical Form of the KL Divergence in ELBO.
A.6
The Weight in EPNDC.
The ELBO log (>(x)) in APNDC.
Converting Other Diffusion Models into Our Definition.
Appendix
B
Experimental Details.
Certified Robustness Details.
2
ImageNet Baselines.
Ablation Studies of Diffusion Models.
B.4
Ablation Studies on Time Complexity Reduction Techniques.
Appendix
C
Discussions.
ELBO, Likelihood, Classifier and Certified Robustness.
Certified Robustness of Chen et al. [3]
The Loss Weight in Diffusion Classifiers.
Time Complexity Reduction Techniques that Do Not Help.
A Proofs
A.1 Assumptions and Lemmas
Assumption A.1. We adopt the following assumptions. These assumptions quite common in the context of certified robustness 38 6 and diffusion models 42 28), and they apply to most common neural networks:
Input image x E [0,
VO < S (x)( E C², h(x, E C² and E (x) | I cc.
For any classifier f mentioned in this paper, f(x) C², and 3C' 2 Vx: [lf(x) SC
4. The output of the diffusion U-Net is bounded: h(x, o,) E [0, lld for all x and This property can be ensured by using the CLIP operator clip the output of the U-Net. Lemma A.2. The second norm of the gradient of softmax function or equal to 2/23'
softmax(x/ (x3)) is less than
_ In other words,
8 softmax(x/8)))) S 2/223 0x
Proof.
i softmax noftmax(x/3),l1
max
||
xx
(attmax(x/3))
max [(e, softmax(x/8))
1
max softmax(x/9)3[[
softmax(x/21))2 +
softmax(x// (3)
3
izy
2
|sofmax(x//B1 softmax(x/8)))² 1
max
3
2v22
14

---

A.2 Lipschitz Constant of Diffusion Classifiers
Lemma A.3. (Adapted from Chen et al. (3).) The gradient of the diffusion classifier is given by
①
Olog llgg((x(>))
2
Be (xe, 04,1) -x x11 = EEe
[o( oz, y)
x x1
TE (x, oz, (2:0))~33 - x)
dx
dx
Ox
where
i Olog Plgg((x/(x)
X xx1
x
00E 0f of
log exp
0x
0x
20
dt
Lemma A.3 already derive the gradient of the diffusion classifier, and transfer the target of nabla operator to distribution function. Hence, we only need to bound the lg norm of both term in Lemma
For the first term:
log p(xx xx)
|Bel
(x0, v) -x x1211l2
Ox
/ p(c) [|bo(x,, 01.9) - -x11]dee112
1
max u T / p(eecclho(xx, 02.8) - x 12
0e ||
D
/ /ple)e (x 02, v) x de
max u ot ||u||==1
D
The term in Solman et
38
The last inequality holds since (1)) is function in [o, 1]_, thus it satisfies the condition D
of Lemma 1 in Salman et al. (38] For the second term, since x E [0, l]l and hx or, v) E [0, I)
hence h 9) x E [0. 1I consequently,
[ho 0. - x) -1ll2
2 lll2 = ||E [ho((,,, 01,8) x)]ll2 S
2
VD. 2
at
Therefore,
d
D 2 +
+VD 2 - at
2 2VD).
Eg
[o Xx, v) x x112112 <
(D
(17)
dx
Both Chen al. Li et al. (26). Clark and Jaini (5] formulate the logit of the diffusion classifier
as Σ F2 ho Xt, ot. y) x However, in practice, both Chen et al. B and et al. 26 use MSE loss rather than L2 loss in the diffusion classifier. In other words, they multiply the logit by DT. Therefore, in this paper, we directly formulate the diffusion classifier using the MSE loss, as demonstrated in Eq. (6). Consequently, the maximum gradient norm of the logits in the diffusion classifier is:
T
T
d
Σ (=1
we
Fe v) x x1
W
2
2 VD
(18)
dx DT
T
t=1
Remark A.4. There may be concerns regarding how the selection of temperature (whether multiplying logits by ) can significantly influence certified robustness. However, this is not the case. The temperature simultaneously affects both the scale of output from the diffusion classifier and the Lipschitz scale, with these scales changing proportionately. This is analogous to multiplying function by a constant k: the Lipschitz constant will increase by factor of k, but the gap between the outputs will also increase by the same factor, thus leaving the certified robustness unchanged.
Eq. 18 provides the maximum gradient norm (Lipschitz constant) in the logit space. One can already use Eq. (8) to perform certified robustness in the logit space, which is precisely what we did in experiments. However, since our diffusion classifier is defined by the class probabilities rather
15

---

than the logits, to ensure consistency with our main text, we will derive the Lipschitz constant of the diffusion classifier in the class probabilities space in the following.
Let's define one-hot vector e; in IR" to be the vector where the i-th element is and all other elements O. Hinton et al. [10] proves that è log softmax(x/8)) = (ey softmax(x/8)) where is 2x
the softmax temperature. Consequently,
xxf)) = 0x
log (ogsottax(xx33) softmax(x/8),
xx
(cy softmax(x/3) softmax(x//))
B
We can derive the maximum &g norm of the gradient as
(())2x))l2
0xo
=||
softmax(f(x)))ll
Xxo
(f
0(- 1 DT
Et=1 Ee [wo (ool/bo(xe, t, -xull3 xxllā]
y=1
0
21=1
T
Be [w)/| ( xxo1
Oxo
K
@softmax (f [x))
01 1 Σi=
Ee
ww (x (xxxt,t)) x001
|2
DTT
0(
-t=1
Ee [we] ha Xr, 1,10 -x0)-xx11))
Oxg
DT
T
Wi T;T
2/2
VD
The last step is get by using Lemma A.2 for the first term and Eq. (18) for the second term. Denote as a unit vector, the Lipschitz constant of the diffusion classifier p(y is
max II p(yxx) max I|u T
0x
p(ulx)]l2
8 0x p(uxx)))>
Wi T
2 π
+
2
Ox
2/2
VD
(19)
is important to note that this represents the upper bound of the Lipschitz constant for the diffusion classifier. In practical scenarios, the actual Lipschitz constant is much smaller, due to the conservative nature of the inequalities used in the derivation. To gain an intuitive understanding of the practical Lipschitz constant for diffusion classifiers, and noisy data. Furthermore, employing the algorithm from Chen et al. [4], we empirically determine the maximum gradient norm. Our results the CIFAR-10 0 test set indicate that the gradient norm is less than 0.02, suggesting that the Lipschitz constant for our diffusion classifier is smaller than 0.02 on this dataset.
measure the gradient norm of the classifier clean
A.3 Stronger Randomized Smoothing When f Possess Lipschitzness
In this section, we will show that f has smaller Lipschitz constant, will induce more smoothed function g. thus has a higher certified robustness. Here we discuss a simple case: the weak law of randomized smoothing proposed in Salman et al. (38] with a 1. We complement this law with much more details, and we hope detailed explanation could assist newcomers in the field in quickly grasping the key concepts in randomized smoothing.
derivation of
To derive the Lipschitz constant of the smoothed function g. we only need to derive the maximum dot product between the gradient of g and unit vector u for the worst f.
maxu Vxg(x) maxu u VxEelf(x +e]
maxu u Vx (()) e)de
1
|EE| f((x + e)de
-maxu u T Vx (2m))//2
exp
16

---

1
|t
x1
max u Vx (2
exp (
s(tt)t
2
||
x
maxu (2T))//2
exp
)(t x)f(t)dt
2
||t
- x12
max u (2
exp
)(t x) - x)dt
2
||
x11 [u [t. x)] xjdt
max (2n)n\/2
exp
2
In the next step, we transition to another orthogonal coordinate system, denoted as u, u2, up. This change is made with the assurance that the determinant of the Jacobian matrix, representing the transformation from the old coordinates to the new ones, equals 1. We then decompose the vector t x in the new coordinate system as follows:
t t- x aiu 2242 + azus + ... apup.
Therefore,
x [u' T - (t-x)]f(C x)dt
max 1
(2x)n/2
exp (
+ 0211 + 03 U3 + + anup
= max
/
(2t)
exp
2
)a f(a)da
0
03
0
a
-ax
(2
exp
2
)a (a)da
1
2
00
2
a
= =max
exp
exp
exp
(a)ddr daz............................. ... dap
(2
2
2
2
1
a dan
< max (2n)
exp
Jai (ai(dd)
exp
dag
expl
of
= -max (2m)
exp (
)a (ai)daa
2
< <ax (2x)
exp
2 )sds.
We could get easily the result by change of variable:
1
(2T) exp (- (-
5²
exp
2 )dss
122
V2m
The classifier will robustly classify the input data as long as the probability of classify the noisy data as the correct class is greater than the probability of classifying the noisy data as the wrong class. If one estimate lower bound P4 of the accuracy of the correct class over noisy sample and upper bound PB of the probability of classify the noisy input wrong class using the Clopper-Pearson interval, we could get the robust radius by
π 2
R
((PA PA
PB),
which will ensure that for any |61|| I R and any wrong class ÿ + y.:
g(x + 5)y = P(f(x + 8 + c) = v) > g(x + 8)g P(f 0).
Hence, g(x) will robustly classify the input data.
When f satisfies the Lipschitz condition with Lipschitz constant I., since it impossible to one when > 0 and zero when < 0. the inequality here can be tighter, can get smaller Lipschitz
17

---

constant. In fact, in this case, the maximum Lipschitz constant of g is:
1
cxp(-s//2)s{(s))
max
2T
s.t., 0 S 11 f(s) is L-lipschitz
However, obtaining an analytical solution for the certified radius when f adheres to Lipschitz continuity appears infeasible. To understand why, consider the following: firstly, should approach zero as x tends toward negative infinity and one as x tends toward positive infinity, Secondly, must be increasing function, with only interval of increase. Additionally, within this interval, is either zero or one outside the bounds of increase, and it must take a linear form within, with a slope of We define the left endpoint of this increasing interval a, which necessarily lies in the range [- 0J. Also notice that both - and a 0 yield the same certified radius. However, when a E (-t. 0), the certified radius must smaller. To see why, let's consider
0,
$ S a
0,
S
0
1
fa(s) = L(s a), a as S a+
L with special case fo(s)
Ls,
0
S 8
<
1
1
s a L
1,
L
Denote fa(x)
I -2)) The difference of Lipschitz constant between two ran-
domized function
(fo(s) - fa(s)]ds== (fu(s)) - (f()s)) / [f((s) - fa(s))
// L-d² [fo(s) - [s))
1/LL - - f.((]] + [ [fo(s) fa((s) 0
Consequently, the corner case for a must lie within the open interval (-1/T,,0, However, the corresponding integral lacks analytical solution, and taking the derivative of it results in function whose zero points are indeterminable. Therefore, obtaining an analytical solution for the improvement in certified robustness when function exhibits Lipschitz continuity is challenging. Nevertheless, can approximate the result with numerical algorithms, and it is evident that this Lipschitzness leads non-trivial enhancement in certified robustness of randomized smoothing.
A.4
ELBO for Noisy Data in EPNDC
Similar to Ho et al. [.] we derive the ELBO as
p(x+r))(xx++1111 dx dx
log p(x,) = log
((x++1:T x+)
p(X::T)
log E Eg((x H1r())))
(X++1:7 (x+)
p(xr (xx- [x
= log 1ogg
(x 1.77
p(XT (x
(T)
2 11 flog
(x x
((XT) [ p(xx (x+11)
-
1 (x(+1 X1,
p(xr) (=r p(x, xx+1)
= -x0 flo
g(x.+1 x, (x(x, 1xx))
G(x.
p(x)) [T- p(x((x++1)
T
(x (x-)
= EE x flog
log
1- (xx x+)
xxx,
t=
18

---

p(Xr)
l=r p(x,
g(xr xc,)
trr,, (lo
log
t= (xx x
((x, (x,)
1' 11 xxg] xx+1)
g(xr (x,)
log
7 1
9 X5x Xt+1 1,,+),,))))))
p(xr)
p(x xx+1)
=
fxx 117xx)
xx. (x
q( X x x x+)
pl X xx+1)
B (x,)
[log
Ex(xrr (x,, DKL (xx.lg(xxr/bx>>lllxxxx>>
{xxe Xx+1, xx)
llog p(xe(xx+1)
((xx(x(41,x,,) ((x1/1x11112)) /
g (x.x / xxx)
logp(x, [x++))
Eg(xr(x (x, (DLL (x)xx//()))) T-1
=
This could be understood generalization of the ELBO in Ho et al. when T = 0. Notice that the summation of KL divergence in ELBO of log p(x,) start from 7 + 1 and end while that of log p(xo) start from Besides, the posterior is ((xx Xx+1, x,) instead of q(x, Xo).
[T] which is special case
Similarly, the conditional ELBO is give by: jox,(x1le) 2 log p(x, |x, u) (x((er ( (gx (xx
1xx (xxx1 Xr, (r:):,ixxx)))))>>>>>>>>>>>>>>>>a + Cs-
This is equivalent to adding the condition y to all posterior distributions in the unconditional ELBO.
A.5 The Analytical Form of the KI. Divergence in ELBO
The KI. divergence Theorem 3.2 is the expectation of the log ratio between posterior and predicted reverse distribution, which requires integrating over the entire space. To compute this KI. divergence more efficiently, we derives its analytical form:
(xxxxx+11,xx) g(xx|xx)9(( (x
g(x++1 x+)
N(x: Xx,, (o (x)+ 0))
N(x++1 Xy, (o - 02)1)
12(00-023)m12 exp( |x,-x.11
[ xx -1 -o75
expl
2(0 -
(2m
117
(2m(a]_) 0f)))/ exp(
|x+1 x,
2(
Since the likelihood distribution g(xe+1 (x.) and the prior distribution q(x; x+) are both Gaussian distribution, the posterior g(x+ [x+1, x,) is also Gaussian distribution. Therefore, we only need to derive the expectation and the covariance matrix. In the following, instead of derive the q(x, X x,)
using equations, we use some trick to simplify the derivation: [xx xx+1; xx)
19

---

1x x, 1|2
|xx+1 xr|12
|xx+| x, 11
x exp(
+
2 - o
-2(02+1 - ot)
-( - 07)
||x, - x=12
+ ||x+11 - x1|2
||x++1 - x-1121
=xxp(
(0 o2) )
2
(o - -
(0 07)
X 1 2x"'xx x ||x|12 fxl12-2x(+1xx 2x
+ -C(x)H1122))
exp(
2
(o) - -0
(0 - -7)
| 1|
x
|x
2x 1x:
+ +C(xx41,x2))
exp(
( - d?)
(o -?))
(o/+1 - -0,)
(o++) - o0
1
x
(o oî) )x, + C(x(+1, )
x
exp(
+
)|xx 11 - 2(
+
2
(oî - o2)
(0+ of)
(0 -z
[o] - o2) + (0 ot)
x
xf+1
)x, - -(xx++1,x x
exp(
Xx| 2 2(
2
(o) of (071 - of)
(0)
(o of)
x
xf+1
exp(
|x/122 2(
)x, + ((x0+1,xx))
(ot
(o) o()
(0î 0f)
(0 oi)
10 x
o of
||x,|| (0f off
+
(07-1-07)
expl
X1
+ +((x++1,++) )
(o ) 2 of)
-
(0 10 -07)
i+ oz
||x,|| 12 - (0 of x + +077
-2)xtt(xx) x)) ) + ((S0)H))))))
= exp(
2
[o] - (0 - o,
02+1 - o²
1
(o%-1 - ,;)x, Xr + 10, - o x;)x
2
+ +C(80-1122))
expp(
lo] o0) -of
X1
0 -0²
0111 03
(0 of Xx, + [o, o x+)x+11
(of
X (x;:
1).
024 o?
0 o²
The KL divergence between the posterior and predicted reverse distribution is (xx,(1(x|xx+11,>> Xx+1, x+) 11)0 (x, xx+1))
[Dxi(N(x;; (o - o7 xx, + (0ū 02)x1+1 (0 (0, of) 0 07
0 - o²
(ot of o2)h((x+1101)) (x) + of
Nix
,0(1))
1
|| [[xxxx/xen1xxx((x) [xx] (x)x))))))))x])]] + C2
2 (aj a. ( -tt)
00?
2
2
[B [xx - )x) + Cz. 2(0 (0 97)
When 7 0, the result degrade to:
+ ofx11 - 1). - -02+1007
q[x:|x+41, = N(x:;
0741
07+1
When do, == 0+41- - oe + O, the KL divergence between posterior and model prediction is simplified by:
lim DKL ( ((1(xx/XX4111XXX xo) (1x(() d0
(o4 0f)x0 + xfx1t1
of - of) |)ll
lim (Nxxi -0
07
20

---

((x; (ot+1 (x)x(x(+1,04411 oixi+1 .61))
o2t1
1
(oit1 -,,)x0
(0 - -ci))(xx+1,
lim
do:
2
2
lat
[4
-ff)
0/+1
07t1
i+1
(o
lim
|xu h(xx+1,
do
07 20044 -1
0
(o 0,)
lim
|x0 0xx1+1
do
2 oi
[+1
141
(0 0??
lim
|xx0 - 0(x))
do
20141
doi
1|00 - (18(+110++11]]
=x(i)|xx0 h(x++1, 0+11)11
which is consistent to the results in Kingma et al. [17 and Karras et al. [16].
A.6 Deriving the Weight in EPNDC
If we interpret the shift in weight from 00t1-0s 22t
exp(
log mogga.-A o
a reweighting
0/02 v2rk.
21g
of DKI(g (g(x) (x//xx-1 lo)llpo (x, (x+)x))))) by Le a similar methodology can applied to derive the weight for (KL(g(x/ x (xx (x+())+))):
Wi DKL (g(x) x; x=) (x((xxxx((x)))
lim
do, 40
W
lim
E (xxxx//xx4 [xx] Epcx (x0x)//04))))))))))) [x,]
da, d0 We -0)00 -07)
1/71 -0
1t
1
lim
E |x Ex(x.1xe11) [x,]1
d0 des 1+1
2 (at n? dor)
o7
-0
W
lim
By 1xxx Ex(x, (x)x)
do
(do.)²
[o
-o3)
6-1
0107+ (0741
02)
lim
| (1(xx|(++xxx7(xx - E Ep(x, (xxx))++))) [x:]11
d0 4(0g
o7 (do:)
0. + o
| 0: kx
0 1 (0 - o
lim
exp(
do
oio²
V2T
2h
1(07 (
[x:]]1
of + to
log 0+
k
o - 0²
lim
exp(
-0
oy
2
21h
4(07 0 (0 01)
||
Exxx (x
(x:111
We compare different weights in EPNDC. As demonstrated in Table 3 these weights are not as effective as the derived weight. Interestingly, simply setting the weight to zero when the standard deviation falls below a certain threshold significantly boosts the performance of the derived weight. This suggests that the latter part of the derived weight might be close to the optimal weight. We observe a similar phenomenon with the final weight we use, suggesting that the current weight might not be optimal. We defer the investigation into how find the optimal weight, what constitutes this optimal weight, and why it is considered optimal to future work.
21

---

Table 3: The accuracy of EPNDC using the EDM checkpoint [6 on CIFAR-10 test set with various weight when a 0.25. Result are tested on the same subset with 512 images as we clarified in Sec. 4.1
Weight Name
Weight
Accuracy (%)
Normalized Weight
81.6
|| [x 18c. pxxx [x]]
Derived Weight
Wt
67.5
Truncated Derived Weight
I[ > 1}
82.8
Linear Weight
Wr-wwn + w0
43.8
Truncated Linear Weight
Wr win
+ wo) 1f0, > 0.5)
77.0
20-00
We also attempt to learn an optimal weight for our EPNDC. However, the learning process difficult (n)(xx)]l [xe]|e_ Attempts to simplify the learning process through cubic spline interpolation for reducing the number of learned parameters are also time-consuming, Our work primarily focuses robust classification of input data using single off-the-shelf diffusion model. Therefore, we leave the exploration of this aspect for future research.
due to the high variance of (xxx [xx] - Ep(x; |x, (1))
A.7 ELBO for Noisy Data in APNDC
In this section, we show that APNDC is actually use the expectation of the ELBOS calculated from samples that are first denoised from the input and then have noise added back. In other word, APNDC approximate l(g)();) by the lower bound of
[log p+ (x+)]-
We first derive the lower bound for 4x, xx [log pr (x+) )] The derivation of this lower bound is just the discrete case of the proof Kingma and Gao [18. We include it here only for completeness.
E Ex( (co) [log Pr (x,)) )]
f ((x, (xx) log g (x, (xp) log (x+)
log (xx - (x0)
/x)) Exx (xo) [log (x, [xo]] DKL (x0(xx/X)))lpppp) (pr
E gix xxo) log (x,, [xo)] DKL
(g(Xx: DKL
X (x0)
- -Eg (xo) [log q(xx(1xxx))) [xo)] (
DEL ( X
+ (x(xx
-C4-
DKL D D
-C4
Xo (x++))
=C4
W Wr w/
-x122
Given input image X,, the ELBOs of Eg(R, (xo= [logpp (8, (X, rather than its ELBO, to approximate its log likelihood:
log p(x,) R
(x,)) C1
Σ we w/Exx~g(xx)x)) (xt, σr) - x x1
Hence, APNDC is actually use the expectation of the ELBOS calculated from samples that are first denoised from the input and then have noise added back.
22

---

Algorithm 3 Linear to EDM
1: Require: A pre-trained EDM hg, noisy input image X,, noise level t, linear schedule {ax))... and {a:)/=1-
2: Calculate the denoised image Xo using he: X
hag ce ae
3: if performing So-prediction then
4: Return: Xo-
5: end if
6: Calculate the noise component Xx-0,N0
7: if performing e-prediction then dt
8: Return:
9: end if
Algorithm 4 EDM to Linear
1: Require: A pre-trained predictor hg, noisy input image X,, noise level a, linear schedule
{a:}/-1 and {o
2: Calculate arg min, a - a|;
3: if performing e-prediction then
4: Predict = t()
5: Calculate X X .
6: end if
7: if performing X prediction then
8: Predict Xn = (()
9: end if
10: Return: X0.
A.8
Converting Other Diffusion Models into Our Definition.
In this paper, we introduce a new definition for diffusion models, specifically as discrete version of Karras et al. [16]. This definition encompasses various diffusions, including VE-SDE, VP-SDE, and methods like x-prediction, v-prediction, and into the difference of parametrization in h. -), makes thcoretical analysis extremely convenient. This operation also decouple the training of diffusion models and the sampling of diffusion models, i.e., any diffusion model could use any sampling algorithm. To better demonstrate this transformation. we present the pseudocodes.
transforming their differences
Linearly adding noise diffusion models. These kind of diffusion models define the forward process as linear interpolation between the clean image and Gaussian noise, iee. X, = 0,Xo + a,e. could be transformed as:
in EDM
in EDM
Xg
Q2
Hence, could directly pass Algorithm 4
Xt ae
and as
EDM model to get the predicted Xo, as shown in
de
DDPM. DDPM define sequence (8.)T and v (1 B1xx /1 IT 3,),, which could seen as special case Linear diffusion models.
VP-SDE, VP-SDE the continuous case of DDPM, which define stochastic differential equa- tion (SDE)
1 3 + VB(taw,, t [0, 1].
dX,, =
where 3(t) = B.r T. Consequently, we could also use an EDM model to solve the reverse VP-SDE by predicting Xa = ho(
1-exp (- f B(e)ds) exp exp - 13 p())da)
x.
Vexp (- ((s)ds)
23

---

VE-SDE, The forward process of VE-SDE is defined as
dX, V (1) dW,.
EDM a special case of VE-SDE, where (1) = L. For a x VE-SDE, the variance of the noise (l). Hence, we could directly use (x,,,, (()) to get the predicted Xp-
B
Experimental Details
B.1 Certified Robustness Details
We adhere to the certified robustness pipeline established by Cohen et al. [6,, yet our method potentially offers tighter certified bound, demonstrated in Appendix [A. To prevent confusion regarding our hyper-parameters and those in Cohen et al. 66. we clarify these hyper-parameters as follows:
maximum allowed l perturbation of the input
number of samples used binomial test to estimate the lower bound PA
σ = std. of Gaussian noise data augmentation during training and certification
T number of diffusion timesteps
T number of diffusion timesteps we selected to calculate/(estimate) evidence lower bounds
a Type one error for estimating the lower bound PA-
To ensure a fair comparison, we follow previous work and do not estimate FB. instead directly setting PB = - PA This approach results in a considerably lower certified robustness, especially for ImageNet. Therefore, it is possible that the actual certified robustness of diffusion classifiers might be significantly higher than the results we present.
There are multiple ways to reduce the number of timesteps selected to estimate the evidence lower bounds (e.g., uniformly, selecting the first T timesteps). Chen al. ( demonstrate that these strategies achieve similar results. In this work, we just adopt the simplest strategy, i.e., uniformly select T' timesteps.
B.2 ImageNet Baselines
We compare our methods with training-based methods as outlined Cohen et al. 16), Salman et al. [38], Jeong and Shin [3] Zhai et al. [50], and with diffusion- based purification methods in Carlini et al. (2). Xiao et al. 47 Since none these studies provide code for ImageNet64x64, we retrain ResNet-50 using these methods and certify it via randomized smoothing. For training based
methods, we utilize the implementation by Jeong and Shin [3 2 with their default Slyper-paramee for IeageNet. For diffusion-based purification methods, first resize the input images 64x64, then resize them back to 256x256, and feed them into the subsequent classifiers. This process ensures fair comparison with method.
B.3 Ablation Studies of Diffusion Models
In the ImageNet dataset, we employ the same diffusion models as our baseline studies, Carlini et al. 2 and Xiao et al. [4]] For the CIFAR- 10 dataset, however, we opt for a 55M diffusion model from Karras et al. [16], as its parameterization aligns more closely with our definition of diffusion models. In contrast, Carlini et al. [2] utilizes 50M diffusion model from Nichol and Dhariwal 33 When we replicate the study by Carlini al. (2) using the model from Karras et [16] and WRN-70-2 [9). we achieve certified robustness of 76.5%% 59.761 76%, and 41.01% for radii 0.25, 0.5, and 0.75. respectively, which nearly identical to their results shown in Table [ choice of diffusion models does not significantly impact certified robustness.
This finding suggests that the
We choose the discrete version of the diffusion model from Karras et al. 16 our definition because it is the simplest version for deriving the ELBOs in this paper. For more details, please see Appendix[A.3
24

---

Name
Properties
ELBO: log (xo]v) 2 Σi=1 13 [wo]] (X1, No +C
expl- >i (
Diffusion Classifier: DC(x),
Eg exp( (
DC
Smoothed Classifier: (oc(X) = DC(()
V2T(pA
Certified Robustness: 12/v /2/=) EL wa/ms
ELBO: logp(x:ly) 2 E.= u. [(g Xx41, (xp(x; X -)]l C2
Diffusion Classifier: EPNDC(x:), expl my
EPNDC
Smoothed Classifier: gENNDC (x), = Pe-NiiON (arg maxy EPNDC =)))====)
Certified Robustness: R (0- (pa) (pE))
ELBO: Mo Pox Et [wi Xollă] Cs
Diffusion Classifier: APNDC(X(), = exp(- ΣT (l (o(5.
Eg exp Elar Be
APNDC
Smoothed Classifier: gAPNDC(X), = : Pa- (arg maxy APNDC(X, +))
Certified Robustness:
(pA)
Table 4: An illustration of the relationship between different ELBOs, likelihood, classifiers, and certified robustness.
B.4 Ablation Studies on Time Complexity Reduction Techniques
Variance reduction proves beneficial. As illustrated in Figure 2(a) our variance reduction technique enables significant reduction in time complexity while maintaining high clean accuracy. Regarding certified robustness, T that tenfold reduction in time complexity results in only a minor, approximately 3%, decrease in certified robustness across all radii. Notably, with 7" 100, our method still attains tate--ofthhe-att clean accuracy and certified robustness for 0,25, 0.5, 0.75 while only cost one-fourth the NFEs Xiao et al. This underscores the effectiveness of our variance reduction approach.
Sift-and-refine proves beneficial. Our method's requirement for function evaluations (NFEs) is proportional to the number of classes, which limits its scalability in datasets with large number of candidate classes. For instance, the ImageNet dataset, without the Sift-and-refine algorithm, our method necessitates approximately 10 NFEs per image (i.e., 100 1000 1000), translating to about 3 x 10t seconds for certifying each image on single 3090 GPU. In contrast, Xiao et [47]s method requires about 4 10t NFEs (i.e., 40 10 10000), roughly 3 x 10 seconds. Our proposed Sift-and-refine technique, however, can swiftly identify the most likely candidates, thereby reducing the time complexity. It adjusts the processing time based on the difficulty of the input samples. With this technique, our method requires only about 1 x 10t seconds per image, making it more efficient compared to Xiao al. 47
C Discussions
C.1 ELBO, Likelihood, Classifier and Certified Robustness
As demonstrated Figure and Table the basic idea of these diffusion classifiers to approximate the log likelihood by ELBO and calculate the classification probability via Bayes' theorem. All these classifiers possess non-trivial robustness, but certified lower bounds vary in tightness.
25

---

noisy samples Table 5: The accuracy of diffusion classifier 3 using the EDM checkpoint [6 on CIFAR-10 test set with various weight. Result are tested on the same subset with 512 images as Chen al. [3]
Weight Name
W
Accuracy (%)
EDM
exp(
log
94.92
V2rks
2kg
Uniform
85.76
DDPM
90.23
d1 of - 0f
EDM-W
88.67
EDM-p(()
exp(
log
93.75
/2tke
26
ELBO
44.53
The diffusion classifier is intuitively considered the most robust, as it process not only clean images but also those corrupted by Gaussian noise. This means it can achieve high clean accuracy by leveraging less noisy samples, while also enhancing robustness through where adversarial perturbations are significantly masked by Gaussian noise. However, its certified robustness not tight as desired. As explained in Appendix |A.22 this is because assume that the maximum Lipschitz condition holds across the entire space, which is a relatively broad assumption, resulting in less stringent certified robustness.
EPNDC and APNDC utilize the Evidence Lower Bound (ELBO) of corrupted data log p(x,). This implies that the least noisy examples they process are at the noise level corresponding to As T increases, the upper bound certified robustness also rises, but this simultaneously diminishes the classifiers' ability to accurately categorize clean data. As highlighted in Chen al. [3, this mechanism proves less effective, particularly in datasets with a large number of classes but low resolution. In such cases, the addition of even small variance of Gaussian noise can render the entire image unclassifiable.
Generally, the Diffusion Classifier is intuitively more robust than both EPNDC and APNDC. However, obtaining a tight theoretical certified lower bound for the Diffusion Classifier proves more challenging compared to EPNDC and APNDC. Therefore, contend that in practical applications, the Diffusion Classifier is preferable to both EPNDC and APNDC. Looking forward, we aim to derive a tighter certified lower bound for the Diffusion Classifier in future research.
C.2 The Loss Weight in Diffusion Classifiers
Typically, when training diffusion models by Eq. (5). most researchers opt to use a re-designed weight vi (e.g., ti in Ho et al. (II), rather than the derived weight wy. When constructing diffusion classifier from an off-the-shelf diffusion model, we find that maintaining consistency between the loss weight in diffusion classifier and the training weight is crucial. As shown Table any inconsistency in loss weight leads to a decrease in performance. Conversely, performance enhances when the diffusion classifier's weight closely aligns with the training weight. Surprisingly, the derived weight (ELBO) yields the worst performance. Therefore, when T = O, we use the training weight úù rather than the derived weight w..
Similarly, when r * O, the derived weight wr(") also results in the worst performance among different weight configurations, as detailed in Appendix C.2 However, determining the optimal weight in this general case is complex challenge. Directly replacing wn(T) with the training weight ú is not appropriate, as wi * we. To address this issue, we propose an alternative: multiplying the weight by dex (i.e., using حuwe?") (r) of with Wi when r O. However, it is important to note that this approach is not optimal, and deriving an optimal weight appears to be infeasible.
w; the weight for EPNDC). This method effectively acts substitution
To enhance generative performance, most researchers opt not to use the derived weight we for the training loss [|]][g(x|xx=1)>>> For example, Ho et al. [I]] define úù = 2. designed distribution p(t), rather than uniform distribution. This approach can be interpreted as
(lp(xx|x+11]]l Instead, they employ redesigned weight w; 11. Another approach involves sampling i from specifically
26

---

adjusting the loss weight to wi = p(t), without altering the distribution of i:
E (xppt( Ex, [1]h(x;; or) x112]
Ex Ext [x( 07) - -x -x1
= =Ixx, Ex,
(p(()))((x,00)) -
gito 070%
For example, Karras al. 16 employ
as the loss weight but modify p(() to (- || llog oullll? where da, Ris kp are hyper-parameters. Thus, is equivalent to setting
v2nks exp
2
+7 oi0.
1
exp (- log a, -
v
2
We discover that maintaining consistency in the loss weight used in diffusion classifiers and during training is crucial. Take EDM as an example. As demonstrated in Table if we fail to maintain the consistency of the loss weight between training and testing, significant performance drop occurs. The closer the weight during testing is to the weight used during training, the better the performance.
Surprisingly, the derived weight (ELBO) yields the poorest performance, indicated in Table 5 This issue also occurs when calculating DKL (k (g(x, X x | our derived weight is significantly inferior to both the uniform weight and the DDPM weight. For (xL(g(x/|X<+11 [p(x x++1)), substituting the derived weight "cti-" with the training weight
(x(+))))) The performance of
o7
o2+o2 1 of02 V2
exp( log a. a. k2 [ is feasible. However, this substitution becomes problematic for
2x2
(x (x)xx((xx>>xxxx>>>>>>>>>>>>>>)>) )). as there is no St-1-- term, outlined in Eq. 13 We propose of two alternative strategies: one interprets the shift from We to iy as reweighting the KL divergence by
requiring only the multiplication of dis to our derived weight. The other strategy involves using the equation úi = wy to reduce the number parameters. While these two interpretations yield iden- tical results for Dx1,(1(x, Xx+1, xo) (o)]le(xe [x++))). they differ for DRr. (g(xx/x(x+11 xx)]lp(Xe (X++ Therefore, directly deriving an optimal weight appears infeasible. For detailed information, see Appendix A.6
w.
C.3 Certified Robustness of Chen et al. 13
In this section, our goal is establish certified lower bound of Chen al. 3. Specifically, under the conditions where PA = 1 and PB = 0, the maximum certified radius is determined to be approximately 0.39. This implies that the certified radius we derive could not surpass 0.39. In practical applications, our method achieves an average certified radius of 0.0002.
Nevertheless, can significantly enhance the certified radius by adjusting wy. For example, simply set W/ = 1, we can get an average certified radius of 0.009, 34 times larger than previous one. By reducing Wy for smaller and increasing it for larger 1, such zeroing the weight when o, S 0.5, achieve an average radius 0.156.
It is important to note that this finding does not imply that Chen et al. 3 lacks robustness in its weight-adjusted version. As discussed in previous sections, the certified radius merely a lower bound of the actual robust radius, and higher lower bound does not necessarily equate to higher actual robust radius. When wy is increased for larger t. obtaining a tighter certified radius will be much easier, but the actual robust radius could intuitively decrease due to increased noise in the input images.
C.4 Time Complexity Reduction Techniques that Do Not Help
Advanced Integration. In this work, we select T timesteps uniformly. As we discuss earlier, there one-to-one mapping between a and in our context. When we change the variable to a, this can be seen as calculating the expectation using the Euler integral. We also try using more advanced integration methods, like Gauss Quadrature, but only observe nuanced differences that there is no any difference in clean accuracy and certified robustness, indicating that the expectation calculation is robust to small truncation errors. We do not attempt any non-parallel integrals, as they significantly reduce throughput.
27

---

Algorithm 5 Sift-and-refine
1: Require: An ELBO computation function for a given timestep / and a class denoted as (applicable for
DC, EPNDC, or APNDC); noisy input image xzi sift timesteps [f, (40) refine steps (r.)rr threshold r.
2: Initialize: the candidate class list C = 10. K).
3: for i- 0 to 1, do
4: for each class in C do
Calculate ELBO for class y at timestep 4 Cg = (
6: end for
7: Find the class m with the minimum ELBO: m arg mi
8: Update C by removing classes with reconstruction loss greater than that of m:
C= {v E C: Cy Cm +}
9: end
10: Reinitialize ey: = ac Vy & C,0Vy
11: for = (11 to T, do
12:
for each class y in C do
13:
Calculate and accumulate ELBO for class y at timestep 4 ey = ey cx(xx,,,,)))
14: end for
15:
end for
16: Return: ÿ= arg miny Cy.
Algorithm Discrete Progressive Class Selection
1: Require: A pre-trained diffusion model Eg, input image x, predefined number of classes K, class candidate trajectory Cound and timestep candidate trajectory Teund-
2: Initialize: entire timesteps i 2e,([1,2, ,'').. counter pointer 0 and top-k cache Kup
{1, (1, .K).
3: for (C1. 62) in (Crund, Tennd) do
4: Esclect = t|cc2 c2)
5: Calculate logit, Enetaey [w) |lls (x., v) =| for all Kop simultancously using hg-
6: Merge logit, calculated in the previous step into logit, currently calculated.
Sort )
8: Set the smallest ej class new Kup from the sorted ylo
Update counter pointer e 02.
10: end for
11:
Return: Kepp
Sharing Noise Across Different Timesteps. In Sec. 3.4 we demonstrate that by using the same X; for all classes, we significantly reduce the variance predictions. This allows us to use fewer number of timesteps, thereby greatly reducing time complexity. From another perspective, using the same x; for all classes is equivalent to applying the same noise to samples at the same timestep. This raises the question: "If share the noise across all samples, could we further reduce time complexity?" However, this approach proves incffective. Analyzing the difference between the logits of two classes reveals that sharing noise does not reduce the variance of this difference. Consequently, we opt not to share noise across different timesteps but only within the same timestep for different classes.
Discrete progressive class selection algorithm. We design a normalized discrete critical class selection algorithm for accelerating diffusion classifiers. Typically, the time complexity of the vanilla diffusion classifier can be defined as (KTT), where K denotes the count of classes and denotes the number of timesteps. Sharpening T is tractable, but overdoing that practice can have extremely negative impact on final performance. Another way to speed up the computation is to actively discard some unimportant classes when estimating the conditional likelihood via conditional ELBO. Indeed, these two sub-approaches can be merged in parallel in a single algorithm (i.e., our proposed class selection algorithm). Additionally, to achieve in-depth analysis of acceleration in diffusion classifiers, the time complexity of our proposed discrete acceleration algorithm can be determined by predefined manual class candidate trajectory Crand as well predefined manual timestep candidate trajectory Teand-
The procedure of the discrete progressive class selection algorithm can be described in Algorithm 6 The specific mechanism of Algorithm 6 can be described from a simple example: the predefined trajectory Ceand is set as [400, 80, 40, I] and the predefined trajectory Teand is set as [2, 5, 25, 50]
28

---

Table 6: The experimental results of discrete progressive class selection algorithm.
Timestep Trajectory
Classes Trajectory
Time Complexity
Accuracy
2,
5, 25, 50
400, 80. 40. 1]
5800
58.00%
2, 5, 17, 50
500, 136, 37,
6353
58.20%
12 5, 17, 50
500, 100, 20,
5360
57.80%
12 4, 12, 25
500, 136, 37,
4569
54.10%
2, 4, 12, 25
500, 100, 20,
4060
54.69%
22 7, 35, 50
297, 80, 15.
5900
56.84%
12, 7, 35, 50
297, 100, 20,
6535
57.42%
(2. 6, 20, 50
350, 100, 20,
5400
57.81%
[2, 6, 25, 50
350, 100, 20,
5800
56.10%
2, 7, 35, 50
297, 80, 40. 1
6275
56.84%
2, 25, 50
297, 80, 40.
5491
57.42%
2, 5, 15, 50
500, 80, 40, 1
5700
59.18% %
4, 8, 50
500, 200, 100,
8000
56.05%
2, 4, 8, 50
400, 160, 80, 1
6800
56.25%
2, 4, 8, 50
400, 120, 60,
5800
56.05%
2, 4, 8, 50
4000 80, 40,
4800
55.47%
simultaneously. Assume we conduct this accelerated diffuusin classifier with K = =000 in the specific ImageNet [47]. First, we estimate the diffusion loss, which equivalent to conditional likelihood, for 1000 classes by time points and then sort the losses of the different classes obtain the smallest 400 classes. Subsequently, we estimate the diffusion loss for 400 classes by 3 (w.r.. 5-2) time points and then sort the losses for different classes obtain the smallest 80 classes. Ultimately, the procedure concludes with the selection of 40 out of 80 classes with 20 time points (w.r.. 25-5), followed by choosing class from 40 classes with 25 (w.r.. 50-25) time points.
The ablation outcomes presented in Table illustrate that suitable design of predefined manual timestep candidate trajectories Crand and Teand are crucial in the final performance of diffusion classifiers. salient observation in the initial definition Crand and Teand is that Teand can initially be small, whereas Ceand must start significantly larger to achieve high accuracy while ensuring low time complexity. Thus, timestep trajectory [2, 5, 15, 50) and the classes trajectory [400, 80, 40, I] are in accordance with the above conditions and achieve the best performance in various predefined trajectories.
Accelerated Diffusion Models. We observe that consistency models [43] and CUD [40 determine the class of the generated object at large timesteps, while they primarily refine the images at lower timesteps. In other words, at smaller timesteps, the similarity between predictions of different classes is so high that classification becomes challenging. Conversely, at larger timesteps, the images become excessively noisy, leading to less accurate predictions. Consequently, constructing generative classifiers from consistency models and CUD appears to difficult task.
D Limitations
Despite the significant improvements in certified robustness, this work still presents limitations. Firstly, the time complexity of the diffusion classifier restricts its applicability in real-world scenarios, providing primarily theoretical benefits. Additionally, the certified bounds for diffusion classifiers not straightforward enough. Future efforts could emulate the strong law of randomized smoothing to establish more direct certified lower bound for Chen et al. 3
29

---

Ethics Statements
The advancement of robust machine learning models, particularly in the realm of classification under adversarial conditions, is crucial for the safe and reliable deployment of Al in critical applications. Our work on Noised Diffusion Classifiers (NDCs) represents a significant step towards developing more secure and trustworthy Al systems. By achieving unprecedented levels of certified robustness, our approach enhances the reliability of machine learning models adversarial environments. This particularly beneficial in fields where decision-making reliability is paramount, such autonomous driving, medical diagnostics, and financial fraud detection. Our methodology could substantially increase public trust in AI technologies by demonstrating resilience against adversarial attacks, thereby fostering wider acceptance and integration of Al solutions in sensitive and impactful sectors.
30

---

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

---

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

---

Answer: [Yes]
Justification:
We only use CIFAR-10 and ImageNet.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.cm cc/
httpl///uuiies/ooeeuuuiiiiseeees wwwllmmmiiioooocccyc..... Pllccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wtw.iideeeoooSSubiissseeeeee /
seiiiissssiiiciiyioo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This work employs single off-the off-the-shelf diffusion model for robust classifica- tion without requiring any additional training.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Following previous work in the community of certified robustness, we use the same type error, 0.001.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eπror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
33

---

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

---

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

---

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


Reviews:
[{"review_id": "YqreEvSEyi", "reviewer": "Reviewer_LwbB", "summary": "This paper presents a theoretical analysis of the enhanced robustness in diffusion-based classifiers and introduces a generalized Noised Diffusion Classifier, EPNDC. The authors utilize the Evidence Lower Bound (ELBO) of each conditional log-likelihood $\\log p(x_\\tau | y) $and Bayes' theorem as the logits for each class. They identified that EPNDC is time-consuming due to the iterative computation of two conditional ELBOs. To address this, they leverage the ELBO of an ensemble of EPNDC to approximate the expected likelihood as logits without additional computational cost. Additionally, they developed variance reduction and sift-and-refine techniques to reduce time complexity. Experimental results demonstrate that APNDC achieves significantly better robustness without requiring extra training data, fewer diffusion steps, and a reduced number of samples needed to estimate the Lipschitz bound.", "questions": "1. Refer to weaknesses. \n\n2. Eq (15) uses the diffusion model $h_\\theta$ one more time than Eq (12). Why does APNDC not increase the computational overhead compared to EPNDC (Line201)? Please explain further.", "limitations": "The authors didn't address the limitations of APNDC, but Diffusion Classifiers are still far behind the current SOTA in classification accuracy. These are some potential limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The entire paper is logically structured with a clear progression, enabling readers to understand it well. From Algorithm 1 to Algorithm 2 to Algorithm 5, the authors continuously explore problems, improve algorithms, and provide thorough analysis and theoretical proofs.\n\n2. The experiments are comprehensive, and compared to the benchmark, EPNDC shows significant improvements in certified accuracy. This demonstrates EPNDC's high scalability in handling large datasets with numerous categories.", "weaknesses": "1. Some causal relationships are unclear or lack citations, requiring further explanation from the authors. For instance, in Line 156: What does the \"nabla operator\" refer to? It is neither explained nor cited. In Lines 161-164: \"However, similar to the weak law of randomized smoothing, such certified robustness has limitations because it assumes the maximum Lipschitz condition is satisfied throughout the entire perturbation path. As a result, the robust radius is less than half of the reciprocal of the maximum Lipschitz constant.\" The causal relationship here is unclear and needs further clarification.\n\n2. Although the diffusion classifier is highly scalable and robust, its clean accuracy on ImageNet is still far behind the current state-of-the-art (90%+). More details can be found at [https://paperswithcode.com/sota/image-classification-on-imagenet](https://paperswithcode.com/sota/image-classification-on-imagenet).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating the writing and contribution of our paper. We are deeply encouraged by your kind words. Below we address detailed comments, and hope you may find our reponse satisfactory.\n\n\n\n***Weakness 1: Nabla operator is unclear.***\n\nThank you for pointing this out. In our paper, the Nabla operator refers to the gradient operator. We will make this clearer in the final version.\n\n***Weakness 2: Lines 161-164 is unclear.***\n\nThank you for your suggestion. We will modify this section in the final version to:\n\n\n> However, similar to the weak law of randomized smoothing, such certified robustness has limitations because it assumes the maximum Lipschitz condition is satisfied throughout the entire perturbation path, i.e., it assumes the equality always holds in \\\\(|f(\\\\mathbf{x}\\_{adv})\\_y - f(\\\\mathbf{x})\\_y| \\leq L\\\\|\\\\mathbf{x}-\\\\mathbf{x}\\_{adv}\\\\|\\_2\\\\) when \\\\(f\\\\) has Lipschitz constant \\\\(L\\\\). As a result, the equality also holds in \\\\( f(\\\\mathbf{x}\\_{adv})\\_y \\geq f(\\\\mathbf{x})\\_y -  L\\\\|\\\\mathbf{x}-\\\\mathbf{x}\\_{adv}\\\\|\\_2 \\\\) and \\\\(f(\\mathbf{x}\\_{adv})\\_{\\hat{y}} \\leq f(\\mathbf{x})\\_{\\hat{y}} +  L\\\\|\\mathbf{x}-\\mathbf{x}\\_{adv}\\\\|\\_2\\\\) for \\\\(\\max\\_{\\hat{y} \\neq y} f(\\mathbf{x})\\_{\\hat{y}}\\\\). To guarantee the prediction is unchanged (i.e., \\\\(f(\\mathbf{x}\\_{adv})\\_y \\geq f(\\mathbf{x}\\_{adv})\\_{\\hat{y}}\\\\)), its requires the perturbation \\\\(\\\\|\\mathbf{x}-\\mathbf{x}_{adv}\\\\|_2\\\\) must be less than \\\\(\\frac{1}{2L}\\\\). \n\n\n***Weakness 3: Still not comparable with discriminative classifiers on ImageNet.***\n\n\n\nWe acknowledge and agree that generative classifiers, including diffusion classifiers, currently lag behind discriminative classifiers in terms of clean accuracy on ImageNet. We recognize this as the primary limitation of our work and will include it in the limitation section of our paper. However, generative classifiers are still promising due to their robustness, interpretability, certifiability, and strong mathematical foundation, which are advantages not typically found in discriminative classifiers. We will continue to focus on advancing generative classifiers and believe they will play a crucial role in security applications.\n\n\n\n\n***Question 1: APNDC has one more NFE than EPNDC.***\n\nThank you for your meticulous observation. APNDC does require one more forward pass to compute \\\\(h\\_\\theta(x\\_\\tau, \\tau)\\\\). We have revised our claim about the time complexity of APNDC and EPNDC to: \"This nearly free ensemble can be executed with only one more forward pass of UNet.\"", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KRdPAgqBv1", "reviewer": "Reviewer_TbjG", "summary": "This work proves that diffusion classifiers possess inherent robustness to adversarial attacks by demonstrating their O(1) Lipschitzness and establishing their certified resilience. By generalizing these classifiers to handle Gaussian-corrupted data and using evidence lower bounds for likelihood approximation, the research demonstrates the superior certified robustness of Noised Diffusion Classifiers (NDCs).", "questions": "Please address the weaknesses mentioned above.", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper showcases the robustness of the proposed Noised Diffusion Classifiers (NDCs), achieving high certified robustness on the CIFAR-10 and ImageNet 64x64 datasets. The study also provides a proof of O(1) Lipschitzness for diffusion classifiers.", "weaknesses": "1. The proposed method combines two existing techniques, diffusion classifiers and randomized smoothing, which is not sufficiently novel. The paper needs to better highlight what sets this approach apart from existing methods and how it fundamentally advances the field. Although the authors attempt to establish a theoretical framework, the derivation of the Lipschitz constant and its implications are not sufficiently detailed, leaving unanswered questions about the robustness guarantees.\n\n2. The experimental evaluation relies heavily on the small CIFAR-10 and ImageNet 64x64 datasets. Expanding the experiments to include larger datasets, such as ImageNet-1K, would provide a more comprehensive assessment.\n\n3. The paper discusses techniques to reduce time complexity but does not convincingly demonstrate the practicality of the proposed methods with experimental results, such as throughput or inference latency. A more detailed analysis and comparisons of computational efficiency, especially in relation to existing methods, are needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating the strong results of our methods. Below we address the detailed comments, and hope you may find our response satisfactory and update the score accordingly.\n\n\n***Weakness 1: Insufficient Novelty.***\n\nWe disagree with our highest respect. We justify the novelty from two aspects. First, diffusion classifiers have demonstrated superior empirical robustness and are increasingly used in robust classification tasks. However, a comprehensive theoretical understanding of their robustness is still lacking. There are concerns about whether their robustness is overestimated or if they might be vulnerable to potentially stronger adaptive attacks in the future. In this work, **we address these concerns by using proper mathematical tools (e.g., randomized smoothing) to provide a theoretical foundation for diffusion classifiers**. This contribution is novel and valuable to our community.\n\nSecond, the analysis of diffusion classifiers is highly nontrivial, with several key technical contributions that are also new:  \n\n1. **Theoretical Foundation for Diffusion Classifiers:**\n   Diffusion classifiers are traditionally **not** compatible with randomized smoothing because they struggle to handle noisy data. To address this, we derive the analytical solution of the diffusion classifiers' gradient and bound their gradient norm (Lipschitz constant in Appendix A.2). This provides a lower bound and demonstrates the inherent robustness of diffusion classifiers, offering insights into the source of their robustness.\n\n\n2. **Generalization to Noisy Data and Remarkable Certified Robustness Record:**\n\n   Bounding robustness using the maximum Lipschitz constant \\\\(L\\\\) can only provide a certified robustness of at most \\\\(\\frac{1}{2L}\\\\). To achieve a tighter certified bound, we generalize diffusion classifiers to handle noisy data by deriving two noisy ELBOs, for which we can establish their point-wise Lipschitzness. These generalized diffusion classifiers achieve remarkable certified robustness, breaking previous records by exceeding 70\\% certified robustness at \\\\(\\epsilon\\_2=0.5\\\\), which is less than 10\\% below the empirical upper bound.\n\n3. **Reduction in Time Complexity:**\n   We reduce the time complexity of diffusion classifiers by more than 10x using our proposed variance reduction and sift-and-refine methods, making diffusion classifiers more practical for large-scale applications.\n\nOverall, **we fundamentally address the key concerns about the robustness of diffusion classifiers by proving their robustness lower bound.** These contributions are significant and new, as agreed by reviewers LwbB, p9kw, and yRsf.\n\n\n***Weakness 2: Experiments on ImageNet-256x256.***\n\nThank you for the valuable suggestion. We agree that experiments on ImageNet-256x256 are crucial for demonstrating the scalability of diffusion classifiers. However, there are currently no conditional diffusion models available at 256x256 resolution **in the RGB space**.\n\nExisting ImageNet diffusion models are trained either at 64x64 resolution (e.g., EDM [3]) or in a 64x64 latent space (e.g., stable diffusion [2]). Although the latent diffusion models achieve state-of-the-art generation performance, they cannot be applied to adversarial defense tasks because their encoder is vulnerable to attacks [4].\n\nWe recognize this as a primary limitation of our work. We will continue to address this issue by employing more advanced diffusion training methods (e.g., [1]).\n\n\n\n***Weakness 3: Comparison of inference latency.***\n\nThank you for the valuable suggestion. We provide further results on  time complexity:\n\nCIFAR10:\n\n|              Method              | Architecture | Certifying NFEs | Certifying Real Time | Inference NFEs | Inference Real Time |\n|:---:|:---:|:--:|:---:|:----:|:----:|\n|  RS/SmoothAdv/Consistency/MACER  |  ResNet-110  |      O(N)       |        \\\\(10.81\\\\)         |      O(1)      |  \\\\(0.001\\\\)   |\n| Carlini | UNet+WRN-72  |      O(N)       |   \\\\(1.78 \\times  10^3\\\\)   |      O(1)      |  \\\\(0.030\\\\)   |\n|               Xiao               | UNet+WRN-72  |     O(400N)     |   \\\\(7.44 \\times 10^4 \\\\)  |     O(400)     |  \\\\(1.14\\\\)   |\n| DC/APNDC/EPNDC (variance-reduction) |     UNet     |    O(1250N)     |   \\\\(2.92 \\times  10^4 \\\\)  |    O(1250)     |   \\\\(2.92\\\\)     | \n\nImageNet:\n\n|              Method              |  Architecture  | Certifying NFEs | Certifying Real Time  | Inference NFEs | Inference Real Time |\n|:-------:|:---:|:------:|:-----:|:------:|:---------:|\n|  RS/SmoothAdv/Consistency/MACER  |   ResNet-50    |      O(N)       |   \\\\(26.701\\\\)   |      O(1)      |        \\\\(0.004\\\\)        |\n| Carlini | UNet+ResNet-50 |  O(N)  |     \\\\(1025.586\\\\)        |      O(1)      |     \\\\(0.108\\\\)  |\n| Xiao | UNet+ResNet-50 |  O(400N)   |  \\\\(432000\\\\)         |     O(400)     |    \\\\(43.2\\\\)   |\n| DC/APNDC/EPNDC (sift-and-refine) |      UNet      | undetermined  | \\\\(1.1 \\times  10^5\\\\) | undetermined |   \\\\(112.3\\\\)     | \n\n\nAs shown:\n\n- When using sift-and-refine, the NFEs for each image depend on the specific image. Thus, the time complexity is undetermined.\n- During certification, different samples are computed in parallel, so the time complexity is much lower than Inference Real Time * N.\n- The value of N for the Diffusion Classifier is ten times smaller than for other models.\n- The time complexity of diffusion classifiers is slightly higher than that of the approach by Xiao et al. (2022). We recognize this as a primary limitation of both our approach and generative classifiers in general. We are actively working to reduce the time complexity so that it becomes independent of $K$.\n\n\n\n## Reference:\n\n[1] Matryoshka diffusion models. ICLR, 2023.\n\n[2] High-resolution image synthesis with latent diffusion models. CVPR, 2022.\n\n[3] Elucidating the design space of diffusion-based generative models. NeurIPS, 2022.\n\n[4] Pixel is a Barrier: Diffusion Models Are More Adversarially Robust Than We Think. arXiv, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2RYawwmGjU", "reviewer": "Reviewer_76VC", "summary": "The authors investigate the certified robustness of diffusion classifiers. For this purpose, they first show that these classifiers have O(1) Lipschitzness and subsequently achieve tighter robustness bounds through Bayes' theorem and the ELBO.", "questions": "Q1: Could the authors provide a computational cost comparison between different methods?", "limitations": "Limitations are included in the appendix.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: Using diffusion models to generate large amounts of synthetic data is one of the most promising approaches to improve empirical and certified robustness in recent years. The authors utilize diffusion models directly to achieve high certified robustness. \n\nS2: While prior work has investigated the robustness of diffusion classifiers, they do not provide certified guarantees. This gap is addressed in this work.\n\nS3: The work provides both relevant empirical and theoretical contributions", "weaknesses": "W1: References could be ordered by appearance (minor)\n\nW2: The nature of diffusion classifiers induces a considerable computational overhead compared to standard classifiers. However, the authors try to address this issue through their sift-and-refine algorithm. Still a comparison between different methods w.r.t. inference time would have been informative. (could also include standard classifiers). Note that I would not consider large computational cost as a negative point concerning paper acceptance I just believe that a comparison would be helpful for the reader. Still the appendix provides some information w.r.t. time complexity so I view this as a minor issue. \n\nW3: Appendix D is very short and could be incorporated into the paper (at least in the camera-ready version)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the contribution of our work and for providing valuable feedback. Below we address your detailed comments and hope that you find our responses satisfactory.\n\n***Weakness 1: References could be ordered by appearance.***\n\nThank you for your suggestion. We will revise the references to be ordered by appearance in the final version.\n\n***Weakness 2: Appendix D can be incorporated into the main text.***\n\nThank you for your advice. We will incorporate the Limitation section into the end of the main text in the final version.\n\n\n\n***Weakness 3 and Q1: A table for comparing time complexity.***\n\n\n\nThank you for your valuable suggestion. We strongly agree that a table presenting the comparison of time complexity is necessary. The result is shown below:\n\n\n\n\nCIFAR10:\n\n|              Method              | Architecture | Certifying NFEs | Certifying Real Time | Inference NFEs | Inference Real Time |\n|:---:|:---:|:--:|:---:|:----:|:----:|\n|  RS/SmoothAdv/Consistency/MACER  |  ResNet-110  |      O(N)       |        \\\\(10.81\\\\)         |      O(1)      |  \\\\(0.001\\\\)   |\n| Carlini | UNet+WRN-72  |      O(N)       |   \\\\(1.78 \\times  10^3\\\\)   |      O(1)      |  \\\\(0.030\\\\)   |\n|               Xiao               | UNet+WRN-72  |     O(400N)     |   \\\\(7.44 \\times 10^4 \\\\)  |     O(400)     |  \\\\(1.14\\\\)   |\n| DC/APNDC/EPNDC (variance-reduction) |     UNet     |    O(1250N)     |   \\\\(2.92 \\times  10^4 \\\\)  |    O(1250)     |   \\\\(2.92\\\\)     | \n\nImageNet:\n\n|              Method              |  Architecture  | Certifying NFEs | Certifying Real Time  | Inference NFEs | Inference Real Time |\n|:-------:|:---:|:------:|:-----:|:------:|:---------:|\n|  RS/SmoothAdv/Consistency/MACER  |   ResNet-50    |      O(N)       |   \\\\(26.701\\\\)   |      O(1)      |        \\\\(0.004\\\\)        |\n| Carlini | UNet+ResNet-50 |  O(N)  |     \\\\(1025.586\\\\)        |      O(1)      |     \\\\(0.108\\\\)  |\n| Xiao | UNet+ResNet-50 |  O(400N)   |  \\\\(432000\\\\)         |     O(400)     |    \\\\(43.2\\\\)   |\n| DC/APNDC/EPNDC (sift-and-refine) |      UNet      | undetermined  | \\\\(1.1 \\times  10^5\\\\) | undetermined |   \\\\(112.3\\\\)     | \n\n\n\n\n\nAs shown:\n\n- When using sift-and-refine, the NFEs for each image depend on the specific image. Thus, the time complexity is undetermined.\n- During certification, different samples are computed in parallel, so the time complexity is much lower than Inference Real Time * N.\n- The value of N for the Diffusion Classifier is ten times smaller than for other models.\n- The time complexity of diffusion classifiers is slightly higher than that of the approach by Xiao et al. (2022). We recognize this as a primary limitation of both our approach and generative classifiers in general. We are actively working to reduce the time complexity of diffusion classifiers so that it becomes independent of $K$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TDoWrV0b9L", "reviewer": "Reviewer_p9kw", "summary": "This paper derives an upper bound of the Lipschitz constant for diffusion classifiers. Then, it proposes Exact Posterior Noised Diffusion Classifier (EPNDC) and Approximated Posterior Noised Diffusion Classifier (APNDC) by deriving ELBO upper bounds on $\\log p (x_\\tau)$ and thereby enabling classifying noisy images. The APNDC achieves state-of-the-art certified robustness.", "questions": "- Line 145: Why are the mentioned quantities bounded in the range $[0, 1]^D$? Do you clip $h_\\theta (x_t, \\sigma_t)$ to $[0, 1]^D$? How about $\\|\\| h_\\theta (x_t, \\sigma_t) \\|\\|_2^2$?\n- Eq (12): The notation $q$ was introduced in Eq (1) to represent probabilities in the forward diffusion process. So, how to compute $q (x_t | x_{t+1})$? It would also be nice to add subscripts to each of the nested expectations, so that it's clear what variables the expectations are taken over. \n- Also Eq (12): does the method become computationally cheaper when $\\tau$ increases? Is it correct that different values of $\\tau$ can reuse some computation, so if you set $\\tau$ to 0, you simultaneously get the ELBO bound for $\\tau = 0, 1, \\ldots, T$?\n- Remark 3.4: when would it make sense to use $\\tau = 0$? When $\\tau$ is $0$, is $\\sigma_\\tau$ also 0? Does this mean randomized smoothing is not used?\n- Line 224: the APNDC reconstruction loss $\\|\\| h_\\theta (x_\\tau, \\sigma_\\tau) \\|\\|_2^2$ sees great resemblance to the training objective of consistency models. Does this intuitively imply that consistency models are more suitable or less suitable for APNDC? I see a short discussion about consistency models in the appendix, but it does not fully address my curiosity.\n- Line 247 mentions that $\\sigma_\\tau \\in \\\\{ 0.25, 0.5, 1.0 \\\\}$. What are the corresponding $\\tau$ values? Which setting is used for which results? Are the different radii in Table 1, Table 2, and Figure 2 evaluated with the same $\\sigma_\\tau$ or different ones?", "limitations": "As is the case for numerous diffusion classifier paper, the computation complexity, while improved in this paper, is far from ideal. This paper evaluates the method on a small subset of CIFAR-10 and ImageNet, probably due to this reason.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theory is cool and the math is intriguing. I like this direction because it leverages the shared Gaussian structure in diffusion models and randomized smoothing while circumventing the challenges of attacking diffusion models. The empirical evaluation results (especially Figure 2a) are also impressive.", "weaknesses": "In my opinion, some of the contents are not explained very clearly. Please see below and the contents of the \"Questions\" section.\n\n- Table 4 is nice. However, I wish it was in the main text instead of the appendix, because the current main text misses the discussion on how to calculate the certified robustness for the proposed models.\n- Figure 2 doesn't present the certified radius with a conventional diffusion classifier, as derived in Eq. (11). Since (11) is an important contribution of this work, I believe it should be included.\n- I would like to see an ablation study on $\\sigma_\\tau$, but could not find this result.\n\nOverall, this is still a nice paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the topics and contributions of our paper. We are greatly encouraged by your appreciation. Below, we address your detailed comments and hope that you find our responses satisfactory.\n\n***Weakness 1: Table 4 should be put in the main text.***\n\nThank you for your advice. We will move Table 4 into the main text.\n\n***Weakness 2: Certified radii of diffusion classifiers should be included in the main table.***\n\nThank you for your advice. We will incorporate these results into Table 1.\n\n\n\n\n\n***Weakness 3: Ablation studies in \\\\(\\sigma_\\tau\\\\).***\n\nThank you for your advice. However, we are unable to perform these experiments during the rebuttal phase because, for each \\\\(\\sigma\\_\\tau\\\\), we would need to obtain predictions from our model over the dataset 10,000 times. Nearly all previous work uses \\\\(\\sigma\\_\\tau \\in \\\\{0.25, 0.5, 1\\\\}\\\\), and these studies have already demonstrated that these three radii are sufficient for obtaining the upper bound of the certified radius. Therefore, we did not perform this ablation study. We adopt this setting to enable fair and equitable comparisons and to avoid recoding all previous baselines.\n\n\n\n\n\n\n***Question 1: \\\\(h_\\theta(x_t,t)\\\\) are bounded.***\n\nYes, we clip the output of the UNet \\\\(h_\\theta(x_t,t)\\\\) to \\\\([0,1]\\\\), thus it is bounded.\n\n\\\\(\\mathbb{E}\\_{x\\_t}[\\|h\\_\\theta(x\\_t,t)\\|\\_2^2]\\\\) is the expectation of a function whose output is bounded within \\\\([0,1]\\\\) over a Gaussian distribution, which is in the form of randomized smoothing, thus its Lipschitz constant can be bounded.\n\n\n\n\n\n\n***Question 2: About \\(q\\) distribution.***\n\nThank you for your suggestion. We will add subscripts to each of the nested expectations to clarify the expression:\n\n\\\\[\n\\log p(\\mathbf{x}\\_\\tau) \\geq -\\sum\\_{t=\\tau}^{T}w\\_t^{(\\tau)} \\mathbb{E}\\_{q(\\mathbf{x}\\_{t+1}|\\mathbf{x}\\_\\tau)}\\left[\\\\|\\mathbb{E}\\_{q(\\mathbf{x}\\_t|\\mathbf{x}\\_{t+1},\\mathbf{x}\\_\\tau)}[\\mathbf{x}\\_t]-\\mathbb{E}\\_{p(\\mathbf{x}\\_{t}|\\mathbf{x}\\_{t+1})}[\\mathbf{x}\\_{t}]\\\\|^2\\right] + C\\_2,\n\\\\]\n\nin the revision.\n\nWe do not calculate \\\\(q(\\mathbf{x}\\_t|\\mathbf{x}\\_{t+1})\\\\) directly; instead, we only calculate the expectation of the reverse Gaussian distribution \\\\(q(\\mathbf{x}\\_t|\\mathbf{x}\\_{t+1})\\\\), as shown in Eq. (13), \\\\(\\mathbb{E}\\_{q(\\mathbf{x}\\_t|\\mathbf{x}\\_{t+1},\\mathbf{x}\\_\\tau)}[\\mathbf{x}\\_t]=\\frac{(\\sigma\\_{t+1}^2-\\sigma\\_t^2)\\mathbf{x}\\_{\\tau}+(\\sigma\\_t^2-\\sigma\\_\\tau^2)\\mathbf{x}\\_{t+1}}{\\sigma\\_{t+1}^2-\\sigma\\_\\tau^2}\\\\).\n\n\n\n\n\n\n***Question 3: About Eq. (12).***\n\nDiffusion can be considered a continuous stochastic differential equation (SDE) within the range \\\\([\\sigma_\\tau, \\sigma_T]\\\\). The number of function evaluations (NFEs) depends on both \\\\(\\sigma_T - \\sigma_\\tau\\\\) and the discretization interval \\\\(\\sigma_{i+1} - \\sigma_i\\\\). If you keep the discretization interval unchanged, the NFEs decrease as \\\\(\\tau\\\\) increases or \\\\(\\sigma_T\\\\) decreases.\n\nWe are impressed by your idea of reusing computations to calculate all evidence lower bounds (ELBOs) simultaneously. Since the neural network output \\\\(p(\\mathbf{x}\\_t|\\mathbf{x}\\_{t+1})\\\\) does not depend on \\\\(\\tau\\\\), we can reuse this part when calculating ELBOs for different \\\\(\\tau\\\\). Given that the neural network's forward pass is the computational bottleneck compared to other parts of the ELBO calculations, this means that for a given \\\\(\\mathbf{x}\\_0\\\\), we can compute all ELBOs over \\\\(\\tau\\\\) simultaneously in the time it takes to compute a single ELBO.\n\n\n\n\n\n***Question 4: In the case of \\\\(\\tau=0\\\\).***\n\nWhen \\\\(\\tau=0\\\\), the ELBOs of EPNDC reduce to the ELBOs in DDPM, and the EPNDC reduces to vanilla diffusion classifiers. In this case, we cannot use randomized smoothing.\n\n\n\n\n\n\n***Question 5: Similarity between APNDC and consistency models.***\n\nWe agree that there is a significant similarity between the training loss of consistency models and APNDC's ELBO. However, consistency models (CD) seem to lose their ability to classify and instead overfit to the generation task. Specifically, when \\\\(t\\\\) is small, the predictions for all labels \\\\(h(x_t, t, y)\\\\) are nearly identical, with their cosine similarity exceeding 0.99. We suspect this is due to the distillation phase causing consistency models to overfit to the generation task. We plan to investigate this issue further by training consistency models ourselves to understand the underlying reasons.\n\n\n\n\n\n\n***Question 6: About \\\\(\\sigma\\_\\tau\\\\).***\n\nKarras et al. [2] emphasize that since there is a bijection between \\\\(t\\\\) and \\\\(\\sigma\\\\), and \\\\(t\\\\) depends on discretization, it is better to use \\\\(\\sigma\\\\) as the variable to describe the noise added to the input images. Therefore, finding \\\\(\\tau\\\\) for \\\\(\\sigma\\_\\tau=0.25\\\\) is meaningless. In practice, we directly set \\\\(\\sigma\\_\\tau=0.25\\\\) and determine \\\\(T'\\\\) discretization steps within \\\\([\\sigma\\_\\tau, \\sigma\\_T]\\\\) to calculate the MSE loss at these \\\\(T'\\\\) timesteps.\n\nFor Tables 1 and 2, we follow previous work by calculating the certified radius using \\\\(\\sigma\\_\\tau=0.25, 0.5, 1\\\\), respectively, and selecting the maximum one to include in the tables and figures.\n\n\n\n\n\n\n[1] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. \"Certified adversarial robustness via randomized smoothing.\" international conference on machine learning. PMLR, 2019.\n\n\n\n[2] Karras, Tero, et al. \"Elucidating the design space of diffusion-based generative models.\" Advances in neural information processing systems 35 (2022): 26565-26577.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work investigates the robustness of diffusion classifiers. It is shown that diffusion classifiers are inherently robust since they possess O(1) Lipschitzness and their certified robustness is also established. Furthermore, the authors achieve tighter bounds for diffusion classifiers that classify Gaussian-corrupted data (called Noised Diffusion Classifiers; NDCs), using evidence lower bounds (ELBOs) for the appropriate distributrions and Bayes' theorem. Empirical evaluation of NDCs using CIFAR-10 shows that NDCs are certifiably robust up to 80% and 70% under $\ell_2$ perturbations that have magnitude less than 0.25 and 0.5 respectively.
Decision: Accept (poster)