Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing
Authors: Weizhi Gao
Zhichao Hou
Han Xu
Xiaorui Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: trustworthy machine learning; certified robustness; randomized smoothing
Primary area: safety_in_machine_learning

Abstract: Implicit models such as Deep Equilibrium Models (DEQs) have emerged as promising alternative approaches for building deep neural networks. Their certified robustness has gained increasing research attention due to security concerns. Existing certified defenses for DEQs employing interval bound propagation and Lipschitz-bounds not only offer conservative certification bounds but also are restricted to specific forms of DEQs. In this paper, we provide the first randomized smoothing certified defense for DEQs to solve these limitations. Our study reveals that simply applying randomized smoothing to certify DEQs provides certified robustness generalized to large-scale datasets but incurs extremely expensive computation costs. To reduce computational redundancy, we propose a novel Serialized Randomized Smoothing (SRS) approach that leverages historical information. Additionally, we derive a new certified radius estimation for SRS to theoretically ensure the correctness of our algorithm. Extensive experiments and ablation studies on image recognition demonstrate that our algorithm can significantly accelerate the certification of DEQs by up to 7x almost without sacrificing the certified accuracy. The implementation will be publicly available upon the acceptance of this work. Our code is available at https://github.com/WeizhiGao/Serialized-Randomized-Smoothing.

Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing
Weizhi Gao' ugao23@ncsu. edu
Zhichao Hou' zhou4@ncsu, edu
Han Xu² xuhan20ar izona, edu
Xiaorui Liu!" xl xliu96@ncsu, edu
North Carolina State University, The University of Arizona
*corresponding author
Abstract
Implicit models such Deep Equilibrium Models (DEQs) have emerged promis- ing alternative approaches for building deep neural networks. Their certified robust- ness has gained increasing research attention due to security concerns. Existing certified defenses for DEQs employing deterministic certification methods such interval bound propagation and Lipschitz- bounds datasets. Besides, they are also restricted to specific forms of DEQs. In this paper, we provide the first randomized smoothing certified defense for DEQs to solve these limitations. Our study reveals that simply applying randomized smoothing certify DEQs provides certified robustness generalized large-scale datasets but incurs extremely expensive computation costs. To reduce computational re- dundancy, we propose a novel Serialized Randomized Smoothing (SRS) approach that leverages historical information. Additionally, we derive a new certified ra- dius estimation for SRS theoretically ensure the correctness of our algorithm. Extensive experiments and ablation studies on image recognition demonstrate that our algorithm can significantly accelerate the certification of DEQs by up to 7x almost without sacrificing the certified accuracy. Our code is available at https://github.com/ http://wwweeeeiiaaaaaeeeeeaaaaaa httpa////SSSraiiieeeaaaannmiieee Smoothing
not certify large-scale
Introduction
The recent development of implicit layers provides alternative and promising perspective for neural network design (Amos & Kolter 2017] Chen et al., 2018 Agrawal et al. 2019 Bai et al.) 2019 2020 El Ghaoui al. 2021). Different from traditional deep neural networks (DNNs) that build standard explicit deep learning layers, implicit layers define the output as the solution to certain closed-fome form functions of the input. These implicit layers represent infinitely deep neural networks using only one single layer that is defined implicitly. The unique definition endows implicit models with the capability model continuous physical systems, task that traditional DNNs cannot accomplish (Chen et al., 2018). Additionally, the implicit function theorem enhances memory efficiency by eliminating the need store intermediate states during forward propagation (Chen et al.) 2018 [Bai et al. 2019). Furthermore, implicit models offer valuable accuracy-efficiengy trade-off, making them adaptable varying application requirements (Chen al. 2018). These advantages underscore the significant research value of implicit models.
Deep equilibrium models (DEQs) output as the solution to input-dependent fixed-point problems (Bai et al., 2019). With a fixed-point solver, DEQs be seen infinite-eppth and weight-tied neural networks. The modern DEQ-based architectures have shown comparable or even surpassing performance compared with traditional
promising class of implicit models that construct the
explicit models (Bai al., 2019 2020 Gu et al. 2020 Chen et al. 2022). Due the superior
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

performance of DEQs, their adversarial robustness has gained increasing research interest. Recent research has revealed that DEQs also suffer from similar vulnerabilities as traditional DNNs, which raises security concerns (Gurumurthy et al., 2021 Yang et al. 2022). Multiple works propose empirical defenses to improve the adversarial robustness of DEQs using regularization methods (Chul et al. 2023; El Ghaoui et al. 2021) and adversarial training (Yang et al., 2023 Gurumurthy et al. 2021 Yang et al. 2022). These empirical defenses measure models' adversarial robustness by the robust performance against adversarial attacks. However, they do not provide rigorous security guarantees and often suffer from the risk of a false sense of security (Athalye et al. 2018), leading to tremendous challenges for reliable robustness evaluation.
As alternatives to empirical defenses. certified defenses aim to provide theoretical robustness guaran- tees. It is worth noting that certified defenses certify that no adversarial example can ever exist within a neighhorhood of the test sample regardless of the attacks, providing reliable robustness measure- ments and avoiding the false sense of security caused by weak attacking algorithms. Recent works have explored interval bound propagation (IBP) (Wei & Kolter 2021 Li et al. 2022) and Lipschitz bounding (LBEN) (Havens et al. 2023 Jafarpour et al. 2021) for certifiable DEQs. However, IBP usually estimates a loose certified radius due to the error accumulation in deep networks (Zhang et al. 2021 | and the global Lipschitz constant tends to provide a conservative certified radius (Huang et al. 2021). Due to the conservative certification, IBP and LBEN generate trivial certified radii (namely, close to 0) in some cases such as deep networks, especially in large-scale datasets (e.g..
ImageNet) (Zhang et al. [021] Li et al. (023). Moreover, the design of IBP and LBEN relies on specific forms of DEQs and can not be customized to various model architectures, restricting the application of these methods.
Given the inherent limitations of existing works, the objective of this paper is to explore the certified robustness of DEQs via randomized smoothing for the first time. Randomized smoothing approaches construct smoothed classifiers from arbitrary base classifiers and provide certified robustness via statistical arguments (Cohen et al., 2019) based on the Monte Carlo probability estimation. Therefore, compared with IBP and LBEN methods, randomized smoothing has better flexibility in certifying the robustness of various DEQs of different architectures. More importantly, the probabilistic certification radius provided by randomized smoothing can be larger and generalized to large-scale datasets.
Our study reveals that applying randomized smoothing to certify DEQs can indeed provide better certified accuracy but it incurs significant computation costs due to the expensive fixed point solvers in DEQs and Monte Carlo estimation in randomized smoothing. For instance, certifying the robustness of one 256 256 image in ImageNet dataset with typical DEQ takes up to 88.33 seconds. This raises significant efficiency challenges for the application of certifiable DEQs in real-world appli- cations. In this paper, we further delve into the computational efficiency of randomized smoothing certification of DEQS. Our analysis reveals the computation redundancy therein, and we propose an effective approach, named Serialized Random Smoothing (SRS). Importantly, the certified radius and theoretical guarantees of vanilla randomized smoothing can not be applied in SRS. Therefore, we develop a new certified radius with theoretical guarantees for the proposed SRS. Our method tremendously accelerates the certification of DEQs by leveraging their unique property and reducing the computation redundancy of randomized smoothing. The considerable acceleration of SRS-DEQ allows us to certify DEQs on large-scale datasets such as ImageNet, which not possible in previous works. In a nutshell, our contributions are as follows:
We provide the first exploration of randomized smoothing for certifiable DEQs. Our study reveals significant computation challenges in such certification, and we provide insightful computation redundancy analyses.
We propose a novel Serialized Randomized Smoothing approach to significantly acceler- ate the randomized smoothing certification for DEQs and corresponding certified radius estimation with new theoretical guarantees.
We conduct extensive experiments on CIFAR-10 and ImageNet to show the effectiveness of our SRS-DEQ. Our experiments indicate that SRS-DEQ can speed up the certification of DEQS up to 7x almost without sacrificing the certified accuracy.
2 Background
In this section, we provide necessary technical background for DEQs and Randomized Smoothing.
2

---

2.1 Deep Equilibrium Models
Traditional feedforward neural networks usually construct forward feature transformations using fixed-size computation graphs and explicit functions z/+1 So, (2'). where z' and I are the input and output of layer fe, (-) with parameter 0t. DEQs, as an emerging class of implicit neural networks, define their output as the fixed point solutions of nonlinear equations:
Implicit formulation.
fo x),
where z" is the output representation of implicit neural networks and x is the input data. Therefore, the computation of DEQs for each input data point x requires solving fixed-point problem to obtain the representation z².
Fixed-point solvers. Multiple fixed-point solvers have been adopted for DEQs, including the naive solver, Anderson solver, and Broyden solver (Geng & Kolter 2023). The naive solver directly repeats the fixed-point iteration until it converges:
z = s(2',x)
More details about these solvers can be referred to in the work (Cohen al. 2019). In this paper, we denote all solvers as follows:
= Solver(J, x, 22.)
(3)
where z" is the initial feature state that is taken as 0 in DEQs. All the solvers end the iteration if the estimation error f(z) of the fixed point reaches given tolerance error or a maximum iteration threshold L.
2.2 Randomized Smoothing
Randomized smoothing (Cohen et al. 2019) is certified defense technique that guarantees & 22-norm certified robustness. Given arbitrary base classifier f()), we construct a smoothed classifier g(-):
g(x) arg max 1aaxxPffF (Pf + +) = c),
(4)
cEY
E~N(0,0'1))
(5)
where y is the label space, and 2 is the variance of Gaussian distribution. Intuitively, the smoothed classifier outputs the most probable class over a Gaussian distribution. If we denote PA and pg as the probabilities of the most probable class CA (z) and second probable class eg (z). Neyman- Pearson theorem (Neyman & Pearson 1933) provides fz-norm certified radius R for the smoothed classifier g:
g(x + 8) (x) for all ||01|2 R,
(6)
where R = - + (PA) - -- (pB)).
(7)
Here (xx) is the inverse of the standard Gaussian cumulative distribution function, and PA PB E [0, 1] satisfy:
-)) 2 PA PB
max +c) c
In practice, PA and pø are estimated using the Monte Carlo method. It is crucial to maintain the independence of each prediction in the simulation ensure the correctness of randomized smoothing.
Serialized Randomized Smoothing
In this section, we begin by revealing the computation challenges associated with certifying DEQs using Randomized Smoothing. Subsequently, we propose Serialized Random Smoothing (SRS), a novel approach to remarkedly enhance the efficiency of DEQ certification. However, directly applying the estimated radius of the standard randomized smoothing to SRS breaks the theoretical guarantee of certified robustness. To address this challenge, we develop the correlation-eliminal certification technique to estimate the radius in SRS.
3

---

