Universally Amplifying Randomized Smoothing for Certified Robustness with Anisotropic Noise

Thank you for the insightful comments and please find our clarifications as below. We also make more clarifications in the paper to avoid confusion/misunderstanding.

1. On the Novelty of Theorem 3.2:

The paper presents only an incremental improvement on SOTA methods, and in many ways the main Theorem (3.2) is really no more than a simple Corollary from prior work with a simple affine transformation on the variables (which would usually be done anyway in dealing with non-image data with very different means and scales in each data dimension).

We respectfully clarify that the derived universal theories are not simple (by covering both strict robustness w.r.t. heterogeneous dimensions and universality), as detailed in Appendix A. Even if its conclusion might be considered as simple, as noted by Reviewer v1kJ, simple-but-effective solutions are not generally considered as ``weakness'', but would be desirable in practice.

2. Clarification on Isotropic Results:

In the experiments, it seems that the results vs $\{min \sigma_i\} R$ should be presented (per Corollary 3.3) for a fair comparison, i.e. it is not clear to me that the proposed technique certifies a strictly larger $L_p$ ball in the same conditions than SOTA (and what “same conditions” may mean is not clear e.g. it may mean isotropic $\sigma=1$ and $\prod \sigma_i = 1$ in anisotropic case). That said, the results in section 5.3 apparently include a certified accuracy wrt radius. It is not clear if this may be an answer to my query as it is not clear exactly what is being reported here.

In our experimental results, the “certified accuracy w.r.t radius” refers to certified accuracy w.r.t. $\min\{\sigma_i\}R$, which equals to the $\ell_p$ radius (e.g., the Gaussian $\ell_2$ case). Therefore, we did achieve a strictly larger $\ell_2$-ball than other SOTAs. In the entire paper (including Section 5.3), all the “radius” means traditional radius for the $\ell_p$ ball.

3. Input-dependent Certification Validity:

Re section 4.3, I am a bit confused. This input-dependent proposal would give an x-dependent sigma, and hence an x-dependent classifier (ie x-dependent noise, over and above the obvious dependence on x). Theorem 3.2 holds assuming the noise is constant in the ball around x. This proposal in 4.3 violates that surely. Hence it is no longer true that Theorem 3.2 guarantees that the classifier gives an unchanged output in the region claimed, and so the proposed classifier is not certified robust in the claimed region around x.

Regarding the input-dependent certification, we noticed the discussion in Eiras et al. (2021). We respectfully clarify that our input-dependent noise method is still sound and does not breach certification principles.

The $x$-dependent classifier is fixed in the certification on $x$, that means with $g(x,\mu(x),\sigma(x))$ and $R$, we are guaranteeing $g(x+\delta,\mu(x),\sigma(x))=g(x,\mu(x),\sigma(x))$ as described in Theorem 3.2 (note that noise is pre-computed and $\mu(x),\sigma(x)$ are actually constants). We do not change the $x$-dependent classifier during the certification, thus we achieve consistent prediction over such a specific classifier. This does not violate the certification of randomized smoothing, instead, it sticks to the inherent characteristics of the RS-based certification, i.e., input-dependence (The RS certification is inherently input-dependent since the radius $R(x)$ only works on the specific input $x$ and a specific classifier). Please also see the detailed explanation in our ``Common Concerns'' response.

4. Responses to Minor Comments:

• Binary Case: We appreciate this observation and have revised the caption of Table 1 accordingly.

• Metrics Clarification: The metric named $V'_S$ is referred to as ALM throughout the paper. We have amended the symbols to ALM for consistency and clarity.

• Performance at Small Radii: The reason SOTA methods perform better at smaller radii is due to the noise variance-prediction accuracy trade-off. Our method, with single $\lambda\approx 1$, competes with SOTA methods at various $\lambda$ settings. Notably, our Input-dependent method outperforms these trade-offs even with a single setting.

• Cohen's Tight Radius: We have revised the statement about Cohen's method to reflect its application more accurately.

