Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing

Dear reviewer, thank you so much for your valuable comments and recognition of the novelty, effectiveness, and presentation of our work. We are happy to address your concerns and questions with the following results and illustrations.

Weakness 1: In the evaluation, the authors only show the discretized certified radius curve...

Answer: Thank you for your suggestion. We produce the results with the ACR metric for CIFAR-10 following the definition in [1]. Here we report them in Table 1. We will add them to the main paper in a revised version.

Table 1: Average certified radius for the MDEQ architecture with $\sigma=0.5$ on CIFAR-10.

[1] Chen, Ruoxin, et al. "Input-specific robustness certification for randomized smoothing." AAAI 2022.

Weakness 2: The authors indicate that the models are trained via Gaussian, while there are many recent advances...

Answer: Thank you for your suggestion. Here we produce the results with SmoothAdv to show the effectiveness of our method, and we will add them to the main paper in a revised version. For SmoothAdv, we choose PGD [1] as the adversarial attack and the number of adversarial examples in the training is set as 4. The results are shown in Table 2. With SmoothAdv, the certified accuracy will increase for both the standard randomized smoothing and our SRS.

Table 2: Certified accuracy for the MDEQ-SMALL architecture with $\sigma=0.5$ on CIFAR-10 using SmoothAdv.

[1] Kurakin, Alexey, Ian Goodfellow, and Samy Bengio. "Adversarial machine learning at scale." arXiv:1611.01236 (2016).

Weakness 3: Line 190 says that the bounding subset is selected during the SRS sampling, this means ...

Answer: Thanks for pointing out our problem. Because the two hypothesis tests are both based on noisy samples, they could be dependent. In this case, we slightly revise our proof as follows: denote the event that the radius of SRS is smaller than the radius of RS as $A$ and the event that the radius of RS can certify the data points $B$. We can conclude that $\mathbb{P}(\bar{A})=\mathbb{P}(\bar{B})=\tilde{\alpha}$ following the hypothesis tests. The final probability of successfully certifying the data point is:

$$\mathbb{P}(A\cup B) = \mathbb{P}(B)-\mathbb{P}(\bar{A}\cup B) = 1-\mathbb{P}(\bar{B})-\mathbb{P}(\bar{A}\cup B) \geq 1-\mathbb{P}(\bar{B})-\mathbb{P}(\bar{A}) = 1-2\tilde{\alpha}$$

where $\mathbb{P}(\bar{A})$ is the probability that $A$ does not happen. By setting $\tilde{\alpha}=\alpha/2$, we complete the proof. By carefully reevaluating the differences between the previous $\tilde{\alpha}=1-\sqrt{1-\alpha}$ and the current one in our proof, the reported accuracy does not change because $\alpha$ is very small (e.g., $\alpha=0.01$). We will revise our proof and the corresponding algorithm in a new version of our paper.

Weakness 4: SRS basically reduces the complexity of fixed point iteration, by making the prediction serial...

Answer: Because of the page limitation, the corresponding analysis is in Appendix K (start points). For convenience, we briefly restate our conclusion of the analysis. The results with the last fixed points are better than those with the first prediction when the number of the fixed-point iterations is small as shown in Table 2. With the previous fixed point, our certification process accumulates randomness to avoid the bad guess at the beginning so we get better results. We will discuss the question more in the revised version.

Table 3: Certified accuracy for the MDEQ-LARGE architecture with $\sigma=0.5$ on CIFAR-10. The first two rows represent the results starting from clean data.

Minor Question: Line 98 & 158, Cohen et al did not discuss fixed point solvers and DEQs. Is that a wrong citation?...

Answer: Thanks for pointing out the wrong citation, we are supposed to cite the paper about the solver [1]. Besides, we will remove the duplicated words in the text.

As you understand, $p_m$ is the probability that the prediction is correct under SRS but not normal RS. Therefore $N_E^A$ is the number of effective predictions in SRS, which is a conservative estimation of randomized smoothing. We will correct all of those mistakes and clarify the notations in a revised version of our paper.

[1] Bai, Shaojie, Vladlen Koltun, and J. Zico Kolter. "Neural deep equilibrium solvers." ICLR 2021.

Updating Limitations: Thanks for pointing out the lack of limitations. We will add the following text in a revised version: ''Though our paper speeds up the certification of DEQs with randomized smoothing, it cannot be directly applied to other architecture. We regard the speedup for the general method as our future research.''

Dear reviewer, thank you so much for your valuable comments and recognition of the novelty, effectiveness, and presentation of our work. We are happy to address your concerns and questions.

