Average Certified Radius is a Poor Metric for Randomized Smoothing

## Abstract

Abstract Randomized smoothing is a popular approach for providing certified robustness guarantees against adversarial attacks, and has become a very active area of research. Over the past years, the average certified radius (ACR) has emerged as the single most important metric for comparing methods and tracking progress in the field. However, in this work, we show that ACR is an exceptionally poor metric for evaluating robustness guarantees provided by randomized smoothing. We theoretically show not only that a trivial classifier can have arbitrarily large ACR, but also that ACR is much more sensitive to improvements on easy samples than on hard ones. Empirically, we confirm that existing training strategies that improve ACR reduce the model’s robustness on hard samples. Further, we show that by focusing on easy samples, we can effectively replicate the increase in ACR. We develop strategies, including explicitly discarding hard samples, reweighing the dataset with certified radius, and extreme optimization for easy samples, to achieve state-of-the-art ACR, although these strategies ignore robustness for the general data distribution. Overall, our results suggest that ACR has introduced a strong undesired bias to the field, and better metrics are required to holistically evaluate randomized smoothing.

## 1 Introduction

Adversarial robustness, namely the ability of a model to resist arbitrary small perturbations to its input, is a critical property for deploying machine learning models in security-sensitive applications. Due to the incompleteness of adversarial attacks which try to construct a perturbation that manipulates the model (Athalye et al., ), certified defenses have been proposed to provide robustness guarantees. While deterministic certified defenses (Gowal et al., ; Mirman et al., ; Shi et al., ; Müller et al., ; Mao et al., ; ; Palma et al., ; Balauca et al., ) incur no additional cost at inference-time, randomized certified defenses scale better with probabilistic guarantees at the cost of multiplied inference-time complexity. The most popular randomized certified defense is Randomized Smoothing (RS) (Lécuyer et al., ; Cohen et al., ), which computes the maximum certified radius for every input given the accuracy of a base model on noisy inputs $p_{A}$.

Figure: Figure 1: Conceptual illustration of the effect of RS training strategies.
Refer to caption: x1.png

To train better models with larger certified radius under RS, many training strategies have been proposed (Cohen et al., ; Salman et al., ; Jeong & Shin, ; Zhai et al., ; Jeong et al., ). 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. However, in this work, we show that ACR is a poor metric for evaluating the true robustness of a given model under RS. We prove theoretically that ACR of a trivial classifier could be arbitrarily large given enough certification budget, and then show empirically that state-of-the-art (SOTA) RS training strategies reduce the accuracy on hard inputs to increase the ACR. Further, we demonstrate that through explicitly reweighing the training data to focus only on easy inputs, the simplest Gaussian training can be gradually amplified to achieve a SOTA ACR, questioning the development of RS training strategies.

#### Main Contributions

Our key contributions are:

- •
We theoretically prove 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 (Section 4.1 and Section 4.2).
- •
We empirically compare RS training strategies to Gaussian training and show that all current RS training strategies are actually reducing the accuracy on hard inputs where $p_{A}$ is relatively small, and only focus on easy inputs where $p_{A}$ is very close to 1 to increase ACR (Section 4.3). Figure 1 conceptually visualizes this effect.
- •
Based on these novel insights, we develop strategies to amplify Gaussian training to achieve a SOTA ACR by reweighing the training data to focus only on easy inputs. Specifically, we discard hard inputs during training, reweigh the dataset with their contribution to ACR, and push $p_{A}$ extremely close to 1 for easy inputs via adversarial noise selection. With these simple modifications to Gaussian training, which do not optimize robustness for the general data distribution, but only ACR, we achieve a new SOTA in ACR (Section 5 and Section 6).

Overall, our work proves the need for new metrics for RS. In particular, we suggest to use certified accuracy at various radii as a more informative metric and encourage the community to re-evaluate existing RS training more uniformly (Section 7). We hope this work can inspire future research in this direction.

## 2 Related Work

Randomized Smoothing (RS) is a defense against adversarial attacks that provides certified robustness guarantees (Lécuyer et al., ; Cohen et al., ). However, to achieve strong certified robustness, special training strategies tailored to RS are essential. Gaussian training, which adds Gaussian noise to the original input, is the most common strategy, as it naturally aligns with RS (Cohen et al., ). Salman et al. () propose to add adversarial attacks to Gaussian training, and Li et al. () propose a regularization to control the stability of the output. Salman et al. () further shows that it is possible to exploit a pretrained non-robust classifier to achieve strong RS certified 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. () propose an attack-free mechanism that directly maximizes certified radii; Jeong & Shin () propose a regularization to improve the prediction consistency; Jeong et al. () propose to calibrate the confidence of smoothed classifier; Horváth et al. () propose to use ensembles as the base classifier to reduce output variance; Vaishnavi et al. () apply knowledge transfer on the base classifier; Jeong et al. () distinguishes hard and easy inputs and apply different loss for each class. While they all improve ACR, this work shows that ACR is a poor metric for robustness, and that these training algorithms 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 alternatives.