Thank you for the insightful comments and please find our clarifications as below. We also make more clarifications in the paper to avoid confusion/misunderstanding.

1. On the Contribution and Novelty:

The first is the fact that the contribution in constructing the anistropic noise measures (the core conceit of the paper) is essentially just a basic modification to extant techniques, with no other modifications being made.

We would like to respectfully clarify that our core contribution is not on the construction of the ALM measure but on the theoretical analysis of the robustness bound when injecting anisotropic noise, as well as the framework and novel methods for customizing anisotropic noise. ALM is one of our metrics for evaluating the certified robustness with anisotropic noise while we also derive the traditional $\ell_p$ radii (Corollary 3.3) for the robustness region with anisotropic noise.

My primary concern relates to the alignment of the chosen area of investigation to the broader problem space. Specifically, I do not think that there is any framework (either in the literature or suggested in the framework) that would care about the area of the region of certification.

The certified $\ell_p$ radius can be seen as a measure for the area of the regular and symmetric robustness region within the overall robustness region (sub-region in $\ell_{1,2,\infty}$ shape). On the other hand, ALM provides a full capture of the overall robustness region (a comprehensive understanding of the theoretical guarantees and boundaries of the certified defense). These two metrics complement each other, and we have provided the results for both $\ell_p$ radius and ALM as well as performed evaluations on both of them in the original submission.