Weakness 1: In the process of correlation-eliminated certification, this paper requires the use of standard DEQs to drop unreliable predictions, which necessitates additional memory overhead for standard DEQs during actual deployment.

Answer: We think there are some slight misunderstandings of the DEQs. The memory cost of the standard DEQs is independent of the number of the fixed-point iterations. Our experiments show that both of them use about 1.5 GB of memory with a batch size of 400. The standard DEQs have the same memory overhead as our method because we only change the number of fixed-point iterations but keep the same solvers. Therefore, we only need more time to run the standard randomized smoothing. Thanks for your question and we will clarify it clearly in the revision of our paper.

Question 1: In this paper, the authors have been exploring the introduction of a new serialized random smoothing certification method for robustness to avoid the expensive computational costs of previous methods while ensuring that certified accuracy is not affected. I would like to know if the serialized smoothing certification method for robustness has any impact on the clear accuracy metric for DEQs compared to the previous traditional random smoothing certification methods, and if so, how significant is this impact?

Answer: We assume you are referring to the ''clean'' accuracy of our proposed method instead of the ''clear'' accuracy. In Table 1-3 of the main paper, we show the certified accuracy under different radii. The clean accuracy is a special case where the radius is 0. In this case, we do not require the smoothed classifier to be robust but to have the correct predictions. For convenience, we copy part of the results to show it. Our method will sacrifice little clean accuracy (only 1%) compared to the standard randomized smoothing as shown in Table 1.

Hope our answer can address your question, and we are glad to reply if you need more description.

Table 1: Clean accuracy for the MDEQ-LARGE on CIFAR-10.

Dear reviewer, thank you so much for your valuable comments and recognition of the novelty, effectiveness, and presentation of our work. We are happy to address your concerns and questions.

Question 1: What is the effect of using a model trained with Jacobian regularization on your method? Do you think this is crucial for certifying a DEQ?

Answer: Jacobian regularization stabilizes the training of the backbones but it is not crucial for the certification. To answer your question, we conduct the experiments without the Jacobian regularization as shown in Table 1. The results show that using Jacobian regularization can help stabilize the fixed-point solvers but will almost not affect the final performance with enough fixed-point iterations. Generally speaking, the more stable the model is, the more efficient our approach is (i.e., we can use fewer steps of iterations). Our conclusion is consistent with [1] where the regularization does not increase the accuracy but decreases the number of fixed-point iterations.

The experiments show that using Jacobian regularization is not crucial in the certification. However, we recommend to use the regularization in the training for more stable performance. We hope this answer addresses your question, and we are happy to provide further details if needed.

Table 1: Ablation study of Jacobian regularization for the MDEQ-SMALL architecture with $\sigma=0.5$ on CIFAR-10.

[1] Bai, Shaojie, Vladlen Koltun, and Zico Kolter. "Stabilizing Equilibrium Models by Jacobian Regularization." International Conference on Machine Learning. PMLR, 2021.

Question 2: What is the relationship between the number of samples that are checked with the DEQ in Line 13 of Algorithm 1, and the total number of samples obtained via SRS?

Answer: Thank you for pointing out our unclear expressions and overlooking the equation changes with the notations in Algorithm 1. Generally speaking, Line 13 of Algorithm 1 returns the standard DEQs predictions, which are used to compare with the SRS predictions. The comparison tells us what $p_m$ should be. After dropping the unreliable predictions with $p_m$, we will use the total number of samples $N$ to predict the certified radius.

To be specific, Line 14 should be expanded into two steps. First, we use equation (12) to compute the estimated $\overline{p_m}$, namely:

$$N_1 = \sum\nolimits_{i=1}^{K}\mathbf{1} \\{Y_m = Y_g \text{ and } Y_g = c_A(x) \\} ,$$ $$N_2 = \sum\nolimits_{i=1}^{K}\mathbf{1}\\{Y_m = c_A(x)\\},$$ $$\overline{p_m} = 1-\text{LowerConfBound}(N_1, N_2, 1-\tilde{\alpha}),$$

Then we use equation (9) to estimate the effective samples that are predicted as class $c_A (x)$ with our estimated $\overline{p_m}$:

$$N_A^E = N_A - \overline{p_m} N_A,$$

Finally, with the total number of samples $N$, we compute the radius with equations (13) and (14):

$$\underline{p_A} = \text{LowerConfBound}(N_A^E, N, 1-\tilde{\alpha})$$ $$R = \sigma\Phi^{-1}(\underline{p_A}),$$