x
c-1(0,
XA K6
X4
(a) Standard Randomized Smoothing
(b) Serialized Randomized Smoothing
Figure I: Illustrations of the standard DEQ and our SRS-DEQ. The representation for each sample goes through layers in standard DEQ. Our SRS-DEQ uses the previous representation as the initialization and converges to the fixed point with few layers (S < D). After get all the predictions, SRS-DEQ makes use of correlation-eliminnt certification to estimate the certified radius.
3.1 Computation Challenges
According Eq. 7 need to estimate the lower bound probability PA and upper bound probability Рg. The appliance of Monte Carlo sampling rescues as follows:
N Σ N
- +c((x+c)=c)
(8)
where 1 is the indicator function, and & WO0, o'I) is the i-th random perturbation sampled from Gaussian distribution. However, it introduces computation challenges due to the large sampling number N. Our empirical study (Section 4.2 indicates that applying randomized smoothing to certify
MDEQ (Bai et al. 2020) on one 32 x 32 image in CIFAR-10 takes 12.89 seconds, and 88.33 seconds for one 256 x 256 image in ImageNet. The computation challenges raise tremendous limitations in real-world applications.
We provide an analysis for the slow randomized smoothing certification of DEQs. First, each forward iteration of DEQs can be very expensive. This is because DEQs are typically weight-tied neural networks so one layer f (z, x) of DEQs needs be complex maintain the expressiveness. Second, the fixed-poine solver needs many iterations for convergence. To maintain the best performance, the solvers usually set small value for the error tolerance (e.g., 0.001). A Although second-order solvers like Broyden's 'ss method have faster convergence, their computation cost per iteration is higher. Third, the Monte Carlo estimation randomized smoothing further exacerbates the expensive inference of DEQs, leading to significant computation challenges, as shown in Figure Ta
3.2 Serialized Randomized Smoothing
As introduced in Section 3.1 the Monte Carlo method is employed in randomized smoothing estimate the prediction probability, typically necessitating over 10, 000 times inference computation data point. Despite the independent sampling of Gaussian noises, these noises {<x) are added to the same certified data point x to form noisy data samples (x + e.)- Notably, these samples are numerically and visually similar each other as can be seen in Figure I Moreover, in randomized smoothing, the base classifier is trained on Gaussian-augmennter data to be resistant noises added to data points, yielding robust features and base classifiers. Therefore, the feature representation of these noisy samples computed in the forward computation of DEQs shares significant similarities, resulting in substantial computation redundancy in the fixed-point solvers. The computation redundancy contributes to the inefficient DEQ certification with randomized smoothing as a primary factor. Consider a DEQ with layers as an illustrative example. the Monte Carlo estimation with N = 10, 000, it requires the forward computation of 50 x 10, 000 500, 000 layers. However, if we can estimate the intermediate representation at the 45th layer, the required forward iterations reduce to 5 10, 000 50, 000 layers, bringing x0x acceleration.
for certifying

---

Motivated by the above challenges and analyses, we propose novel solution, Serialized Randomized Smoothing (SRS), to effectively reduce the computation redundancy in the certification of DEQs. The key idea of Serialized Randomized Smoothing is to accelerate the convergence of fixed-point solvers of DEQs by harnessing historical feature representation information z computed from different noisy samples, thereby mitigating redundant calculations. While the hidden representation z is initialized as 0 in standard DEQs (Bai et al. 2021a), we propose to choose a better initialization of z to accelerate the convergence of DEQs (Bai et al., 202 which can potentially reduce the number of fixed-point iteration and computation cost. Specifically, our Serialized Randomized Smoothing approach leverages the representation z computed from the previous noisy sample e; as the initial state of the fixed-pot -oint solver of the next noisy sample:
Solver x x Et, 1,1)
where: i= 1,2, ........ .,,,,,,,,,,. NN.
As shown in Figure lb due to the similarity between 27-1 2i_1) and (F 255 as analyzed the motivation, it only takes a few fixed-point iterations to adjust the feature representation from z 2 (e= 2²',, which significantly accelerates the prediction of DEQs.
Though a better initialization accelerates the inference of DEQs, it introduces an unnecessary correlation within the framework of randomized smoothing. In standard randomized smoothing, each prediction is made independently. However, the predictions are linked through previous fixed points as defined by Solver(J,, x + <;; = To exemplify this, consider extreme case where the solver functions as an identity mapping. In such a case, all subsequent predictions merely replicate the first prediction. This pronounced correlation effectively reduces the process an amplification of the first prediction, breaking the confidence estimation for Monte Carlo. Therefore, we develop new estimation of the certified radius with theoretical guarantces in the next subsection.
3.3
Correlation Ellminated Certification
The primary challenge is to confirm how much the initialization of the fixed-point solver influences the final predictions. For different data samples x + and initialization z the cases can be different depending on the complex loss landscape of the fixed-point problem and the strength of the solver. Nonetheless, comparing all predictions from SRS with standard predictions, which necessitate numerous inference steps, is impractical. Such a comparison contradicts the fundamental requirement for efficiency in this process.
To maintain the theoretical guarantee of randomized smoothing, we propose correlation-llimination certification to obtain a conservative estimate of the certified radius. The core idea involves discarding those samples that are misclassified as the most probable class, ca during the Monte Carlo process. Let Pm represent the probability that a sample is predicted class ca (2) using SRS but falls into other classes with the standard DEQ. We can drop the misclassified samples as follows:
N = - AA
(10)
where NA represents the count of samples predicted as class (z(z) and N refers to the subset of these effective samples that are predicted as class ca (z)) Utilizing NE and N, able to estimate the certified radius. For the reason that pm is intractable, we employ an additional hypothesis test using limited number of samples approximate its upper bound. During the Monte Carlo sampling of SRS, we randomly select K of samples (a small number compared to N) along with their corresponding predictions, which are then stored as Xmm and Y m. respectively. After the Monte Carlo sampling, these samples, Xm. are subjected to predictions using the standard DEQ to yield the labels Y gg which serve as the ground truth. Mathematically, we estimate Pm as follows:
ultimately
Ni = Σx K
1=1 1[Ym = Y, and Y, = cx()),
(11)
No Σ 1fmm = cA(x)}
(12)
Pm = 1 LowerConfBound( 1 a),
(13)
where ā aa/2 is for keeping the confidence level of the two-stage hypothesis test. Besides, LowerCon/Boundd( n, 1 a)) returns a one-sided (1 - a:) lower confidence interval for the Binomial parameter p given that k Binomial(n, p). In other words, it returns some number p for which
p S p with probability at least over the sampling of k Binomial (n. p). Intuitively, smaller
5

---

Pm indicates higher consisteney between the predictions of SRS and those of the standard DEQ, yielding greater number of effective samples. To enhance comprehension, we include an example in Appendix to demonstrate the workflow of correlatoonellminateed certification. In the end, we estimate the certified radius with the following equation:
PA LowerConfBound NN N. â)
(14)
R - (pA)
(15)
To implement SRS-DEQ efficiently, we stack the noisy samples into mini-batches for faster parallel computing as shown in Algorithm Given a certified point, we sample batch-wise noisy data. After solving the fixed-point problem for the first batch, the subsequent fixed-point problem initialized with the solution of the previous one. By counting the effective predictions using Eq. (TO), the algorithm finally returns the certified radius as in standard randomized smoothing (Cohen et all]|22099] The following Theorem 3.1 theoretically guarantees the correctness of our algorithm (proof available in Appendix(A]
Theorem 3.1 (Correlation-Elimine
Certification). If Algorithm returns class ē^ (x) with radius R calculated by equation 14 and 15 then the smoothed classifier g predicts e (2( within radius R around x: g(x 5) g(x) for all [|8]| < R, with probability at least 1 a.
4 Experiments
In this section, we conduct comprehensive experiments in the image classification tasks to demonstrate the effectiveness of the proposed SRS-MDEQ. First, we introduce the experimental settings in detail. Then we present certification on CIFAR-10 and ImageNet datasets to demonstrate the certified accuracy and efficiency. Finally, we provide comprehensive ablation studies to understand its effectiveness.
4.1 Experiment Settings
Datasets. We use two classical datasets in image recognition, CIFAR-10 (Krizhevsky et al.) 2009) and ImageNet (Russakovsky et al., 2015). to evaluate the certified robustness. is crucial emphasize that this is the first attempt to certify the robustness of DEQs on such a large-scale dataset.
DEQ Architectures and Solvers. We select MDEQ with Jacobian regularization (Bai al.) 2020), type of DEQs specially designed for image recognition, to serve as the base classifier in randomized smoothing. Specifically,
choose AIDE--MMALI and HIDE-LLARGE for CIFAR- 10, and MDEQ- SMALL for ImageNet. To obtain a satisfactory level of certified accuracy, all the base classifiers are trained on the Gaussian augmented noise data with mean 0 and variance a². Detailed information regarding the model configuration and training strategy is available in Appendix B
We closely follow the solver setting in MDEQ (Bai et al. 2020p. For the standard MDEQ CIFAR- 10, we use the Anderson solver with the step of [1, 5, 30J. For the standard MDEQ on ImageNet, use the Broyden solver with the step of (1, 5, 14). We apply Anderson and Naive solvers CIFAR-10 10 and Broyden solver on ImageNet for the proposed SRS-MDEQ with the step of ( (1, 3). We adopt warm-up technique, where first batch in Algorithm []] The warm-up steps for our SRS-MDEQ are set as 30 and 14 steps for CIFAR-11 10 and ImageNet, respectively. The details of warm-up up strategy shown in Appendix K For notation simplicity, we use a number after the algorithm name to represent the number of layers of the model, and use "N", "A", and "B" to denote the Naive, Anderson, and Broyden solvers. For instance, SRS-MDEQ-3A denotes SRS-MDEQ method with steps of Anderson iterations.
multi-steps to solve the fixed-poin problem for the
Randomized smoothing. Following the setting in randomized smoothing (Cohen et al. 2019). we use four noise levels to construct smoothed classifiers: (0.12, 0.25, 0.50, 1,00J. We report the approximate certified accuracy as in (Cohen al. 2019), which is defined as the fraction of the test data that is both correctly classified and certified with a norm certified radius exceeding a radius threshold In experiments, we set the failure rate = 0.001 and the sampling number as = 10, 000 in the Monte Carlo method, unless specified otherwise. All the experiments are conducted on one A 100 GPU.
Baselines. We majorly use standard Randomized Smoothing for MDEQs as our baseline for compar- ison. It is also important to compare method with state-of-the-art certified defenses. Note that the

---

results of randomized smoothing are not entirely comparable to deterministic methods. Although randomized smoothing can provide better certified radii, its certification is probabilistic, even if the certified probability is close to 100%. Therefore, we only show the comparison in Appendix D for reference. However, our results indicate that the certified radii can be more promising certain cases when using deterministic methods as references.
4.2 Certification on CIFAR-10 and ImageNet
Table 1: Certified accuracy and running time of one image for the MDEQ-LARGE on CIFAR-10. 10.
The best certified accuracy for each radius is in bold and the time is compared with MDEQ-30A.
Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
ACR
Time (s)
MDEQ-IA IA
28%
19%
13%
8%
5%
3%
1%
0.27
1.06
MDEQ-SA
50%
41%
32%
21%
15%
10%
6%
0.47
2.59
MDEQ-30A
67%
55%
45%
33%
23%
16%
12%
0.62
12.89
SRS-MDEQ-IN IN SRS-MDEQ-IA
61%
52%
44%
31%
22%
15%
11%
0.57
1.02 (13x)
63%
53%
45%
32%
22%
16%
12%
0.59
1.79 (7x)
SRS-MDEQ-3A
66%
54%
45%
33%
23%
16%
11%
0.62
2.55 (5x)
Certified accuracy and running time of one image for the MDEQ-SMALL on CIFAR-1O. 10. The best certified accuracy for each radius is in bold and the time is compared with MDEQ-30A.
Table 2:
Model \ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
ACR
Time (s)
MDEQ-1A IA
21%
17%
13%
10%
6%
4%
1%
0.23
0.28
MDEQ-5A
52%
42%
29%
21% %
11%
7%
3%
0.45
0.64
MDEQ-30A
62%
50%
38%
30%
22%
13%
9%
0.59
3.08
SRS-MDEQ-IN
47%
38%
28%
19%
6%
2%
0.41
0.27 (11x)
BRS-MDEQ-LA IA
60%
47%
36%
27%
17%
12%
8%
0.56
0.46 (7x)
ERS-MDEQ-33
60%
50%
38%
29%
21%
12%
8%
0.59
1.14 (3x)
Table 3: Certified accuracy and running time of one image for the MDEQ-SMM SMALL ImageNet. The best certified accuracy for each radius is in bold and the time is compared with MDEQ- 14B.
Model Radius
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Time (s)
MDEQ-IB
2%
1%
1%
1%
1%
0%
7.30
MDEQ-SB
39%
33%
28%
23%
19%
15%
11%
31.77
MDEQ-14B
45%
39%
33%
28%
22%
17%
11%
88.33
SRS-MDEQ-IB
40%
34%
32%
27%
21%
16%
10%
15,21 (6x)
SRS-MDEQ-3B
44%
39 %
33%
28%
22% %
17%
11 %
27.48 (3x)
We compare the certified accuracy and the running time of standard MDEQ and our SRS-MDEQ across various layers further validate the efficiency and robustness of the models. The experimental 0.5 are presented in Tables T and and the results on Imagenet with o = 1.0 are shown in Table 3 The results for models using different values of are provided in the Appendix E Based on these results, we make the following observations from several aspects.
results of the large and small architectures on the CIFAR-10 with
Number of layers. We delve into a detailed study of the impact of layers in MDEQ. The results in Table [ Table [] and Table [ indicate that the certified accuracy of both MDEQ and SRS- MDEQ increases with the increase of layers. Moreover, with few layers, our SRS-MDEQ-1 1 and SRS-MDEQ-3 can significantly outperform the MDEQ-1 and MDEQ-5 and achieve comparable performance to MDEQ-30. For instance, for CIFAR-10, SRS-MDEQ-3A can outperform MDEQ- 1/MDEQ-5 by an average of 28.5% (large) and 24.3% 8. (small), respectively. The results with other noise levels are shown in Appendix

---

HEEO 43
Formnn Emequuenyy
HCE2-AJ A3 45
Formoltend reqqurro
SRS-MOEQ-AA
10
8.
RAD
AAD
Figure 2: RRD histogram with MDEQ-LARGE LARGE with 20 bins.
20
aimralted frequuecy
SRS-MDED-A1
SRS-MOEQ-A3
Foomall do (nequuency
SRS-L BRG-LIRGE-A
20-
00
0.2
0.4
0.6
0.8
3.0
8.
6x
(a)
(b)
(c)
(d)
Figure 3: Gap histogram of MDEQ-LARGE and Pm histogram of MDEQ-LARGE with 10 bins.
Running Time. The running time summarized in Table I Table 2 and Table shows significant efficiency improvements of our SRS-DEQ method compared with standard randomized smoothing. In general, the time cost almost linearly increases with the number of layers. The standard MDEQ requires 30 layers to certify each image satisfactory extent, which costs 12.89 seconds per image for the large model and 3.08 seconds per image for the small model on CIFAR-10. This process leads to a heavy computational burden the certification process. Fortunately, this process can be significantly accelerated by our SRS-MDEC To be specific, for CIFAR-10, 10, large SRS-MDEQ-IT is near 11x faster than large MDEQ-30 with 2.5% certified accuracy drop. Besides, small SRS-MDEQ-3A outperforms small MDEQ-30A in efficiency by 7x with only 1% accuracy drop. On Imagenet, our AAS-MDEQ-IB can speed up the certification by 6x while enhancing certified robustness compared to MDEQ-14B.
4.3 Ablation Study
In this section, we conduct comprehensive ablation studies to investigate the instance-level consistency and the effectiveness of our correlation eliminated certification. We also provide more ablation studies on the hyperparameter MDEQ solvers in Appdenix
correlation-llimiaate
F and Finally, we show the empirical
robustness performance of our method in Appendix
Instance-level consistency. Besides providing global measurements for the SRS-MDEQ with the certified accuracy in Section [.2 we study how closely SRS-MDEQ matches accurate MDEQ at the instance level based on our proposed Relative Radius Difference (RRD). RRD compares the relative difference between the certified radius of SRS-MDEQ and the accurate MDEQ for each instance x;;
RRD(x;)
(16)
where rÿ and r represent the certified radius of x; with MDEQ-30A and SRS-MDEQ, respectively. We compute RRD over the instances with a positive certified radius to avoid the singular value.
We present the histograms of RRD in Figure 2 certified radius achieved by SRS-MDEQ- IA is quite close to the accurate MDEQ since these relative differences are mostly small and close to O, and it significantly outperforms the standard MDEQ-IA IA with one layer. Moreover, with layers as shown in Section 4.3 the RRD values become even more concentrated around 0, which shows very consistent certified radius with the accurate MDEQ. The instance level measurement for other settings of MDEQs are shown in Appendix H
As shown in Section 4.3 only with one layer, the
Power of correlation-eliminaeee certification. The correctness of our method is based on estimating the upperbound of Pm- this ablation study, we investigate the effectiveness in the following two aspects. We provide additional analysis for this technique in Appendix]] !

---

(1) The magnitude of the upperbound. A large pm indicates that we need to drop many predictions in CA. showcasing strong correlation in SRS-DEQ. We plot the histogram pm show the magnitude. Figure 3a and 3b illustrates that the majority of Pm values fall within lower intervals, even with just a single step. This trend is more pronounced with three layers, as depicted in Figure 3b) These observations suggest that an increase in the number of steps reduces the correlation in predictions, resulting in a certified radius calculated by our method closer to the one obtained through standard randomized smoothing for DEQs. The inner reason is that our approach does not necessitate the exclusion of a large number samples for most certified points.
(2) The empirical correctness of the upperbound, i.e., if the estimated value is larger than the number of samples we should drop. For each certified point, we calculate the gap between those two values:
N Σ 1=
Pm
1l + yº and y" CA).
(17)
N
where NA is the number of samples classified as Ca with SRS. As shown Figure 3c and 3d the histogram of the gap, the value is always larger than 0, meaning that the estimation effectively covers the samples that we should drop. Moreover, the gap distribution is notably skewed towards For example, more than 95% of the gaps less than 0.2, signifying that our estimation is not only effective but also tight. More results can be found Appendix
Model Radius
Model|Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
ResNet- 110
65%
54%
41%
32%
23%
15%
9%
MDEQ-30A
%
55% %
45%
33%
23%
16%
12%
SRS-MDEQ-3A
66%
54%
45%
33%
23%
16%
11%
Table 4: Comparison of certified accuracy for ResNet-110 10 and the MDEQ-LARGE architecture with 0.5 on CIFAR-10. The best certified accuracy for each radius is in bold.
Compared to explicit neural networks. To demonstrate the superior performance of certification with DEQs, we also compare our results against those of explicit neural networks. 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 4 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 (Cohen et al.) 2019).
Results Other Randomized Smoothing methods. In addition the standard version of random- ized smoothing (Cohen et al. 2019), there are more advanced methods available. To demonstrate the general adaptability of our approach to randomized smoothing, we conduct experiments using SmoothAdy (Salman et al. 2019). For these experiments, we utilize PGD (Kurakin et al. 2016) as the adversarial attack method, setting the number of adversarial examples during training to 4. The results, presented in Table 5] show that SmoothAdv improves certified accuracy for both standard randomized smoothing and our SRS approach.
Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
MDEQ-IA (adv)
23%
17%
12%
9%
6%
2%
MDEQ-5A (adv)
52%
44%
32%
21%
17%
14%
10%
MDEQ-30A (adv)
62%
54%
43%
37%
30%
23%
14%
MDEQ-30A (standard)
62%
50%
38%
30%
22%
13%
9%
SRS- RRS-MDEQ-IA (adv)
60%
43%
35%
27%
18%
14%
9%
SRS SRS-MDEQ-3A (adv)
60%
52%
43%
36%
29%
22%
14%
Table 5: Certified accuracy for the MDEQ-SMALL architecture with 0.5 on CIFAR-10 using SmoothAdv. The maximum norm of PGD is set as 0.5 and the number of steps T is set as 2.

---

5 Related Work
5.1 Deep Equilibrium Models
Recently, there have been many works on deep implicit models that define the output by implicit
functions (Amos & Kolter 2017 Chen et al. 2018: Bai et al. 2019 Agrawal et al. 2019 El Ghaoui
et al., 2021; Bai et al.] 2020] Winston & Kolter 2020). Among these, deep equilibrium model defines the implicit layer by solving fixed-point problem (Bai et al. 2019 2020j. There are many fundamental works investigating the existence and the convergence of the fixed point (Winston) & Kolter 2020; Revay et al., 2020, Bai et al.] 2021b Ling et al., 2023). With many advantages, DEQs achieve superior performance in many tasks, such as image recognition (Bai et al.) (020). image generation (Pokle et al. 2022), graph modeling (Gu et al., 2020; Chen et al. 2022). language modeling (Bai et al., 2019), and solving complex equations (Marwah et al. 2023). Though DEQs catch up with the performance of DNNs, the computation inefficiency borders the deployment of
deep implicit models in practice (Chen et al. 2018 Dupont et al. 2019 Bai et al. 2019). Related works focus on reusing information from diffusion models and optical flows, demonstrating the effectiveness of reducing computational redundancy of DEQs (Bai & Melas-Kyriazi 2024 Bai et al. 2022). However, this paper focuses on the certified robustness of DEQs and provides a theoretical analysis of our proposed method.
5.2 Certified Robustness
Empirical defenses like adversarial training are well-known in deep learning (Goodfellow et al., 2014). Some existing works improve the robustness of DEQs by applying adversarial training (Gurumurthy
cct al. 2021 Yang et al. 2023 2022). Different from the empirical defense like adversarial training, certified defenses theoretically guarantee the predictions in small ball maintain as a constant (Wong & Kolter 2018 Raghunathan et al. 2018 Gowal et al. 2018 Cohen et al. 2019). The most common way certify robustness to define convex program, which lower bounds the worst-case perturbed output of the network (Raghunathan et al. 2018) Wong & Kolter 2018). The increasing computation complexity in high-dimension optimization hinders the generalization of these methods. Interval bound propagation (IBP) is another certification method for neural networks, which computes an upper bound of the class margin through forward propagation (Gowal al., 2018). However, the layer-by- layer computation mode brings a potentially loose certified radius. Recently, randomized smoothing has drawn much attention due to its flexibility (Cohen et al.) 2019). Randomized smoothing certifies fz-norm robustness for arbitrary classifiers by constructing a smoothed version of the classifier. There are some existing works certifying robustness for DEQs Most of them adapt IBP to DEQs by constructing joint fixed-point problem (Wei & Kolter 2021 Li et al.) 2022). Others design specific
forms of DEQs to control the Lipschitz constant of the models (Havens et al., 2023) Jafarpour et al.)
2021). Yet, no existing work explores randomized smoothing for certifiable DEQs.
6 Conclusion
In this work, we provide the first exploration of randomized smoothing certification for DEQs. Our study shows that randomized smoothing for DEQs can certify more generalized architectures and be applied to large-scale datasets but incurs significant computation costs. We delve into the computation bottleneck of this certified defense and point out the new insight of computation redundancy. We further propose a novel Serialized Random Smoothing approach to significantly reduce the computation cost by leveraging the computation redundancy. Finally, we propose new estimation for the certified radius for our SRS. Our extensive experiments demonstrate that our algorithm significantly accelerates the randomized smoothing certification by up to 7x almost without sacrificing the certified accuracy. Our discoveries and algorithm provide valuable insight and solid step toward efficient robustness certification of DEQS. Our work significantly improves the security of artificial intelligence, especially applicable in sensitive domains, enhancing the appliance of the models and maintaining the integrity of Al-driven decisions. 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.
10