## 3 Background

In this section, we briefly introduce the background required for this work.

Adversarial Robustness is the ability of a model to resist arbitrary small perturbations to its input. Formally, given an input set $S(x)$ and a model $f$, $f$ is adversarially robust within $S(x)$ iff for any $x_{1},x_{2}\in S(x)$, $f(x_{1})=f(x_{2})$. In this work, we focus on the $L_{2}$ neighborhood of an input, i.e., $S(x):=B_{\epsilon}(x)=\{x^{\prime}\mid\|x-x^{\prime}\|_{2}\leq\epsilon\}$ for a given $\epsilon\geq 0$. For a given $(x,y)$ from the dataset $({\mathcal{X}},{\mathcal{Y}})$, $f$ is robustly correct iff $\forall x^{\prime}\in S(x)$, $f(x^{\prime})=y$.

Randomized Smoothing constructs a smooth classifier $\hat{f}(x)$ given a base classifier $f$, defined as follows: $\hat{f}(x):=\operatorname*{arg\,max}_{c\in{\mathcal{Y}}}\mathbb{P}_{\delta\sim
{\mathcal{N}}(0,\sigma^{2}I)}(f(x+\delta)=c)$. Intuitively, the smooth classifier assigns the label with maximum probability in the neighborhood of the input. With this formulation, Cohen et al. () proves that $\hat{f}$ is adversarially robust within $B_{R(x,p_{A})}(x)$ when $p_{A}\geq 0.5$, where $R(x,p_{A}):=\sigma\Phi^{-1}(p_{A})$, $\Phi$ is the cumulative distribution function of ${\mathcal{N}}(0,1)$ and $p_{A}:=\max_{c\in{\mathcal{Y}}}\mathbb{P}_{\delta\sim{\mathcal{N}}(0,\sigma^{2
}I)}(f(x+\delta)=c)$ is the probability of the most likely class. Average Certified Radius (ACR) is defined as the average of $R(x,p_{A})I(\hat{f}(x)=y)$ over the dataset. In practice, $p_{A}$ cannot be computed exactly, and an estimation $\hat{p}_{A}$ such that $\mathbb{P}(p_{A}\geq\hat{p}_{A})\geq 1-\alpha$ is substituted, where $\alpha$ is the confidence threshold and $\hat{p}_{A}$ is computed based on $N$ trials for the event $I(f(x+\delta)=c)$. We call $N$ the certification budget, which is the number of queries to the base classifier $f$ to estimate $p_{A}$. Since RS certifies robustness based on the accuracy of the base model on samples perturbed by Gaussian noise, *Gaussian training*, which augments the train data with Gaussian noise, is the most common method to train the base model for RS. Specifically, it optimizes

$$ $\operatorname*{arg\,min}_{\theta}\mathbb{E}_{(x,y)\sim({\mathcal{X}},{\mathcal {Y}})}\frac{1}{m}\sum_{i=1}^{m}L(x+\delta_{i};y)$ $$

where $\delta_{i}$ are sampled from ${\mathcal{N}}(0,\sigma^{2}I)$ uniformly at random, $m$ is the number of samples and $L$ is the cross entropy loss.

## 4 Weakness of ACR and the Consequence

We now first theoretically show that ACR can be arbitrarily large for a trivial classifier, assuming enough budget for certification (Section 4.1). We then demonstrate that with a realistic certification budget, an improvement on easy samples could contribute more than 1000 times to ACR than on hard samples (Section 4.2). Finally, we empirically show that due to the above weakness of ACR, all current RS training strategies evaluated with ACR reduce the accuracy on hard samples and only focus on easy samples (Section 4.3), improving ACR at the cost of performance on hard samples.

### 4.1 Trivial Classifier with Infinite ACR

In Theorem 1 below we show that for every classification problem, there exists a trivial classifier with infinite ACR given enough budget for certification, while such a classifier 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 $\alpha>0$, there exists a trivial classifier $f$ which always predicts the same class with a certification budget $N>0$, such that the ACR of $f$ is greater than $M$ with confidence at least $1-\alpha$.

###### Proof.

Assume we are considering a $K$-class classification problem with a dataset containing $T$ samples. Let $c^{*}$ be the most likely class and $X^{*}$ be the set of all samples with label $c^{*}$; then there are at least $\lceil T/K\rceil$ samples in $X^{*}$ due to the pigeonhole theorem. We then show that a trivial classifier $f$ which always predicts $c^{*}$ can achieve an ACR greater than $M$ with confidence at least $1-\alpha$ with a proper budget $N$.

