Average Certified Radius is a Poor Metric for Randomized Smoothing
Authors: Chenhao Sun
Yuhao Mao
Mark Niklas Mueller
Martin Vechev
Venue: ICML 2025 poster (2025)
Keywords: randomized smoothing
metric
average certified radius
Primary area: deep_learning->robustness
TL;DR: We show that the popular average certified radius metric is improper to evaluate randomized smoothing, and suggest new metrics in replacement.

Abstract: Randomized smoothing (RS) is popular for providing certified robustness guarantees against adversarial attacks. The average certified radius (ACR) has emerged as a widely used metric for tracking progress in RS. However, in this work, for the first time we show that ACR is a poor metric for evaluating robustness guarantees provided by RS. We theoretically prove not only that a trivial classifier can have arbitrarily large ACR, but also that ACR is extremely sensitive to improvements on easy samples. In addition, the comparison using ACR has a strong dependence on the certification budget. Empirically, we confirm that existing training strategies, though improving ACR, reduce the model's robustness on hard samples consistently. To strengthen our findings, we propose strategies, including explicitly discarding hard samples, reweighing the dataset with approximate certified radius, and extreme optimization for easy samples, to replicate the progress in RS training and even achieve the state-of-the-art ACR on CIFAR-10, without training for robustness on the full data distribution. Overall, our results suggest that ACR has introduced a strong undesired bias to the field, and its application should be discontinued in RS. Finally, we suggest using the empirical distribution of $p_A$, the accuracy of the base model on noisy data, as an alternative metric for RS.