---

7 Acknowledgements
Weizhi Gao, Zhichao Hou, and Dr. Xiaorui Liu are supported by the National Science Foundation (NSF) National Al Research Resource Pilot Award, Amazon Research Award, NCSU Data Science Academy Seed Grant Award, and NCSU Faculty Research and Professional Development Award.
References
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.
Amos, B. and Kolter, J. Z. Optnet: Differentiable optimization
layer in neural networks. In International Conference on Machine Learning, pp. 136-145, PMLR, 2017.
Araujo, A., Havens, A., Delattre, B., Allauzen, A., and Hu, B. A unified algebraic perspective on lipschitz neural networks. arXiv preprint arXiv:2303.03 2023.
Athalye, A., Carlini, N., and Wagner, D. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning. pp. 274-283. PMLR, 2018.
Bai, S., Kolter, J. Z., and Koltun, V. Deep equilibrium models. Advances in Neural Information Processing Systems, 32, 2019.
Bai, S., Koltun, V., and Kolter, J. Z. Multiscale deep equilibrium models. Advances in Neural Information Processing Systems, 33:5238-5250, 2020.
Bai, S., Koltun, V., and Kolter, Z. Neural deep equilibrium solvers. International Conference on Learning Representations, 2021a.
Bai, S., Koltun, V., and Kolter, J. Z. Stabilizing equilibrium models by jacobian regularization. arXiv preprint 106. 14342, 2021b.
Bai. S., Geng, Z., Savani. Y., and Kolter, J. Z. Deep equilibrium optical flow estimation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 620- 630, 2022.
Bai, and Melas-Kyriazi, L. Fixed point diffusion models. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9430 9440, 2024.
Chen, Q., Wang, Y., Wang, Y., Yang, J., and Lin, Z. Optimizzaiionindduced graph implicit nonlinear diffusion. In International Conference on Machine Learning, pp. 3648-3661. PMLR, 2022.
Chen, R. T., Rubanova, Y., Bettencourt, J., and Duvenaud, D. K. Neural ordinary differential equations. Advances neural information processing systems, 31, 2018.
Chu. H., Wei, S., and Liu, T. Learning robust deep equilibrium models. arXiv preprint arXiv:2304. 12707, 2023.
Cohen, J., Rosenfeld, E., and Kolter, Z. Certified adversarial robustness via randomized smoothing. In international conference on machine leurning, pp. 1310-1320. PMLR, 2019.
Dupont, E., Doucet, A., and Teh, Y. W. Augmented neural odes. Advances in neural information processing systems, 32, 2019.
El Ghaoui, L.., Gu, F., Travacca, B., Askari, A., and Tsai, A. Implicit deep learning. SIAM Journal on Mathematics of Data Science, 3(3):930-958, 2021.
Geng, Z. and Kolter, J. Z. Torchdeq: A library for deep equilibrium models. arXiv preprint UrXiv:2310.18600 2023.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.

