Diffusion Models are Certifiably Robust Classifiers

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.

Weakness 1: Table 4 should be put in the main text.

Thank you for your advice. We will move Table 4 into the main text.

Weakness 2: Certified radii of diffusion classifiers should be included in the main table.

Thank you for your advice. We will incorporate these results into Table 1.

Weakness 3: Ablation studies in $\sigma_\tau$.

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

Question 1: $h_\theta(x_t,t)$ are bounded.

Yes, we clip the output of the UNet $h_\theta(x_t,t)$ to $[0,1]$, thus it is bounded.

$\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.

Question 2: About $q$ distribution.

Thank you for your suggestion. We will add subscripts to each of the nested expectations to clarify the expression:

$

\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,
$

in the revision.

We 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}$.

Question 3: About Eq. (12).

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

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

Question 4: In the case of $\tau=0$.

When $\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.

Question 5: Similarity between APNDC and consistency models.

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

Question 6: About $\sigma_\tau$.

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

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

[1] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. "Certified adversarial robustness via randomized smoothing." international conference on machine learning. PMLR, 2019.

[2] Karras, Tero, et al. "Elucidating the design space of diffusion-based generative models." Advances in neural information processing systems 35 (2022): 26565-26577.

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.

Weakness 1: References could be ordered by appearance.

Thank you for your suggestion. We will revise the references to be ordered by appearance in the final version.

Weakness 2: Appendix D can be incorporated into the main text.

Thank you for your advice. We will incorporate the Limitation section into the end of the main text in the final version.

Weakness 3 and Q1: A table for comparing time complexity.

Thank you for your valuable suggestion. We strongly agree that a table presenting the comparison of time complexity is necessary. The result is shown below:

CIFAR10:

ImageNet:

As shown:

• When using sift-and-refine, the NFEs for each image depend on the specific image. Thus, the time complexity is undetermined.
• During certification, different samples are computed in parallel, so the time complexity is much lower than Inference Real Time * N.
• The value of N for the Diffusion Classifier is ten times smaller than for other models.
• 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$.

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.

Weakness 1: Insufficient Novelty.

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

Second, the analysis of diffusion classifiers is highly nontrivial, with several key technical contributions that are also new:

1. Theoretical Foundation for Diffusion Classifiers: 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.

2. Generalization to Noisy Data and Remarkable Certified Robustness Record:

   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.

3. Reduction in Time Complexity: 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.

Overall, 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.

Weakness 2: Experiments on ImageNet-256x256.

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

Existing 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].

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

Weakness 3: Comparison of inference latency.

Thank you for the valuable suggestion. We provide further results on time complexity:

CIFAR10:

ImageNet:

As shown:

• When using sift-and-refine, the NFEs for each image depend on the specific image. Thus, the time complexity is undetermined.
• During certification, different samples are computed in parallel, so the time complexity is much lower than Inference Real Time * N.
• The value of N for the Diffusion Classifier is ten times smaller than for other models.
• 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$.

Reference:

[1] Matryoshka diffusion models. ICLR, 2023.

[2] High-resolution image synthesis with latent diffusion models. CVPR, 2022.

[3] Elucidating the design space of diffusion-based generative models. NeurIPS, 2022.

[4] Pixel is a Barrier: Diffusion Models Are More Adversarially Robust Than We Think. arXiv, 2024.

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.

Weakness 1: Nabla operator is unclear.

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

Weakness 2: Lines 161-164 is unclear.

Thank you for your suggestion. We will modify this section in the final version to:

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}$.

Weakness 3: Still not comparable with discriminative classifiers on ImageNet.

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

Question 1: APNDC has one more NFE than EPNDC.

Thank 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."