Note that $p_{A}=1$ for $x\in X^{*}$, and thus the certified radius of $x\in X^{*}$ is $R(x)=\sigma\Phi^{-1}(\alpha^{1/N})$. Therefore, $\text{ACR}=\frac{1}{T}\left[\sum_{x\in X^{*}}R(x)+\sum_{x\notin X^{*}}R(x)
\right]\geq\frac{1}{T}\sum_{x\in X^{*}}R(x)\geq\frac{1}{K}\sigma\Phi^{-1}(
\alpha^{1/N})$. Setting $N=\lceil\frac{\log(\Phi(MK/\sigma))}{\log(\alpha)}\rceil+1$, we have $\text{ACR}>M$.
∎

Theorem 1 shows that ACR can be arbitrarily large for a trivial classifier with large enough certification budget. This implies that ACR is not reliable for evaluating a model under RS, as a trivial classifier can achieve infinite ACR with minimal robustness on at least half of classes. In practice, the budget certification $N$ is usually limited, and thus $R(x,p_{A})$ is bounded by a constant for every $x$ and $p_{A}$. In this case, the ACR of a trivial classifier is also bounded. However, in Section 4.2 below, we will show that this is still problematic, as ACR is much more sensitive to improvements on easy samples than on hard samples.

###### Theorem 1 .

###### Proof.

### 4.2 ACR Strongly Prefers Easy Samples

Figure: (a)
Refer to caption: x2.png

We now discuss the effect of ACR with a limited budget. We follow the standard certification setting in the literature, setting $N=10^{5}$ and $\alpha=0.001$. With this budget, the maximum certified radius for one input is $R(x,p_{A}=1)=\sigma\Phi^{-1}(\alpha^{1/N})\approx 3.8\sigma$. However, we will show that $\frac{\partial R(x,p_{A})}{\partial p_{A}}$ grows extremely fast, exceeding $1000\sigma$ when $p_{A}\rightarrow 1$ and close to 0 0 when $p_{A}\rightarrow 0.5$.

Without loss of generality, we set $\sigma=1$ and denote $R(x,p_{A})$ as $r$. Figure 2 shows $r$ and $\frac{\partial r}{\partial p_{A}}$ against $p_{A}$. While $r$ remains bounded by a constant $3.8$, $\frac{\partial r}{\partial p_{A}}$ grows extremely fast when $p_{A}$ approaches 1. As a result, increasing $p_{A}$ from $0.99$ to $0.999$ improves $r$ from $2.3$ to $3.0$, matching the improvement achieved by increasing $p_{A}$ from 0 0 to $0.76$. Therefore, to achieve maximum ACR, it is much more efficient for the training algorithm to focus on improving $p_{A}$ on easy samples where $p_{A}$ is close to 1. Further, when $p_{A}<0.5$, the data point will not contribute to ACR at all, thus optimizing ACR will not increase $p_{A}$ with a local optimization algorithm like gradient descent. Therefore, it is natural for RS training to disregard inputs with $p_{A}<0.5$ as their ultimate goal is to improve ACR.

### 4.3 RS Training Trades off Hard Samples for ACR

We have shown that ACR strongly prefers easy samples in Section 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 objectives, and finally evaluate the model with ACR. Thus, it is unclear whether and to what extent the design of training algorithms is affected by the ACR metric. We now empirically quantify the effect, confirming the theoretical analysis. Specifically, we show that SOTA training strategies reduce $p_{A}$ of hard samples and put more weight (measured by gradient norm) on easy samples compared to Gaussian training.

Figure 3 shows the empirical cumulative distribution of $p_{A}$ for models trained with SOTA algorithms and Gaussian training. Clearly, for various $\sigma$, SOTA algorithms have higher density than Gaussian training at $p_{A}$ close to zero and one. While they gain more ACR due to the improvement on easy samples, hard samples are consistently underrepresented in the final model compared to Gaussian training. As a result, Gaussian training has higher $\mathbb{P}(p_{A}\geq 0.5)$ (clean accuracy), and SOTA algorithms exceed Gaussian training only when $p_{A}$ passes a certain threshold, i.e., when the certified radius is relatively large. This is problematic in practice, indicating that ACR does not properly measure the model’s ability. 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.

Figure: (a) $\sigma=0.25$
Refer to caption: x4.png

To further quantify the relative weight between easy and hard samples indicated by each training algorithm, we measure the average gradient $l_{2}$ norm of easy and hard samples for models trained with different algorithms and $\sigma=0.5$, as a proxy for the sample weight. Intuitively, samples with larger gradients contribute more to training and thus are more important for the final model. As shown in Table 1, 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 CAT-RS (Jeong et al., ), while for Gaussian training it is 0.45. This confirms that SOTA algorithms indeed prioritize easy samples over hard samples, consistent with the theoretical analysis in Section 4.2.

