Certified Robustness for Deep Equilibrium Models via Serialized Random Smoothing

Authors: weizhi  gao
han  xu
xiaorui  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:01:57

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.

Main paper: 
 introduction: 
 The recent development of implicit layers provides an alternative and promising perspective for neural network design (Amos & Kolter, 2017; Chen et al., 2018; Agrawal et al., 2019; Bai et al., 2019 Bai et al., , 2020;; El Ghaoui et 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-form functions of the input. These implicit layers can represent infinitely deep neural networks using only one single layer that is defined implicitly. The unique definition endows implicit models with the capability to model continuous physical systems, a task that traditional DNNs cannot accomplish (Chen et al., 2018) . Additionally, the implicit function theorem enhances memory efficiency by eliminating the need to store intermediate states during forward propagation (Chen et al., 2018; Bai et al., 2019) . Furthermore, implicit models offer a valuable accuracy-efficiency trade-off, making them adaptable to varying application requirements (Chen et al., 2018) . These advantages underscore the significant research value of implicit models.Deep equilibrium models (DEQs) are one promising class of implicit models that construct the output as the solution to input-dependent fixed-point problems (Bai et al., 2019) . With a fixed-point solver, DEQs can be seen as infinite-depth and weight-tied neural networks. The modern DEQ-based architectures have shown comparable or even surpassing performance compared with traditional explicit models (Bai et al., 2019 (Bai et al., , 2020;; Gu et al., 2020; Chen et al., 2022) . Due to the superior 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 (Chu 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 guarantees. It is worth noting that certified defenses certify that no adversarial example can ever exist within a neighborhood of the test sample regardless of the attacks, providing reliable robustness measurements 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., 2021; Li et al., 2023) . 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 a typical DEQ takes up to 88.33 seconds. This raises significant efficiency challenges for the application of certifiable DEQs in real-world applications. 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 is 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 accelerate 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 7× almost without sacrificing the certified accuracy.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Section 1 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: 
 In this section, we provide necessary technical background for DEQs and Randomized Smoothing.Implicit formulation. Traditional feedforward neural networks usually construct forward feature transformations using fixed-size computation graphs and explicit functions z l+1 = f θ l (z l ), where z l and z l+1 are the input and output of layer f θ l (•) with parameter θ l . DEQs, as an emerging class of implicit neural networks, define their output as the fixed point solutions of nonlinear equations:EQUATIONwhere 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 a 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:EQUATIONMore details about these solvers can be referred to in the work (Cohen et al., 2019) . In this paper, we denote all solvers as follows:EQUATIONwhere z 0 is the initial feature state that is taken as 0 in DEQs. All the solvers end the iteration if the estimation error f (z) -z of the fixed point reaches a given tolerance error or a maximum iteration threshold L.Randomized smoothing (Cohen et al., 2019) is a certified defense technique that guarantees ℓ 2 -norm certified robustness. Given an arbitrary base classifier f (•), we construct a smoothed classifier g(•):EQUATIONEQUATION)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 p A and p B as the probabilities of the most probable class c A (x) and second probable class c B (x), Neyman-Pearson theorem (Neyman & Pearson, 1933) provides a ℓ 2 -norm certified radius R for the smoothed classifier g:EQUATIONwhereEQUATIONHere Φ(x) is the inverse of the standard Gaussian cumulative distribution function, and p A , p B ∈ [0, 1] satisfy:P(f (x + ϵ) = c A (x)) ≥ p A ≥ p B ≥ max c̸ =c A (x) P(f (x + ϵ) = c).In practice, p A and p B are estimated using the Monte Carlo method. It is crucial to maintain the independence of each prediction in the simulation to ensure the correctness of randomized smoothing.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: Section 6Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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-eliminated certification technique to estimate the radius in SRS. After get all the predictions, SRS-DEQ makes use of correlation-eliminated certification to estimate the certified radius.According to Eq. ( 7), we need to estimate the lower bound probability p A and upper bound probability p B . The appliance of Monte Carlo sampling rescues as follows:EQUATIONwhere 1{•} is the indicator function, and ϵ i ∼ N (0, σ 2 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 × 32 image in CIFAR-10 takes 12.89 seconds, and 88.33 seconds for one 256 × 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 to be complex to maintain the expressiveness. Second, the fixed-point solver needs many iterations for convergence. To maintain the best performance, the solvers usually set a small value for the error tolerance (e.g., 0.001). Although second-order solvers like Broyden's method have faster convergence, their computation cost per iteration is higher. Third, the Monte Carlo estimation in randomized smoothing further exacerbates the expensive inference of DEQs, leading to significant computation challenges, as shown in Figure 1a .As introduced in Section 3.1, the Monte Carlo method is employed in randomized smoothing to estimate the prediction probability, typically necessitating over 10, 000 times inference computation for certifying one data point. Despite the independent sampling of Gaussian noises, these noises {ϵ i } are added to the same certified data point x to form noisy data samples {x + ϵ i }. Notably, these samples are numerically and visually similar to each other as can be seen in Figure 1 . Moreover, in randomized smoothing, the base classifier is trained on Gaussian-augmented data to be resistant to 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 a 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 50 layers as an illustrative example. In the Monte Carlo estimation with N = 10, 000, it requires the forward computation of 50 × 10, 000 = 500, 000 layers. However, if we can estimate the intermediate representation at the 45 th layer, the required forward iterations reduce to 5 × 10, 000 = 50, 000 layers, bringing a 10× acceleration.Motivated by the above challenges and analyses, we propose a 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 0 is initialized as 0 in standard DEQs (Bai et al., 2021a) , we propose to choose a better initialization of z 0 to accelerate the convergence of DEQs (Bai et al., 2021a) , which can potentially reduce the number of fixed-point iteration S and computation cost. Specifically, our Serialized Randomized Smoothing approach leverages the representation z S i computed from the previous noisy sample x + ϵ i as the initial state of the fixed-point solver of the next noisy sample:EQUATIONwhere i = 1, 2, . . . , N . As shown in Figure 1b , due to the similarity between z * i-1 (≈ z S i-1 ) and z * i (≈ z S i ) as analyzed in the motivation, it only takes a few fixed-point iterations to adjust the feature representation from z S i-1 to z * i (≈ z S i ), 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(f, x + ϵ i , z S i-1 ). To exemplify this, consider an 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 to an amplification of the first prediction, breaking the confidence estimation for Monte Carlo. Therefore, we develop a new estimation of the certified radius with theoretical guarantees in the next subsection.The primary challenge is to confirm how much the initialization of the fixed-point solver influences the final predictions. For different data samples x + ϵ i and initialization z S i , 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-elimination 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, c A (x), during the Monte Carlo process. Let p m represent the probability that a sample is predicted as class c A (x) using SRS but falls into other classes with the standard DEQ. We can drop the misclassified samples as follows:EQUATIONwhere N A represents the count of samples predicted as class c A (x) and N E A refers to the subset of these effective samples that are predicted as class c A (x). Utilizing N E A and N , we are ultimately able to estimate the certified radius. For the reason that p m is intractable, we employ an additional hypothesis test using a limited number of samples to 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 X m and Y m , respectively. After the Monte Carlo sampling, these samples, X m , are subjected to predictions using the standard DEQ to yield the labels Y g , which serve as the ground truth. Mathematically, we estimate p m as follows:EQUATIONEQUATIONEQUATIONwhere α = α/2 is for keeping the confidence level of the two-stage hypothesis test. Besides, LowerConfBound(k, n, 1 -α) returns a one-sided (1 -α) 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 ≤ p with probability at least 1 -α over the sampling of k ∼ Binomial(n, p). Intuitively, a smaller p m indicates a higher consistency between the predictions of SRS and those of the standard DEQ, yielding a greater number of effective samples. To enhance comprehension, we include an example in Appendix I to demonstrate the workflow of correlation-eliminated certification. In the end, we estimate the certified radius with the following equation:EQUATIONTo implement SRS-DEQ efficiently, we stack the noisy samples into mini-batches for faster parallel computing as shown in Algorithm 1. 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 is initialized with the solution of the previous one. By counting the effective predictions using Eq. ( 10), the algorithm finally returns the certified radius as in standard randomized smoothing (Cohen et al., 2019) .The following Theorem 3.1 theoretically guarantees the correctness of our algorithm (proof available in Appendix A): Theorem 3.1 (Correlation-Eliminated Certification). If Algorithm 1 returns a class ĉA (x) with a radius R calculated by equation 14 and 15, then the smoothed classifier g predicts ĉA (x) within radius R around x: g(x + δ) = g(x) for all ∥δ∥ < R, with probability at least 1 -α.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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.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. It is crucial to 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 et al., 2020) , a type of DEQs specially designed for image recognition, to serve as the base classifier in randomized smoothing. Specifically, we choose MDEQ-SMALL and MDEQ-LARGE 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 σ 2 . 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., 2020) . For the standard MDEQ on CIFAR-10, we use the Anderson solver with the step of {1, 5, 30}. For the standard MDEQ on ImageNet, we use the Broyden solver with the step of {1, 5, 14}. We apply Anderson and Naive solvers on CIFAR-10 and Broyden solver on ImageNet for the proposed SRS-MDEQ with the step of {1, 3}.We adopt a warm-up technique, where we use multi-steps to solve the fixed-point problem for the first batch in Algorithm 1. The warm-up steps for our SRS-MDEQ are set as 30 and 14 steps for CIFAR-10 and ImageNet, respectively. The details of warm-up strategy are 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 we use "N", "A", and "B" to denote the Naive, Anderson, and Broyden solvers.For instance, SRS-MDEQ-3A denotes SRS-MDEQ method with 3 steps of Anderson iterations.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.00}. We report the approximate certified accuracy as in (Cohen et al., 2019) , which is defined as the fraction of the test data that is both correctly classified and certified with a ℓ 2 -norm certified radius exceeding a radius threshold r. In our experiments, we set the failure rate as α = 0.001 and the sampling number as N = 10, 000 in the Monte Carlo method, unless specified otherwise. All the experiments are conducted on one A100 GPU.Baselines. We majorly use standard Randomized Smoothing for MDEQs as our baseline for comparison. It is also important to compare our 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 in certain cases when using deterministic methods as references. We compare the certified accuracy and the running time of standard MDEQ and our SRS-MDEQ across various layers to further validate the efficiency and robustness of the models. The experimental results of the large and small architectures on the CIFAR-10 with σ = 0.5 are presented in Tables 1 and 2 , and the results on Imagenet with σ = 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.We delve into a detailed study of the impact of layers in MDEQ. The results in Table 1, Table 2, and Table 3 indicate that the certified accuracy of both MDEQ and SRS-MDEQ increases with the increase of layers. Moreover, with a few layers, our SRS-MDEQ-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%/12.1% (large) and 24.3%/8.8% (small), respectively. The results with other noise levels are shown in Appendix E. Running Time. The running time summarized in Table 1, Table 2, and Table 3 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 to a 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 in the certification process. Fortunately, this process can be significantly accelerated by our SRS-MDEQ. To be specific, for CIFAR-10, large SRS-MDEQ-1N is near 11× faster than large MDEQ-30A with a 2.5% certified accuracy drop. Besides, small SRS-MDEQ-3A outperforms small MDEQ-30A in efficiency by 7× with only a 1% accuracy drop. On Imagenet, our SRS-MDEQ-1B can speed up the certification by 6× while enhancing certified robustness compared to MDEQ-14B.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 of MDEQ solvers in Appdenix F and G. Finally, we show the empirical robustness performance of our method in Appendix L.Instance-level consistency. Besides providing global measurements for the SRS-MDEQ with the certified accuracy in Section 4.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 i :EQUATIONwhere r i b and r i s represent the certified radius of x i 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 . As shown in Section 4.3, only with one layer, the certified radius achieved by SRS-MDEQ-1A is quite close to the accurate MDEQ since these relative differences are mostly small and close to 0, and it significantly outperforms the standard MDEQ-1A with one layer. Moreover, with 3 layers as shown in Section 4.3, the RRD values become even more concentrated around 0, which shows a very consistent certified radius with the accurate MDEQ. The instance level measurement for other settings of MDEQs are shown in Appendix H.Power of correlation-eliminated certification. The correctness of our method is based on estimating the upperbound of p m . In this ablation study, we investigate the effectiveness in the following two aspects. We provide additional analysis for this technique in Appendix I.(1) The magnitude of the upperbound. A large p m indicates that we need to drop many predictions in ĉA , showcasing strong correlation in SRS-DEQ. We plot the histogram of p m to show the magnitude. Figure 3a and 3b illustrates that the majority of p m 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 of 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:EQUATIONwhere N A is the number of samples classified as c A with SRS. As shown in 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 0. For example, more than 95% of the gaps are less than 0.2, signifying that our estimation is not only effective but also tight. More results can be found in Appendix I. 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 on Other Randomized Smoothing methods. In addition to the standard version of randomized 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 SmoothAdv (Salman et al., 2019) . For these experiments, we utilize PGD (Kurakin et al., 2016) 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 
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 a fixed-point problem (Bai et al., 2019 (Bai et al., , 2020)) . 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., 2020) , 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.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 et al., 2021; Yang et al., 2023 Yang et al., , 2022)) . Different from the empirical defense like adversarial training, certified defenses theoretically guarantee the predictions in a 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 to certify robustness is to define a 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 et al., 2018) . However, the layer-bylayer 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 ℓ 2 -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 a 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. 
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 it 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 a 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 7× almost without sacrificing the certified accuracy. Our discoveries and algorithm provide valuable insight and a 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 AI-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.A Proofs of Theorem 3.1Theorem. With probability at least 1 -α over Algorithm 1. If Algorithm 1 returns a class ĉA with a radius R, then the smoothed classifier g predicts ĉA within radius R around x: g(x + δ) = g(x) for all ∥δ∥ < R.Proof. From the contract of the hypothesis test, we know that with the probability of at least 1 -α over all the samplings ϵ 1 , ϵ 2 , • • • , ϵ N , we have p m > P(y i s = ĉA and y i b ̸ = ĉA ) = p m , where y i s and y i b represent the predictions of x + ϵ i given by SRS and the standard DEQ, respectively. Denote the number of samplings as follows:EQUATIONEQUATIONwhere N E A is the fact number that the predictions of the standard DEQs are class ĉA , while N E A is the number we estimate. In this way, LowerConfBound( N E A , N, α) < LowerConfBound(N E A , N, α). Suppose the standard randomized smoothing returns R with N E A and N , we conclude that R < R with the probability of at least 1-α. With Proposition 2 in the standard randomized smoothing (Cohen et al., 2019) , g(x + δ) = g(x) for all ∥δ∥ < R for all ∥δ∥ < 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( Ā) = P( B) = α following the hypothesis tests. The final probability of successfully certifying the data point is:P(A ∪ B) = P(B) -P( Ā ∪ B) = 1 -P( B) -P( Ā ∪ B) ≥ 1 -P( B) -P( Ā) = 1 -2α (20)where P( Ā) is the probability that A does not happen. By setting α = α/2, we complete the proof. □ 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: Section 4.1 and Appdendix B 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: Multi-resolution deep equilibrium models (MDEQ) are a new class of implicit networks that are suited to 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 a single model on a diverse set of tasks and loss functions, such as using a single MDEQ to perform both image classification and semantic segmentation. MDEQs are able to 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, we utilize both MDEQ-SMALL and MDEQ-LARGE architectures, while for ImageNet, we only employ MDEQ-SMALL. 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 [8, 16, 32] [32, 64, 128, 256] [32, 64, 128, 256 ] Number of Head Channels [7, 14, 28] [14, 28, 56, 112] [28, 56, 112, 224 We report the training hyperparameters in Table 8 . Following work (Bai et al., 2021b) , we use Jacobian regularization to ensure stability during the training process. Moreover, to 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 to be robust against Gaussian noise. Therefore, we train the MDEQs with Gaussian augmentation. Following the standard randomized smoothing (Cohen et al., 2019) , we augment the original data with noise sampled from N (0, σ 2 I), 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:EQUATIONwhere (x i , c i ) is one clean data point with its ground-truth label. According to Jensen's inequality, Equation ( 21) is the lower bound of the following one:EQUATION)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 c i when Gaussian augmentation is applied. By doing so, we aim to maximize the likelihood of the smoothed classifier g(x):EQUATIONTo 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 it is not crucial for the certification (Bai et al., 2021b) . The results in Table 7 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. 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.5MDEQ-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-30A (w Jacobian) 62% 50% 38% 30% 22% 13% 9% SRS-MDEQ-3A (w Jacobian) 60% 50% 38% 29% 21% 12% 8%Table 7 : Ablation study of Jacobian regularization for the MDEQ-SMALL architecture with σ = 0.5 on CIFAR-10.In this subsection, we present the pseudo code of our algorithm in Algorithm 1. The implementation is based on mini-batch mode, which is efficient in practice. : α = 1 - √ 1 -α 3: Fixed-point initialization: Z 0 = 0 ∈ R B×d 4: for 1 ≤ i ≤ N/B do 5: X = [x, x, . . . , x] ⊤ ∈ R B×d 6: Sample ϵ j ∼ N (0, σ 2 I), ∀j = 1, 2, • • • , B 7: X = [x + ϵ 1 , x + ϵ 2 , . . . , x + ϵ B ] ⊤ ∈ R B×d 8: Z i = Solver(f, X, Z i-1 ) 9:Classify Z i to get Predictions Update Counts according to Predictions 12: end for 13: Predict X m with the standard DEQ to get Y g 14: Compute the estimated p m using Eq. ( 13) 15: Compute N E A using Eq. ( 10) 16: Compute R with Counts using Eq. ( 7) Return: RIn certified defenses, ℓ 2 -norm and ℓ ∞ -norm are widely used. Since randomized smoothing provides ℓ 2 -norm certified radii, we choose baselines with the same certified norm. We compare the performance with the state-of-the-art DEQ certification methods on CIFAR-10 (Havens et al., 2023) including SLL (Araujo et 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. We present the certified accuracy for the large SRS-MDEQ under different certified radii. Since the code of SLL and LBEN is not publicly available, our comparison is based on reported results in their papers for CIFAR-10. As shown in Table 9 , our SRS-MDEQ-1 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%.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 on other noise levels in Tables 10 to 17 . For ImageNet, we adopt a larger noise level as suggested in paper (Cohen et al., 2019) . 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.The observed performance trend aligns with standard randomized smoothing techniques. When using a smaller noise level σ, 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 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 a larger noise level σ, the model can certify a larger radius, but this results in a drop in accuracy on clean data.Model \ Radius 0.0 0.25 0.5 0.75 1.0 1.25 1.5MDEQ-1A 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-1N 85% 67% 0% 0% 0% 0% 0% SRS-MDEQ-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% 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 us to use a quasi-Newton method to keep the convergence of the model. The number of steps is another crucial factor for the performance. The model has better performance no matter what solver you use.In the main paper, we showcase the results of our SRS limited to a maximum of 3 steps for efficiency. These results nearly match the performance of the standard randomized smoothing approach, albeit 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 18 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 are sufficient for all the experiments conducted in our paper.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 54% 40% 0% 0% 0% 0% 0% MDEQ-14B 67% 52% 0% 0% 0% 0% 0% SRS-MDEQ-1B 62% 52% 0% 0% 0% 0% 0% SRS-MDEQ-3B 66% 52% 0% 0% 0% 0% 0% 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 to ImageNet, our primary focus lies on the Broyden solver, as detailed in the main paper. encountered in high-dimensional data introduces heightened complexities, necessitating a solver with superior convergence properties, as elaborated upon in (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 our objective is to establish MDEQs as a baseline with superior performance, we exclusively present results obtained with the Anderson solver in the main paper for meaningful comparison.In the main paper, we utilize RRD as the measurement to validate the effectiveness of our method.In this appendix, we extend our evaluation to observe the performance of RRD specifically on MDEQ-SMALL architectures.As illustrated in Figure 4 , our method demonstrates strong performance for MDEQ-SMALL at the instance level. Regarding RRD, SRS-MDEQ exhibits a notable concentration of small values, indicating the efficacy of our serialized randomized smoothing in aligning radii. Further insight is gained from Figure 4b , 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 a trend toward increased concentration, with 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.In this appendix, we delve deeper into the nuances of our approach to correlation-eliminated certification. As shown in Figure 5 , 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 ĉA . This process intuitively reassigns all incorrectly classified predictions from class ĉA to class ĉB , effectively aligning them with the predictions made by the standard DEQ. Finally, we estimate p m to get a conservative estimation of these converted samples. Figure 5 : The illustration of our correlation-eliminated certification. If we input the noisy panda images into the standard DEQ and our 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 + ϵ 2 are different with RS and SRS. Therefore, the prediction of x + ϵ 2 will not be counted as the most probable class ĉA . Finally, we use these converted predictions to calculate the certified radius to 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.Given the noise variance σ, a sampling number N , and failure tolerance α, the cut-off radius means the maximum radius that can be certified, i.e., the radius when all samples are classified correctly.With SRS, since we have an upper bound on p m , the maximum empirical confidence p A 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 (p m ≈ 0). More formally,EQUATIONWe provide the numerical cut-off radius with the hyperparameters used in our paper: N = 10, 000, B = 1, 000, α = 0.001. The results are shown in Table 23 . As a special case (when the ratio is 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 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 p m for MDEQ-SMALL models. These results are illustrated in Figure 3 and Figure 7 . Regarding the gap, we observe a trend consistent with that for MDEQ-LARGE models: a predominant skew towards 0 while maintaining positive values, which underscores the efficacy of our estimation approach. As for p m , 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.We investigate the effect of the number of samplings in our randomized smoothing approach by conducting experiments with σ = 0.5 depicted in Figures 8 and 9 . Notably, these results align well with those reported in (Cohen et al., 2019) . Across all results, a 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. 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 on the performance of our method. As shown in Figures 10a and 10b , there is a marginal improvement in the performance of MDEQ-LARGE when the number of warm-up steps is increased to 30. The performance of MDEQ-SMALL remains stable. For the sake of time efficiency, we adopt 10 as the default parameter in our 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 11a and 11b 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.Restart: Considering the potential accumulation of fixed-point errors due to the distance of samplings, we investigate the necessity of a restart strategy for our method. Specifically, we implement this strategy by warming up every K 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 a restart strategy with varying intervals yields a slight performance increase. For the sake of time efficiency, we default to 10 as the parameter in our main experiments. Start Points: There are two choices for the start points of the warm-up strategy: (1) start from the clean data point x for all the noisy data x + ϵ;(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 p m in the correlation-eliminated certification. The certified accuracy is shown in Table 24 . The differences between the two start initialization come from the correlated-elimination certification. The final radius will depend on the estimated p m (smaller p m is better). With the previous fixed point, our certification process accumulates randomness to avoid the bad guess at the beginning. The distribution of p m will be more concentrated to 0 with our method that starts from the previous solutions. It means we need to drop more predictions if we start from the clean data. As a result, the certified accuracy of starting from the previous fixed points is better.Model \ Radius 0.0 0.25 0.5 0.75 1.0 1.25 1.5 SRS-MDEQ-1A-clean 56% 48% 40% 29% 20% 16% 12% SRS-MDEQ-3A-clean 64% 52% 45% 33% 23% 15% 11% SRS-MDEQ-1A 63% 53% 45% 32% 22% 16% 12% SRS-MDEQ-3A 66% 54% 45% 33% 23% 16% 11% Table 24 : Certified accuracy for the MDEQ-LARGE architecture with σ = 0.5 on 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.In this appendix, we present the performance of SRS-MDEQ under adversarial attacks to show our model is robust empirically. To demonstrate the efficacy of our approach, we assess predictions using the strongest adversarial attack PGD-ℓ 2 and its variant for randomized smoothing, Smooth-PGD (Salman et al., 2019) . Projected Gradient Descent (PGD) leverages the principles of gradient descent to iteratively update input data. It begins with an initial input, calculates the gradient of 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 a 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-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 use between Smooth-PGD and standard PGD.Following work (Salman et al., 2019) , we select the number of samplings m in Smooth-PGD from {1, 4, 8, 16}. We compare the empirical results with the certified accuracy reported in our main paper toNeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: 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.

Reviews: review: paper_summary: paper_summary: This paper introduces a novel method based on random smoothing to improve the certified robustness of Deep Equilibrium Models (DEQs), a promising type of implicit neural network.

Directly applying random smoothing to DEQs incurs high computational costs. To overcome this issue, the authors leverage the properties of DEQs and design a serialized random smoothing (SRS) strategy. This method uses the output from one noisy input as the starting point for the next, significantly accelerating convergence.

Subsequently, to eliminate the dependence between noisy samples created by SRS, the authors introduce Correlation-Eliminated Certification, a new method to obtain certified radius estimation.

Experimental results on CIFAR-10 and ImageNet demonstrate the efficiency of the proposed model.
strength_weakness: strength_weakness: The proposed method is only applicable to DEQs. Although DEQs are a promising architecture, they have not been as widely applied as explicit neural networks or proven to scale well, limiting the scope of this paper. Moreover, the paper does not include a performance comparison of the proposed against other non-DEQ models.
questions: questions: - On line 52, "Due to the conservative certification, IBP and LBEN cannot be generalized to large-scale datasets (e.g., ImageNet)." There seems to be a logical gap in this sentence. Could the authors elaborate more on this point? Is there any reference that can back up this claim?
- Is the certified robustness of the proposed model (SRS-DEQ) competitive against the certified robustness of other non-DEQ architectures with random smoothing? For example, the paper "CERTIFIED ROBUSTNESS FOR DEEP EQUILIBRIUM MODELS VIA INTERVAL BOUND PROPAGATION" compares their models with other explicit neural networks. Such comparisons are important for the audience to position the proposed model in a larger context.
- Are there any insights or techniques from this paper that can be applied to improve other performance aspects of DEQs (besides certified robustness) or improve non-DEQ models?
limitations: limitations: na
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The conceptual novelty may not be that significant since randomized smoothing is a well-known technique in the first place. 

2. By the end of the paper, it is unclear whether the results in this paper have achieved SOTA certified robustness among all networks. I mean, does the certified robust accuracy of DEQ reach to the level of existing results on feed-forward networks using standard RS?
questions: questions: 1. Can the authors clarify the difficulty and novelty of implementing their method for large-scale datasets like ImageNet?

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

3. Can the authors further justify the unique novelty and technicality of their contribution?
limitations: limitations: The authors have partially addressed limitations in their paper. However, there seems to lack a substantial discussion on broader societal impacts.
paper_summary: paper_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.
strength_weakness: strength_weakness: * It would be nice to provide more careful definitions. One definition that should be in the paper is that of $\ell_2$-norm certified radius, as is defined for example in [1]. A pointer to a paper which introduces this is also missing. Generally speaking, although [1] also uses similar notation to this paper, it is a bit confusing to write $c_A$ without writing it as a function of $x$. My understanding is that $c_A$ is the most likely class given some sample $x$, so as a reader this is a bit confusing to not write it as a function of $x$. Another definition which seems to be crucial in your paper is LowerConfBound (e.g. Equation (12)) and hence it would be nice to provide the definition rather than to point the reader to [1]. Furthermore, there are less crucial definitions such as $K$, in Equation (10), which are not defined (but I assume represents the number of samples from SRS, $K < N$). Furthermore, can you please make the notation consistent between Section 3.3 and Appendix A which contains the proof for Theorem 3.1? Specifically there is lower-case $y$ in Appendix A and the subscript notation for the labels is also different between the two sections.
* Using a model with Jacobian regularization seems as though it might be more suitable for a certification method. It would be nice to provide more justification as regards to this choice, and how the method would perform on a MDEQ trained without Jacobian regularization.


[1] Cohen, J., Rosenfeld, E., and Kolter, Z. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pp. 1310–1320. PMLR, 2019

Some notes: 
* Lines 49-54 introduce acronyms that are not defined
* Neyman-Pearson is spelled incorrectly on line 108
* Figure 5 caption: converted -> converts. The sentence starting with “For instance” does not read well. Overall, could you write your caption a bit more clearly? 
* Line 574: missing period
* Algorithm 1: line 13 Should say Predict Y_g? It seems as though some indexing is also missing. Also, it is not clear to me what the relationship between the  total number of samples is as the number of samples that is used for $p_m$ in Algorithm 1.
questions: questions: 1. What is the effect of using a model trained with Jacobian regularization on your method? Do you think this is crucial for certifying a DEQ?
2. What is the relationship between the number of samples that are checked with the DEQ in Line 13 of Algorithm 1, and the total number of samples obtained via SRS?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: In the process of correlation-eliminated certification, this paper requires the use of standard DEQs to drop unreliable predictions, which necessitates additional memory overhead for standard DEQs during actual deployment.
questions: 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: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: I don't find major drawbacks in the approach and the evaluations. Below are some minor concerns:

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

[1] Salman et al., Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers.
[2] Jeong et al., Confidence-aware Training of Smoothed Classifiers for Certified Robustness.
questions: questions: See weakness. Below are some additional questions:

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

Comments: title: Thank you
Thank you
Thank you
Thank you
Thank you
Thanks for the response
comment: Thank you very much for your positive feedback and reconsidering our submission.

If you have any further concerns, please don't hesitate to let us know.
Thank you for the detailed response. This addresses my concerns, so I’ll be raising my score to accept.
Thank you very much for your positive feedback. We appreciate your thoughtful review and are glad that our work met your expectations. If you have any additional comments or suggestions, we would be happy to address them.
Thank you for answering my questions and for addressing my concerns. I maintain my recommendation to accept the paper.
Thank you very much for reconsidering our submission. We will promptly incorporate the related works you mentioned.

If you have any further concerns, please don't hesitate to let us know.
Thank you very much for reconsidering our submission. 

If you have any further concerns, please don't hesitate to let us know.
Thank you very much for reconsidering our submission. We will promptly incorporate the related works you mentioned.

If you have any further concerns, please don't hesitate to let us know.
Thanks for addressing my comments. I have raised my score to 7.
Thank you for addressing all my questions with experiments and clarification. I have raised my score accordingly. 

I found your response to Question 3 especially inspiring. I think that adding a paragraph in the related work section discussing the “DEQ fixed-point reuse” technique would broaden the appeal of this paper, and effectively position the paper's core technique within its context. For example, besides the Bayesian inference example that you gave, [1] exploited fixed-point reuse in the diffusion process, and [2] applied the technique to optical flow estimation.

[1] Bai, Xingjian, and Luke Melas-Kyriazi. "Fixed Point Diffusion Models." CVPR, 2024.

[2] Bai, Shaojie, Zhengyang Geng, Yash Savani, and J. Zico Kolter. "Deep Equilibrium Optical Flow Estimation." CVPR, 2024.
Thanks for the detailed rebuttal from authors. This clears my concerns. I will raise my score to accept.