We hope this answer addresses your question, and we are happy to provide further details if needed.

Weakness 1: Revising the typos and unclear expressions

Answer: Thanks for pointing out the inconsistency of the notations and the unclear expressions and we are glad to correct them in a revised version. First, we will add the definition of $\ell_2$ norm and claim $c_A$ as the function of $\mathbf{x}$, namely $c_A (\mathbf{x})$. Secondly, we will correct the typos and the inconsistency notation in the proof. Thirdly, we will add the definition of acronyms for Interval Bound Propagation (IBP) and Lipschitz Bounded Equilibrium Networks (LBEN). Besides, we will revise the caption of Fig.5 as: ``For instance, the predictions of $\mathbf{x}+\epsilon_2$ are different with RS and SRS. Therefore, the prediction of $\mathbf{x}+\epsilon_2$ will not be counted as the most probable class $\hat{c}_A(\mathbf{x})$.''

For the definition of $K$, it is a hyperparameter that we add descriptions but forget to mark it. To be specific, we are supposed to define it from line 189 to line 191: ``During the Monte Carlo sampling of SRS, we randomly select $K$ of samples (a small number compared to $N$) along with their corresponding predictions''.

Finally, we will add the definition of LowerConfBound as follows: LowerConfBound$(k, n, 1-\alpha)$ returns a one-sided $(1-\alpha)$ lower confidence interval for the Binomial parameter $p$ given that $k\sim\text{Binomial}(n, p)$. In other words, it returns some number $\underline{p}$ for which $\underline{p} \leq p$ with probability at least $1-\alpha$ over the sampling of $k\sim\text{Binomial}(n, p)$.

Weakness 2: Using a model with Jacobian regularization seems as though it might be more suitable for a certification method. It would be nice to provide more justification as regards to this choice, and how the method would perform on a MDEQ trained without Jacobian regularization.}

Answer: To solve your concern, we refer you to the results we provided in Question 1.

Dear reviewer, thank you so much for your valuable comments and recognition of the topic, effectiveness, and presentation of our work. We are happy to address your concerns and questions with the following results and illustrations.

Question 1: Can the authors clarify the difficulty and novelty of implementing their method for large-scale datasets like ImageNet?

*Answer: For large-scale datasets like ImageNet, the standard randomized smoothing can be too expensive to apply on DEQs because (1) DEQs can be slow on such a high-resolution dataset and (2) need a second-order fixed-point solver to guarantee convergence. With other methods, such as IBP and LBEN, it is hard to compute a non-trivial certified radius because the certification is deterministic [1]. In contrast, our method accelerates the standard randomized smoothing by reusing the historical fixed points and guarantees the theoretical correctness of the certification by the two-stage hypothesis testing.

We hope this answer addresses your question, and we are happy to provide further details if needed.

[1] Li, Linyi, Tao Xie, and Bo Li. "Sok: Certified robustness for deep neural networks." 2023 IEEE symposium on security and privacy (SP). IEEE, 2023.

Question 2: Does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS?

Answer: Thanks for your question. To address your concern, we are glad to provide a comparison between the explicit models and DEQs. Despite surpassing the performance of explicit neural networks is not our target, we claim the performance over DEQs can catch up with them, as shown in Table 1. We provide a comparison between DEQs and ResNet-110 under the same training and evaluation setting, and the results are consistent with those reported in [1]. We will add the results to the main paper in a revised version.

Table 1: Certified accuracy for the MDEQ-LARGE architecture with $\sigma=0.5$ on CIFAR-10. The best certified accuracy for each radius is in bold.

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

Question 3: Can the authors further justify the unique novelty and technicality of their contribution?

Answer: The major contribution of this paper is to explore randomized smoothing certification for implicit models for the first time. Specifically, we discover that existing randomized smoothing techniques are not suitable for certifying implicit models such as DEQs because of the dominating computation cost. Therefore, we propose serialized randomized smoothing that leverages the historical fixed points to effectively reduce the computation redundancy and accelerate randomized smoothing significantly. However, the serialized operation brings correlations between the predictions, breaking the correctness of the existing theorem of randomized smoothing. To solve the challenge, we then propose a two-stage certification technique (hypothesis testing) to provide correct certification. The new theorem and empirical studies verify that our algorithm works as expected.

Weakness 1: The conceptual novelty may not be that significant since randomized smoothing is a well-known technique in the first place.