Table: Table 1: The average gradient $l_{2}$ norm of easy ($p_{A}>0.5$) and hard ($p_{A}<0.5$) samples for models trained with different algorithms and $\sigma=0.5$, along with their relative magnitude (*easy / hard*). The corresponding ACR is also shown.

## 5 Amplifying Easy Data Greatly Improves ACR

In Section 4, we concluded that ACR strongly prefers easy samples, and RS training trades off hard samples for ACR. This raises the question of whether explicitly focusing on easy data during training can effectively replicate the increase in ACR. In this section, we propose three modifications to the simplest Gaussian training to achieve this goal.

### 5.1 Discard Hard Data During Training

Samples with low $p_{A}$ contribute little to ACR, especially those with $p_{A}<0.5$ which have no contribution at all (Section 4.2). Further, as shown in Figure 3, more than 20% of the data has $p_{A}<0.5$ after training converges. Therefore, we propose to discard hard samples directly during training, so that they explicitly have no effect on the final training convergence. Specifically, given a warm-up epoch $E_{t}$ and a confidence threshold $p_{t}$, we discard all data samples with $p_{A}<p_{t}$ at epoch $E_{t}$. We fix the number of steps taken by gradient descent and re-iterate on the distilled dataset when necessary to minimize the difference in training budget. After the discard, Gaussian training also ignores hard inputs, similar to SOTA algorithms.

### 5.2 Data Reweighing with Certified Radius

Figure: Figure 4: Certified radius (divided by the value at $p_{A}=0.75$) and the sampling weight of the data against $p_{A}$.
Refer to caption: x7.png

ACR relates non-linearly to $p_{A}$, and the growth of the certified radius is much faster for easy samples with high $p_{A}$ (Figure 2). 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 probability for every data point being sampled. We formulate the weight $w$ of every data point $x$ as:

$$ $\displaystyle\hat{p}_{A}$ $\displaystyle=\textsc{LowerConfBound}(C,N,1-\alpha)$ $\displaystyle w$ $\displaystyle=\max(1,\Phi^{-1}(\hat{p}_{A})/\Phi^{-1}(p_{\rm min})),$ $$

where $C$ is the count of correctly classified noisy samples and $p_{\rm min}$ is the reference probability threshold. Note that the estimation of $\hat{p}_{A}$ aligns with the certification. We normalize the weight to be at least 1 since the original radius is zero when $p_{A}$ is relatively low. To minimize computational overhead, we evaluate $\hat{p}_{A}$ every 10 epoch with $N=16$ and $\alpha=0.1$ throughout the paper. We set $p_{\rm min}=0.75$ because this is the minimum probability that has positive certified radius under this setting. The sampling weight curve is visualized in Figure 4. After the reweighing, ACR has an approximately linear relationship to $p_{A}$ when $w>1$, and easy samples are sampled more frequently than hard samples so that Gaussian training also improves $p_{A}$ further for easy samples.

### 5.3 Adaptive Attack on the Sphere

Figure: Algorithm 1 Adaptive Attack

SOTA algorithms re-balance the gradient norm of easy and hard samples in contrast to Gaussian training (Table 1). In addition, when $p_{A}$ is close to 1, Gaussian training can hardly find a useful noise sample to improve $p_{A}$ further. To tackle this issue, we propose to apply adaptive attack on the noise samples to balance samples with different $p_{A}$. Specifically, we use Projected Gradient Descent (PGD) (Madry et al., ) to find the nearest noise to the Gaussian noise which can make the base classifier misclassify. Formally, we construct

$$ $\delta^{*}=\operatorname*{arg\,min}_{f(x+\delta)\neq c,\|\delta\|_{2}=\|\delta _{0}\|_{2}}\|\delta-\delta_{0}\|_{2},$ $$

where $\delta_{0}$ is a random Gaussian noise sample. Note that when $x+\delta_{0}$ makes the base classifier misclassify, we have $\delta^{*}=\delta_{0}$, thus hard inputs are not affected by the adaptive attack. In addition, we remark that we do not constrain $\delta^{*}$ to be in the neighborhood of $\delta_{0}$ which is adopted by CAT-RS (Jeong et al., ); instead, we only maintain the $l_{2}$ norm of the noise, thus allowing the attack to explore a much larger space. This is because for every $\delta^{*}$ such that $\|\delta^{*}\|_{2}=\|\delta_{0}\|_{2}$, the probability of sampling $\delta^{*}$ is the same as $\delta_{0}$. We formalize this fact in Theorem 2.

###### Theorem 2 .

Assume $\delta_{1},\delta_{2}\in{\mathbb{R}}^{d}$ and $\delta_{1}\neq\delta_{2}$. If $\|\delta_{1}\|_{2}=\|\delta_{2}\|_{2}$, then $\mathbb{P}_{{\mathcal{N}}(0,\sigma^{2}I_{d})}(\delta_{1})=\mathbb{P}_{{
\mathcal{N}}(0,\sigma^{2}I_{d})}(\delta_{2})$ for every $\sigma>0$.