---

Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovie, R., Mann, T., and Kohli, On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 12715, 2018.
Gu, F., Chang, H., Zhu, W., Sojoudi, S., and El Ghaoui, L. Implicit graph neural networks. Advances in Neural Information Processing Systems, 33:1 1984-1118 1995, 2020.
Gurumurthy, S., Bai, S., Manchester, Z., and Kolter, Z. Joint inference and input optimization in equilibrium networks. Advances in Neural Information Processing Systems, 34:16818 188888-16832, 2021.
Havens, A. J., Araujo, A., Garg. S., Khorrami, F., and Hu, B. Exploiting connections between lipschitz structures for certifiably robust deep equilibrium models. In Thirly-seventh Conference on Neural Information Processing Systems, 2023.
Huang, Y.. Zhang, H., Shi, Y., Kolter, J. Z., and Anandkumar, A. Training certifiably robust neural networks with efficient local lipschitz bounds. Advances in Neural Information Processing Systems, 34:22745-22755 2021.
Jafarpour, S., Abate, M., Davydov, A., Bullo, F., and Coogan, S. Robustness certificates for implicit neural networks: A mixed monotone contractive approach. arXiv preprint 12Xiv:2112.053100 2021.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Kurakin, A., Goodfellow, I., and Bengio, S. Adversarial machine learning at scale. arXiv preprint arXiv:1611.011 2016.
Li, L., Xie, T., and Li, B. Sok: Certified robustness for deep neural networks. In 2023 IEEE symposium on security and privacy (SP), pp. 1289-1310. IEEE, 2023.
Li, M., Wang, Y., and Lin, Z. Cerdeq: Certifiable deep equilibrium model. In International Conference Machine Learning, pp. 12998-13013, PMLR, 2022.
Ling, 7., Xie, X., Wang, Q.. Zhang, Z., and Lin, Global convergence of over-parameterized deep equilibrium models. In International Conference on Artificial Intelligence and Statistics, pp. 767-787. PMLR, 2023.
Marwah, T., Pokle, A., Kolter, J. Z., Lipton, Z. C., Lu, J., and Risteski, A. Deep equilibrium based neural operators for steady-state pdes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Neyman, J. and Pearson, E. S. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical Physical Character, 231 231(6947006:228)
1933.
Pokle, A., Geng, Z., and Kolter, Z. Deep equilibrium approaches to diffusion models. Advances in Neural Information Processing Systems, 35:37975-37990, 2022.
Raghunathan, A., Steinhardt, J., and Liang. P. Certified defenses against adversarial examples. arXiv preprint arXiv: 1801.0:8001.9944 2018.
Revay, M., Wang, R., and Manchester, I. R. Lipschitz bounded equilibrium networks. arXiv preprint arXiv:2010.01332, 2020.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Visual Recognition Challenge. International Journal Computer Vision (IJCV), 115 2015. doi: 10.1007/
Salman, H., Li, J., Razenshteyn, I., Zhang, P., Zhang, H., Bubeck, S., and Yang, G. Provably robust deep learning via adversarially trained smoothed classifiers. Advances Neural Information Processing Systems. 32, 2019.
12

---

Wei, C. and Kolter, J. Z. Certified robustness for deep equilibrium models via interval bound propagation. In International Conference on Learning Representations. 2021.
Winston, E. and Kolter, J. Z. Monotone operator equilibrium networks. Advances in neural information processing systems, 13:10718-10722 2020.
Wong, H. and Kolter, Z. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning, pp. 5286-5295. PMLR, 2018.
Yang, Z., Pang, T., and Liu, Y. A closer look the adversarial robustness of deep equilibrium models. Advances in Neural Information Processing Systems, 35:10448-1046,, 2022.
Yang. Z., Li. P., Pang. T., and Liu, Y. Improving adversarial robustness of deqs with explicit regulations along the neural dynamics. arXiv preprint arXivv2306.01435, 2023.
Zhang, B., Cai, T., Lu, Z., He, D., and Wang, Towards certifying I-infinity robustness using neural networks with l-inf-dist neurons. In International Conference Machine Learning, pp. 12368-12379. PMLR, 2021.
13

---