From the certifiers perspective, what information about the security of a model is gained by knowledge of the Lebesgue measure of the noise region (or any other measure of the area of certification)? The primary measure of risk is the nearest extant adversarial example - this is well established in the literature as a measure of the adversarial risk (see Gilmer's "Motivating the Rules of the Game for Adversarial Example Research", 2018), because this measures the effort required for an adversary to identify an adversarial example. Any other risk measure would need to be well justified and well posed, and this is not the case within this work.

Thanks for the insightful comment. We know that the certified radius provides the knowledge that any perturbation within the $\ell_p$ distance will not succeed. In practice, the defense may tolerate the perturbation of a larger distance in some dimensions (see Figure 1 (b)), how to measure this gain of robustness would be a problem. Therefore, we propose the complementary ALM metric to measure the full area of the (certified) robustness region.

As you stated, researchers may only care about the nearest extant adversarial example (AE), however, this AE indeed only measures the minimum effort required for finding an AE, while the ALM can be seen as a measure for showing the average effort required for finding an AE. These two metrics just reflect two different aspects of the certified defense, so we provide both the nearest measure ($\ell_p$ radius in Corollary 3.3) and the average measure (ALM). Our method significantly improves the certification performance under both measures.

Given that the certified distances to the nearest possible adversarial example are unchanged by your work, I do not see how this leads to an improved understanding of adversarial risk. I would argue that rather than significantly improving upon SOTA, you're introducing a new metric to mask the fact that you do not appear to produce any level of outperformance.

As discussed before, our method drastically improves the robustness against both the certified distance to the nearest possible AE (please see ``certified accuracy w.r.t. radius'' in Table 2-4 in our original submission) and the average distance measure (ALM).

The idea of including a headline figure of an 182.6% improvement over SOTA - anyone reading this who was not familiar with this field would assume that this would be an apples-to-apples comparison, but it's not. There's no SOTA for certification that cares about area driven measures of certification, and so claiming a comparison to these prior techniques is not reasonable or well justified.

The 182.6% gain over SOTA is under the evaluation of a standard certified $\ell_p$ radius (derived in Corollary 3.3, and measured via the ``certified accuracy w.r.t. radius'' in Table 2-4), which is an apples-to-apples comparison.

2. Addressing Minor Technical Issues:

Thanks for your observations regarding the minor issues. We have revised the notation to $||z||_\infty$.

Thank you for the insightful comments and please find our clarifications as below. We also make more clarifications in the paper to avoid confusion/misunderstanding.

1. On the Presenting of Related Works:

"However, its theory is based on assumptions and the universality is relatively limited." What assumptions? Please at least briefly mention them and why they are stringent.

Our approach does not need the assumptions in Eiras et al., where the classifier's $L$-Lipschitz continuity is a prerequisite. This assumption imposes limitations on the universality of their theorem. Conversely, our method is designed to work universally with any classifier, thereby offering broader applicability.

2 & 3. Regarding the Paper Revisions:

Definition 3.1 does not really appear to be a "definition" in mathematical terms. It looks more like you are re-stating the certified radius theorems for general distributions and norms. So, this should probably be labeled as a "theorem". Please move the definition/review of alternative Lebesgue measure to Section 3.1, where Table 1 appears with Alt. Lebesgue Measure as a column.

We appreciate your suggestions for improving the paper's structure and clarity. We have revised the paper accordingly, particularly in relabeling Definition 3.1 as a theorem and relocating the alternative Lebesgue measure definition to Section 3.1, as suggested.

4. Clarifications in Section 4.2:

In Section 4.2, the loss function is solely a function of the NPG parameters $\theta_g$, correct? If so, it would be good to explicitly write $\mathcal{L}(\theta_g)$ to emphasize to the reader what you are optimizing over. Furthermore, $\sigma$ and $\mu$ would be functions of this parameter $\theta_g$, right? If so, it would also be good to write $\sigma(\theta_g)$ and $\mu(\theta_g)$ in the smoothing loss expression.

We have updated our paper to clarify that the loss function is optimized over both $\theta_f$ and $\theta_g$. Additionally, we have made it explicit that $\mu$ and $\sigma$ are functions of the parameter $\theta_g$. These revisions should enhance the clarity of our methodology.

5. On the Validity of Input-Dependent Randomized Smoothing:

Your highest performing approach, using input-dependent anisotropic smoothing parameters that are optimized per-input, breaks the robustness certificates.

We noticed the discussion in Eiras et al. (2022) and understand your concerns regarding our input-dependent Randomized Smoothing (RS) approach. However, we respectfully clarify the soundness of this method.

Namely, randomized smoothing robustness certificates intimately rely on the same model being used to predict at the nominal point $x$ and all perturbed versions $x+\delta$ in the certified ball around $x$.However, if you optimize $\mu,\sigma$ at $x$, then the smoothing-based certificate only says that $x+\delta$ will yield the same prediction if you also use the same parameters $\mu,\sigma$ to define the prediction at $x+\delta$. But, according to your scheme, you actually re-optimize $\mu,\sigma$ at the perturbed test input $x+\delta$ to generate the prediction at $x+\delta$, meaning you are using a different model than what smoothing certifies at $x$. This mathematical breakdown of certified robustness for input-dependent smoothing has been noted before in past works, and is the reason why works like Eiras et al. (2022) augment their input-dependent scheme with "memory."

In this case, with $g(x,\mu(x),\sigma(x))$ and $R$ where $\mu(x),\sigma(x)$ are pre-computed (independent of $\delta$) as constants, we are guaranteeing $g(x+\delta,\mu(x),\sigma(x))=g(x,\mu(x),\sigma(x))$ as described in Theorem 3.2. Then, the models used for predicting $x$ and $x+\delta$ are the same in the certification, thus do not break the certification. The entire certification process has nothing to do with $g(x+\delta,\mu(x+\delta),\sigma(x+\delta))$ and the noise optimization is not based on $x+\delta$. Please also see the detailed explanation in our Common Concerns response.

Thanks again for the prompt reply. First of all, with respect to your two proposed situations:

Assuming that you always know the clean input $x$ is an unrealistic and very stringent assumption. If I gave you $x'=x+\delta$, how would you know what the clean input $x$ is? If this were the case, then all of the recent work on certifiably robust machine learning in the presence of $\ell_p$-norm bounded additive adversaries would be pointless, since one could simply reconstruct $x$ from $x'$, and then classify the clean input $x$ (which is much less likely to induce an error). So, this first situation is meaningless to consider in your setting of adversarial threats. Thus, the standard setting for papers in this area (and randomized smoothing, in particular), is to assume that all that you have at your disposal is whatever input you are given ($x'$ in the case of an attacked input), and you cannot distinguish whether this was attacked or not. In this standard setting, there is no possible way for you to take the attacked $x'$ as an input, and compute $\mu(x),\sigma(x)$ for the clean input.

So, there is an essential question to consider that points to the flaw at hand: What does your "certificate" $g(x+\delta,\mu(x),\sigma(x)) = g(x,\mu(x),\sigma(x))$ represent? To me, this says that, if you predict the output of $x+\delta$ using the smoothing distribution for $x$, then the prediction will match that of $x$. The problem is twofold: 1) you cannot compute $\mu(x),\sigma(x)$ (or even samples drawn from this distribution) unless you have access to the clean input $x$, which you do not, and 2) $g(x+\delta,\mu(x),\sigma(x))$ is not even the prediction that your scheme would output if $x+\delta$ was treated as its own input, since the smoothing distribution would be re-optimized for the input $x+\delta$.

