Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing

Summary

This work first studies Randomized Smoothing in Deep Equilibrium Models. To combat the prohibitive computational cost, this work designs a procedure called SRS to speed up certification, mainly relying on the fast convergence of multiple predictions with DEM. The certification theorem is revised accordingly to adapt to the new procedure. Experimental results prove that the new algorithm achieves stronger or comparable performance over the standard RS, with a major speedup.

Strengths

This paper first studies RS in DEM, and thus presents a solid step. I appreciate the authors' considering the speedup of the standard approach and the performance of their approach. The theoretical analysis seems correct, despite minor issues.

Weaknesses

I don't find major drawbacks in the approach and the evaluations. Below are some minor concerns: 1. In the evaluation, the authors only show the discretized certified radius curve, while the average certified radius (ACR) is the standard metric for evaluating RS. I suggest the authors to report ACR as well. 2. The authors indicate that the models are trained via Gaussian, while there are many recent advances in training RS models, e.g., SmoothAdv [1] and CATRS [2]. I advise the authors to include the performance of SRS under at least one of these more advanced training tricks, if applicable, to show the universality of their approach w.r.t. the model. 3. Line 190 says that the bounding subset is selected during the SRS sampling, this means the hypothesis test here is not independent of the SRS; thus in the proof, the multiplication of events could fail. The authors should rethink and potentially fix their proof accordingly. 4. SRS basically reduces the complexity of fixed point iteration, by making the prediction serial. However, this is not ideal for parallelization. In Fig 1.b, SRS sequentially uses the result from the last prediction as the initialization; while these factual more precise fixed points could be beneficial, to facilitate parallelization, I suspect that even initializing all others with the result of the first prediction is sufficient, as they follow the same distribution. Could the authors elaborate more on this? [1] Salman et al., Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers. [2] Jeong et al., Confidence-aware Training of Smoothed Classifiers for Certified Robustness.

Questions

See weakness. Below are some additional questions: Minor: Line 98 & 158, Cohen et al did not discuss fixed point solvers and DEQs. Is that a wrong citation? Line 454 & 455, `for $\|\delta\|<R$` is duplicated. Further, I advise the authors to explain why they specifically chose $N^E_A$ in their algorithm: the proof does not seem to motivate this choice. Regarding $p_m$, should it be the probability that the prediction is correct under SRS but not normal RS?

Rating

7

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

The authors do not seem to include a limitation section. They point to the conclusion section in the checklist, which I don't find valid.

Summary

Due to the inability of existing deterministic methods for providing certified robustness to Deep Equilibrium Models (DEQs) to be applied to large-scale datasets and network structures, this paper provides scalable certified robustness for DEQs through the probabilistic method of random smoothing. To avoid the high computational costs associated with directly using existing random smoothing methods, this paper implements Serialized Randomized Smoothing using historical information from previous inputs to reduce computational overhead. The paper also provides theoretical correctness proofs for this method. Experiments show that significant computational performance improvements can be achieved without sacrificing certified accuracy.

Strengths

Originality. Through an analysis of the computational efficiency of directly applying random smoothing methods to obtain certified robustness for DEQs, it was concluded that the Monte Carlo estimation in the random smoothing method and the fixed-point solver in DEQs are the computational efficiency bottlenecks. This paper proposes a serialized smoothing method, which improves the computational efficiency of the certified robustness method while maintaining certified accuracy. Compared to directly applying random smoothing for certified robustness, this represents a significant improvement in computational performance. Quality. The paper concisely utilizes the historical feature representation information from other noisy samples, eliminating the substantial redundant computations caused by Monte Carlo estimation in random smoothing. This enhances the practicality of the proposed certified robustness method. Furthermore, by introducing a new certified radius estimation method, they ensure the correctness of this concise algorithm. Significance. This paper effectively addresses the practicality issues caused by the computational overhead when applying the seemingly universal random smoothing method to specific deep learning models. It provides a concise processing solution tailored to the computational characteristics of specific network models. The authors also conduct a theoretical analysis of the method's correctness resulting from its application. This work offers an inspiring research approach for the research community to improve the computational efficiency of random smoothing in future studies.

Weaknesses

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.

Questions

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?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

yes

Summary

This paper provides a method for randomized smoothing for DEQs. Given the computational challenges associated with DEQs, the authors propose a method that is intended to speed up the process of creating a smooth classifier for a DEQ model based on fixed-point reuse. Given that fixed-point reuse introduces dependency between the predictions for the models f, the authors propose a method called Correlation-Eliminated Certification in which the goal is to remedy the aforementioned issue with fixed-point reuse. This method is centered on approximating the probability with which SRS misclassifies a point as the most probable class, and uses the original DEQ to achieve this. Then the authors provide a high probability certification result in Theorem 3.1.

Strengths