A Proofs of Theorem 3.1
Theorem. With probability at least 1 a over Algorithm 1 If Algorithm returns a class č with a radius R, then the smoothed classifier 9 predicts C within radius R around x: g(x + 8) - g(x) for all |6 < R.
Proof. From the contract of the hypothesis test, we know that with the probability of at least ā over all the samplings <1, E2, ,,N, have pm > P(y êλ and y * ŌΔ) Pm. where y and v represent the predictions of x + 6 given by SRS and the standard DEQ, respectively. Denote the number samplings as follows:
N NA- Pm.
(18)
NE = NA -PmNA
(19)
where N is the fact number that the predictions of the standard DEQs are class čΛ. while N is the number we estimate. In this way, LowerConfBound A NN, a) < LowerConfBound( A N, ().
Suppose the standard randomized smoothing returns I with N and N, we conclude that R < R with the probability of at least 1 1-a. With Proposition in the standard randomized smoothing (Cohen
et al. 2019). g(x + 6) = g(x) for all |o]|| < R for all |d]|| < R. 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 P(A) IP (B) = following the hypothesis tests. The final
probability of successfully certifying the data point is:
P-BP (PA)) 1 2ā (20) P)AUB)= P(B) P(AU B) 1 P(B) P(AUB) 2- PPB)
where (AA) the probability that A does not happen. By setting ā = a/2, we complete the proof. 0
B
Experiment Details
B.1 Model Architecture
Multi-resolution deep equilibrium models (MDEQ) are a new class of implicit networks that are suited large-scale and highly hierarchical pattern recognition domains. They are inspired by the modern computer vision deep neural networks, which leverage multi-resolution techniques to learn features. These simultaneously learned multi-resolution features allow us to train single model on diverse set of tasks and loss functions, such as using a single MDEQ to perform both image classification and semantic segmentation. MDEQs are able match or exceed the performance of recent competitive computer vision models, achieving high accuracy in sequence modeling.
We report the model hyperparameters in Table 6 For CIFAR-10, utilize both MDEQ-SMALL and MDEQ-LARGE architectures, while for ImageNet, we only employ ADDOLSMMAL. Most of the hyperparameters remain consistent with the ones specified in work (Bai et al. 2021b). MDEQs define several resolutions in the implicit layer to align with ResNet in computer vision. Consequently, the primary distinction between the models lies in the channel size and resolution level. Additionally, all the models are equipped with GroupNorm, as presented in the standard MDEQ (Bai et al.
2020
CIFAR-10
ImageNet SMALL
SMALL
LARGE
Input Size
32 32 BASIC
32 32 BASIC
224 x 224 BOTTLENECK
Block
Number of Branches
4 [32, 64, 128, 256] [14, 28, 56, 112]
Number of Channels
[8, 16, 32]
[32, 64, 128, 256] [28, 56, 112, 224] 2048
Number of Head Channels
[7, 14. 28]
Final Channel Size
200
1680
Table Model hyperparameters our experiments.

---

B.2
Training Setting
We report the training hyperraraaeteess in 8 Following work (Bai et al. 2021b). we use Jacobian regularization to ensure stability during the training process. Moreover, prevent overfitting, we employ data augmentation techniques such as random cropping and horizontal flipping. which are commonly utilized in various computer vision tasks.
Gaussian Augmentation: As mentioned in Section 3.2 randomized smoothing requires the base classifier be robust against Gaussian noise. Therefore, train the MDEQs with Gaussian augmentation. Following the standard randomized smoothing (Cohen et al. 2019), we augment the original data with noise sampled from (0 I2)), where denotes the noise level in the smoothed classifier. Intuitively, the training scheme forces the base classifier to be robust to the Gaussian noise, which is used in randomized smoothing. Formally, under the cross-entropy loss, the objective is to maximize the following:
exp fe, (x; + c) EeEy exp fx( + e)*
Σ E. log
(21)
where (2i;, Ci is one clean data point with its ground-truth label. According Jensen's inequality, Equation 21 is the lower bound of the following one:
exp fe (x; +c)
log EE, Eeey exp fe(x; +
(22)
The equation within the expectation represents the softmax output of the logits produced by the base classifier f. This can be seen as a soft version of the argmax function. Consequently, the expectation approximates the probability of class a; when Gaussian augmentation is applied. By doing so, we aim to maximize the likelihood of the smoothed classifier g(x):
Σ log P(f(xx; + c)).
(23)
To demonstrate our method is general to DEQs with any training scheme, we conduct ablation studies of Jacobian regularization. Jacobian regularization stabilizes the training of the backbones but is not crucial for the certification (Bai et al. (0211). The results in Table /soow that using Jacobian regularization can help stabilize the fixed exed-point solvers but will almost not affect the final performance with enough fixed-point iterations. Our conclusion is consistent with Bai et al. (2021b) where the regularization does not increase the accuracy but decreases the number of fixed-point iterations. Though the experiments show that using Jacobian regularization is not crucial in the certification, we recommend to use the regularization in the training for more stable performance.
Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-30A 30A (w/o Jacobian)
63%
51%
38%
29%
19%
13%
7%
SRS-MDEQ-3A (w/o Jacobian)
60%
49%
38%
28%
18%
12%
6%
MDEQ-300 30A (w Jacobian)
62%
50%
38%
30%
22%
13%
9%
ERS-MDEQ-3A (w Jacobian)
60%
50%
38%
29%
21%
12%
8%
Table 7: Ablation study of Jacobian regularization for the LIDEQ-SMALI architecture with or 0.5 on CIFAR-10.
C Algorithm
In this subsection, we present the pseudo code of our algorithm in Algorithm T The implementation is based on mini-batch mode, which is efficient in practice.

---

CIFAR-10
ImageNet
SMALL
LARGE
SMALL
Batch Size
96
96
128
Epochs
120
220
100
Optimizer
Adam
Adam
SGD
Learning Rate
0.001
0.001
0.04
Learning Rate Schedule
Cosine
Cosine
Cosine
Momentum
0.98
0.98
0.9
Weight Decay
0.0
0.0
2 x 10-3
Jacobian Reg. Strength
0.5
0.4
2.5
Jacobian Reg. Frequency
0.05
0.02
0.08
Table 8: Training hyperparameters in experiments.
Algorithm Certified Radius with SRS-DEQ
Require: DEQ f(-), certified data x, sampling numbers N, batch size B, failure rate a
1: Initialize Counts with 0 for each class
2: Calculate hypothesis test confidence: == v1 -a
3: Fixed-point initialization: 7 0 E IR Bxd
4: for < N/B do
5:
= x, x.,, x] Bxd
6:
Sample (0, σ I), Vj 1,2,- ,
7:
X 61, 62. .....
x , Eg] g Bxd
8:
Z' Solver(f. X, Z
9:
Classify Z' to get Predictions
Store samples and labels in x, and Ym..
11: Update Counts according to Predictions
end for
13: Predict X,, with the standard DEQ Y
14: Compute the estimated Pm using Eq. (13)
15: Compute & using Eq. (T0)
16: Compute R with Counts using Eq.
Return: R
D Comparsion with Baselines
In certified defenses, norm and foo norm are widely used. Since randomized smoothing provides f--norm certified radii, we choose baselines with the same certified norm. We compare the per- formance with the state-of-the-and art DEQ certification methods on CIFAR-10 (Havens et al. 2023) including SLL (Araujo al., 2023) and LBEN (Revay et al.) 2020), which certify robustness with Lipschitz bound. To align with the numbers reported in Havens et al. (2023), we adopt the same certified radius in the table. certified radii. Since the code of SLL and LBEN is not publicly available, our comparison is based on reported results their papers for CIFAR-10.
present the certified accuracy for the large SRS-MDEQ under different
Model
Certification Method
== 0.0
36
72
108 255
== 1.0
255
255
SLL LBEN
Lipschitz Bound
65%
56%
46%
36%
11%
Lipschitz Bound
45%
36%
28%
21%
4%
SRS-MDEQ-1A
Randomized Smoothing
633
59% 62%
53%
48%
22%
SRS-MDEQ-3A
Randomized Smoothing
66%
56%
52%
25%
Table 9: Comparison with existing certification methods and SRS- SRS-MDEQ-LARGE, The best certified accuracy is in bold.

---