Answer: Though randomized smoothing is a well-known technique, it cannot be easily applied to DEQs for computation reasons as we illustrate in Question 1. Therefore, we propose our novel serialized randomized smoothing which is much more efficient and with a new theorem as illustrated in Question 3. In this way, our method demonstrates novelty. We hope this answer addresses your question, and we are happy to provide further details if needed.

Weakness 2: By the end of the paper, it is unclear whether the results in this paper have achieved SOTA certified robustness among all networks. I mean, does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS?

Answer: To answer your concern, we refer to the comparison provided in Question 2.

Updating Limitations: Thanks for pointing out the lack of a substantial discussion on societal impacts. We will add the following discussion in the revised version: ''Our work significantly improves the security of artificial intelligence, especially applicable in sensitive domains. Our proposed SRS can provide significant acceleration of defending the attacks for AI models, enhancing the appliance of the models and maintaining the integrity of AI-driven decisions.''

Dear reviewer, thank you so much for your valuable comments and recognition of the novelty, effectiveness, and presentation of our work. We are happy to address your concerns and questions with the following results and illustrations.

Question 1: On line 52, "Due to the conservative certification, IBP and LBEN cannot be generalized to large-scale datasets (e.g., ImageNet)." There seems to be a logical gap in this sentence. Could the authors elaborate more on this point? Is there any reference that can back up this claim?

Answer: Thanks for your question. The sentence here tries to convey that the deterministic methods will generate a trivial certified radius (namely, close to 0) because their estimation is not tight enough in some cases such as deep networks [1]. When it comes to large-scale datasets, we refer to high-resolution and many-class cases, such as ImageNet. It increases the difficulty of the task and usually requires more complex models, deteriorating the trivial certified radius problem. In Section E of [2] (the first paragraph and the practical implications part), the authors make similar claims. We will describe the logic and cite the above reference to support our claim in a revised version.

[1] Zhang, Bohang, et al. "Towards certifying l-infinity robustness using neural networks with l-inf-dist neurons." International Conference on Machine Learning. PMLR, 2021.

[2] Li, Linyi, Tao Xie, and Bo Li. "Sok: Certified robustness for deep neural networks." 2023 IEEE symposium on security and privacy (SP). IEEE, 2023.

Question 2: Is the certified robustness of the proposed model (SRS-DEQ) competitive against the certified robustness of other non-DEQ architectures with random smoothing? For example, the paper "CERTIFIED ROBUSTNESS FOR DEEP EQUILIBRIUM MODELS VIA INTERVAL BOUND PROPAGATION" compares their models with other explicit neural networks. Such comparisons are important for the audience to position the proposed model in a larger context.

Answer: We appreciate that you recognize the value of DEQs, which present advantages compared to explicit neural networks in some cases, such as memory efficiency in the training and accuracy-speed trade-off during inference [1]. According to your suggestion, we are glad to provide a comparison between the explicit models and DEQs. Despite surpassing the performance of explicit neural networks is not our target, we claim the performance of DEQs can catch up with them, as shown in Table 1. We provide the comparison between DEQs and ResNet-110 under the same training and evaluation setting, and the results are consistent with those reported in [2]. We will add the results to the main paper in a revised version.

Table 1: Certified accuracy for the MDEQ-LARGE architecture with $\sigma=0.5$ on CIFAR-10. The best certified accuracy for each radius is in bold.

[1] Bai, Shaojie, J. Zico Kolter, and Vladlen Koltun. "Deep equilibrium models." Advances in neural information processing systems 32 (2019).

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

Question 3: Are there any insights or techniques from this paper that can be applied to improve other performance aspects of DEQs (besides certified robustness) or improve non-DEQ models?

Answer: Yes. The insights and techniques to exploit computation redundancy can be applied to improve other performance aspects. For instance, the uncertainty estimation with Bayesian inference requires multiple samples of the model parameters, resulting in inference with similar model parameters (instead of similar data input in this paper). When applying the Bayesian neural networks to DEQs, our techniques can improve the efficiency of the uncertainty estimation. However, we must admit that our current fixed-point reusing technique may be not directly applied to non-DEQ models, and new techniques to exploit computation redundancy will need to be developed. This is one of our future work.

Weakness 1: The proposed method is only applicable to DEQs. Although DEQs are a promising architecture, they have not been as widely applied as explicit neural networks or proven to scale well, limiting the scope of this paper. Moreover, the paper does not include a performance comparison of the proposed against other non-DEQ models.

Answer: We appreciate that you recognize the value of DEQs again. The corresponding results are provided in the reply to Question 2.