"Let's assume that all we have at our disposal is whatever input we are given, then given arbitrary $x'$ by an adversary, what information about robustness does randomized smoothing provide?"

• Conventional randomized smoothing, with a smoothing distribution that is uniform over the entire input space, DOES give you that the classification of $x'$, namely, $g(x')$, is the same as that of the certified clean input $x$, even if you don't know $x$, so long as $\lVert x-x'\rVert \le R$ with $R$ being the certified radius. This result intimately relies on the fact that $g(x')$ is computing using the same smoothing distribution as $g(x)$ is computed.

"The more realistic setting is the model owner holds a $x$, and then computes a certified radius $R$ on it, then given any input $x'$ by the adversary the model owner can compute $\delta=x'-x$ and compare $\lVert \delta \rVert_p$ to $R$ to pre-determine the prediction without execution"

• This is not how adversarial threat models are usually formulated. Can you point to a paper that assumes that they have access to the clean input $x$ at the time when they are predicting the class of an attacked input $x+\delta$? The two closest things that come to mind are [1] and [2], which use memory-based techniques for input-dependent randomized smoothing, in particular as a method to overcome the exact issue that I am saying your approach suffers from. However, you do not make clear in your paper that you are using such a memory-based approach, and furthermore those memory-based approaches have their own limitations. For example, the classification of an input may in general be dependent on the order of inputs that were previously classified+certified, and furthermore you incur a memory cost that continually grows as you predict+certify more and more inputs.

[1] "ANCER: Anisotropic Certification via Sample-wise Volume Maximization", Eiras et al.

[2] "Data Dependent Randomized Smoothing", Alfarra et al.

Thank you for your response. I believe you are still misunderstanding my point. Let me try to make it more clear:

I agree with you that, mathematically, the equality $g(x+\delta,\mu(x),\sigma(x)) = g(x,\mu(x),\sigma(x))$ holds. However, my main point is that this equality does not reflect how your classifier makes its predictions in reality, and thus provides no meaningful robustness guarantee.

To see why this is the case, let $x$ be some fixed input. Your scheme then chooses a mean $\mu(x)$ and covariance $\sigma(x)$ based on this $x$. Then, to form the prediction for the input $x$, you compute $g(x,\mu(x),\sigma(x)) = \arg\max_{c\in\mathcal{C}} \mathbb{P}_{\epsilon \sim D} (f(x + \epsilon^\top \sigma(x) + \mu(x))=c)$, where $D$ is some isotropic "base distribution," such as an isotropic Gaussian. Now, your equality says that $g(x + \delta,\mu(x),\sigma(x)) = g(x,\mu(x),\sigma(x))$ for all perturbations $\delta$ inside of some region $\mathcal{R}$ of the input space containing $x$. This does not imply that your classification scheme's prediction is constant over this region.

Specifically, consider a NEW input $x'$ (possibly different from $x$, and therefore I put the "prime") for which you are to make a prediction. Well, substituting $x'$ for $x$ in the above prediction rule (which we both have agreed upon) gives that the prediction is $g(x',\mu(x'),\sigma(x')) = \arg\max_{c\in\mathcal{C}} \mathbb{P}_{\epsilon \sim D} (f(x' + \epsilon^\top \sigma(x') + \mu(x'))=c)$. In other words, to form a prediction for the input $x'$, you again compute the input-dependent mean and covariance, and perform the RS-based prediction at $x'$ using its optimized $\mu(x')$ and $\sigma(x')$.