As shown in Table 9 our SRS-MDEQ-1 I already significantly outperforms existing certification methods across all the certified radii. It also verifies that randomized smoothing defense provides tighter certification bounds. We want to emphasize again that the results of randomized smoothing are not entirely comparable to deterministic methods. Although randomized smoothing can provide better-certified radii, its certification is probabilistic, even if the certified probability is close to 100%.
E
Other Noise Levels
In the main paper, we present results using a noise level of = 0.5 for CIFAR-10 and 1.0 for ImageNet. In this appendix, we present the results other noise levels in Tables T0 to 17 For ImageNet, we adopt a larger noise level as suggested in paper (Cohen et al. 2019p. The reason behind this choice is that images can tolerate higher levels of isotropic Gaussian noise while still preserving their high-resolution content. Since the noise level does not affect the running time, we do not show the running time in these tables.
Tendency:
The observed performance trend aligns with standard randomized smoothing techniques. When using a smaller noise level a, the models exhibit higher certified accuracy within a smaller radius. However, the models are unable to provide reliable certification for larger radii due to the base classifier's lack of robustness against high-level noise. For example, the smoothed classifier with 0.12 on CIFAR-10 10 can certify up to 70% accuracy within a radius of 0.25, but its certification capability is truncated when the radius exceeds 0.5. Conversely, when employing larger noise level a, the model can certify a larger radius, but this results in drop in accuracy on clean data.
Model \ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-IA IA
23%
14%
0%
0%
0%
0%
0%
MDEQ-5A
73%
48%
0%
0%
0%
0%
0%
MDEQ-30A
86%
68%
0%
0%
0%
0%
0%
SRS-MDEQ- IN
85%
67%
0%
0%
0%
0%
0%
BRS-MDEQ-LLE 1A
85%
68%
0%
0%
0%
0%
0%
SRS-MDEQ 3N
85%
65%
0%
0%
0%
0%
0%
SRS-MDEQ-3A
86%
69%
0%
0%
0%
0%
0%
Table 10: Certified accuracy for MDEQ-LARGE with a 0.12 on CIFAR-IO.
Model \ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-1A
20%
13%
8%
4%
0%
0%
0%
MDEQ-5A
33%
21 %
15%
10%
0%
0%
0%
MDEQ-30A
79%
63%
47%
32%
0%
0%%
0%
SRS-MDEQ-IN
74%
61%
46%
30%
0%
0%
0%
SRS-MDEQ-IA
74%
61%
46%
29%
0%
0%
0%
SRS-MDEQ-3N
77%
60%
48%
31%
0%
0%
0%
SRS-MDEQ-3A
80%
63%
47%
31%
0%
0%
0%
Table 11: Certified accuracy for MDEQ-LARGE with σ 0.25 on CIFAR-10.
The strength of the solvers influences the certified accuracy. With a stronger Anderson solver, the SRS-MDEQ performs better than the naive one. For ImageNet, the high-resolution difficulty even requires to use quasi-Newton method to keep the convergence of the model. The number of steps another crucial factor for the performance. The model has better performance no matter what solver you use.
F MDEQs with More Steps
In the main paper, we showease the results of our SRS limited to maximum of 3 steps for efficiency. These results nearly match the performance of the standard randomized smoothing approach, albeit

---

Model
Radius
0.0
0.25
0.5
0.75
1.0
1.25
MDEQ-IA
16%
14%
13%
11%
9%
7%
6%
MDEQ-5A
38%
30%
24%
18%
14%
11%
8%
MDEQ-30A
48 %
41%
35 %
28%
23%
19%
15%
SRS-MDEQ-IN IN
40%
35%
28%
24%
19%
16%
11%
SRS- RRS-MDEQ-ILE IA
42%
38%
29%
24%
19%
17%
14%
44%
40%
32%
24%
20%
17%
13%
SRS-MDEQ-3A
46%
41%
34%
28%
23%
18%
15%
Table 12: Certified accuracy for MDEQ-LARGE with
1.0 CIFAR-10.
Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-IA
28%
15%
0%
0%
0%
0%
0%
MDEQ-5A
62%
35%
0%
0%
0%
0%
MDEQ-30A
80%
52%
0%
0%
0%
0%
0%
SRS-MDEQ-IN
72%
37%
0%
0%
0%
0%
0%
SRS-MDEQ-I A
75%
44%
0%
0%
0%%
0%
0%
SRS-MDEQ-3N
75%
44%
0%
0%
0%
0%
0%
SRS-MDEQ-3A
79%
52%
0%
0%
0%
0%
0%
Table 13: Certified accuracy for HIDEQ-SMALL with or
0.12 on CIFAR-10 10.
Model \\ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-IA 1A
21%
12%
7%
4%
0%
0%
0%
MDEQ-5A
56%
37%
20%
12%
0%
0%
0%
MDEQ-30A
72%
54%
38%
24%
0%
0%
0%
SRS-MDEQ-IN IN
62%
48%
30%
14%
0%
0%
0%
SRS-MDEQ-IA
69%
52%
35%
19%
0%
0%
0%
SRS- BRS-MDEE-3N
69%
51%
34%
16%
0%
0%
0%
SRS- URS-MDEQ-3A
72%
53%
36%
24%
0%
0%
0%
Table 14: Certified accuracy for MDEQ-SMALL with σ = 0.25 on CIFAR-10.
Model \ Radius
0.0
0.25
0.5
0.75
1.25
MDEQ-IA
21%
18%
15%
13%
1 11%
9%
6%
MDEQ-5A
37%
31 %
23%
17%
14%
11%
9%
MDEQ-30A
46%
39 %
32%
24%
19%
16%
14% %
IN
38%
32%
25%
20%
17%
14%
11%
SRS-MDEQ IA
42%
35%
26%
22%
18%
15%
13%
44%
35%
27%
21%
17%
15%
12%
SRS-MDEQ-3A
46 %
38%
32%
24%
19%
16%
13%
Table 15: Certified accuracy for the MDEQ-SMALL with 1.0 on CIFAR-10.
with slight discrepancies. This ablation study extends the process to 5 steps to evaluate potential performance improvements. We replicate the experimental settings from the main paper but with the increased step count. The outcomes, detailed in Tables T8 to 20 reveal that while there is some enhancement in performance, the gains are marginal. Given that our method prioritizes efficiency, we find that three steps sufficient for all the experiments conducted in our paper.
5

---

Model
Radius
0.0
0.5
1.0
1.5
2.0
2.5
MDEQ-IB 1B
0%
0%
0%
0%
0%
0%
0%
MDEQ-5B
54%
40%
0%
0%
0%
0%
0%
MDEQ-14B
67%
52%
0%
0%
0%
0%
0%
SRS-MDEQ-IB 1B
62%
52% %
0%
0%
0%
0%
0%
3RS-MDEQ-33B
66%
52%
0%
0%
0%
0%
0%
Table 16: Certified accuracy for the MDEQ-SMALL with 0.25 on ImageNet.
Model | Radius
0.0
0.5
1.0
1.5
2.0
2.5
3.0
MDEQ-1B
0%
0%
0%%
0%
0%
0%
0%
MDEQ-5B
47%
38%
29%
22%
0%
0%
0%
MDEQ-14B
57%
46%
37%
27%
0%
0%
0%
SRS-MDEQ-IB
53%
46 %
37%
27 %
0%
0%
0%
SRS-MDEQ-3B
55%
46%
37%
27%
0%
0%
0%
Table 17: Certified accuracy for the MDEQ-SMALL with 0.5 on ImageNet.
Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-30A
67%
55 %
45%
33%
23%
16%
12%
SRS-MDEQ-IA
63%
53%
45%
32%
22%
16%
12%
SRS-MDEQ-34
66%
54%
45%
33%
23%
16%
11%
SRS-MDEQ-5A
66%
54%
45%
33%
23%
16 %
12%
Table 18: Certified accuracy for MDEQ-SMALL with more steps CIFAR-10 (a 0.5).
Model \\ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-30A
62%
50%
38%
30%
22%
13 %
9%
SRS-MDEQ-IA
60%
47%
36%
27%
17%
12%
8%
SRS-MDEQ-3A
60%
50%
38%
29%
21%
12%
8%
SRS-MDEQ-5A
61%
50%
38 %
30%
22%
12%
8%
Table 19: Certified accuracy for MDEQ-SMALL with more steps on CIFAR-10 (a = 0.5).
Model \\ Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-14B
45%
39%
33%
28%
22%
17%
11 %
SRS-MDEQ-ID
40%
34%
32%
27%
21%
16%
10%
SRS-MDEQ-3B
44%
39%
33%
28%
22%
17%
1 1%
SRS-MDEQ-SB
44%
39%
33%
28%
21%
17%
11 %
Table 20: Certified accuracy for MDEQ-SMALL with more steps on ImageNet (a = 1.0).
G MDEQs with Different Solvers
In the main paper, our presentation of MDEQ results exclusively features the Anderson solver applied to CIFAR-10. Complementary to this, in the appendix, we provide results obtained with the naive solver on CIFAR-10 to show whether the choice of the solver significantly affects the performance. For the experiments conducted on MDEQs applied ImageNet, our primary focus lies on the Broyden solver, detailed in the main paper. It is worth noting that the fixed-point problem

---

Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
MDEQ-LARGE-30N
64%
53%
42%
31%
21%
13%
11%
MDEE-LAARGE-30A
67%
55%
45%
33%
23%
16%
12%
MDEQ-SMALL-30N
60%
47%
36%
29%
19% 22%
11%
8%
HIDEO-SMAL--- 62%
50%
38%
30%
13%
9%
Table Certified aceuracy of MDEQ-SMALL with different solvers on CIFAR-10.
Large
Small MDEQ
MDEQ
SRS-MDEQ
SRS-MDEQ
Anderson
0.6140
0.0266
0.5180
0.0786
Anderson
0.3240
0.0210
0,2561
0.0324
Naive 1
0.5219
0.0396
0,4761
0.2322
Naive 3
0.1268
0.0425
0,2138
0.0825
Table 22: The mean RRD measurements over all images.
encountered in high-dimensional data introduces heightened complexities, necessitating a solver with superior convergence properties, elaborated upon (Bai et al. 2020).
The outcomes obtained with various solvers are detailed in Table 21
Notably, while MDEQs employing the naive solver exhibit slightly faster certification compared to those with the Anderson solver, both the large and small architectures encounter some accuracy drops, with deviations of up to 3%. Given that objective is to establish MDEQs baseline with superior performance, we exclusively present results obtained with the Anderson solver in the main paper for meaningful comparison.
H Instance-Level Consistency
In the main paper, we utilize RRD as the measurement to validate the effectiveness of our method. In this appendix, we extend our evaluation observe the performance of RRD specifically on MDEQ-SMALL architectures.
As illustrated in Figure the instance level. Regarding RRD, SRS-MDEQ exhibits a notable concentration small values, indicating the efficacy of our serialized randomized smoothing in aligning radii. Further insight is gained from Figure where the RRDs of all samples for SRS-MDEQ-A3 are consistently smaller than 0.2, contrasting with MDEQ-A3, which features numerous samples with large LADs. Notably, with an increasing number of steps, both MDEQ and SRS-MDEQ exhibit trend toward increased concentration, with SRS- SRS-MDEQ consistently outperforming MDEQ. Besides. we also exhibit the mean RRD values over the whole dataset in Table 22 consistently showing the better performance of our SRS-MDEQ.
method demonstrates strong performance for MDEQ -EEEL
I Correlation-Elimnnated Certification
I.1 Detailed Illustration
In this appendix, we delve deeper into the nuances of our approach to correlation-eliminatee certifica- tion. As shown in Figure the correlation eliminated certification is based on dropping unreliable predictions. To be specific, our method compares the predictions of SRS-DEQ with the ones with standard DEQ and then drops the inconsistent predictions in the most probable class č This process intuitively reassigns all incorrectly classified predictions from class č to class čn, effectively aligning them with the predictions made by the standard DEQ. Finally, we estimate Pm to get conservative estimation of these converted samples.
oorrelationellminateed

---

20
20
normalized frequency
MDEQ-A1 SRS-MDEQ -A1
normalized frequency
MDEQ-A3 SRS-MDEQ-A3
15
15
10
10
5
0.0
0.2
0.4
0.6
0.8
1.0
8.0
0.2
0.4
0.6
0.8
1.0
RRD
RRD
(a)
(b)
Figure 4: RRD histogram with MDEQ-SMALL models. There are 10 bins in each histogram.
x preserve
X
DEQ
SRS-DEQ
x x1
Panda
Panda
x++
Globon
Compare
Panda
Ep
Panda
Panda
&
Figure 5: The illustration of our correlation-elmminated certification. If we input the noisy panda images into the standard DEQ and SRS-DEQ, there will be some misalignment due to the correlation introduced by SRS. Our method conservatively converts these predictions back to the correct ones. For instance, the predictions of x + e2 are different with RS and SRS. Therefore, the prediction of x + will not be counted as the most probable class č Finally, we use these converted predictions calculate the certified radius recover the standard DEQ's predictions. In the implementation, we try to estimate the number of these converted predictions instead of using the standard DEQ to get the inferences.
I.2 Cut-off Radius
Given the noise variance a,, a sampling number N, and failure tolerance a, the cut-off radius means the maximum radius that can be certified, i.c., the radius when all samples are classified correctly. With SRS, since have an upper bound on Pm. the maximum empirical confidence PA could be lower. Here we provide analysis for the cut-off radius comparison. To be specific, we present the comparison of the radius with different correct ratios (the percentage of class A) when there are no wrong predictions from our method (pm. 0). More formally,
Rratio LowerConfBoundd Pm.) ratio, N. a)
(24)
D LowerConfBound B, B,
(25)
We provide the numerical cut-off radius with the hyperparameters used in our paper: N 10, 000, B 1, 000, a = 0.001. The results are shown in Table 23 As special case (when the ratio 1), the cut-off radius of our method is 1.594, and the cut-off radius of the original method is 1.860. For the samples with smaller ratios, the gap between the standard method and our method will further decrease because of the marginal effect (Cohen et al. 2019).

---

ratio
0.75
0.80
0.85
0.90
0.95
0.99
1.00
0.332
0.415
0.512
0.634
0.814
1.148
1.860
Reatio
0.331
0.414
0.511
0.633
0.812
1.139
1.594
Table 23: Comparison of Ryatio and Pratio for different ratio values.
normalized frequency
BRS-SMALL-AN
normalized frequency
SRS-SMALL-A3
15
15
10
10
5
0.1
0.0
0.1
0.2
0.3
0.4
0.5
00.
0.0
0.1
0.2
0.3
0.4
0.5
gap
gap
(a)
Figure 6: Gap histogram with MDEQ-SMALL models. There 10 bins in each histogram.
normalized frequency
SRS-MDEQ-A1
normalized frequency
SRS-MDEQ-A3
15
15
10
10
5
8.0
8.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Pm
Pm
(a)
(b)
Figure 7: Pm histogram with MDEQ-SMALL models. There are 10 bins in each histogram.
I.3 More Results
In this appendix, we extend our analysis to include additional results for the correlation-eliminated certification, focusing particularly on the distribution of the gap and Pm for MDEQ-SMALL models. These results are illustrated in Figure Figure Regarding the gap, we observe a trend consistent with that for MDEQ-LARGE models: predominant skew towards O while maintaining positive values, which underscores the efficacy of our estimation approach. As for Pm its distribution appears more uniform in MDEQ-SMALL with one step, compared to MDEQ-LARGE, This aligns with the observed phenomenon where the certified accuracy is somewhat lower than that achieved through standard randomized smoothing for DEQs with a single step.
The Number of Samplings
We investigate the effect of the number of samplings in our randomized smoothing approach by conducting experiments with = 0.5 depicted in Figures and Notably, these results align well with those reported in (Cohen et al. 2019). Across all results, consistent trend emerges, revealing that there are no substantial differences observed between N 10, 000 and N = 100, 000 across most radii. This insight underscores the robustness and stability of the results, emphasizing that the choice of the number of samplings within this range does not significantly impact the outcomes.

---