###### Proof.

Let $\delta=[q_{1},q_{2},\dots,q_{d}]\in{\mathbb{R}}^{d}$ be sampled from ${\mathcal{N}}(0,\sigma^{2}I_{d})$.
Then we have

$$ $\mathbb{P}(\delta)=\frac{1}{(2\pi)^{d/2}\sigma^{d}}\exp\left(-\frac{1}{2\sigma ^{2}}\sum_{i=1}^{d}q_{i}^{2}\right)=\frac{1}{(2\pi)^{d/2}\sigma^{d}}\exp\left( -\frac{1}{2\sigma^{2}}\|\delta\|_{2}^{2}\right).$ $$

This concludes the proof.
∎

Figure: (a) Before adaptive attack
Refer to caption: x8.png

Figure 5 visualizes the gradient norm distributions for different $p_{A}$ before and after the adaptive attack. We observe that the adaptive attack balances the gradient norm of easy and hard samples. Before the attack, the gradient norm of easy samples is much smaller than that of hard samples, while after the attack, the gradient norm of easy samples is amplified without interfering the gradient norm of hard samples. Therefore, with the adaptive attack, Gaussian training obtains a similar gradient norm distribution to SOTA algorithms, and it can find effective noise samples more efficiently. Pseudocode of the adaptive attack is shown in Algorithm 1, and more detailed description is provided in Section A.2.

###### Theorem 2 .

###### Proof.

### 5.4 Overall Training Procedure

Figure: Algorithm 2 Overall Training Procedure

We now describe how the above three modifications are combined. At the beginning, we train the model with the Gaussian training (Cohen et al., ), which samples $m$ noisy points from the isometric Gaussian distribution uniformly at random and uses the average loss of noisy inputs as the training loss. When we reach the pre-defined warm-up epoch $E_{t}$, all data points with $p_{A}<p_{t}$ are discarded, and the distilled dataset is used thereafter, as described in Section 5.1. After this, we apply dataset reweighing and the adaptive attack to training. Specifically, every 10 epoch after $E_{t}$ (including $E_{t}$), we evaluate the model with the procedure described in Section 5.2 and assign the resulting sampling weight to each sample in the train set. In addition, we use the adaptive attack described in Section 5.3 to generate the noisy samples for training. The pseudocode is shown in Algorithm 2.

## 6 Experimental Evaluation

We now evaluate our proposed method extensively.
Overall, our method always achieves better ACR than SOTA methods, which indicates that focusing on easy data can effectively improve ACR.

Baselines. We compare our method to the following methods: Gaussian (Cohen et al., ), SmoothAdv (Salman et al., ), MACER (Zhai et al., ), Consistency (Jeong & Shin, ), SmoothMix (Jeong et al., ), and CAT-RS (Jeong et al., ). 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. We set $m=4$ for Gaussian training and our method, since this is the standard setting for SOTA methods (Jeong et al., ).

Main Result. Table 2 shows the ACR of different methods on CIFAR-10. Detailed description of the training, including applied hyperparameters, is provided in Section A.1. Our method consistently outperforms all baselines on ACR, which confirms the effectiveness of our modification 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 systematically worse than Gaussian training, while at large radii, these methods consistently outperform Gaussian training.
The success of our simple and intuitive modification to Gaussian training suggests that ACR introduces a systematic bias in method selection, and that the field should re-evaluate RS training strategies with better metrics.

Table: Table 2: 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.

Figure: (a) $\sigma=0.25$
Refer to caption: x10.png

Table: Table 3: Ablation study on each component in our method.

Ablation Study. We present a thorough ablation study in Table 3. 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 improvement of ACR. In addition, they mostly improve the certified accuracy at large radii and reduce certified accuracy at small radii, which is consistent with our intuition that focusing on easy inputs can improve the ACR. More ablation on the hyperparameters is provided in Appendix B.

## 7 Discussion

We have shown that ACR does not uniformly represent the robustness of a model for different data. Therefore, the field has to seek better alternative metrics to evaluate the robustness of models under RS. We suggest to use certified accuracy at various radii as a more informative metric, which can be easily computed with the same certification budget as ACR. In addition, since achieving maximum certified accuracy at all radii is a challenging task, we should allow algorithms to customize models for different radii, including the certification hyperparameter $\sigma$. This is similar to the practice in deterministic certified training (Gowal et al., ; Mirman et al., ; Shi et al., ; Müller et al., ; Mao et al., ; ; ; Palma et al., ; Balauca et al., ).

While our modifications presented in Section 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 metrics which considers robustness more uniformly should be developed to evaluate RS, and algorithms that outperform generally at various radii are encouraged. We hope this work can inspire future research in this direction.