Now, suppose that I reveal to you that actually, I was an adversary, and the input $x'$ that I gave to you and asked you to classify was $x'=x+\delta$ for some perturbation $\delta$ that I chose within your region $\mathcal{R}$. Then your prediction for this perturbed input was computed as $g(x',\mu(x'),\sigma(x'))=g(x+\delta,\mu(x+\delta),\sigma(x+\delta)) = \arg\max_{c\in\mathcal{C}} \mathbb{P}_{\epsilon \sim D} (f(x + \delta + \epsilon^\top \sigma(x+\delta) + \mu(x+\delta))=c)$, which is not guaranteed to be equal to the prediction $g(x,\mu(x),\sigma(x))$ corresponding to $x$. Therefore, the equality $g(x+\delta,\mu(x),\sigma(x)) = g(x,\mu(x),\sigma(x))$ does not say anything about the prediction/output $g(x+\delta,\mu(x+\delta),\sigma(x+\delta))$ of an attacked input $x+\delta$.

2. In Response to the Theoretical Concerns:

In Theorem 3.2, your certification using the p-norm of $\delta_i/\sigma_i$ but it seems that $\delta_i/\sigma_i$, is a one-dimension scalar as is the i-th dimension of perturbation $\delta$.

The Hadamard division of $\delta$ over $\sigma$ ($\delta_i/\sigma_i$) is formally defined in Theorem 3.2 and Appendix A.

Furthermore, this theorem is seemingly a direct corollary from Theorem 3.1, because your certification divides the variance $\sigma_i$ for each $\delta_i$ (not anisotropic anymore?).

We ensure that Theorem 3.2, while appearing to be straightforward, is a unique universal transformation from Definition 3.1, as detailed in Appendix A. We respectfully clarify that the derived theories in the theorem are not a direct corollary from Theorem 3.1 (since it covers both strict robustness w.r.t. heterogeneous dimension and universality). The guarantee in Theorem 3.2 is anisotropic w.r.t. $\delta$, although our focus is not to derive an ``anisotropic radius'', but to extend isotropic noise to anisotropic noise for RS. The guarantee on the perturbation $\delta$ can be either anisotropic (Theorem 3.2) or isotropic (Corollary 3.3).

3. As per the Suggestion to Compare with $\ell_1$ and $\ell_\infty$ Methods:

There might be missing of some baselines for $\ell_1$ [a] and $\ell_\infty$ [b, c] certified robustness. It will be better to compare the UCAN with existing certified $\ell_1$ and $\ell_\infty$ methods.

Our method, when benchmarked against $\ell_1$ and $\ell_\infty$ methods, shows significant improvements (see tables provided). This underscores our method's effectiveness across different metrics. We respectfully clarify that RS-based methods and $\ell_\infty$-distance neural network-based methods may not be directly comparable (due to their differences, e.g., RS can certify any classifier). To further address this concern, we still compare with them, and our method also demonstrates superior performance in these scenarios (a huge improvement space brought by the anisotropic noise for RS).

Table 1. Certified accuracy vs. $\ell_1$ perturbation (CIFAR10)

Table 2. Certified accuracy vs. $\ell_\infty$ perturbation (CIFAR10)

4. Responses to Specific Questions:

Why using 5-layers NN when generating universal/ input-dependent anisotropic noises? Is there some motivations or ablation studies for that?

The 5-layer MLP architecture in our Universal method is inspired by GANs (Goodfellow et al., Communications 2020), and the CNN structure in our Input-dependent method is designed per the dense blocks (Huang et al., CVPR 2017).

Could you provide more details on training of universal anisotropic noise? It seems that the variance loss is to optimize $\sigma$ and smoothing loss containing $\sigma$ when optimizing classifier $\theta_f$. I believe the two losses are optimized alternately but not simultaneously.

For the training of NRG and the classifier, we employed simultaneous training, optimizing both for predictive accuracy and noise pattern enhancement. While alternate training is possible, our current approach promotes synergy between the classifier and NRG.

The authors said that randomized smoothing achieved great success for certified adversarial robustness. Could RS really make classifier robust? Can you provide comparison of RS based model to the SOTA methods for achieving robustness?

Please see the above experimental results and discussion. It is worth noting that RS methods can be universally applied to any classifier with different scales, and it is unfair to compare the robustness performance of different types of classifiers.

Thanks for the comments again. We hope these clarifications can address your concerns.

Thank you for the insightful comments and please find our clarifications as below. We also make more clarifications in the paper to avoid confusion/misunderstanding.

1. Regarding the Evaluation Concerns Raised:

If I am not misunderstanding, the evaluation criterion is based on scaled radius, which has different weight in each dimension.

Our experimental evaluations are based on both 1) the $\ell_p$ radius from Corollary 3.3 ($min \sigma_i R$), which is a tight bound for the perturbation in anisotropic RS, and has the same weight in each dimension (please see Table 2-4 in the original submission); 2) the ALM metric ($\sqrt[d]{\prod^d_i \sigma_i} R$), which is a measure on the volume of the irregular asymmetric robust region, and has different weights in each dimension.