* The paper adapts the certified robustness method of randomized smoothing to deep equilibrium models while keeping in mind the nuances of a DEQ. In doing so, they come up with a novel and unique method for certifying a DEQ. The paper also provides careful analysis of their method, and shows that their method is both efficient and admits high certified accuracy. * The authors provide a thorough ablations section which answers questions regarding the goodness of their approximation for $p_m$. * The authors provide a theoretical guarantee for the correctness of their method, and provide extensive experimental results.

Weaknesses

* It would be nice to provide more careful definitions. One definition that should be in the paper is that of $\ell_2$-norm certified radius, as is defined for example in [1]. A pointer to a paper which introduces this is also missing. Generally speaking, although [1] also uses similar notation to this paper, it is a bit confusing to write $c_A$ without writing it as a function of $x$. My understanding is that $c_A$ is the most likely class given some sample $x$, so as a reader this is a bit confusing to not write it as a function of $x$. Another definition which seems to be crucial in your paper is LowerConfBound (e.g. Equation (12)) and hence it would be nice to provide the definition rather than to point the reader to [1]. Furthermore, there are less crucial definitions such as $K$, in Equation (10), which are not defined (but I assume represents the number of samples from SRS, $K < N$). Furthermore, can you please make the notation consistent between Section 3.3 and Appendix A which contains the proof for Theorem 3.1? Specifically there is lower-case $y$ in Appendix A and the subscript notation for the labels is also different between the two sections. * 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. [1] Cohen, J., Rosenfeld, E., and Kolter, Z. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pp. 1310–1320. PMLR, 2019 Some notes: * Lines 49-54 introduce acronyms that are not defined * Neyman-Pearson is spelled incorrectly on line 108 * Figure 5 caption: converted -> converts. The sentence starting with “For instance” does not read well. Overall, could you write your caption a bit more clearly? * Line 574: missing period * Algorithm 1: line 13 Should say Predict Y_g? It seems as though some indexing is also missing. Also, it is not clear to me what the relationship between the total number of samples is as the number of samples that is used for $p_m$ in Algorithm 1.

Questions

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? 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?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Summary

This paper develops the first randomized smoothing certified defense for DEQs, termed as Serialized Random Smoothing (SRS). To address the scalability issue of randomized smoothing, To reduce computational redundancy, SRS leverages historical information and a new certified radius estimation. The proposed method can cover various DEQ structures, significantly expanding the scope of existing work. Extensive experiments and ablation studies on large-scale tasks such as ImageNet have been presented to demonstrate the proposed method. Overall, this paper presents a significant contribution to the field of certified robustness for DEQs. The SRS method offers a promising approach to make certification more practical for these models, especially on larger datasets.

Strengths

1. This paper addresses an important gap in the literature by obtaining non-trivial certified robustness of DEQs across various datasets and network structures. 2. Both the empirical and theoretical developments are solid. The proposed method significantly reduces computation time, making certification feasible for larger models and datasets. The authors have included extensive evaluations on different datasets, model sizes, and hyperparameters. 3. The paper is well written and easy to follow.

Weaknesses

1. The conceptual novelty may not be that significant since randomized smoothing is a well-known technique in the first place. 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?

Questions

1. Can the authors clarify the difficulty and novelty of implementing their method for large-scale datasets like ImageNet? 2. Does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS? 3. Can the authors further justify the unique novelty and technicality of their contribution?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

The authors have partially addressed limitations in their paper. However, there seems to lack a substantial discussion on broader societal impacts.

Summary

This paper introduces a novel method based on random smoothing to improve the certified robustness of Deep Equilibrium Models (DEQs), a promising type of implicit neural network. Directly applying random smoothing to DEQs incurs high computational costs. To overcome this issue, the authors leverage the properties of DEQs and design a serialized random smoothing (SRS) strategy. This method uses the output from one noisy input as the starting point for the next, significantly accelerating convergence. Subsequently, to eliminate the dependence between noisy samples created by SRS, the authors introduce Correlation-Eliminated Certification, a new method to obtain certified radius estimation. Experimental results on CIFAR-10 and ImageNet demonstrate the efficiency of the proposed model.

Strengths

- The paper is well-written, making it easy to follow the key techniques. The experiments and ablation studies are informative. - The proposed method presents an inspiring use of the representational properties of DEQs. Specifically, DEQs characterize their output as the fixed point of a function (conditioned on their input). Therefore, when running inference on a group of similar samples, DEQs are essentially solving a group of similar fixed-point equations; their inference can be accelerated by reusing the fixed-point between samples. - The designed certified radius estimation algorithm, Correlation-Eliminated Certification, is straightforward but effective. With a two-stage hypothesis test, this method eliminates the dependency (a side effect of SMS).

Weaknesses

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.

Questions

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

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

na

Thanks for the response

Thanks for addressing my comments. I have raised my score to 7.