## 8 Conclusion

This work rigorously demonstrates that Average Certified Radius (ACR) is a poor metric for Randomized Smoothing (RS). Theoretically, we prove that ACR of a trivial classifier can be arbitrarily large, and that an improvement on easy inputs contributes much more to ACR than on hard inputs. 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 reweighing the training data to focus only on easy inputs. Specifically, we discard hard inputs during training, weight the dataset with their contribution to ACR, and 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 a new SOTA ACR. Overall, our results suggest the need for evaluating RS training with better metrics.

## Appendix A Experiment Details

### A.1 Training Details

We follow the standard training protocols in previous works. Specifically, we use ResNet-110 (He et al., ) for CIFAR-10. We investigate three noise levels, $\sigma=0.25,0.5,1.0$. We train the model for 150 epochs with an initial learning rate of 0.1, which is decreased by a factor of 10 in every 50 epochs. Stochastic gradient descent (SGD) optimizer with a momentum of 0.9 is used, and the batch size is set to 256. We adjust the following hyperparameters to find the best performance for each setting:

$$ $\displaystyle E_{t}$ $\displaystyle=\text{the epoch to discard hard data samples}$ $\displaystyle p_{t}$ $\displaystyle=\text{the threshold of $p_{A}$ to discard hard data samples}$ $\displaystyle T$ $\displaystyle=\text{the maximum number of steps of the PGD attack}$ $\displaystyle\epsilon$ $\displaystyle=\text{the step size of the PGD attack}$ $$

All other parameters are fixed to their default values. Specifically, we use 100 noise samples ($N=100$) to calculate $p_{A}$ when discarding hard samples. For updating dataset weight, we use 16 noise samples ($N=16$) to calculate $p_{A}$, with a minimum value set to 0.75 ($p_{\rm min}$=0.75). The number of noise samples for each input is set to $m=4$. The hyperparameters we use on CIFAR-10 are shown in Table 4.

We use the Certify function in Cohen et al. () to calculate the certified radius, same as previous baselines, where $N=10^{5}$ and $\alpha=0.001$.

Table: Table 4: Hyperparameters we use on CIFAR-10.

### A.2 Adversarial Attack Algorithm

In the adaptive attack, we implement the $l_{2}$ PGD and $l_{\infty}$ PGD attack. The difference between them lies in how the noise is updated based on the gradient.
For $l_{2}$ PGD, the noise is updated as follows:

$$ $\delta^{*}=\delta+\epsilon\cdot\nabla_{\delta}L(f(x+\delta),y)/\|\nabla_{ \delta}L(f(x+\delta),y)\|_{2},$ $$

while for $l_{\infty}$ PGD, the noise is updated as follows:

$$ $\delta^{*}=\delta+\epsilon\cdot\text{sign}(\nabla_{\delta}L(f(x+\delta),y)),$ $$

where $L$ is the loss function, $f$ is the model, $x$ is the input, $y$ is the label, $\delta$ is the noise, $\delta^{*}$ is the updated noise, sign is the sign function, and $\epsilon$ is the step size.
Without specific instructions, our experiments are always conducted with $l_{2}$ PGD. We show the results with $l_{\infty}$ PGD on CIFAR-10 in Section C.2.

## Appendix B Additional Ablation Studies

In this section, we provide additional ablation studies on the effect of different hyperparameters. All results are based on $\sigma=0.5$ and CIFAR-10. Unless otherwise specified, all hyperparameters are the same as those in Table 4.

### B.1 Effect of Discarding Hard Data

Table: Table 5: Effect of the discarding epoch $E_{t}$.

Table: Table 6: Effect of the discarding $p_{A}$ threshold $p_{t}$.

We investigate the effect of the two hyperparameters $E_{t}$ and $p_{t}$ in discarding hard samples. The results are shown in Table 5 and Table 6.
If hard samples are discarded too early, it leads to a decrease in accuracy for all radii, as many potential easy samples are discarded before their $p_{A}$ reaches $p_{t}$. 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.

### B.2 Effect of Adaptive Attack

Table: Table 7: Effect of the adversarial attack step size $\epsilon$.

Table: Table 8: Effect of the number of steps of adversarial attack $T$.

Figure: (a) Effect of $\epsilon$
Refer to caption: x13.png

Table: Table 9: ACR and certified accuracy under the $l_{\infty}$ PGD attack with $\sigma=0.5$ on CIFAR-10 with different step size.

Table: Table 10: ACR and certified accuracy under the $l_{\infty}$ PGD attack with $\sigma=0.5$ on CIFAR-10 with different number of steps.