Average Certified Radius is a Poor Metric for Randomized Smoothing
Chenhao Sun Yuhao Mao
Mark Niklas Müller
Martin Vechev
Abstract
Density
Randomized smoothing (RS) is popular for pro- viding certified robustness guarantees against ad- versarial attacks. The average certified radius (ACR) has emerged as a widely used metric for tracking progress in RS. However, in this work, for the first time we show that ACR a poor metric for evaluating robustness guarantees pro- vided by RS. We theoretically prove not only that trivial classifier can have arbitrarily large ACR, but also that ACR is extremely sensitive to im- provements on easy samples. In addition, the comparison using ACR has a strong dependence on the certification budget. Empirically, we con- firm that existing training strategies, though im- proving ACR, reduce the model's robustness on hard samples consistently. To strengthen findings, we propose strategies, including ex- plicitly discarding hard samples, reweighing the dataset with approximate certified radius, and ex- treme optimization for easy samples, to repli- cate the progress in RS training and even achieve the state-of-the-arr ACR CIFAR-10, without training for robustness on the full data distribu- tion. Overall, our results suggest that ACR has introduced a strong undesired bias to the field, and its application should be discontinued in RS. Finally, we suggest using the empirical distribu- tion of PA. the accuracy of the base model on noisy data, as alternative metric for RS.
Ganssian RS Training
0.5
P4
Figure 1: Conceptual illustration of the effect of RS training.
of adversarial attacks which try to construct a perturbation that manipulates the model (Athalye et al., 2018), certified defenses have been proposed to provide robustness guaran- tees. While deterministic certified defenses (Gowal et al., 2018; Mirman et al., 2018; Shi et al., 2021; Müller al., 2023; Mao al., 2023; 2024a; De Palma et al.; Balauca et al., 2024) incur no additional cost at inference-time, ran- domized certified defenses scale better with probabilistic guarantees at the cost of multiplied inference-time com- plexity. The most popular randomized certified defense is Randomized Smoothing (RS) (Lécuyer et al., 2019; Cohen et al., 2019), which certifies a smoothed classifier given the accuracy of base model noisy data, PA-
To train better models with larger certified radius under RS, many training strategies have been proposed (Cohen et al., 2019; Salman et al., 2019; Jeong & Shin, 2020; Zhai et al., 2020; Jeong et al., 2023). Average Certified Radius (ACR), defined to be the average of the certified radii over each sample in the dataset, has been common metric to eval- uate the effectiveness of these methods. Although some studies refrained from using ACR in their evaluation unin- tentionally (Carlini et al., 2023; Xiao et al., 2022), the in- herent limitation of ACR remains unknown. As a result, the community remains largely unaware of these issues, result- ing subsequent research relying on ACR continuously (Zhang et al., 2023; Jeong Shin, 2024). However, in this work, we show that ACR is poor metric for evaluating the true robustness of given model under RS.
1. Introduction
Adversarial robustness, namely the ability of model to resist arbitrary small perturbations to its input, is crit- ical property for deploying machine learning models in security-sensitive applications. Due to the incompleteness
'qqual contribution 'Department of Computer Science, ETH Zurich, Switzerland LLogicStar.ai. Correspondence to: <chen- sun @ student.ethz.ch, maa, martin, vechev ) @ enf.ctth..ch. mark @ logicstar.aiz.
Main Contributions
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
We theoretically prove that with a large enough certi- fication budget, ACR of trivial classifier can be arbi- trarily large, and that with the certification budget com-

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
monly used in practice, an improvement on easy inputs contributes much more ACR than on hard inputs, more than 1000x in the extreme case ($4.1 and $4.2).
easy inputs and apply different loss for each class. While these methods all improve ACR, this work shows that ACR is poor metric for robustness, and that these training algo- rithms all introduce undesired side effects. This work is the first to question the development of RS training strategies evaluated with ACR and suggests new metrics as alterna- tives. While there exists various ways for RS certification (Cullen et al., 2022: Li al., 2022), this work only focus on the certification algorithm proposed by Cohen et al. (2019), which is the most widely used in the literature.
We empirically compare RS training strategies Gaus- sian training and show that all current RS training strategies are actually reducing the accuracy on hard inputs where PA is relatively small, and only focus on easy inputs where PA is very close to to increase ACR ($4.3). Figure conceptually visualizes this effect.
Based on these novel insights, we develop strategies to replicate the advances in ACR by encouraging the model to focus only on easy inputs. Specifically, we discard hard inputs during training, reweight the dataset with their contribution to ACR, and push PA extremely close to 1 for easy inputs via adversarial noise selection. With these simple modifications to Gaussian training, we achieve the new SOTA in ACR on CIFAR-10 and competitive ACR on IMAGENET without targeting ro- bustness for the general case ($5 and $6).
To better understand the application of ACR, we conduct a literature review in RS for publications on top confer- ences (ICML, ICLR, AAAL, NeurlPS), ranging from 2020 (since the first evaluation with ACR) to 2024 (until this work). We only include works that use the certification algorithm proposed by Cohen et al. (2019) and propose general- purppss dataset-agnostic RS algorithms. We iden- tify 13 works with the specified criteria, and report for each of them (1) whether ACR is evaluated, (2) whether uni- versal improvement in certified accuracy is achieved at all radii, (3) whether a customized base model is used (either parameter tuning or architecture design) and (4) whether SOTA achievement is claimed. The result is shown in Ta- ble 1. Among them, we find 10 works that customize the model and claim SOTA, which is the focus of our study. 8 of them evaluate with ACR, and 7 of them claim SOTA solely based on ACR, i.c., claim SOTA without universal improvement in certified accuracy at various radii. There- fore, we conclude that ACR is of great importance to the field, and the practice of claiming SOTA based ACR is widely spread.
Overall, our work proves that the application of ACR should be discontinued in the evaluation of RS. In partic- ular, we suggest using the empirical distribution of pa as more informative metrics, and encourage the community to evaluate RS training more uniformly ($7). We hope this work will motivate the community to permanently abandon ACR and inspire future research in RS.
2. Related Work
Randomized Smoothing (RS) is a defense against adver- sarial attacks that provides certified robustness guarantees (Lécuyer al., 2019; Cohen al., 2019). However, to achieve strong certified robustness, special training strate- gies tailored to RS are essential. Gaussian training, which adds Gaussian noise to the original input, is the most com- mon strategy, as it naturally aligns with RS (Cohen et al., 2019). Salman et al. (2019) propose to add adversarial at- tacks to Gaussian training, and Li et al. (2019) propose regularization control the stability of the output. Salman et al. (2020) further shows that it is possible to exploit pretrained non-robust classifier to achieve strong RS certi- fied robustness with input denoising. Afterwards, Average Certified Radius (ACR), the average of RS certified radius over the dataset, is commonly used to evaluate RS training: Zhai et al. (2020) propose an attack-free mechanism that di- rectly maximizes certified radi;; Jeong& & Shin (2020) pro- pose regularization to improve the prediction consistency; Jeong et al. (2021) propose to calibrate the confidence of smoothed classifier; Horváth et al. (2022) propose to use ensembles as the base classifier to reduce output variance; Vaishnavi et al. (2022) apply knowledge transfer on the base classifier; Jeong et al. (2023) distinguishes hard and
3. Background
In this section, we briefly introduce the background re- quired for this work.
Adversarial Robustness the ability of a model resist arbitrary small perturbations to its input. Formally, given an input set S(x) and model J. ʃ is adversarially robust within S(x) iff for every I2, E S(x), f(x1) = f(z2). In this work, we focus on the L2 neighborhood of an input, i.c., S(z) = (x(x) = {x' | ||x - 2'112 I c} for a given 2 0. For a given (x. y) from the dataset (X) f is robustly correct iff Var E S(x), f(x') -
Randomized Smoothing constructs smooth classifier fxx given base classifier f, defined as follows: f(x) == arg max.ey (1==) (2 + 6) = c). Intuitively, the smooth classifier assigns the label with maximum prob- ability in the neighborhood of the input. With this for- mulation, Cohen et al. (2019) proves that f is adversar- ially robust within BA( when Pa 2 0.5, where R(*,pA) == o (PA). d is the cumulative distribution
2

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
Literature
Use ACR
Universal improvement
Claim SOTA
Customized model
Zhai et al. (2020)
Jeong & Shin (2020)
Awasthi et al. (2020)
Jeong et al. (2021)
Horváth et al. (2022)
Chen et al. (2022)
Vaishnavi et al. (2022)
Yang ct al. (2022)
Carlini et al. (2023)
Jeong et al. (2023)
Wu et al. (2023)
Li al. (2024)
Wang et al. (2024)
Table 1: A literature survey in Randomized Smoothing for publications top conferences, ranging from 2020 to 2024. It only includes works that use the certification method proposed by Cohen et al. (2019) and propose general-purpose datnset-agnostic RS algorithms.
function of the standard Gaussian distribution N (O, 1), and PA := max.ey PP (f + d) = <) is the prob- ability of the most likely class. Average Certified Radius (ACR) is defined as the average of ((zxpa)1(f(=) y) over the dataset, where 1(.) is the indicator function. In practice, PA cannot be computed exactly, and an estimation PA such that F(AA 2 PA) 2 1 - a is substituted, where a is the confidence threshold. Thus, AA is computed based on N trials for the event (x = c). We call N the certi- fication budget, which is the number of queries the base classifier f to estimate PA- Since RS certifies robustness based the accuracy of the base model on samples per- turbed by Gaussian noise, Gaussian training, which aug- ments the train data with Gaussian noise, is the most intu- itive method to train the base model for RS. Specifically, it optimizes
Finally, we empirically show that due to the above weak- ness of ACR, all current RS training strategies evaluated with ACR reduce the accuracy on hard samples and only focus on easy samples ($4.3), improving ACR at the cost of performance on hard samples.
4.1. Trivial Classifier with Infinite ACR
In Theorem I below we show that, for every classification problem, there exists trivial classifier with infinite ACR given enough budget for certification, while such classi- fier can only robustly classify samples from the most likely class in the dataset and always misclassifies samples from other classes
Theorem 1. For every M 0 and a > 0, there exists trivial classifier which always predicts the same class with a certification budget N >> O, such that the ACR of f is greater than M with confidence at least 1 a.
1 m 1=1
arg min ((.)))(()))) 8
L(x + 5,:
The proof of Theorem is deferred to App. A.I. De- spite an intuitive proof, Theorem reveals an important fact: ACR can be arbitrarily large for classifier with large enough certification budget. Further, trivial classifier can achieve infinite ACR with minimal robustness on all but one classes. Therefore, the ACR metric presented in the literature is heavily associated with the certification bud- get; when the certification budget changes, the order of ACR between models may change as well, since inputs with lower P. require larger budget to certify. For exam- ple, given a perfectly balanced binary dataset and N 50, = 0.001, o 1, trivial classifier can achieve ACR equals 0.565, while another classifier with ery input can only achieve ACR equals 0.544, making the trivial classifier the better one. However, when N in- creased to 100, the latter achieves ACR equals 0. 0,756, sur-
where & are sampled from NN00, uniformly ran- dom, is the number of samples and T. is the cross en- tropy loss. Due to space constraints, we omit the details of other training strategies for RS, and refer interested readers to Cohen et al. (2019); Salman et al. (2019); Jeong & Shin (2020); Zhai et al. (2020); Jeong et al. (2023).
4. Weakness of ACR and the Consequence
We now first theoretically show that ACR can be arbitrar- ily large for a trivial classifier, assuming enough budget for certification ($..1). We then demonstrate that with real- istic certification budget, an improvement on easy samples could contribute more than 1000 times to ACR than the same magnitude of improvement on hard samples ($4.2).
0.9 on ev-
3

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
r
10 PPA
dr
Method
ACR
easy
hard
easy / hard
Gaussian
0.56
10.10
22.67
0.45
3-
SmoothAdv
0.68
5.60
5.62
1.00
10a
Consistency
0.72
14.99
19.32
0.78
2
SmoothMix
0.74
11.72
11.79
0.99
10a-
1-
CAT-RS
0.76
30.45
7.12
4.28
0-
10
0.0
0.5
1.0
0.6
0.8
1.0
Table 2: The average model parameters gradient 12 norm of easy (PA > 0.5) and hard (pa < 0.5) samples for models trained with different algorithms and o 0.5, along with their relative magnitude (easy / hard). The corresponding ACR is provided for reference.
P4
PA
())
(b)
Figure 2: Certified radius r and its sensitivity врд
är against pa-
Note the log scale of y axis in Figure 2b. N is set to 10" a is set to 0.001, and a is set to 1.
than achieving PA 0.9 on every input when evaluated with ACR, which is misaligned with our intuition. This toy example highlights again that the unmatched contribution to ACR from easy and hard samples leads to biases.
passing the trivial classifier which has ACR equals 0.750, Interestingly, when we further increase N to 200, the trivial classifier achieves ACR equals 0.913, surpassing the latter which has ACR equals 0.909, thus the order is reversed again. This toy example showcases the strong dependence of the evaluation results on the certification budget, espe- cially the comparative order of different models. This is problematic in practice, as the budget usually differs de- pending on the task and the model, resulting uncertainty when choosing training strategies evaluated based on ACR.
It is important to note that, while improvements in PA for easy samples contribute disproportionately more to the overall ACR compared to improvements on hard samples, this does not imply that increasing PA for easy samples it- self is casier. However, we hypothesize that focus im- proving PA on easy samples can increase ACR. As we will show in $5 and $6, this hypothesis holds true empirically.
4.2. ACR Prefers Improving Easy Samples
4.3. Selection Bias in Existing RS Training Algorithms
We now discuss the effect of ACR with a constant budget and fixed a. We follow the standard certification setting in the literature, setting N 10 and 0.001 (Cohen et al., 2019). With this budget, the maximum certified ra- dius for data point is R(E,PA 3.8o. However, we will show that @R(..Pa) grows ex- tremely fast, exceeding 1000 when pa + and close to 0 when PA- + 0.5.
We have shown that ACR strongly prefers easy samples in $4.2. However, since ACR is not differentiable with respect to the model parameters because it is based on counting, RS training strategies usually do not directly apply ACR as the training loss. Instead, they optimize various surrogate ob- jectives, and finally evaluate the model with ACR. Thus, it is unclear whether and to what extent the design of training
1) o ( x
algorithms is affected by the ACR metric. We now em- pirically quantify the effect, confirming that the theoretical weakness of ACR has introduced strong selection biases in existing RS training algorithms. Specifically, we show that SOTA training strategies reduce PA of hard samples and put more weight (measured by gradient magnitude) on easy samples when compared to Gaussian training.
Without loss of generality, we set a 1 and denote R(I, r. Figure shows r and ar against While 3p4
Ör r' remains bounded by a constant 3.8, θрд grows extremely fast when PA approaches 1. As result, increasing PA from 0.99 to 0.999 improves from 2.3 to 3.0, matching the im- provement achieved by increasing PA from 0 to 0.76. Fur- ther, when PA- < 0.5, the data point will not contribute to ACR at all, thus optimizing ACR will not increase PA with a local optimization algorithm like gradient descent. Therefore, it is natural for RS training to disregard inputs with PA- < 0.5, as their ultimate goal is to improve ACR.
Figure 3 shows the empirical cumulative distribution of pA for models trained with SOTA algorithms and Gaussian training on CIFAR-10. Clearly, for various a, SOTA al- gorithms have higher density than Gaussian training at PA close to zero and one. While they gain more ACR due to the improvement on easy samples, hard samples are con- sistently underrepresented in the final model compared to Gaussian training. The same results hold on IMAGENET (Figure 11 in App. E.2). As a result, Gaussian training has higher P(pA 2 0.5) (clean accuracy), and SOTA al- gorithms exceed Gaussian training only when PA passes a certain threshold, i.e., when the certified radius relatively
We use the same toy example as in $4.1 to further demon- strate this problem. If we further increase N beyond 200, we can find, surprisingly, that the classifier with PA = 0.9 for every input always has a smaller ACR than the trivial classifier. This means that achieving PA = 1 on only half of the dataset and getting PA = 0 for the rest is "more robust"
4

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
ECDF
ECDF
ECDF
1.0
1.0
1.0
Gaussian
0.5
Smooth
0.5
0.5
Consisteney
SmoothMix
CAT-RS
0.0
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
P4
p4
(a) a 0.25
(b) a 0.5
(c) = 1.0
Figure 3: The empirical cumulative distribution (ECDF) of Pa on CIFAR-10 for models trained and certified with various a with different training algorithms.
large. This is problematic in practice, indicating that ACR does not properly measure the model's ability even with a fixed certification setting. For example, a face recognition model could have a high ACR but consistently refuse to learn some difficult faces, which is not acceptable in real- world applications.
points has PA < 0.5 after training converges on CIFAR- 10. Therefore, we propose to discard hard samples directly during training. so that they explicitly have diminished ef- feet on the final training convergence. Specifically, given a warm-up epoch E, and a confidence threshold pt. we dis- card all data samples with PA < Pt epoch F,- We fix the number of steps taken by gradient descent and re-iterate on the distilled dataset when necessary to minimize the differ- ence in training budget. After the discard, Gaussian train- ing also ignores hard inputs, similar to SOTA algorithms.
To further quantify the relative weight between easy and hard samples indicated by each training algorithm, we mea- sure the average gradient 12 norm of easy and hard samples for model parameters trained with different algorithms and 0.5, as a proxy for the sample weight. Intuitively, sam- ples with larger gradients on parameters contribute more to training and thus more important the final model. As shown in Table 2, Gaussian training puts less weight on easy samples than hard samples, which is natural as easy samples have smaller loss values. However, SOTA algorithms put more weight on easy samples compared to Gaussian training, e.g., the relative weight between easy and hard samples is 4.28 for the best ACR baseline, CAT- RS (Jeong al., 2023), while for Gaussian training it is 0.45. This confirms that SOTA algorithms indeed prioritize easy samples over hard samples, consistent with the theo- retical analysis in $4.2.
5.2. Data Reweighting with Certified Radius
ACR relates non-linearly to Pa. and the growth of the cer- tified radius is much faster when improving casy samples. We account for this by reweighing the data points based on their certified radius. Specifically, we use the approximate (normalized) certified radius as the weight of the data point, realized by controlling the sampling frequency of each data point. The weight w of every data point x is defined as:
PA = LOWERCONFBOUNDDC....I a) (- (Pmin)))
5. Replicating the Progress in ACR
In $4, we find that ACR strongly prefers easy samples, and this bias has been introduced to the design of RS training strategies. This questions that whether explicitly focusing on easy data during training can effectively replicate the increase in ACR gained by years spent on the development of RS training strategies. In this section, we propose three intuitive modifications on the Gaussian training, answering this question affirmatively.
where C' is the count of correctly classified noisy sam- ples and Punin is the reference probability threshold. Note that the estimation of ΩA aligns with the certification. We clip the weight at to avoid zero weights. To minimize computational overhead, we evaluate ΩA every 10 epoch with N 16 and a 0.1 throughout the paper. We set Pmii 0.75 because this is the minimum probabil- ity that has positive certified radius under this setting. The sampling weight curve is visualized in Figure 4. After the reweight, ACR has an approximately linear connection to PA when w > 1, and easy samples are sampled more fre- quently than hard samples so that Gaussian training also improves PA further for easy samples.
5.1. Discard Hard Data During Training
Samples with low PA contribute little to ACR, especially those with Pa 0.5 which have no contribution all ($4.2). Further, as shown in Figure 3, 20%-50% of data
5

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
Gradient norm
Normalized Rtdius
10a
Sampling Weight
8
10a
4-
(0.75,
0)
0.0
0.5
1.0
10-2
11 0.40
P4
0.0
0.5
1.0
Figure 4: Certified radius (divided by the value at pa 0.75) and the sampling weight of the data against pa.
(a) Before adaptive attack
Gradient norm
Algorithm Adaptive Attack
function ADAPTIVEADY(S.......... 8' < 6 for /. = 1 to to T do if f(x + 8*) + then
10e
break end if
8' one step PGD attack on 5 with step size
10a
R²
0.19
8 < 1-18112- --" 81/1|0
0.0
0.5
1.0
end for return 8
PA
After adaptive
end function
Figure Comparison of the gradient norm distributions for dif- ferent PA before and after the adaptive attack, a = 0.5. Note the log scale of axis.
5.3. Adaptive Attack on the Sphere
SOTA algorithms re-balance the gradient norm of easy and hard samples in contrast to Gaussian training (Table 2). In addition, when PA is close to Gaussian training can hardly find useful noise sample to improve PA further. To tackle this issue, we propose to apply adaptive attack on the noise samples to balance samples with different PA- Specifically, we use Projected Gradient Descent (PGD) (Madry et al., 2018) to find the nearest noise to the Gaus- sian noise which can make the base classifier misclassify. Formally, construct
where PN is the probability density function of the isometric Gaussian distribution with mean O and covariance o² la.
every
The proof of Theorem is deferred to App. A.2. Figure 5 visualizes the gradient norm distributions for different pA- before and after the adaptive attack.
observe that the adaptive attack balances the gradient norm of easy and hard samples. Before the attack, the gradient norm of easy sam- ples is much smaller than that of hard samples, while af- ter the attack, the gradient norm of easy samples is am- plified without interfering the gradient norm of hard sam- ples. Therefore, with the adaptive attack, Gaussian train- ing obtains a similar gradient norm distribution to SOTA algorithms, and can find effective noise samples more ef- ficiently. Pseudocode of the adaptive attack is shown in Algorithm and more detailed description is provided in App. C.3.
8"
arg min 8(x+8)yfe, 1
| 60ll2,
where 5n is a random Gaussian noise sample. Note that when x + 5g makes the base classifier misclassify, have 5" do. thus hard inputs are not affected by the adaptive attack. In addition, we remark that we do not constrain 8" to be in the neighborhood of ôu which is adopted by CAT-RS (Jeong et al., 2023); instead, we only maintain the 22 norm of the noise, thus allowing the attack to explore a much larger space. This because for every 8' such that | 1| [|8o|12, the value of the probability density function 5* is the same dg. We formalize this fact in Theorem 2.
5.4. Overall Training Procedure
We now describe how the above three modifications combined. At the beginning, we train the model with the Gaussian training (Cohen et al., 2019), which samples m noisy points from the isometric Gaussian distribution uni- formly at random and uses the average loss of noisy inputs as the training loss. When we reach the pre-defined warm-
Theorem 2. Assume 82 E Rdd and on + 82. If |/2 ||52||2, then ( = PN (82) for
6

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
up epoch E,,, all data points with PA < Pt are discarded, and the distilled dataset is used thereafter, as described in $5.1. After this, we apply dataset reweight and the adap- tive attack to training. Specifically, every 10 epoch after Eg (including F,,), we evaluate the model with the proce- dure described in $5.2 and assign the resulting sampling weight to each sample in the train set. In addition, we use the adaptive attack described in $5.3 to generate the noises used for training. The pseudocode is shown in Algorithm 2 in App. C.I.
Gaussian training suggests that existing approaches do not fully converge on strategies exploiting the weakness of ACR, and that the field should re-evaluate RS training strategies with better metrics instead of discarding them completely.
Ablation Study, We present a thorough ablation study in Table 5. When applied alone, all three components of our method improve ACR compared to Gaussian training. Combing two components arbitrarily improves the ACR compared to using only one component, and the best ACR is achieved when all three components are combined. This confirms that each component contributes to the improve- ment of ACR. In addition, they mostly improve the certi- fied accuracy at large radii and reduce certified accuracy at small radii, which is consistent with our intuition that fo- cusing on easy inputs can improve the ACR. More ablation on the hyperparameters is provided in App. D.
6. Experimental Evaluation
We now evaluate our method proposed in $5 extensively. Overall, simply focusing on easy samples is enough to replicate the advances in RS training strategies, some- times even surpassing existing SOTA algorithms, e.g.. on CIFAR-10. 10. Experiment details, including hyperparam- eters, are provided in App. C.I.
7. Beyond the ACR Metric
Baselines. We compare our method to the following meth- ods: Gaussian (Cohen et al., 2019), SmoothAdv (Salman et al., 2019), MACER (Zhai et al., 2020), Consistency (Jeong & Shin, 2020), SmoothMix (Jeong et al., 2021), and CAT-RS (Jeong et al., 2023). We always use the trained models provided by the authors if they are available and otherwise reproduce the results with the same setting as the original paper. For CIFAR-10, 10, we set m = 4 for Gaussian training and our method, since this is the standard setting for SOTA methods (Jeong et al., 2023).
This work rigorously shows that the weakness of the main evaluation metric ACR has introduced strong biases into the development of RS training strategies. Therefore, the field has to seek better alternative metrics evaluate the robustness of models under RS. When the certification set- ting (budget N and confidence a) is fixed, we suggest us- ing the best certified accuracy at various radii. Specifi- cally, models certified with smaller a tend to achieve higher certified accuracy at smaller radii, whereas models certi- fied with larger usually have higher certified accuracy at larger radii. To extensively illustrate the power of the developed training strategies and avoid such tradeoff and dependence on a,, we suggest reporting the best certified accuracy across o at each radius. In other words, this rep- resents the setting where one first fixes an interested radius, and then try to develop the best model with the highest certified accuracy at the pre-defined radius. Notably, sev- eral studies already adopt this strategy (Carlini al., 2023; Xiao et al., 2022), avoiding the weakness of ACR unin- tentionally. This evaluation is also consistent to the prac- tice in deterministic certified training (Gowal et al., 2018; Mirman et al., 2018; Shi et al., 2021; Müller et al., 2023; Mao et al., 2023; 2024a;b; De Palma et al.; Balauca et al., 2024). Furthermore, the community should also consider RS methods with a as variable rather than hyperparam- eter, thus effectively removing the dependence on ar. While there are some preliminary works in this direction (Alfarra et al., 2022; Wang et al., 2021), they usually break the theo- retical rigor (Súkeník et al., 2022). Rencent works propose sound methods to certify with various a (Súkeník et al., 2022; Jeong & Shin, 2024). However, room for improve- ment remains, and further research is needed.
Main Result. Table 3 shows the ACR of different methods on CIFAR-10. We further include the results of indepen- dent runs in App. 1 to validate the significance of our re- sults. Our method consistently outperforms all baselines on ACR, which confirms the effectiveness of our modi- fication to Gaussian training in increasing ACR. Further, our method successfully increases the certified accuracy at large radius, as we explicitly focus on easy inputs which is implicitly taken by other SOTA methods. Figure 6 further visualizes certified accuracy at different radii, showing that at small radii, SOTA methods (including ours) are system- atically worse than Gaussian training, while at large radii, these methods consistently outperform Gaussian training.
Table shows the results on IMAGENET, which is orga- nized in the same way Table 3. Our method repli-
cates large portion of the ACR advances. Coneretely, for
= 0.25, the proposed method recovers (0.529 0.476) / /0.532- 0.476)= = 94.6% of the advance; for o = 0.5, it recovers (0.842- - 0.733)/ (0.846 - 0.733) = 96.5%; for a = 1.0, it recovers (1.042 0.875) / (1.071 - 0.875) = 85.2%. This confirms that our results generalize across
datasets.
The success of our simple and intuitive modification to
When the certification setting varies, which is common in

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
Cetiifiel sommary
Certified aommar
Certifiee commrny
0.5
0.6
0.8
0.6
0.6
Gansiao
0.4
SmoothiAdv
0.4
0.4
MACER
Consaneury
0.2
0.2
SmaothiMi
0.2
CXT-RS
0.0
Oun
0.0
0.0
0.4
1.0
0.5
0.0
3.0
Cortified radius
Certifted redius
Certified radins
0.25
(b) 0.5
1.0
Figure 6: Certified radius-accuracy curve on CIFAR-IO 10
different methods.
0
Methods
ACK
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussian
0.486
81.3
66.7
50.0
32.4
0.0
0.0
0.0
0.0
0.0
0.0
0.0
MACER
0.529
78.7
68.3
55.9
40.8
0.0
0.0
0.0
0.0
0.0
0.0
0.0
SmoothAdv
0.544
73.4
65.6
57.0
47.5
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Consistency
0.547
75.8
67.4
57.5
46.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.25
SmoothMix
0.543
77.1
67.6
56.8
45.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
CAT-RS
0.562
76.3
68.1
58.8
48.2
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Ours
0.564
76.6
69.1
59.3
48.3
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Gaussian
0.562
68.7
57.6
45.7
34.0
23.7
15.9
9.4
4.8
0.0
0.0
0.0
MACER
0.680
64.7
57.4
49.5
42.1
34.0
26.4
19.2
12.0
0.0
0.0
0.0
SmoothAdv
0.684
65.3
57.8
49.9
41.7
33.7
26.0
19.5
12.9
0.0
0.0
0.0
Consistency
0.716
64.1
57.6
50.3
42.9
35.9
29.1
22.6
16.0
0.0
0.0
0.0
0.5
SmoothMix
0.738
60.6
55.2
49.3
43.3
37.6
32.1
26.4
20.5
0.0
0.0
0.0
CAT-RS
0.757
62.3
56.8
50.5
44,6
38.5
32.7
27.1
20.6
0.0
0.0
0.0
Ours
0.760
59.3
54.8
49.6
44.4
38.9
34.1
29.0
23.0
0.0
0.0
0.0
Gaussian
0.534
$1.5
44.1
36.5
29.4
23.8
18.2
13.1
9.2
6.0
3.8
2.3
MACER
0.760
39.5
36.9
34.6
31.7
28.9
26.4
23.8
21.1
18.6
16.0
13.8
SmoothAdv
0.790
43.7
40.3
36.9
33.8
30.5
27.0
24.0
21.4
18.4
15.9
13.4
Consistency
0.757
45.7
42.0
37.8
33.7
30.0
26.3
22.9
19.6
16.6
13.9
11.6
1.0
SmoothMix
0.788
42.4
39.4
36.7
33.4
30.0
26.8
23.9
20.8
18.6
15.9
13.6
CAT-RS
0.815
43.2
40.2
37.2
34.3
31.0
28.1
24.9
22.0
19.3
16.8
14.2
Ours
0.844
42.0
39.4
36.5
33.9
31.1
28.4
25.6
23.1
20.6
18.3
16.1
Table 3: Comparison of certified test accuracy (%) at different radii and ACR on CIFAR-10. The best and the second best
results are highlighted in bold and underline, respectively: for certified accuracy, we highlight those that are worse than Gaussian training at the same radius in gray.
Methods
ACR
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Gaussian
0.476
66.7
49.4
0.0
0.0
0.0
0.0
0.25
SmoothAdv
0,532
65.3
55.5
0.0
0.0
0.0
0.0
Ours
0.529
64.2
55.8
0.0
0.0
0.0
0.0
0.0
0.0
Gaussian
0.733
57.2
45.8
37.2
28.6
0.0
0.0
0.0
0.0
SmoothAdv
0,824
53.6
49.4
43.3
36.8
0.0
0.0
0.0
0.0
0.5
Consistency
0.822
55.0
50.2
44.0
34.8
0.0
0.0
0.0
0.0
SmoothMix
0.846
54.6
50.0
43.4
37.8
0.0
0.0
0.0
Ours
0.842
$5.5
48.6
43.8
37.6
0.0
0.0
Gaussian
0.875
43.6
37.8
32.6
26.0
19.4
14.8
12.2
9.0
SmoothAdv
1.040
40.3
37.0
34.0
30.0
26.9
24.6
19.7
15.2
Consistency
0.982
41.6
37.4
32,6
28.0
24.2
21.0
17.4
14.2
1.0
SmoothMix
1.047
39.6
37.2
33.6
30.4
26.2
24.0
20.4
17.0
CAT-RS
1.071
43.6
38.2
35,2
30.8
26.8
24.0
20.2
17.0
Ours
1.042
41.0
37.4
33.6
31.0
27.0
23.2
19.4
15.8
Table 4: Comparison of certified test accuracy (%) at differrntt radii and ACR on IMAGENET. This table is structured in the same way as Table 3.
8

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
discard
dataset weight adverserial
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
2.25
2.50
Gaussian
0.486
66.7
50.0
32.4
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.515
53.7
36.8
0.0
0.0
0.0
0.0
0.0
0.0
0.512
81.3
69.4
53.3
36.3
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.25
0.537
76.7
66.7
55.6
44.3
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.523
81.1
69.7
54.6
38.3
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.550
77.4
68.5
57.7
45.4
0.0
0.0
0.0
0.0
0.0
0.0
0.554
48.1
0.0
0.0
0.0
0.0
0.0
0.564
76.6
69.1
59.3
48.3
0.0
0.0
0.0
0.0
0.0
0.0
Gaussian
0.525
22.0
14.1
8.3
3.9
0.0
0.627
49.5
39.4
29.0
20.5
13.0
7.0
0.0
0.662
68.1
59.7
50.3
41.1
31.7
23.7
16.2
9.2
0.0
0.0
0.0
0.5
0.701
63.4
56.2
49.1
41.7
34.5
28.2
22.1
16.5
0.0
0.0
0.0
0.672
68.5
60.1
51.0
41.8
32.4
24.2
16.7
9.3
0.0
0.0
0.0
0.731
63.4
56.8
50.1
43.7
37.0
30.8
24.4
18.0
0.0
0.0
0.0
0.741
47.3
38.6
34.1
29.1
23.1
0.0
0.760
59.3
54.8
49.6
44.4
38,9
34.1
29.0
23.0
0.0
0.0
Gaussian
0.534
13.1
9.2
0.665
42.1
33.1
28.7
24.3
20.2
16.1
12.6
0.695
49.9
44.9
39.7
34,9
29.8
25.3
21.4
17.5
13.6
10.1
7.1
1.0
0.690
47.3
42.0
37.0
32.0
27.1
23.2
19.9
16.6
13.6
10.8
8.4
0.736
48.8
44.5
40.3
35.9
31.4
27.3
22,9
19.1
15.2
11.7
8.7
0.771
47.0
43.1
39.1
35.0
30.9
27.1
23.6
20.2
17.0
14.1
11.6
0.818
32.5
29.9
27.7
25.3
22.6
20.1
17.9
15.8
0.844
42.0
39.4
36.5
33.9
31.1
28.4
25.6
23.1
20.6
18.3
16.1
Table 5: Ablation study on each component in our method.
applying RS to practice, metrics are required to reflect the power RS training strategies under different certification budgets. To this end, we suggest reporting the empirical distribution of P. for large N, e.g., N 10 as com- monly adopted. This approximates the true distribution of PA nicely when N is large, and higher PA usually leads to a larger certified radius consistently under different certifi- cation budgets. To this end, as long as one model has larger P(pa 2 p) for every p E [0.5, 1] than another model, we can claim the former better consistently in different cer- tification settings. A case study is included in App. B to further demonstrate the usage and properties of the empiri- cal distribution of PA-
easy inputs contributes much more to ACR than the same amount of improvement on hard inputs. addition, the comparison results based on ACR varies when the certifi- cation budget changes, thus unsuitable for comparing al- gorithms. Empirically, we show that all state-of-the-art (SOTA) strategies reduce the accuracy on hard inputs and only focus on easy inputs to increase ACR. Based on these novel insights, we develop strategies to amplify Gaussian training by focusing only on easy data points during train- ing. Specifically, we discard hard inputs during training, reweigh the dataset with their contribution apply extreme optimization for easy inputs via adversarial noise selection. With these intuitive modifications to the simple Gaussian training, we replicate the effect of SOTA training algorithms and achieve the SOTA ACR. Overall, our results suggest the need for evaluating RS training with better metrics. To this end, we suggest reporting the empir- ical distribution of p for large N in replacement of ACR. We hope this work will inspire future research in this direc- tion and motivate the community to permanently abandon ACR in the evaluation of randomized smoothing.
ACR, and
While our modifications presented in $5 are not designed to improve robustness for the general data distribution, they show effectiveness in increasing certified accuracy at large radius. Other existing algorithms show similar effects. Therefore, it is important to note that the field has indeed made progress over the years. However, new metries which consider robustness more uniformly should be developed to evaluate RS, and algorithms that outperform at every ra- dius are encouraged. We hope this work can inspire future research in this direction.
Reproducibility Statement
Experimental details, including hyperparameters, datasets, and training procedures, are provided in App. C. Re- sult significance is confirmed in App. E.I. Code and models are available at https://github..co//ette acr-weakness.
8. Conclusion
This work rigorously demonstrates that Average Certified Radius (ACR) is poor metric for Randomized Smoothing (RS). Theoretically, we prove that ACR of a trivial clas- sifier can be arbitrarily large, and that an improvement on

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
Acknowledgements
Cullen, A., Montague, P., Liu, S., Erfani, S., and Rubin- stein, B. Double bubble, toil and trouble: enhancing cer- tified robustness through transitivity. Advances in Neu- ral Information Processing Systems, 15:19099-19112, 2022.
This work has been done as part of the EU grant ELSA (European Lighthouse on Secure and Safe AL. grant agree- ment no. 101070617) and the SERI grant SAFEAI (Certi- fied Safe, Fair and Robust Artificial Intelligence, contract no. MB22.00088). Views and opinions expressed are how- ever those of the authors only and do not necessarily re- flect those of the European Union or European Commis- sion. Neither the European Union nor the European Com- mission can be held responsible for them.
De Palma, A., Bunel, R. R., Dvijotham, K. D., Kumar, M. P., Stanforth, R., and Lomuscio, Expressive losses for verified robustness via convex combinations. In The Twelfth International Conference on Learning Represen- tations.
The work has received funding from the Swiss State Secre- tariat for Education, Research and Innovation (SERI).
Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T. A., and Kohli, P. On the effectiveness of interval bound propagation for training verifiably robust models. ArXiv preprint, abs/1810. 2018.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 770-778, 2016.
References
Horváth, M. Z., Müller, M. N., Fischer, M., and Vechev, M. T. Boosting randomized smoothing with variance re- duced classifiers. In ICLR. OpenReview.net, 2022.
Alfarra, M., Bibi, A., Torr, P. H., and Ghanem, B. Data dependent randomized smoothing, In Uncertainty in Ar- rificial Intelligence, pp. 64 44-74.7 PMLR, 2022.
Jeong, J. and Shin, J. Consistency regularization for cer- tified robustness of smoothed classifiers. In NeurIPS, 2020.
Athalye, A., Carlini, N., and Wagner, D. A. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In Proc. of ICML, 2018.
Jeong, J. and Shin, Multi-scale diffusion denoised smoothing. Advances in Neural Information Processing Systems, 36, 2024.
Awasthi, P., Jain, H., Rawat, A. S.,, and Vijayaraghavan, A. Adversarial robustness via robust low rank representa- tions. In Larochelle, H., Ranzato, M., Hadsell, R., Bal- can, M., and Lin, H. (eds.), Advances in Neural Informa- tion Processing Systems, volume 33, pp. 11391-11403. Curran Associates, Inc., 2020.
Jeong. J., Park, S., Kim, M., Lee, H., Kim, D., and Shin, J. Smoothmix: Training confidence-calibrate smoothed classifiers for certified robustness. In NeurIPS, pp. 2021.
Jeong. J., Kim, S., and Shin, Confidence-aware training of smoothed classifiers for certified robustness. In AAAI, pp. 8005- 8013. AAAI Press, 2023.
Balauca, S., Müller, M. N., Mao, Y., Baader, M., Fischer, M., and Vechev, M. Overcoming the paradox certified training with gaussian smoothing, 2024.
Lécuyer, M., Atlidakis, V., Geambasu, R., Hsu, D., and Jana, S. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, 2019. doi: 10. 00.1109/P2209.000444,
Carlini, N., Tramèr, F., Dvijotham, K. D., Rice, L., Sun, M., and Kolter, J. Z. (certified!!) adversarial robustness for free! In ICLR, 2023.
Chen, R., Li, Yan, J., Li, P., and Sheng, B. Input-specific robustness certification for randomized smoothing. In Proceedings of the AAAI Conference on Artificial Intel-
Li, B., Chen, C., Wang, W., and Carin, L. Certified ad- versarial robustness with additive noise. In Proc. of NeurlPS, 2019.
ligence, volume 36, pp.
2022.
Cohen, J. M., Rosenfeld, E., and Kolter, J. Z. Certified ad- versarial robustness via randomized smoothing. In Proc. of ICMI, volume 97, 2019.
Li, L.,, Zhang, J., Xie, T., and Li, B. Double sampling randomized smoothing. International Conference on Machine Learning, pp. 13163-13208. PMLR, 2022.
10

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
Li, Y., Chen, Z., Jin, K., Wang. J., Lei, J., Li, B., and Xiao, C. Consistency purification: Effective and eff- cient diffusion purification towards certified robustness. Advances in Neural Information Processing Systems. 37: 105017-105038, 2024.
Wang. Z., Zhou, Z., and Liu, W. Drf: improving certified robustness via distributional robustness framework. In Proceedings of the AAAI Conference Artificial Intel- ligence, volume 38, pp. 19752-15760, 2024.
Wu, Q. Ye, H., Gu, Y., Zhang, H., Wang, L., and He, D. Denoising masked autoencoders help robust classi- fication. In The Eleventh International Conference Learning Representations 2023.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In Proc. of ICLR. 2018.
Mao, Y., Müller, M., Fischer, M., and Vechev, M. Connect- ing certified and adversarial training. Advances in Neu- ral Information Processing Systems, 36:73422-7344 2023.
Xiao, C., Chen, Z., Jin, K., Wang, J., Nie, W., Liu, M., Anandkumar, A., Li, B., and Song, D. Densepure: Un- derstanding diffusson models towards adversarial robust- ness. arXiv preprint 2.xx:2221.003222 2022.
Yang. Z., Li, L., Xu, X., Kailkhura, B., Xie, T., and Li, On the certified robustness for ensemble models and beyond. In International Conference on Learning Rep- resentations, 2022.
Mao, Y., Balauca, S., and Vechev, M. Ctbench: A library and benchmark for certified training. ArXiv preprint, abs/2406. 048444406.04848, 2024a.
Mao, Y., Müller, M. N., Fischer, M., and Vechev, M. T. Un- derstanding certified training with interval bound propa- gation. In Proc. of. ICLR, 2024b.
Zhai, R., Dan, C.,, He, D., Zhang, H., Gong, B., Ravikumar, Hsieh, C., and Wang, L. MACER: attack-free and scalable robust training via maximizing certified radius. In ICLR. OpenReview.net, 2020.
Mirman, M., Gehr, T., and Vechev, M. T. Differentiable ab- stract interpretation for provably robust neural networks. In Proc. of ICML, volume 80, 2018.
Zhang, J., Chen, Z., Zhang, H.. Xiao, C., and Li, B. (DiffSmooth): Certifiably robust learning via diffusion models and local smoothing. In 32nd USENIX Secu- rity Symposium (USENIX Security 23), pp. 4787-4804, 2023.
Müller, M. N., Eckert, F., Fischer, M., and Vechev, M. Certified training: Small boxes are all you need. In Proc. ICLR, 2023.
Salman, H., J., Razenshteyn, I. P., Zhang, P., Zhang, H., Bubeck, S., and Yang, G. Provably robust deep learning via adversarially trained smoothed classifiers. In Proc. of NeurlPS, 2019.
Salman, H., Sun, M., Yang, G., Kapoor, A., and Kolter, Z. Denoised smoothing: A provable defense for pre- trained classifiers. In NeurIPS, 2020.
Shi, Z., Wang, Y., Zhang, H., Yi, J., and Hsieh, C. Fast certified robust training with short warmup. In Proc. of NeurIPS, 2021.
Súkeník, P., Kuvshinov, A., and Günnemann, S. Intriguing properties of ieput-dependent randomized smoothing. In International Conference on Machine Learning. PMLR,
2022.
Vaishnavi, P., Eykholt, K., and Rahmati, A. Accelerat- ing certified robustness training via knowledge transfer. In Advances in Neural Information Processing Systems, volume 35, pp. 5269-5281, 2022.
Wang, L., Zhai, R., He, D., Wang, L.,, and Jian, L. Pretrain- to-finetune adversarial training via sample-wise random- ized smoothing. 2021.

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
A. Deferred Proofs
ECDF
0.6
A.1. Proof of Theorem
0.4
Now we prove Theorem 1, restated here for convenience.
Gaussion
Theorem 1. For every M > 0 and O, there exists trivial classifier f which always predicts the same class with a certification budget N > 0, such that the ACR of f greater than M with confidence at least
0.2
Consistency CAT-RS
a.
0.50
0.75
1.00
PA
Proof. Assume we are considering a K-elass classification problem with a dataset containing samples. Let c* be the most likely class and X be the set of all samples with label c"; then there are least [T/K] samples in X due to the pigeonhole theorem. We then show that trivial classifier f which always predicts c* can achieve an ACR greater than M with confidence at least 1 with proper budget N.
Figure 7: The empirical distribution of pa on CIFAR- 10 with = 1.0 and N = 10 Note that this curve is independent of a.
ECDF
0.4
Gamedan
Consirtency
CNT RS
0.2
Note that PA = 1 for x E X* and thus the certified radius of x E X* is R(x) = - (a-N( Therefore, ACR
+ EE R(z)+ + E R[x)] 2 ExEx R(x) 2
0.0
2o Setting N
log (og()()///o)) + 1, we
0.0
0.5
1.0
1.5
2.0
log(())
Certified radius
have ACR M.
Figure 8: The certified accuracy-radius eurve under N 100 and a 0.01 on CIFAR-I0 with a = 1.0, converted from Figure 7.
A.2. Proof of Theorem 2
Now we prove Theorem 2, restated here for convenience.
practitioners to apply RS models in practice, as the cer- tification budget usually varies in different scenarios. Fi- nally, we re-evaluate previous RS training strategies with the ECDF of PA-
Theorem 2. Assume 81, 62 Rdd and 81 * 82. If |611|2 = ||52|l2. then (1)) = (I)) (52) for every a > O, where PN is the probability density function of the isometric Gaussian distribution with mean and covariance o² La.
B.1. From ECDF Certified Accuracy under Different Certification Settings
Proof. Let [q,, ....... qa] NO0, o² Ia)). Then have
Rdd be sampled from
We consider four RS models (Gaussian, Consistency, CAT- RS and ours) trained on CIFAR-10. The ECDF of under N = 10 is shown in Figure 7. Assume now instead of cer- tifying with N = 10 and a = 0.001, we want to certify with N = 100 and a = 0.01, which less expensive and more practical to run on edge devices. We are interested in the certified accuracy-radiie curve under this new certifica- tion setting.
PO0) = (2 o2
exp
20
1=1
20 |8112
(2x)d/20dd exp
Since the ECDF of Pa is calculated with a large N, we assume it equals the true population of PA- When it is computed with a relatively small N, the difference between ECDF and the true population might be non-trivial, and corrections should be done in such cases. We leave this as futurre work, and focus on the case where the ECDF is accurate enough to represent the true population.
This concludes the proof.
B. On the Empirical Distribution of PA
In this section, we include a case study to further demon- strate the idea we presented in $7 about using the empirical distribution of PA evaluate the RS model. We first show how to calculate the certified accuracy for every interested radius and certification budget efficiently, given the ECDF of PA- Then, we show how to convert an existing certified accuracy-radin curve to the ECDF of PA. thus the litera- ture results can be easily reused. These features facilitate
We take the case where cess. Given r = 0.5, N = 100 and a = 0.01, we run a binary search on PA to identify the minimum PA required to certify the radius. In this case, the minimum PA is 0.81. Then, we look up the ECDF curve to find the cor-
0.5 to demonstrate the pro-
12

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
responding P(pA 2 0.81). For our method in Figure 7, P(PA 2 0.81) 0.316. Therefore, the expected certi- fied accuracy under the new certification setting is 0.316. We note that this is an expected value, as multiple runs can lead to different certified accuracies due to the randomness of the noise samples.
0
0.25
0.5
1.0
m
Fx
60
70
60
Pt
0.5
0.4
0.4
T
3
6
4
0.25
0.25
0.5
Now, repeat this process for all radii of interest, and we can obtain the certified accuracy-radius curve under the new certification setting. The results are shown in Figure 8. We remark that no inference of the model is conducted in this process, thus the overhead is negligible.
Table 6: Hyperparameters we use on CIFAR-10.
under all 0, only outperforms other models in the high PA region. For example, with 0.5, our model is the worst when pA is below 0.75. We list some cases where two models have strict orders: with σ 0.25, the CAT-RS model is better than Consistency and SmoothAdv, and our model is better than CAT-RS; with o = 0.5, the CAT-RS model is better than the SmoothMix model; with o = 1.0, the CAT-RS model is better than SmoothMix and MACER, and our model is better than MACER.
B.2. From Certified Radius to ECDF
Computing ECDF for a given model requires the same computation as computing the certified accuracy-radius curve, as the former is a middle step of the latter. Fortu- nately, given the certified accuracy-radius curve commonly presented in the literature with large N, we can also convert ECDF of PA-
C. Experiment Details
The idea is to revert the process in App. B.1. Assume we are given the certified accuracy-radius curve when N = 100 and a = 0.001. Given an interested PA, we first cal- culate the maximum radius that can be certified with this PA under this certification setting. Then, we can look up the certified radius for this PA in the curve, and obtain the corresponding certified accuracy. This is the probability of PA being greater than the given PA ignoring the difference between ECDF and true population. Repeat this process for all interested PA. and we can obtain the ECDF of PA-
C.1. Training Details
We follow the standard training protocols in previous works. Specifically, we use ResNet- 10 (He et al.. 2016) on CIFAR-10 and ResNet-50 on IMAGENET, respectively. For CIFAR-10, we train ResNet-110 10 for 150 epochs with an initial learning rate of 0.1, which is decreased by a factor of 10 in every 50 epochs. The inital learning rate of train- ing ResNet-50 on IMAGENET is 0.1 and it is decreased by factor of 10 in every 30 epochs within 90 epochs. We investigate three noise levels, a = 0.25, 0.5, 1.0. We use SGD with momentum 0.9. The following hyperparameter is tuned for each setting:
B.3. Evaluating Current RS with ECDF
For future reference, we evaluate all existing methods, in- cluding Gaussian, Consistency, SmoothAdv, SmoothMix. MACER, CAT-RS and ours, using the ECDF of PA. to- gether with our proposed algorithm. We use the same dataset and model as in $6, i.e. ResNet- 10 on CIFAR- 10 with a {0.25, 0.5, 1.0} and N 10S. Whenever an official public model is available, ECDF of PA- Otherwise, re-train the model with the same hyperparameters as in the original paper.
m = the number of noise samples for each input
E, the epoch discard hard data samples
Pt the threshold of PA to discard hard data samples
T the maximum number of steps of the PGD attack
use it to compute the
c the step size of the PGD attack
All other hyperparameter is fixed to the default values. Specifically, for CIFAR-10 we use 100 noise samples to calculate PA when discarding hard samples. When up- dating dataset weight, we use 16 noise samples to calcu- late pA, with Pmin 0.75. The hyperparameter tuned on CIFAR-I0 shown in Table 6. For IMAGENET, we skip the 'Data Reweighting with Certified Radius' step for faster training, and use a Gaussian- ResNet-50 to eval- uate the PA with 50 noise samples. The hyperparameters tuned on IMAGENET is shown in Table 7.
The ECDF of Pa is shown in Figure 9. The related data point is available in our GitHub repository. We note that the ECDF independent of a, thus it can be used to eval- uate the certified accuracy under any certification setting. Given the ECDF metric, model A is better than model B if and only if A has higher ECDF than B for all PA 0.5. Therefore, it is possible that neither of two models is better than the other.
For various o, the Gaussian model always the best in the low PA region, i.e. from PA 0.5 to around 0.65. Although the our model consistently has the highest ACR
In Algorithm 2, we present a pseudocode for the overall training procedure described in $5.
13

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
ECDF
BCDF
ECDF
0.8
0.6
0.8
0.6
0.6
Gamsion
0.4
SmaothAdy
Maver
0.4
0.4
SmaothMi
Consistcucy
0.2
0.2
CAT-RS
Oun
0.0
0.0
0.0
0.50
0.75
1.00
0.50
0.75
1.00
0.50
0.75
1.00
PA
PA
P4
0.25 Figure 9: The empirical distribution of PA on CIFAR- with different a and N 10 This figure an extension Figure on more o and algorithms.
(b) 0.5
(c)
1.0
0.25
0.5
1.0
Algorithm 2 Overall Training Procedure
2
Input: Train dataset D, noise level hyperparameters E,, Pt. m, T Initialize the model f for epoch = to Nepoch do epoch < Eg then
F2
Pt
0.2
0.2
0.1
0.5
1.0
2.0
Sample ói...., 6m ~ NN(0021)
Table 7: Hyperparameters we used on IMAGENET.
Perform Gaussian training with 61....,d 8m
continue
else if epoch Eg then Discard hard data samples in D with PA Pt to form D
C.2. Certification Algorithm
We use the CERTIFY function in (Cohen et al., 2019) to calculate the certified radius, same as previous baselines, where = 10 and a 0.001.
end if
epoch %100 then
update dataset weight according to $5.2 end if
C.3. Adversarial Attack Algorithm
Sample |D] data samples from D' with replacement
In the adaptive attack, we implement the la PGD and loo PGD attack. The difference between them lies how the noise updated based on the gradient. For la PGD, the noise is updated as follows:
form the train set D
for input x, label c in D do
Sample .,,..., 6m ~ o0),02))
for = to m do
8 = ô VoLif(x +
v)).
8 < ADAPTIVEADY(S, x, c, 8,, T)
end for Perform Gaussian training with 87 . 5 end for end for
while for loc PGD, the noise is updated as follows:
8 8 e sign( (z + 8),
where L is the loss function, f is the model, r is the input, is the label, 8 is the noise, 5* is the updated noise, sign is the sign function, and is the step size. Unless stated otherwise, our experiments are always conducted with the l PGD attack. We show the results with the loo PGD attack on CIFAR-10 in App. E.4.
D.I. Effect of Discarding Hard Data
We investigate the effect the two hyperparameters E, and p. discarding hard samples. The results are shown in Table 9 and Table 10. If hard samples are discarded too early, it leads to decrease in accuracy for all radii, as many potential easy samples are discarded before their reaches Conversely, discarding hard samples too late allows more samples to remain, resulting in improved clean accuracy but reduced performance on easy samples, as the training focuses less on them.
D. A Aditioona Ablation Studies
In this section, we provide additional ablation studies on the effect of different hyperparameters. All results are based on a = 0.5 and CIFAR-10. Unless stated otherwise, all hyperparameters are the same as those in Table 6.
14

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2,00
2:25
2.50
0.25
0.5613=0000022
76.43-0.111
08.58:00.34
58 38:93:0.34
48.15::0.0 10
0.0
0.0
0.0
0.
0.0
0.5
0.7587+0.0011
59.00+0.20
14.40+0.26
49.57+0.16
44.31+0.14
39.09-0.1 0.19
34 14.14+0.05
2X 28.15
22,3++0.13
0.0
00
0.0
08443450.0003
41.74
39.23:60:44
36.46:0.31
33.7340.33
28.30:00.88
25.6240..09
18.40=0.25
Table 8: Mean and Standard deviation of ACR and certified accuracy on CIFAR-10 10 using our method. The results are based on three independent runs with different random seeds.
Certified accuracy
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
L.75
0.8
0.125
50
0.738
58.0
53.2
48.3
42.9
38.1
33.0
27.5
21.8
70
0.760
59.3
54.8
49.6
44.4
38.9
34.1
29.0
23.0
0.6
0.751
60.1
54.9
49.6
44.1
38.6
33.4
27.5
21.4
0.5
55.1
38.0
33.3
1.0
130
0.738
61.4
56.1
50.2
44.2
37.5
31.7
25.5
19.2
0.4
2.0
Table 9: Effect of the discarding epoch Et.
0.2
Pr
ACR
0.75
1.00
0.00
0.5
1.0
1.5
2.0
0.753
59.5
49.4
44.3
39.0
33.7
28.0
21.9
Certified radius
0.760
59.3
54.8
49.6
44.4
38.9
34.1
29.0
23.0
0.5
0.757
60.0
54.7
49.9
44.5
38.9
33.7
27.9
22.1
(a) Effect of
0.6
0.758
59.2
54.6
49.5
44.3
39.4
34.1
28.7
22.2
Certified accurscy
0.7
0.749
59.5
54.4
49.0
43.7
38.7
33.2
27.7
21.7
0.740
59.5
54.4
49.1
43.6
38.1
32.8
20.8
Table 10: Effect of the discarding PA threshold pt-
0.6
0.4
T
best hyperparameters reported Table 6. The results are based on three independent runs with different random seeds. The standard deviation is relatively small, confirm- ing the stability of our results.
T
0.2
=
T= 10
0.0
0.5
1.0
1.5
2.0
Cortified radius
E.2. Empirical Distribution of Pa on IMAGENET
Effect T
We extend Figure 3 to IMAGENET, shown Figure 11. We observe that for SOTA methods, there more samples with PA below 0.5 compared to Gaussian training, which is consistent to the results on CIFAR-IO in $4.3.
Figure Certified radius-accuracy curves on CIFAR-IO dif- ferent and T.
D.2. Effect of Adaptive Attack
E.3. Discarded Data Ratio
For the adaptive attack, we evaluate the effect of the step size e and the number of steps T. The results are shown in Table 11 and Table 12. In general, increasing the number of steps strengthens the attack, which helps find effective noise samples for extremely easy inputs. As result, per- formance improves at larger radii, but relatively less atten- tion is given to hard samples, leading to a decrease in clean accuracy. Similarly, increasing the step size moderate range (E 1.0) has similar effect. However, if the step size is too large, the attack loses effectiveness, resulting in decreased performance at all radii.
In this section, we are interested in how many data samples are discarded during training. The remaining data ratios under different a on CIFAR-10 are 91%, 80% and 58%, for 0.25, 0.5 and 1.0, respectively. The results indi- cate that even though a significant portion of the training still achieve better
is discarded during training, ACR than the current SOTA model according Table 3. Further, this confirms that larger a leads to more discarded data samples, which is consistent with the intuition.
E.4. Replacing l2 with 1oc PGD Attack
E. Additional Results
In this section, we replace the Lo attack with l.o PGD at- tack. The results are shown in Table 13 and Table 14. For Too attack, we use much smaller step sizes e to have simi- lar attack strengths to la attack. Specifically, we investigate Vd. c = 0. 0., 0.25, 1.5, 1.0 for lox attack, where d the
E. Result Significance
Table 8 shows the mean and standard deviation of the ACR and certified accuracy-radie curve on CIFAR-10 using our
15

---

Average Certified Radius is a Poor Metric for Randomized Smoothing
ECDF
ECDF
ECDF
1.0
1.0
1.0-
0.5
0.5
0.5
Gamesinu
Gaussam
Smoothady
Goussion
Smoothddy
Minotthiix
0.0
Smoothady
0.0
SanothMiix
0.0
CAT-RS
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
PA
PA
PA
0.25
0.5
1.0
Figure 11: The empirical cumulative distribution (ECDF) of pa on IMAGENET for models trained and certified with various with different training algorithms.
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
0.125
0.744
64.2
58.1
51.6
44.7
38.1
31.4
24.4
17.1
0.250
0.760
59.3
54.8
49.6
44.4
38.9
34.1
29.0
23.0
0,250
0.746
62.7
57.0
51.1
44.8
38.4
32.0
25.4
18.5
0.500
0.727
55.7
51.3
46.9
42.5
37.7
32.8
28.0
22.6
1.000
0.624
43.2
40.7
38.2
35.4
32.7
29.7
26.6
22.7
39.9
2,000
0.533
38.1
35.6
33.0
30.5
27.6
24.9
22.0
19.0
Table 13: ACR and certified accuracy under the to PGD
Table 11: Effect of the adversarial attack step size 6.
attack with 0.5 on CIFAR 10 with different step size.
T
ACR
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
ACR
0.00
0.25
0.50
1.75
2
0.719
66.2
58.9
51.5
43.7
36.2
28.9
21.8
14.5
3
0.718
66.0
59.0
51.6
43.8
21.2
14.0
0.752
62.0
56.7
50.9
44.6
38.6
32.7
26.3
19.7
0.731
0.736
64.2
57.8
51.4
23.7
0.748
57.0
52.6
48.0
43.4
38.7
34.2
29.2
23.6
6
0.746
62.7
57.0
51.1
44,8
38.4
32.0
25.4
18.5
10
0.732
54.1
49.9
45.9
42.0
37,8
34.0
29.5
24.6
7
0.743
61,5
56.4
50.6
44.4
38.1
32.4
25.7
19.1
8
0.742
60.1
54.8
49.7
43.7
38.0
32.7
26.9
20.3
Table 12: Effect of the number of steps of adversarial attack
T.
Table 14: ACR and certified accuracy under the 1oo PGD
attack with a 0.5 on CIFAR-10 with different number of steps.
dimension of the input. After the thorough experiments, we find that using /d 6 = 0.25 with other hyperparameters fixed to the values in Table has the best ACR. The loc at- tack has similar effect the l2 attack. Increasing the step size and the number of steps of the attack result in better accuracy at large radii but lower accuracy at small radii.
16


Reviews:
[{"review_id": "riL3CwF6nk", "reviewer": "Reviewer_ukgY", "summary": "The authors investigate the validity of the Average Certified Radius (ACR) as a measure for robustness.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\newcommand{\\Ru}{\\textcolor{green}{uKgY}}$\n$\\newcommand{\\Rp}{\\textcolor{blue}{Ptgp}}$\n$\\newcommand{\\Rn}{\\textcolor{fuchsia}{nJsf}}$\n$\\newcommand{\\Rg}{\\textcolor{purple}{gJ9M}}$\n\nWe thank Reviewer $\\Ru$ for the insightful review. We are happy that Reviewer $\\Ru$ finds our work important and experiments sound. In the following, we will address all concerns raised by Reviewer $\\Ru$. We include new results, named with Figure S1 etc., in the [anonymized link](https://mega.nz/file/2NtyHIpA#EcvgiAMI7xMjXTgcGHnVpWdg-U2QnojAPVqF7peCMwM).\n\n\n**Q1: Does the robustness in this paper (especially Thm 1) consider both predictive performance and output stability under small input perturbation?**\n\nYes. As defined in 68-69 rc, the robustness defined in this work considers both the predictive performance and the output stability. Specifically, Thm 1 also considers both aspects, and inputs that are mistakenly predicted will not contribute to ACR. Furthermore, Reviewer $\\Ru$ claims that ``a constant classifier is the most robust classifier by any measure of robustness``; this is not true. For example, under our definition of robustness, a constant classifier can have zero robustness: consider a dataset that only contains class 0 for a binary classification task, then a constant classifier predicting class 1 will have zero robustness (and zero ACR). We hope this classifies the misconception about our definition of robustness.\n\n**Q2: Why shouldn’t RS training lower $p_A$ for harder samples?**\n\nThe term ``harder samples`` in Sec 4.3 refers to samples with $p_A$ larger than but close to 0.5, and ``easier samples`` refers to samples with $p_A$ close to 1. Therefore, as shown in Sec 4.3, if RS training is justified to lower $p_A$ for harder samples, then under small radii (e.g., $r=0$), the certified accuracy of “better algorithms” will be **lower** than “worse algorithms”, contrary to the intuition. \n\nIn addition, the claim made in Sec 4.3 is not “this has led to wrong RS algorithms”; instead, we claim that this introduces selection bias (that “better algorithms” have worse certified accuracy under small radii) into the development of RS algorithms, as explicitly stated in the title of Sec 4.3. The latter is directly supported by empirical evidence.\n\n**Q3: Given the definition of ACR, will ACR be provably improved by focusing on easy samples? Is the hypothesis “focusing on easy samples improves ACR” trivially true and does not require empirical evidence in this work? What is the main goal of Algorithm 2?**\n\nThe hypothesis is not trivially true. While an improvement on $p_A$ of any input without a decrease on $p_A$ of other inputs leads to increased ACR, it is not guaranteed that improving $p_A$ of easy samples does not reduce $p_A$ of hard samples. In fact, as shown in Sec 4.3, the reverse is usually true. Thus, ACR is not provably increased by focusing on easy samples. Further, the hypothesis will only hold when the benefits of improvement on easy samples exceed the loss on hard samples. This leads to our experimental analysis in Sec. 5 and 6 based on Algorithm 2. The main goal of Algorithm 2 is to both validate this hypothesis and the second hypothesis that the progress in RS training strategies can be replicated by simply focusing on easy samples.\n\n**Q4: Is ACR really misleading, as it is rarely used as a stand-alone metric?**\n\nPlease refer to our reply to Q1 of Reviewer $\\Rg$. \n\n**Q5: Can the entire paper be summarized “ACR is average of the radii, and averages can be arbitrarily moved by just moving one instance, and hence ACR can be made arbitrarily good by just focusing on easy samples with large robustness radii”?**\n\nThis summary is partially true, but misrepresents important scopes established in this work. It is true that ACR is the average of the certified radius, and averages can be arbitrarily moved by an infinite change on only one instance. However, as pointed out in our reply to Q3, this does not directly prove that ACR can be made arbitrarily good by just focusing on easy samples with large radii. In fact, our empirical results in Sec. 6 shows that ACR can at least be amplified to the state-of-the-art (SOTA) by focusing on easy samples, but still not infinitely large. As discussed in Q3, there might exist an equilibrium where the loss on hard samples exactly offsets the improvement on easy samples, leading to maximized ACR. The more accurate summary of this work should be: (i) ACR is problematic because it does not faithfully represents the robustness and it is much more sensitive to the same magnitude of improvements on easy samples than hard samples, (ii) empirical evidence shows that ACR of Gaussian training can be amplified to SOTA by simply focusing on easy samples, and (iii) ACR should be replaced by better alternatives such as certified accuracy at various radii and the ECDF of $p_A$ when evaluating RS training strategies.", "claims_and_evidence": "Claims and Evidence: \n\nC1. Authors theoretically  show that with a large enough certification budget, ACR of a trivial classifier can be arbitrarily large, and that with the certification budget commonly used in practice, an improvement on easy inputs contributes much more to ACR than on hard inputs, more than 1000x in the extreme case.\n\nE1. One of the evidence for this claim provided by the authors is Theorem 1.  I am not convinced of this result being meaningful. Indeed a constant classifier is trivially the most robust classifier by any measure of robustness. And Theorem 1 formalizes this intuition.  But this type of analysis is fundamentally flawed in the methodology: simultaneously optimizing two objectives is not the same as optimizing both of them separately. That is optimizing only robustness will not lead to the same solution as the one when optimizing for robustness and accuracy together.This analysis does not take into account predictive performance of the classifier, and any real-world robustness training algorithm will optimize for both robustness and accuracy. \n\n## Update after rebuttal: The authors correctly pointed out my misjudgment of the theorems results, and I think there analysis is correct and meaningful. \n\nC2.  ACR disproportionately focus on easier examples, i.e., samples with more confident predictions (and hence larger p_A) are disproportionately represented in ACR. However, the authors also claim that this leads to potentially poorer RS algorithms (which I do not agree with, see below). \n\nE2. As ACR is essentially an average, where the weights are the proportional to CDF of a normal distribution at $p_A$, it indeed over-represents samples with larger $p_A$. However, in section 4.3, I do not agree with the analysis. The authors criticize the fact that the RS training procedures \"lowers the $p_A$ for harder samples\" --- I do not understand why they should behave otherwise? I would argue that the user should see a lower $p_A$ for harder samples, this does not contradict the fact that ACR can be misleading, but claiming that this has lead to wrong RS algorithms is misleading. \n\n## Update after rebuttal: I think the situation is clearer to me now. And I think the point about \"selection bias\" seems valid. \n\nC3. The authors show that focusing only on easier samples can improve ACR. \n\nE3. Authors provide an algorithm and experimental evaluation to this end. However, I think this fact is clear, as ACR is a weighted average as mentioned above. See \"Experimental Designs Or Analyses\".\n\n## Update after rebuttal: My statement was wrong, and the authors are indeed correct to provide experimental evidence for gaming ACR.", "methods_and_evaluation_criteria": "Authors provide theoretical results, and verify them experimentally, with an algorithm to produce the misleading ACR behavior, on widely known benchmark datasets and RS.", "theoretical_claims": "See above in \"Claims and Evidence\" section", "experimental_designs_or_analyses": "I think the experimental design is sound, but it is also tautological, i.e., the hypothesis they are testing is not falsifiable by the experiments they are performing. In my understanding, given the definition of ACR, and then discarding hard samples one will provably improve ACR.\n\n\n## Update after rebuttal: I think this assessment was indeed incorrect and my understanding of the paper has been improved by looking at section 4.2 again, and reading the author's discussion with Reviewer nJsf.", "relation_to_broader_scientific_literature": "The main message of the paper is potentially very relevant to RS research, depending on how widely ACR is used as a metric. \nHowever, I think ACR is a misleading metric only if it is used as a stand-alone metric.  \n\nThe fundamental point of the paper can be boiled down to the fact that average, and hence ACR, is not a robust statistic.\n\n## Update after rebuttal: I think this assessment is indeed correct to a large extent.", "essential_references_not_discussed": "None, to the best of my knowledge.", "other_strengths_and_weaknesses": "Strengths:\nThe key message of the  paper is potentially very important. \n\n\nWeakness:\nAlmost all of the peripheral analysis is potentially misleading. \nThe main message should just be that average is not a robust statistic and one should not base metrics for safety-critical applications on that.\n\n## Update after rebuttal: I would like to retract my comments about the \"misleading analysis\". However, I still believe that the main result indeed, in large parts, can be attributed to averages not being robust statistics.", "other_comments_or_suggestions": "-- I am quite ambivalent about the paper, on one hand I think the key message of the paper is pertinent. However, as described above, I find many points raised in the paper to be rather misleading (in my understanding).\n\n## Update after the rebuttal: As mentioned earlier, I do not think anymore that the analysis is misleading, barring the fact that ACR still does not seem to be the most important metric", "questions_for_authors": "-- Why cant the entire message of the paper be summarized in the fact that ACR is average of the radii, and averages can be arbitrarily moved by just moving one instance, and hence ACR can be made arbitrarily good by just focusing on easy samples with large robustness radii?\n\n-- What is the usefulness of Algorithm 2? as one can see from definition of ACR focusing too much on easy samples will indeed improve it. Is Algorithm 2 verifying this point?", "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": "ke9qn49fuc", "reviewer": "Reviewer_Ptgp", "summary": "The authors make a strong claim that the Average Certified Radius (ACR) - which is widely used through the Randomized Smoothing (RS) community - is not a good metric at all for a number reasons. They prove it, and provide the ways how it can be exploited for improving ACR.\n\n## update after rebuttal\nAuthors provided the asked additional experiments (even for ImageNet), so I keep my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rp$ for the insightful review and faithful interpretation of our work. We are happy that Reviewer $\\Rp$ finds our work important, sound and solid. We will resolve all the concerns below. We include new results, named with Figure S1 etc., in the [anonymized link](https://mega.nz/file/2NtyHIpA#EcvgiAMI7xMjXTgcGHnVpWdg-U2QnojAPVqF7peCMwM).\n\n**Q1: Do the results generalize to ImageNet?**\n\nYes. We perform a new analysis on ImageNet, generalizing the findings presented in this work. Concretely, Figure S1 is an extension of Figure 3 on ImageNet, and Table S1 is an extension of Table 2 on ImageNet. The hyperparameters used in the study are reported in Table S2. We find that all our conclusions remain correct on ImageNet, justifying their generalization across datasets.\n\n**Q2: Could the authors extend the evaluation of previous works using the proposed “ECDF of $p_A$” metric?**\n\nSure. The ECDF of $p_A$ on CIFAR-10 with different $\\sigma$ and algorithms are shown in Figure S2. We note that an algorithm is better only if it has higher ECDF for all $p_A \\ge 0.5$. Therefore, it is possible that neither of two algorithms is better than the other. \n\nFor various $\\sigma$, Gaussian is always the best in the low $p_A$ region, i.e. from $p_A=0.5$ to around 0.65. Although CAT-RS consistently has the highest ACR under all $\\sigma$, it only outperforms other methods in the high $p_A$ region. For example, with $\\sigma=0.5$, CAT-RS is the second worst method when $p_A$ is below 0.74. We list some cases where two methods have strict orders: with $\\sigma=0.25$, CAT-RS is better than Consistency and SmoothAdv; with $\\sigma=0.5$, CAT-RS is better than SmoothMix; with $\\sigma=1.0$, CAT-RS is better than SmoothMix and MACER.\n\n**Q3: Clarification of the typo in Sec. 7.**\n\nThanks for pointing out the typo. It should be \"try to develop the best model with the highest **certified accuracy** at the pre-defined radius\".", "claims_and_evidence": "Claims:\n* Theoretic proof that ACR can be arbitrarily large even for a trivial classifier, esp. when its improvement is rooted in easy examples\n* Empirical justification of the current RS training strategies intention to concentrate on easy examples (with high $p_{A}$)\n* Based on theoretical and empirical observations, the authors proposed the specific methods to improve the existing RS training strategies (Section 5) by a) discarding hard examples during training, b) training examples re-weighthing with Certified Radius, and c) adjusting the perturbation to have the same norm but broking the classifier (they called it \"Adaptive Attack\")\n\nOverall, the approach by authors can be formulated as following:\n1. They empirically and theoretically investigated on why the ACR is a bad metric\n2. They exploited their observations to produce the best (SotA) defense methods\n3. They proposed what could be the better metric instead of ACR (Section 7 - e.g., using the best certified accuracy at various radii or use $\\sigma$ as a variable, not a hyperparameter)", "methods_and_evaluation_criteria": "All the proposed methods (already existing and adopted in the community of RS researchers as well as the new one proposed in Appendix B for constructing the Empirical CDF for $p_{A}$) sound solid and reasonable.\n\nAs for the datasets itself, CIFAR-10 was used - which is quite widely used for the task of RS. Unfortunately, no ImageNet results were delivered - which would provide a stronger message about this paper.", "theoretical_claims": "Yes, the authors provided the proof of the Theorem 1 (about arbitrary high ACR) in Appendix A1, as well as the auxiliary simple proof for the Theorem 2 (about the probabilities of the equal norm perturbations). While looking simply the theorems are carefully proved.\n\nMoreover, inside the Appendix B.1 there is a description (while not explicitly theoretically formulated but still rigorous) of the procedure to convert ECDF($p_{A}$) to ECDF($r_{cert}$) with different value of $N$ which is very well described.", "experimental_designs_or_analyses": "Actually, two main remarks:\n1. No usage of other than CIFAR-10 dataset. ImageNet was used even in the seminal paper of [1].\n2. There is no re-estimation of the existing RS defenses for the metrics proposed in Section 7. Yes, there is a slight approach in the Appendix B, but it is definitely not enough. If the paper proposes the new way of measuring Certified Robustness for RS, than it makes to provide the new measurements of the methods and see how they compare against each other - whether the order is different etc\n\n[1] Cohen, J. M., Rosenfeld, E., and Kolter, J. Z. Certified adversarial robustness via randomized smoothing. In Proc. of ICML, volume 97, 2019.", "relation_to_broader_scientific_literature": "The whole paper is devoted to the certified robustness through probabilistic approach - randomized smoothing. RS is the main method to assess certification of deep NNs.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "To me, very well organized paper with the structure: Observation --> Exploitation --> Proposal to change.\n\nWould be nice to address the items mentioned in \"Experimental Designs Or Analyses\"", "other_comments_or_suggestions": "I'm not quite sure if it is a typo or some my misunderstanding of the following sentence in Section 7:\n\n\"this represents the setting where one first fixes an interested radius, and then try to develop the best model with the highest certified radius at the pre-defined radius.\"", "questions_for_authors": "NA", "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": "eoWD002b7i", "reviewer": "Reviewer_nJsf", "summary": "This paper critiques the use of Average Certified Radius (ACR) as an evaluation metric for assessing the performance of certifiably robust classifiers, specifically focusing on randomized-smoothing-based approaches for robustness certification under the $\\\\ell_2$ perturbation threat model.\n\n (To give background: in an  $\\\\ell_2$-certifiably-robust classifier, for each input sample $x$, the classifier both returns a classification $\\\\hat{f}(x)$ as well as a radius $R(x)$, such that for any $x'$ such that  $\\\\|x-x'\\\\|_2 < R(x)$,  the sample $x'$ is guaranteed to be classified in the same way as $x$: that is, $\\hat{f}(x) = \\hat{f}(x')$. Typical randomized smoothing approaches (for the $\\\\ell_2$ metric) compute $\\hat{f}(x)$ by taking the plurality-vote of the output of a _base classifier_ $f(x + \\delta)$ on many noise instances $\\delta$ drawn from an isometric Gaussian distribution: the certified radius $R(x)$ is then computed as a (monotonically increasing) function of $p_A$, the fraction of noise instances $\\delta$ on which $f(x + \\delta)$ retuned the plurality class.)\n\n\nAs an evaluation metric, the Average Certified Radius is defined on a labelled  test set $(x_1, y_1), ..., (x_m,y_m)$ as:\n\n$$ \nACR = \\\\frac{1}{m} \\\\sum_{i=1}^m \\\\begin{cases} R(x_i) & \\\\text{ if } f(x_i) = y_i, \\\\\\\\ 0 & \\\\text{ otherwise. }\\\\end{cases}\n$$\n\nThe paper claims that ACR is commonly used to evaluate randomized-smoothing based certifiably robust classifiers. The paper then notes (Theorem 1)  that ACR can be ``gamed'' to be made arbitrarily large: specifically, a _constant_ function $\\hat{f}(x) = c$, which classifies all samples with the same class c, combined with a certification technique that (_correctly_) reports an arbitrarily large certified radius R(x) for each sample (note that these certifications are correct, because the classification function $\\hat{f}(x)$ is constant) will have an arbitrarily large ACR as long as *any* samples  in the test set are labeled as c. In particular, this set-up can be instantiated using standard randomized smoothing certification techniques, by using a constant base classifier, and a sufficiently-large number of smoothing samples to make R(x) as large as desired.\n\nIn practice, in randomized smoothing (RS) certification techniques, the certified radius R(x) is *capped* by a function of the number of smoothing samples $\\delta$ used, and hence by the certificate computation time. However, the paper goes on to claim that in RS techniques, training design choices that increase ACR tend to increase the certified radii R(x) of the \"easiest\" samples in the data distribution (those which already have a large certified radius) at the expense of \"harder\" samples. This phenomenon is demonstrated empirically by comparing the cumulative certified radius distribution of Cohen et al. (2019), one of the first RS techniques, with the cumulative  certified radius distributions from more-recent works, on CIFAR-10 (Figure 6; Table 2). For small radii r, Cohen et al's method is more likely to correctly classify samples and certify them as robust to radius R(x) >= r, while for large radius r, the more recent techniques prevail. The paper explains this phenomenon theoretically as being due to the fact that the certified radius R(x) grows very quickly as a function of  $p_A$ when $p_A$ is near 1 ( and $R(x)$  is already  large ), while growing much more slowly with  $p_A$ when $p_A$ and $R(x)$ are small. Therefore increasing the certified radii of \"easy\" samples even further is \"easier\" than increasing the certified radii of \"hard\" samples by the same amount, because it requires increasing $p_A$ of the \"easier\" samples by a much smaller increment.\n\n\nThe paper goes on to design a training method for certifiably robust classifiers that is designed to \"game\" ACR as much as possible (practically; without increasing the number of smoothing samples).  They propose to skip \"hard\" samples during training, weight training samples by \"easiness,\" and adversarially choose smoothing perturbation vectors $\\\\delta$ during training to ensure that $p_A$ is as close to 1 as possibly for \"easy\" samples. The resulting classifiers have state-of-the-art ACR on CIFAR-10 and relatively-low clean accuracy (although not the lowest among certifiably-robust methods.\n\nFinally, the paper suggests alternatives to using ACR to evaluate certifiable robustness: reporting the cumulative distribution of R(x) (that is, the fraction of test samples which are correctly classified and have $R(x) \\geq r$ for various values of $R$) as well as the distribution of $p_A$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rn$ for the insightful review. We are happy that Reviewer $\\Rn$ finds our work is important and valuable, and points out imperfect expressions. We will address all the concerns raised by Reviewer $\\Rn$ in the following. We include new results, named with Figure S1 etc., in the [anonymized link](https://mega.nz/file/2NtyHIpA#EcvgiAMI7xMjXTgcGHnVpWdg-U2QnojAPVqF7peCMwM).\n\n\n**Q1: Is ACR the most important metric in the community? Is there any quantitative evidence which supports their claim?**\n\nPlease refer to our reply to Q1 of Reviewer $\\Rg$.\n\n**Q2: SmoothAdv, which is before the invention of ACR, has similar issues as presented in this paper. Does this undermine the claim that ACR introduced a strong undesired bias to the field?**\n\nWe agree that although the empirical evidence in Sec 4.3 shows that a strong bias is introduced to the field, it does not directly imply that ACR is the only reason. In fact, the hypothesis that ACR has causality with the bias is not provable. Therefore, we will temper our tone and state that “A strong bias has been introduced to the field, which is highly likely due to the practice of claiming SOTA based on ACR given the demonstrated properties”.\n\n**Q3: Could the authors clarify notations in Theorem 2 and the text at 305-306 rc?**\n\nWe thank Reviewer $\\Rn$ for pointing out the notation conflicts. We will define the notations more clearly and replace the infinitesimal probability with PDFs of the Gaussian function in the revised manuscript.\n\n**Q4: Easier samples contributing much more to ACR than harder ones does not imply that it is easier to improve $p_A$ of easy samples than hard ones. Is the claim that ACR strongly prefers easy samples proper?**\n\nWe agree that more contribution from easy samples does not directly imply that focusing on easy samples will increase ACR. We refer to our reply to Q3 of Reviewer $\\Ru$ for a detailed discussion. However, the claim that ``ACR strongly prefers easy samples`` simply states that easy samples contribute more, but does not conclude that focusing on easy samples will increase ACR. Nevertheless, to avoid confusion, we will adjust this statement properly.\n\n**Q5: Do the results generalize to other datasets?**\n\nPlease refer to our reply to Q1 of Reviewer $\\Rp$.\n\n**Q6: Does this work assume applying the certification algorithm described in [1]?**\n\nYes. In fact, we only discuss works that are based on the certification algorithm in [1] since the subject is RS training strategies but not certification algorithms. We will clarify this in the revised manuscript.\n\n**Q7: Could the authors clarify the definition of clean accuracy when not using the prediction algorithm of [1]?**\n\nWe consider the certification method in [1], which does not provide a prediction if the empirical $p_A$ is below 0.5 (i.e., the algorithm returns ABSTAIN). In this case, the clean accuracy is defined as the accuracy at a certified radius of 0. This convention is also adopted in previous works such as [1, 2, 3]. \n\nAs a future reference, we additionally report the accuracy of different methods when the model performs a majority vote without abstaining in Table S3. It shows that without abstaining the clean accuracy is always marginally higher than that with abstaining. The result without abstaining is consistent with the analysis in this work performed with abstaining.\n\n**Q8: For the proposed metric, the cumulative distribution of $p_A$, can it be used to compare different certification algorithms? How to use it for downstream applications?**\n\nAs discussed in Q6, this work focuses on the certification algorithm proposed by [1]. However, cross-certification evaluation is still possible. Appendix B thoroughly discusses how to convert the distribution of $p_A$ into certified accuracy at different radii and different budgets. If comparisons of different certification algorithms are desired, then based on methods discussed in appendix B.1, one may first convert it to certified accuracy before comparison. This is more flexible than certified accuracy at fixed budget, because different certification might vary in certification budget. Similarly, for downstream applications, since the proposed metric is more generalized than certified accuracy, it allows more flexible evaluation; importantly, every evaluation that is based on certified accuracy can be recovered cheaply based on the distribution of $p_A$. Nevertheless, this metric is only meaningful for $p_A$-based certification; it must be converted into other metrics to compare with other certification algorithms. We will clarify these aspects in the revised manuscript.\n\nReference\n\n[1] arxiv.org/abs/1902.02918\n\n[2] arxiv.org/abs/1906.04584\n\n[3] arxiv.org/abs/2212.09000", "claims_and_evidence": "The basic argument that ACR alone provides an incomplete picture of certifiable robustness, because it can be made arbitrarily high by using a trivial (constant) classifier, is correct, and the proof of the associated Theorem 1 is correct.\n\nHowever, the submission claims that:\n\n\"Randomized smoothing is a popular approach for providing certified robustness guarantees against adversarial attacks, and has become an active area of research. Over the past years, the average certified radius (ACR) has emerged as the **most important** metric for comparing methods and tracking progress in the field.\" [Abstract] (emphasis added)\n\n\"Average Certified Radius (ACR), defined to be the average of the certified radiuses over each sample in the dataset, has been **the main metric** to evaluate the effectiveness of these methods\" [Introduction, Lines 31-33] (emphasis added).\n\nThese claims are not well-supported. While the paper does cite six works which report ACR as a metric, the following additional context is relevant and is not mentioned:\n- **None** of the works report ACR _alone_ as the sole metric for comparing RS techniques; all of them also give the cumulative distribution of R(x).\n- All but two of the cited works which use ACR share the same first-author, showing that the use of this statistic is less wide-spread than is suggested by the total number of provided references.\n- Several works which deal with $\\\\ell_2$ certifiable robustness via randomized smoothing, which do not use ACR, were not mentioned. This includes works which propose new techniques, such as:\n\nAwasthi et al. \"Adversarial robustness via robust low rank representations\", NeurIPS 2020\n\nZhang et al. \"Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework\" NeurIPS 2020\n\nLi et al. \"Double Sampling Randomized Smoothing\" ICML 2022\n\nas well as survey papers which compare many proposed techniques, and do **not** report ACR, such as:\n\nLi et al. \"SoK: Certified Robustness for Deep Neural Networks\" IEEE SP 2023\n\nFurthermore, the claims in the Abstract and Introduction sections highlighted above are not qualified as being only about $\\\\ell_2$ certifiable robustness, although later it is stated that \" In this work, we focus on the L2 neighborhood of an input,\" (Background, lines 66-67). The cited examples of ACR are all papers about L2 certified robustness, and no examples are given outside of this specific line of work. However, many papers exist which use randomized smoothing-based techniques and do not report ACR.  (See the above survey for examples of certification results for other metrics.) Therefore the general claim made in the abstract that \"Randomized smoothing is a popular approach [...] the average certified radius (ACR) has emerged as the **most important** metric for comparing methods and tracking progress in the field\"  is not supported by evidence provided in the paper. To properly evidence this claim, one would need to perform a much wider and more objective meta-analysis of all literature in randomized smoothing. (Note that even if *every* paper using randomized smoothing reported ACR, this would not justify the claim that ACR is the *most important* metric for comparing methods.)\n\nAdditionally, while the experimental evidence does seem to justify that, for fixed smoothing noise standard-deviation $\\sigma$, newer RS methods tend to increase the certified robustness of \"easy\" samples at the expense of accuracy on \"hard\" samples (at least on CIFAR-10), the experimental comparison includes SmoothAdv (Salman et al. 2019), which does not report ACR, but which seems to behave similarly in terms of the shape of the certificate distribution to the methods which do, at least compared to Cohen et al (2019). This seems to undermine the **causative** claim in the abstract that \"Overall, our results suggest that ACR has introduced a strong undesired bias to the field.\"\n\nThe other claim that this paper makes that I do not believe is sufficiently justified is the relevance of the theoretical argument made in Section 4.2; specifically, the claim that \"We have shown that ACR strongly prefers easy samples in §4.2.\" (line 155-156) The issues with this claim are elaborated below under \"Theoretical Claims.\"", "methods_and_evaluation_criteria": "The methods and evaluation appear to be sound; however, only CIFAR-10 was used in the experiments. It would be better to include a dataset with more natural images (for example ImageNet, or, if that is not feasible, an ImageNet subset).", "theoretical_claims": "The main theoretical claim in the paper (that ACR can be unbounded for trivial classifiers), Theorem 1, is correct and has a correct proof.\n\nTheorem 2 is a minor technical result, which is not of great importance to the paper. However, its proof is only correct as written if we interpret $P_{\\\\mathcal{N}(0,\\\\sigma^2I_d)}(\\\\delta)$ to refer to the probability _density_ at $\\delta$. This notation is not explained, and conflicts with the notation in the Background section, where  $P_{\\\\delta \\\\sim \\\\mathcal{N}(0,\\\\sigma^2I_d)}(f(x+\\\\delta) = c)$ refers to the _probability_ (not the density) of the event. The text at line 305-306: \"This is because for every δ∗such that ∥δ∗∥2 = ∥δ0∥2, the probability of sampling δ∗is the same as δ0. We formalize this fact in Theorem 2.\" should also be revised: \"the probability of sampling δ∗\" is _infinitessimal_.\n\nA major theoretical over-claim in this work is that:  \"We have shown that ACR strongly prefers easy samples in §4.2.\" (line 155-156). The theoretical argument in Section 4.2 shows that the certified radius R(x) grows very quickly as a function of $p_A$ when $p_A$ is near 1 ( and $R(x)$  is already large ), while growing much more slowly with  $p_A$ when $p_A$ and $R(x)$ are small. Therefore, it is suggested that algorithms which are tuned to increase average radius will tend to increase p_A for samples where p_A is already large, because this will have a greater impact on average radius than an equal increase in p_A for samples where p_A is small. However, this theoretical observation alone does *not* establish, as implied, that it is \"easier\" to increase the certified radius of a sample with p_A near 1 than a sample with a lower p_A. Concretely, while it is true that increasing p_A from .99 to .999 increases R(x) by a much larger margin than increasing  p_A from .6 to .609, it is not obvious that it is _as easy to increase_ p_A from .99 to .999 as to increase  p_A from .6 to .609. In fact, one can make a compelling theoretical argument for the opposite: that it should be much harder to increase p_A from .99 to .999 than to increase p_A from .6 to .609. \n\nSpecifically, due to the nature of the high-dimensional Gaussian distribution, the minimum _volume_ around $x$ for which the base classifier $f(x+\\\\delta)$ must return class A in order to achieve $p_A = .999$ is much larger than the minimum volume around $x$ that must belong to class A in order to achieve $p_A = .99$, and in particular,  this gap in minimum-volumes is much larger than the gap between the volumes required to achieve $p_A = .6$ and $p_A = .609$. (To help understand this, note that achieving p_A = 1 _requires_ that $f$ is constant _everywhere_). Therefore an analysis in terms of $p_A$ alone is perhaps misleading, and does not fully \"show that ACR strongly prefers easy samples\".\n\nThe empirical evidence _does_ seem to suggest that the methods with the highest ACR tend to focus on increasing p_A for \"easier\" samples; however, I think it is an over-claim to say that the argument in Section 4.2 fully explains the phenomenon: more nuance is required.", "experimental_designs_or_analyses": "One confusion I had with the experimental design was the explanation of Figure 3 in line 193: \" As a result, Gaussian training has higher P(pA ≥0.5) (clean accuracy),\" Clean accuracy is not the same as p_A >= 0.5. If there are more than two classes, samples can be labeled correctly  by the smoothed classifier with p_A < 0.5; they just won't get a certified radius by Cohen et al's method. It would be good to also label the _actual clean classification accuracy_ of each classifier. (For example, if the classifiers are classifying samples correctly, with radius 0)\n\nAdditionally, throughout the paper, it is implicitly assumed that we are using the empirical certification algorithm described in Cohen et al, which only bounds the probability $f(x+\\delta)$ returning the ``top'' class. For example, on Line 137-138: \" Further, when pA < 0.5, the data point will not contribute to ACR at all,\" Some methods can in fact certify when p_A < 0.5, such as the method used in (Lecuyer et al, 2019; Dvijotham et al., \"A Framework for robustness Certification of Smoothed Classifiers using F-Divergences\" ICLR  2020). This should be clarified.", "relation_to_broader_scientific_literature": "This paper provides concrete suggestions to future researchers in randomized smoothing for certified adversarial robustness, specifically:\n1. To avoid using ACR (Average Certified Radius) as a metric for robustness.\n2. To instead report the highest-achievable certified accuracy at specified radii. \n3. To report the cumulative distribution of p_A for the test set.\n\nFor (1) the paper does establish that at least some prior works do report ACR, and then shows how this statistic can be vacuous; furthermore, I am not aware of any prior works that explicitly point out these issues with ACR. However, it is not well-established that the use of ACR is as common as claimed (\"the most important metric\") . Additionally, as noted above, (2) is already done _nearly-universally_ in prior works.  Furthermore, (3) may be somewhat limited: if methods differ in terms of _how_ they compute certificates given $p_A$, then (3) does not allow for a fair comparison (for example: Li et al. \"Double Sampling Randomized Smoothing\" ICML 2022); additionally, (3) does not allow for comparison to non-RS certified robustness methods. Furthermore, p_A is not actually relevant to downstream applications: it is an internal metric of the certification process.", "essential_references_not_discussed": "See the above discussion. While, to my knowledge, this is the first work to explicitly identify that ACR is a problematic metric, there are many works in this space that do not use ACR but were not cited. To restate some examples given above:\n\nAwasthi et al. \"Adversarial robustness via robust low rank representations\", NeurIPS 2020\n\nZhang et al. \"Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework\" NeurIPS 2020\n\nLi et al. \"Double Sampling Randomized Smoothing\" ICML 2022\n\nLi et al. \"SoK: Certified Robustness for Deep Neural Networks\" IEEE SP 2023\n\nThere are many more such works in existence; a more comprehensive survey is needed to assess whether ACR is truly a ubiquitous metric.", "other_strengths_and_weaknesses": "Strengths:\n- The main argument of the paper, that ACR is not an appropriate metric on its own, because it may be vacuous, is compelling and is argued correctly.\n- While this was not the stated aim of this paper, it appears from the results that the proposed training method (for fixed $\\sigma$) did achieve a higher certified accuracy at large radii than all prior works, at least on CIFAR-10. This training method can then be seen on its own as an additional contribution.", "other_comments_or_suggestions": "Minor Comments:\n\n\nLine 34-35: \"Although some studies refrained from using ACR in their evaluation unintentionally\" -- It is not knowable whether on not this was \"intentional\"; it would be better to say \"Although some studies have not used ACR (without mentioning a justification for this choice)\"\n\nLine 44: \"Due to the incompleteness of adversarial attacks \": I think this means that adversarial attacks only prove an upper bound on the true robustness/distance to the decision boundary, but this is not worded clearly.\n\nLine 31\" \"radiuses\" -> radii\n\nLine 96: \"is commonly used\" -> \"was commonly used\"\n\nEquation on line 94: The sum is meaningless here, and so can be omitted: we're taking the average over m identically-distributed samples, within an expectation. The sum can be commuted with the expectation, where it then becomes clear that all of the summands are equal.\n\nLine 106: \"While they all improve ACR\" -> \"While these methods all improve ACR\" \n\nLine 134-135: \"with minimal robustness on at least half of classes.\" Why not minimal robustness on all but one class?\n\nLines 138-139: \"since inputs with lower pA require a larger budget to certify. \" : This seems to be an oversimplification. On the contrary, isn't the certified radius most sensitive to the estimated probability, and hence to sampling budget, when pA is near 1? (The example given in this paragraph shows a more complex relationship)\n\nLine 160: \"We follow the standard certification setting in the literature, setting N = 10^5 and α = 0.001.\" : I believe these parameters are originally from Cohen et. al. 2019; I would cite them.\n\nSection 4.2 (and Figure 2): I believe this figure is showing the relationship between the _measured_ p_A (from samples) and the certified radius. However, p_A is actually defined as the _population average_ in line 79 in Section 3. This should be clarified.\n\n\nTable 1: is this _parameter_ gradient or _feature_ gradient magnitude?\n\nLine 319-321: \"Therefore, with the adaptive attack, Gaussian training obtains a similar gradient norm distribution to SOTA algorithms\": I would no longer call the proposed method, with the adaptive attack, \"Gaussian training\"\n\n\"Furthermore, the community should also consider randomized smoothing methods with σ as a variable rather than a hyperparameter, thus effectively removing the dependence on σ. While there are some preliminary works in this direction (Nurlanov et al., 2023), they usually break the theoretical rigor, thus more research is needed in this direction.\" Nurlanov et al is not a relevent citation (it does not use randomized smoothing.) There are works in this direction, however, as noted, there are issues with correctness in many of these works. see (Sukenik et al,\"Intriguing Properties of Input-Dependent Randomized Smoothing\" ICML 2022) for further discussion.\n\n\nUse of capital I for both identity matrix and indicator function is confusing; would use bold 1 instead for indicator function.\n\nProof of Theorem 1: the proof seems to implicitly be using binomial (Clopper-Pearson) confidence interval; I would be more explicit about it.", "questions_for_authors": "- Is there any _quantitative evidence_ that the _proportion of published randomized smoothing papers which use ACR_ is above 50\\%? If so, how many use ACR alone? \n\n- Does the observed trend apply to datasets other than CIFAR-10?\n\n++++++++++++++++++++++\nBoth questions were responded to during rebuttal period: I am increasing my score to 'Weak accept'.", "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": "IGYCIS7oPf", "reviewer": "Reviewer_gJ9M", "summary": "This paper studies the shortcomings of Aversage Certified Radius (ACR) as a performance metric for randomized smoothing. It shows theoretically that this metric can be “hacked” by a trivial classifier with an arbitrarily large certified radius on a small number of “easy” input points, thereby achieving SOTA performance under this metric. It confirms this theoretical finding empirically by designing model training strategies that discount hard input samples, prioritize easy samples, and put more weight on higher certified radii. Based on its findings, it argues for the discontinuation of ACR as a metric for evaluating randomized smoothing-based robustness techniques.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer $\\Rg$ for the insightful review. We are happy that Reviewer $\\Rg$ finds that our paper is easy to understand, and that our work provides both theoretical and empirical evidence to justify our conclusion. We address all concerns from Reviewer $\\Rg$ below. We include new results, named with Figure S1 etc., in the [anonymized link](https://mega.nz/file/2NtyHIpA#EcvgiAMI7xMjXTgcGHnVpWdg-U2QnojAPVqF7peCMwM).\n\n\n**Q1: ACR is rarely used as a stand-alone metric. Is the claim that “ACR is the most important metric” proper?**\n\nWe agree that claiming ACR is the most important metric is improper. To gain quantitative insights, we perform a literature survey in RS for publications on top conferences (ICML, ICLR, AAAI, NeurIPS), ranging from 2020 (since the first evaluation with ACR) to 2024. We only include works that use the certification algorithm proposed by Cohen et al. and propose general-purpose dataset-agnostic RS algorithms. We identify 13 works with the specified criteria, and report for each of them (1) whether ACR is evaluated, (2) whether universal improvement in certified accuracy is achieved at various radii, (3) whether a customized base model is used (either parameter tuning or architecture design) and (4) whether claims SOTA. The result is shown in Table S4.\n\nAmong them we find 10 works that customize the model and claim SOTA, which is the focus of our study. 8 of them evaluate with ACR, and 7 of them claim SOTA solely based on ACR, i.e., claim SOTA without universal improvement in certified accuracy at various radii. Therefore, we conclude that ACR is of great importance to the field, and the practice of claiming SOTA based on ACR is widely spread. We will incorporate this study in the revised manuscript and revise the statement about the role of ACR accordingly.\n\n\n**Q2: The method proposed in this paper only has a marginal improvement on ACR compared to state-of-the-art (SOTA) approaches. Does this weaken the conclusion?**\n\nOur finding is that simply focusing on easy samples with the proposed Algorithm 2 replicate the progress in RS training strategies. Therefore, our method is **not** designed to achieve great advances in ACR further; instead, it is to prove how unreliable the evaluation of ACR could be. Therefore, we do not view the relatively small improvement over SOTA as a limitation of this work.\n\n**Q3: The theoretical analysis is straightforward and unsurprising. Does it mean that the paper lacks originality?**\n\nWe agree that the theoretical analysis is straightforward but kindly disagree that it is unsurprising. First, to the best of our knowledge, this analysis has never been done before, leaving the weakness of ACR unknown yet. As a result, ACR is still widely adopted in RS training, as discussed in Q1. Second, the theoretical analysis serves as a crucial foundation for our empirical analysis and motivates our proposal to abandon ACR as the central metric for evaluating RS training algorithms. Therefore, we kindly disagree with the claim that our theoretical analysis lacks originality or significance.", "claims_and_evidence": "1. The paper argues that ACR is not a proper metric for evaluating randomized smoothing. However, most works in this field do not use ACR as the sole evaluation metric. The primary evaluation metric is certified accuracy at different values of the certified radius. This metric does not have the shortcomings of the ACR metric. Even the two works cited by this paper to argue that ACR is being used by the community continuously only use ACR as a secondary evaluation metric together with certified accuracy. Thus, the paper’s claim that ACR “has emerged as the most important metric for comparing methods and tracking progress in the field” is debatable. \n\n2. The theoretical claims regarding a trivial classifier achieving infinite ACR by over-optimizing on easy samples have been validated with short proofs of correctness. However, the theoretical claims are straightforward and not very surprising. Please see my comments under “Theoretical Claims”.", "methods_and_evaluation_criteria": "The paper proposes three modifications to training with Gaussian noise, namely discarding hard inputs, reweighting samples with approximate certified radius and attacking the noised samples, to develop a new method to achieve state-of-the-art performance under the ACR metric. This method shows that improving the ACR metric is indeed possible without actually making the model more robust. However, the method only achieves marginal improvements in ACR over existing methods, as shown in Table 2.", "theoretical_claims": "Proofs of theorems 1 and 2 are both correct. However, as mentioned earlier, these theorems are straightforward and the insights are unsurprising. Theorem 1 formalizes that a trivial classifier can achieve an arbitrarily high ACR by simply predicting the most likely class for all inputs, thereby having infinite certified radii for samples for this class and blowing up the ACR metric. Theorem 2 merely states that two points with the same L_2 norm have the same probability density under an isometric Gaussian distribution.", "experimental_designs_or_analyses": "The experiments and analyses are reasonable for showing the weaknesses of the ACR metric.", "relation_to_broader_scientific_literature": "I am unaware of other works that study the weaknesses of evaluation metrics for certified robustness.", "essential_references_not_discussed": "Several well-known works in this field do not use ACR as their evaluation metric. For instance, [1] and [2] evaluate the certified robustness of RL agents using metrics such as certified reward, which does not suffer from the weaknesses of ACR. The paper should include more examples of works in the field and discuss the metrics used by them to give the reader a better understanding of how commonly the ACR metric is used as the primary evaluation metric in the literature. \n\n[1] CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing, Wu et al, ICLR 2022.\n\n[2] Policy Smoothing for Provably Robust Reinforcement Learning, Kumar et al, ICLR 2022.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is clearly written and easy to understand.\n\n2. It provides theoretical and empirical evidence to justify that ACR is a poor metric for randomized smoothing.\n\nWeaknesses:\n\n1. The claim “the average certified radius (ACR) has emerged as the most important metric for comparing methods and tracking progress in the field” is not well substantiated. Please see my comments under “Claims And Evidence” and “Essential References Not Discussed.”\n\n2. The theoretical claims lack originality. Please see my comments under “Theoretical Claims”.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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: The paper investigates the validity of the Average Certified Radius (ACR) as a measure of robustness. The reviewer overall assessed the results positively; however, there are some concerns that need to be addressed, such as supporting some of the claims in the paper by citing relevant references. The paper should include more examples of works in the field and discuss the metrics used by those works to give the reader a better understanding of how commonly the ACR metric is used as the primary evaluation metric in the literature. Including datasets with more natural images is also suggested, and some issues related to easy samples and ACR need to be further discussed.
Decision: Accept (poster)