1.0
1.0
N-1,000
N-1,000
0.8
0.8
certiiie accuracy
N=100,000
N=100,000
certified
0.4
022
0.2
0.0
0.0
0.50
0.75
1.25
1.50
0.75
1.00
1.75
2.00
radius
radius
(a) Anderson
(b) Naive
Figure 8: Different number of samplings for MDEQ-SMALL with the 3-step solvers.
1.0
N=1,000
N- 1,0000
N=10,000
N 10,000
0.8
0.8
certified accuracy
N=100,000
N=100,000
0.6
0.6
certified
0.0
0.0
0.00
0.25
0.50
0.75
1.00 radius
1.25
1.30
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
radius
(a) Anderson
(b) Naive
Figure 9: Different number of samplings for MDEQ-LARGE with the 3-step solvers.
K
Warm-up Strategy
In our implementation, we employ a warm-up strategy to enhance the initial performance of serialized randomized smoothing during certification. In this appendix, we delve into the effectiveness of this technique.
The Number of Steps: We investigate the influence of the number of warm-up steps the per- formance of our method. As shown in Figures [0a and [Ob there a marginal improvement in the performance of MDEQ-LARGE when the number of warm-up steps is increased to 30. The performance of AIDEO-SMALE remains stable. For the sake of time efficiency, we adopt 10 as the default parameter in main experiments.
The Warm-Up Solver: We explore whether utilizing different solvers during the warm-up phase impacts the performance of our method, denoting the model with the "solver-solver" format. For example, "Anderson-Naive" signifies the warm-up solver as Anderson and the solver for MDEQ as the naive one. Conducting experiments with 10 warm-up steps and 3-step solvers, the results in Figures TIa and Ilb indicate that the choice of warm-up solvers does not significantly affect performance when the solvers for MDEQ are the same (as evidenced by the nearly overlapping lines) for both large and small models. In our main experiments, we consistently use pairwise solvers, where the solver for warming up aligns with that used for MDEQ.
Considering the potential accumulation of fixed- fixed-poine point errors due the distance of samplings, we investigate the necessity of restart strategy for our method. Specifically, we implement this strategy by warming up every batches. Employing pairwise solvers with 10 warm-up steps, the results in Figures 12a and 12b exhibit the findings from the warm-up steps. Implementing restart strategy with varying intervals yields a slight performance increase. For the sake of time efficiency, default to 10 as the parameter in our main experiments.
Restart:
10

---

10
10
alap=10
22
step-20
Stop-30
Certified accuracy
0.
0.8
cartified
02
0.2
5.0
1.0
3.2
0.0
1.2
1.4
redius
radius
(a) Large
(b) Small
Figure 10: Different warm-up steps for SRS-MDEQ-3A.
1.0
1.0
Andeeson-Aodderson halve Anderson
Andersonsindenea
Nalvo Anderson
RndersconNNaivee
Anderaann-haive
Nolve Nalke
Certified accuracy
Nalve- Navve
0.6
0.6
cartified
02
0.2
rad
radius
(a) Large
Small
Figure 11: Different warm-up solvers for SRS- -DDD-3D.....
1.0
1.0
Interval-10
Intervai-10
Interval-100 1.00
Interval-100
0.8
No Interval
No Interval
Certified accuracy
0.6
0.8
0.4 cortified
(a) Large
(b) Small
Figure 12: Different warm-up restart intervals for SRS-
Start Points: There are two choices for the start points the warm-up strategy: (1) start from the clean data point x for all the noisy data x + e: (2) start from previous noisy data in each batch. We choose to start from the previous noisy data because it performs better than using the fixed-point solution of the clean data. This is because the previous noisy data provides smaller pm in the certification. The certified accuracy is shown in Table 24 The differences between the two start initialization come from the correlated-elimmnatiie will depend on the estimated pm (smaller Pm is better). With the previous fixed point, our certification process accumulates randomness to avoid the bad guess at the beginning. The distribution p.. will be more concentrated to 0 with our method that starts from the previous solutions. It means need drop more predictions we start from the clean data. As result, the certified accuracy of starting from the previous fixed points is better.
certification. The final radius

---

Model Radius
0.0
0.25
0.5
0.75
1.0
1.25
1.5
SRS-MDEQ- MADE---A-c-llla
56%
48%
40%
29%
20%
16%
12%
PRS-MDEQ-3A-clens
64%
52%
45%
33%
23%
13%
11%
SRS-MDEQ-14 SRS-MDEQ-3A
63%
53%
45%
32%
22%
16%
12%
66%
54%
45%
33%
23%
16%
11%
Table 24: Certified accuracy for the MIEQ-LAAGE architecture with 0.5
CIFAR-10. The
first two rows represent the results starting from clean data, while the latter two rows represent the results starting from the previous fixed-point solutions.
L Empirical Robustness
In this appendix, we present the performance of SRS-MDEQ under adversarial attacks show our model is robust empirically. To demonstrate the efficacy of our approach, assess predictions using the strongest adversarial attack PGD-&z and its variant for randomized smoothing, Smooth- PGD (Salman et al. 2019).
Attack
0.0
0.25
0.5
r
0.75
1.0
1.25
1.5
PGD
72%
70%
65%
63%
60%
60%
58%
m=1
72%
67 %
63%
62%
61% %
61 %
61% 1
m=4
72%
66%
62%
60%
57%
57%
58%
m=8
72%
66%
61%
58%
56%
55%
54%
m=16
72%
65%
60%
55%
53%
51%
49%
Certified
66%
54%
45%
33%
23%
16%
11%
Table 25: The empirical performance of the randomized smoothing on L.RGGE-RSS-DDEQ--4
Attack
0.0
0.25
0.5
0.75
1.0
1.25
1.5
PGD
66%
63%
61%
57%
53%
49%
45%
m=1
66%
61 %
53%
46%
40%
36%
30%
m=4
66%
61%
53%
46%
40%
36%
32%
m=
66%
61 %
53%
46%
39%
36%
30%
m=16
66%
61%
53%
44%
39%
35%
29%
Certified
60%
50%
38%
29%
21%
12%
8%
Table 26: The empirical performance of the randomized smoothing on SMALL-SRS-MDEQ-N
Projected Gradient Descent (PGD) leverages the principles of gradient descent to iteratively update input data. It begins with an initial input, calculates the gradient the model's loss concerning the input, and adjusts the input in the direction that maximizes the increase in the loss. This adjustment is constrained by small perturbation limit to ensure that the changes remain within acceptable bounds. In the context of randomized smoothing, PGD is employed to directly target the base classifier. We utilize a fixed step size of 0.1 for each iteration, and the total number of iterations is set at 20.
Given that PGD does not directly target the smoothed classifier, we also employ Smooth-PGD to attack our model, following the methodology outlined in (Salman et al. 2019). The indirect attack proves ineffective due to the obfuscated gradient phenomenon (Athalye et al. 2018). Smooth-PGD initially utilizes a soft version to approximate the gradient of the smoothed classifier, mitigating the non con-differentiable nature of the classifier. It then employs the Monte Carlo method to estimate the value of the gradient. Finally, standard PGD is employed to generate adversarial examples using the estimated gradient. Smooth-PGD demonstrates increased effectiveness compared to PGD when given sufficient samplings in Monte Carlo. Throughout our experiments, we maintain consistency in hyperparameter between Smooth-PGD and standard PGD.
Following work (Salman al., 2019), we select the number of samplings m in Smooth-PCI from (1, 4, 8, 16). We compare the empirical results with the certified accuracy reported in our main paper to
12

---

Attack
r
0.25
0.5
0.75
r 1.0
1.25
r 1.5
PGD
5% 0%
14% 0%
15% / 0%
17% / 0%
15% 0%
17% / 0%
m=1
10% / 0%
16% / 0%
16% / 0%
15% / /0%
14% /0%
13% / 0%
m=4
12% / 0%
20% / 0%
20% 10%
20% / 00%
18% 70%
16% / 0%
m=
14% / 0%
21% 0%
23% / 0%
23%/09 /0%
21% 70%
21% / 0%
m=16
16% / 0%
23% 0%
27% / 0%
26% 00
27% 0%
26% / 0%
Table 27: The point-wis wise successful attack rate of on LARGE-SRS-MDEQ-3A The first number the rate of successfully attacking the uncertified points. The second number is the rate of successfully attacking the certified points.
Attack
0.25
0.5
0.75
1.0
1.25
1.5
PGD
6% 0%
8% / 0%
13% 10%
16% / 00
20% 0%
23% / 0%
m=
10% / 0%
22% / 0%
28% / 00
32% 70%
35% /0%
39% / 0%
m=4
10% / 0%
22% 00
28% 00%
32% 70%
34% /0%
37% / 0%
m=
9% / 0%
21% / 0%
28% / 0%
33% /0%
35% /0%
39% / 0%
m=16
10% / 0%
22% 0%
30% / 0%
33% / 0%
36% 00
40% / 0%
Table 28: The point-wise successful attack rate of on SMALL-SRS-MDEQ--AATIII
first number is
the rate of successfully attacking the uncertified points. The second number is the rate of successfully attacking the certified points.
show the correctness of the randomized smoothing. The results are shown in Tables 25 and 26 where r represents the attack budget. 0 means the predicted accuracy clean data. It observed that Smooth-POH exhibits superior strength compared to the standard PGD. The most important finding that the certified accuracy is lower than the accuracy under all the adversarial attacks, meaning all the attacks can not break the certified robustness in randomized smoothing. In essence, these results underscore robustness of our method, showcasing reliable certified accuracy empirically.
Based on the preceding analysis, certified accuracy serves as global metric for evaluating model robustness. However, substantiate the efficacy of certification, the model must ensure that each certified point remains invulnerable within its corresponding certified radius. This appendix conducts an instance-level analysis demonstrate this aspect. Specifically, we quantify the percentage of points successfully attacked within the certified and uncertified subsets, respectively. The outcomes are detailed in Tables 27 and 28 The first number the rate of successfully attacking the uncertified points, while the second number is the rate of successfully attacking the certified points. As m increases, the first number gets larger, meaning the attack is getting stronger. In this case, the second number consistently keeps as O, meaning the certified points can not be attacked at all. Despite minimal failure probability in randomized smoothing certification, our point-wise empirical investigation underscores the robustness and reliability of our method.
13

---

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: Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
14

---

Justification: Appendix A
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4. and Appdendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers 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?
15

---

Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
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 NeurIPS code and data submission guidelines (https
/ cpippi.ccppulli//uuuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiieeeec ssi wswonnolli onnolicy)))) 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, etc.
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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: [Yes]
Justification: Section 4.1 and Appdendix B 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Section 4.1 and Appdendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It 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 enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or 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 in the text how they were calculated and reference the corresponding figures or 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: Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:////nn:: /ttes::///uups..eeeeeeeeees www.eris....puuuuuppeeee http:///c/cccccttttcccsiieeeeeee
Answer: [Yes]
Justification: Section 6
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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: Section 6
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
17

---

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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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: 6
Guidelines: We do not pose such risks.
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
Answer: [Yes]
Justification: Section and Appdendix
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.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, wwppppswpptseeee whworeewwthhhe....cm com/ datasets 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
18

---

Answer:
[NA]
Justification:
We do not introduce new assets in our paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll 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 as details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve crowdsourcing 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 as the institution conducting the review.
19


Reviews:
[{"review_id": "qstCXfHnsR", "reviewer": "Reviewer_3u5s", "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.\n\nDirectly 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.\n\nSubsequently, to eliminate the dependence between noisy samples created by SRS, the authors introduce Correlation-Eliminated Certification, a new method to obtain certified radius estimation.\n\nExperimental results on CIFAR-10 and ImageNet demonstrate the efficiency of the proposed model.", "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?\n- 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.\n- 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?", "limitations": "na", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, making it easy to follow the key techniques. The experiments and ablation studies are informative.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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?\n\n**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.\n\n[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.\n\n[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.\n\n**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.\n\n**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.\n\n| Model\\Radius | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | 1.25 | 1.5 |\n|--------------|-----|------|-----|------|-----|------|-----|\n| ResNet-110   | 65% | 54%  | 41% | 32%  | 23% | 15%  | 9%  |\n| MDEQ-30A     | **67%** | **55%** | 45% | 33% | 23% | 16% | **12%** |\n| SRS-MDEQ-3A  | 66% | 54%  | **45%** | **33%** | **23%** | **16%** | 11% |\n\nTable 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.\n\n[1] Bai, Shaojie, J. Zico Kolter, and Vladlen Koltun. \"Deep equilibrium models.\" Advances in neural information processing systems 32 (2019).\n\n[2] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. \"Certified adversarial robustness via randomized smoothing.\" international conference on machine learning. PMLR, 2019.\n\n**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?\n\n**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.\n\n**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.\n\n**Answer**: We appreciate that you recognize the value of DEQs again. The corresponding results are provided in the reply to Question 2.", "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": "KzrvsHPglC", "reviewer": "Reviewer_2B8g", "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.", "questions": "1. Can the authors clarify the difficulty and novelty of implementing their method for large-scale datasets like ImageNet?\n\n2. Does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS?\n\n3. Can the authors further justify the unique novelty and technicality of their contribution?", "limitations": "The authors have partially addressed limitations in their paper. However, there seems to lack a substantial discussion on broader societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "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.\n\n2. 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.\n\n3. 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. \n\n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Question 1**: Can the authors clarify the difficulty and novelty of implementing their method for large-scale datasets like ImageNet?\n\n***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. \n\nWe hope this answer addresses your question, and we are happy to provide further details if needed.\n\n[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.\n\n**Question 2**: Does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS?\n\n**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.\n\n| Model\\Radius | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | 1.25 | 1.5 |\n|--------------|-----|------|-----|------|-----|------|-----|\n| ResNet-110   | 65% | 54%  | 41% | 32%  | 23% | 15%  | 9%  |\n| MDEQ-30A     | **67%** | **55%** | 45% | 33% | 23% | 16% | **12%** |\n| SRS-MDEQ-3A  | 66% | 54%  | **45%** | **33%** | **23%** | **16%** | 11% |\n\nTable 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.\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**Question 3**: Can the authors further justify the unique novelty and technicality of their contribution?\n\n**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. \n\n**Weakness 1**: The conceptual novelty may not be that significant since randomized smoothing is a well-known technique in the first place.\n\n**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.\n\n**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?\n\n**Answer**: To answer your concern, we refer to the comparison provided in Question 2.\n\n**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.''", "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": "MLiyxRqJIs", "reviewer": "Reviewer_366J", "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.", "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?\n2. 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?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n* The authors provide a thorough ablations section which answers questions regarding the goodness of their approximation for $p_m$.\n* 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.\n* 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.\n\n\n[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\n\nSome notes: \n* Lines 49-54 introduce acronyms that are not defined\n* Neyman-Pearson is spelled incorrectly on line 108\n* 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? \n* Line 574: missing period\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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?\n\n**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.\n\nThe 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.\n\n| Model \\ Radius         | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | 1.25 | 1.5 |\n|------------------------|-----|------|-----|------|-----|------|-----|\n| MDEQ-30A (w/o Jacobian) | 63% | 51%  | 38% | 29%  | 19% | 13%  | 7%  |\n| SRS-MDEQ-3A (w/o Jacobian) | 60% | 49%  | 38% | 28%  | 18% | 12%  | 6%  |\n| MDEQ-30A (w Jacobian)  | 62% | 50%  | 38% | 30%  | 22% | 13%  | 9%  |\n| SRS-MDEQ-3A (w Jacobian) | 60% | 50%  | 38% | 29%  | 21% | 12%  | 8%  |\n\nTable 1: Ablation study of Jacobian regularization for the MDEQ-SMALL architecture with $\\sigma=0.5$ on CIFAR-10.\n\n[1] Bai, Shaojie, Vladlen Koltun, and Zico Kolter. \"Stabilizing Equilibrium Models by Jacobian Regularization.\" International Conference on Machine Learning. PMLR, 2021.\n\n**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?\n\n**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.\n\nTo be specific, Line 14 should be expanded into two steps. First, we use equation (12) to compute the estimated $\\overline{p_m}$, namely:\n$$\nN_1 = \\sum\\nolimits_{i=1}^{K}\\mathbf{1} \\\\{Y_m = Y_g \\text{ and } Y_g = c_A(x) \\\\} ,\n$$\n$$\nN_2 = \\sum\\nolimits_{i=1}^{K}\\mathbf{1}\\\\{Y_m = c_A(x)\\\\},\n$$\n$$\n\\overline{p_m} = 1-\\text{LowerConfBound}(N_1, N_2, 1-\\tilde{\\alpha}),\n$$\nThen we use equation (9) to estimate the effective samples that are predicted as class $c_A (x)$ with our estimated $\\overline{p_m}$:\n$$\nN_A^E = N_A - \\overline{p_m} N_A,\n$$\nFinally, with the total number of samples $N$, we compute the radius with equations (13) and (14):\n$$\n\\underline{p_A} = \\text{LowerConfBound}(N_A^E, N, 1-\\tilde{\\alpha})\n$$\n$$\nR = \\sigma\\Phi^{-1}(\\underline{p_A}),\n$$\nWe hope this answer addresses your question, and we are happy to provide further details if needed.\n\n**Weakness 1**: Revising the typos and unclear expressions\n\n**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). \nBesides, 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})$.''\n\nFor 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''.\n\nFinally, 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)$.\n\n**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.}\n\n**Answer**: To solve your concern, we refer you to the results we provided in Question 1.", "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": "oYfTcc6Nti", "reviewer": "Reviewer_eMdN", "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.", "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?", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nQuality. 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.\n\nSignificance. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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.\n\n**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.\n\n**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?\n\n**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.\n\nHope our answer can address your question, and we are glad to reply if you need more description.\n\n| Model       | Clean Accuracy |\n|-------------|----------------|\n| MDEQ-30A    | 67%            |\n| SRS-MDEQ-3A | 66%            |\n\nTable 1: Clean accuracy for the MDEQ-LARGE on CIFAR-10.", "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": "K35zM0mVA5", "reviewer": "Reviewer_qqXj", "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.", "questions": "See weakness. Below are some additional questions:\n\nMinor: \nLine 98 & 158, Cohen et al did not discuss fixed point solvers and DEQs. Is that a wrong citation?\nLine 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?", "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.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "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:\n\n1. 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.\n2. 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.\n3. 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.\n4. 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?\n\n[1] Salman et al., Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.\n[2] Jeong et al., Confidence-aware Training of Smoothed Classifiers for Certified Robustness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Weakness 1**: In the evaluation, the authors only show the discretized certified radius curve...\n\n**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.\n\n| Model                | ACR  |\\| Model                | ACR  |\n|----------------------|------|----------------------|------|\n| MDEQ-LARGE-1A        | 0.27 |\\| MDEQ-SMALL-1A        | 0.23 |\n| MDEQ-LARGE-30A       | 0.62 |\\| MDEQ-SMALL-30A       | 0.59 |\n| SRS-MDEQ-LARGE-1A    | 0.59 | \\|SRS-MDEQ-SMALL-1A    | 0.56 |\n| SRS-MDEQ-LARGE-3A    | 0.62 |\\| SRS-MDEQ-SMALL-3A    | 0.59 |\n\nTable 1: Average certified radius for the MDEQ architecture with $\\sigma=0.5$ on CIFAR-10.\n\n[1] Chen, Ruoxin, et al. \"Input-specific robustness certification for randomized smoothing.\" AAAI 2022.\n\n**Weakness 2**: The authors indicate that the models are trained via Gaussian, while there are many recent advances...\n\n**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.\n\n| Model \\ Radius          | 0.0 | 0.25 | 0.5 | 0.75 | 1.0 | 1.25 | 1.5 |\n|-------------------------|-----|------|-----|------|-----|------|-----|\n| MDEQ-30A (adv)          | **62%** | **54%** | 43% | **37%** | **30%** | **23%** | 14% |\n| MDEQ-30A (standard)     | 62% | 50%  | 38% | 30%  | 22% | 13%  | 9%  |\n| SRS-MDEQ-1A (adv)       | 60% | 43%  | 35% | 27%  | 18% | 14%  | 9%  |\n| SRS-MDEQ-3A (adv)       | 60% | 52%  | **43%** | 36%  | 29%  | 22%  | **14%** |\n\nTable 2: Certified accuracy for the MDEQ-SMALL architecture with $\\sigma=0.5$ on CIFAR-10 using SmoothAdv. \n\n[1] Kurakin, Alexey, Ian Goodfellow, and Samy Bengio. \"Adversarial machine learning at scale.\" arXiv:1611.01236 (2016).\n\n**Weakness 3**: Line 190 says that the bounding subset is selected during the SRS sampling, this means ...\n\n**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:\n$$\n    \\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}\n$$\nwhere $\\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.\n\n**Weakness 4**: SRS basically reduces the complexity of fixed point iteration, by making the prediction serial...\n\n**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.\n\n| Model \\ Radius      | 0.0  | 0.25 | 0.5  | 0.75 | 1.0  | 1.25 | 1.5  |\n|---------------------|------|------|------|------|------|------|------|\n| SRS-MDEQ-1A-clean   | 56%  | 48%  | 40%  | 29%  | 20%  | 16%  | 12%  |\n| SRS-MDEQ-3A-clean   | 64%  | 52%  | 45%  | 33%  | 23%  | 15%  | 11%  |\n| SRS-MDEQ-1A         | 63%  | 53%  | 45%  | 32%  | 22%  | 16%  | 12%  |\n| SRS-MDEQ-3A         | 66%  | 54%  | 45%  | 33%  | 23%  | 16%  | 11%  |\n\nTable 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.\n\n**Minor Question:** Line 98 \\& 158, Cohen et al did not discuss fixed point solvers and DEQs. Is that a wrong citation?...\n\n**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. \n\nAs 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.\n\n[1] Bai, Shaojie, Vladlen Koltun, and J. Zico Kolter. \"Neural deep equilibrium solvers.\" ICLR 2021.\n\n**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.''", "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 paper advances a new method to achieve certified robustness on deep equilibrium models which reduces what would otherwise be high computational costs. The paper also provides proofs showing correctness of the method. After robust discussion all reviewers agreed the paper was novel, interesting, and overall a good contribution to NeurIPS.

I am recommending this paper be accepted as a poster and not a higher accolade mostly because the scope of the paper is fairly narrow. While it was well-executed, it only focuses on deep equilibrium models which could limit the breadth of its impact.

I recommend the authors to add clear discussions both of the limitations of their work and potential broader impacts for the camera-ready version.
Decision: Accept (poster)