For the adaptive attack, we evaluate the effect of the step size $\epsilon$ and the number of steps $T$. The results are shown in Table 7 and Table 8. In general, increasing the number of steps strengthens the attack, which helps find effective noise samples for extremely easy inputs. As a result, performance improves at larger radii, but relatively less attention is given to hard samples, leading to a decrease in clean accuracy. Similarly, increasing the step size in a moderate range ($\epsilon<1.0$) has a similar effect. However, if the step size is too large, the attack loses effectiveness, resulting in decreased performance at all radii.

## Appendix C Additional Results

### C.1 Ratio of Remained Data after Discarding Hard Samples

The remaining data ratios after discarding hard samples under different $\sigma$ on CIFAR-10 are $91\%$, $80\%$ and $58\%$, when $\sigma=0.25$, $0.5$ and $1.0$ respectively. The results indicate that even though a significant portion of the training set is discarded during training, we still achieve a better ACR than the current SOTA model according to Table 2. This indicates that discarding a large amount of data during training leads to a better ACR, proving once again that ACR may not accurately represent the overall robustness of the model.

### C.2 Experiments on l ∞ subscript 𝑙 l_{\infty} italic_l start_POSTSUBSCRIPT ∞ end_POSTSUBSCRIPT PGD Attack

In this section, we show the results under $l_{\infty}$ PGD attack in Table 9 and Table 10. For $l_{\infty}$ attack, we use much smaller step sizes $\epsilon$ to have the similar attack strength to $l_{2}$ attack. Specifically, we investigate $\sqrt{d}\cdot\epsilon=0.125,0.25,1.5,1.0$ for $l_{\infty}$ attack, where $d$ is the dimension of the input. After the thorough experiments, we find that using $\sqrt{d}\cdot\epsilon=0.25$ and the same with $l_{2}$ attack for other hyperparameters reaches the best ACR.

The the $l_{\infty}$ attack has the similar effect on results to the $l_{2}$ attack. Increasing the step size or the number of steps of the attack will result in better accuracy at large radii but lower accuracy at small radii.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 5
presentation: 3
questions: No specific questions.
soundness: 3
strengths: 1. Revealing the problem of ACR to the randomized smoothing community, which rectifies the past error and promotes a more scientific evaluation protocol.

2. Technically sound and clear writing.
summary: This submission studies the metric of average certified radius (ACR) in randomized smoothing training literature. First, the submission theoretically shows that ACR is ill-posed in terms of unboundedness for trivial toy classifiers and uneven sensitivity for easy and hard samples. Then, harnessing these features, a training method that overly focuses on easy samples can hack the metric to achieve a state-of-the-art ACR.
weaknesses: 1. The impact is limited. ACR is a rather specific metric that mainly exists in the randomized smoothing literature. Moreover, in the literature, ACR is used in conjunction with certified accuracy under various radii - as a poor metric, the community is not overly focused on the metric yet.

2. Technical contribution is limited. It is relatively obvious to see the unboundedness of ACR (for a constant classifier) and the sensitivity with respect to $P_A$ is a direct consequence of $\Phi^{-1}(\cdot)$'s bounded domain and unbounded value domain.

3. The paper is overly focused on a narrow topic and can be benefited from better contextualization. For example, for randomized smoothing, diffusion-purification is an active and developing method, such as "(Certified!!) Adversarial Robustness for Free!", DensePure, and DiffSmooth; ensemble-based training is also widely studied such as Horvath et al (boosting) and Yang et al (on the certified...).


Minor:
The implication of Figure 1 on page 1 is not clear.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Recognizing that ACR is an inadequate metric, please include a more detailed discussion on designing a more effective comparison metric.
2. The training algorithm presented is based on adversarial methods; please add a comparison regarding computational overhead.
soundness: 3
strengths: This paper presents a fact that the Average Certified Radius (ACR) is an unfair metric for evaluating robustness in Randomized Smoothing (RS), which is helpful to future research on Randomized Smoothing.
summary: The paper discusses the limitations of using the Average Certified Radius (ACR) as a primary metric for evaluating robustness in Randomized Smoothing (RS), a technique used to defend machine learning models against adversarial attacks. The authors argue that ACR disproportionately focuses on easy samples and can be artificially inflated, even by trivial classifiers. Their key contributions include:
1.	Theoretical Analysis: The paper shows that a trivial classifier can achieve arbitrarily large ACR given a sufficient certification budget, proving that ACR is unreliable as a robustness measure.
2.	Empirical Findings: They demonstrate that existing state-of-the-art (SOTA) RS training strategies, which improve ACR, reduce model accuracy on hard samples, thus prioritizing easy samples.
3.	Proposed Solutions: The authors introduce training modifications—such as discarding hard samples, reweighing data based on certified radius, and applying adaptive adversarial attacks—that achieve a new SOTA ACR by focusing only on easy samples. These strategies improve ACR but ignore general robustness.
weaknesses: 1. Novelty is relatively limited. The first contribution suggests that the Average Certified Radius (ACR) can be increased arbitrarily by enlarging the sample size. However, [1] also finds that certified accuracy is closely related to sample size. Figure 4(a) in [1] demonstrates that as pA -> 1.0, the certified radius significantly increases with sample size. The existence of [1] diminishes the novelty of this paper, which also fails to reference this closely related work.