I believe this is true because I am surprised to the evaluation results provided in Table 3 that the $\ell_2$ certification on CIFAR-10 reach over $70$% even under radius 1.75.

In Table 3, the 70% certified accuracy at $R=1.75$ on CIFAR10 is the performance based on the $\ell_p$ radius ($min\{\sigma_i\} R$), which is strictly derived in Corollary 3.3. This validates the significant improvement of RS with anisotropic noise over SOTA methods.

This result is unbelievable, because existing SOTA performance of CIFAR-10 robustness may only achieve about 60% if no further data augmentations are conducted (like diffusion model)

We agree with the reviewer that existing isotropic RS methods can hardly improve their performance to this level. However, we focus on a new dimension of RS (with anisotropic noise) that is orthogonal to existing RS methods, which can boost all the RS methods. Such results are based on $\ell_p$ radius, rather than scaled radius.

Therefore, although the paper said they evaluate certified accuracy w.r.t radius, I am doubtful of this claim and I think the authors only consider scaled radius robustness.

We understand the reviewer's concern as our results drastically outperform the SOTA methods (evaluated on both $\ell_p$ radius and ALM). To address the concern, we are providing our code in the supplemental material for transparency. Please see line 180-182 in certification_personalized.py for the implementation of our $\ell_p$ radius (and corresponding evaluations).

However, scaled radius certification seems not a fair criterion for certified robustness. It is reasonable that in some dimensions, the image is vulnerable to adversarial attacks, e.g., contour of an image. Reversely, in some dimension images are intrinsically robust to perturbations like background of the image. Overall, the evaluation setting of this paper seems differently from existing RS methods. It is a consensus that using $\ell_p$ norm as constraint for images, the authors should provide corresponding evaluation on standard $\ell_p$ norm, or at least, provide the explanations or practical scenario on why using scaled radius as the evaluation criterion.

We agree with the reviewer that the ALM (scaled radius) may result in some ``weak'' dimension for the adversary, which only provides the certified robustness in a specific shape (depends on $\sigma$).

While working on the paper earlier, we also understood that reviewers may concern that solely evaluating on the ALM might be unfair (though ALM is defined as a full capture of the robustness region). Thus, we have also derived and presented the $\ell_{1,2,\infty}$ radii (derived in Corollary 3.3), and evaluated the performance of our method and SOTA using the ``certified accuracy w.r.t. $\ell_p$ radius'' (please see Table 2-4) in our original submission. We show that by customizing appropriate anisotropic noise, our method achieves significantly boosted performance on both the standard $\ell_p$ radius and the new ALM metric.