2. The logic of this paper is somewhat unnatural. While it proves that ACR is a poor metric because it favors easy samples, it would be more logical to design a more reasonable metric. Instead, the paper proposes a new training algorithm that gives more weight to easy samples, exploiting the weakness of the ACR metric to increase ACR.

3. The proposed training algorithm requires using Projected Gradient Descent (PGD) to compute adversarial examples, which is computationally expensive. This is why methods like MACER and consistency, choose attack-free training algorithms to mitigate computation costs.

[1] Input-Specific Robustness Certification for Randomized Smoothing. AAAI 2022.

---

confidence: 5
contribution: 3
initial_rating: 5
presentation: 2
questions: I mainly have two questions based on the points mentioned in weaknesses above, If they can be answered properly, specifically question 1, then I am willing to increase the rating.

1. Could you clarify how the limitations of **ACR** apply to **other RS methods**? Since ACR is also used in these methods to evaluate certified robustness, how do your findings extend to these approaches? It would be helpful to understand whether ACR is equally flawed in these contexts. Or if the work is specific to **training-based RS methods**?

2. You propose using **certified accuracy at various radii** as an alternative to ACR. Could you provide more specific guidance on how this should be applied in practice? For example, how should practitioners choose appropriate radii, and how would this approach balance performance across easy and hard samples?
soundness: 3
strengths: 1. **Originality and Significance:** The paper presents an original and critical perspective on a widely accepted metric in adversarial robustness, the **Average Certified Radius (ACR)**, which has been largely unchallenged in the literature. By demonstrating that ACR is a flawed metric for evaluating randomized smoothing (RS) models, the authors provide a fresh lens through which the community can reevaluate robustness. By exposing the weaknesses of ACR, the paper has significant implications for future research in the field of certified defenses. 

2. **Quality:** The theoretical analysis is well-supported by empirical results, making the paper technically sound. The authors back their theoretical claims with well defined experiments that verify their theoretical findings. The experiments are well-designed, with appropriate baselines and metrics to validate the claims. The paper covers a lot of **training based RS stratagies** to support their claims which further adds to the experimental aspect of this work.
summary: This paper evaluates the effectiveness of **Average Certified Radius (ACR)**, a popular metric for assessing model robustness against adversarial attacks, particularly within the context of **Randomized Smoothing (RS)**. The authors specifically target **existing training strategies**, showing that these methods provide a misleading sense of general robustness.

They prove that a trivial classifier can achieve arbitrarily high ACR with a large certification budget, despite being unreliable. Additionally, they demonstrate that ACR disproportionately benefits from improvements on "easy" samples, with gains potentially over 1000x greater than those on "hard" samples. Through experiments, they reveal that state-of-the-art (SOTA) RS training methods inflate ACR by focusing on easy inputs while sacrificing robustness on harder samples. To further critique ACR, the authors propose strategies to boost ACR artificially, such as discarding hard inputs and reweighing data, reinforcing the bias toward easy samples.

The paper concludes by highlighting the limitations of ACR, presenting experimental evidence, and advocating for a shift in how the field evaluates robustness in **randomized smoothing**, suggesting **certified accuracy at various radii** as a more reliable alternative metric.
weaknesses: 1. **Limited Scope**: The paper lacks proper clarity on one aspect, wether it's findings are specific to **training-based RS methods** or **Randomized Smoothing** in general.  If I understood correctly, than the theoretical analysis in section 4.1 is not specific to **training based RS methods**, but during evaluation the paper mainly critiques **ACR** for **training-based RS methods** but doesn't extend/discusses the impact of theoretical analysis to **other RS methods**, which also rely on ACR to evaluate certified robustness. Expanding the critique to cover these methods would provide a more comprehensive view and increase the impact of the findings. 

2. **Lack of Practical Guidance**: While the authors propose **certified accuracy at various radii** as an alternative metric, they don’t provide detailed guidance on how to implement it effectively in practice. Offering concrete steps or case studies on how this metric can be integrated into evaluation pipelines would make the solution more actionable. Furthermore, **certified accuracy at various radii* is a metric which is more commonly used, compared to ACR, to evaluate **other RS methods**, hence this further limits the scope of the work as it adds to the point that this work is only relevant to **training-based RS methods**.

Meta-review: This paper is the first to show that  the average certified radius (ACR) is a poor metric for evaluating robustness provided by randomized smoothing. The idea is interesting. But reviewers think the technical contribution is limited and topics of this paper is too narrow. It is better to appear in the workshop of the specific conferences.

Decision: Reject