# Trust, But Verify: A Survey of Randomized Smoothing Techniques

Anupriya Kumari  ECE dept.
IIT Roorkee
<EMAIL_ADDRESS>Devansh Bhardwaj  ECE dept.
IIT Roorkee
<EMAIL_ADDRESS>Sukrit Jindal  DSAI dept.
IIT Roorkee
<EMAIL_ADDRESS>Sarthak Gupta  Mathematics dept.
IIT Roorkee
<EMAIL_ADDRESS>
###### Abstract

Machine learning models have demonstrated remarkable success across diverse
domains but remain vulnerable to adversarial attacks. Empirical defence
mechanisms often fall short, as new attacks constantly emerge, rendering
existing defences obsolete. A paradigm shift from empirical defences to
certification-based defences has been observed in response. Randomized
smoothing has emerged as a promising technique among notable advancements.
This study reviews the theoretical foundations, empirical effectiveness, and
applications of randomized smoothing in verifying machine learning
classifiers. We provide an in-depth exploration of the fundamental concepts
underlying randomized smoothing, highlighting its theoretical guarantees in
certifying robustness against adversarial perturbations. Additionally, we
discuss the challenges of existing methodologies and offer insightful
perspectives on potential solutions. This paper is novel in its attempt to
systemise the existing knowledge in the context of randomized smoothing.

###### Index Terms:

Deep learning, adversarial attacks, randomized smoothing, certification-based
defense

††publicationid: pubid: *Equal Contribution

##  I Introduction

Machine Learning (ML) has significantly advanced, notably since the
development of deep neural networks (DNNs) [79]. However, a significant
challenge is the susceptibility of state-of-the-art networks to adversarial
examples [65, 68] limiting their application in safety-critical areas [77].
Adversarial attacks include techniques like DeepFool [95], AutoAttack[96], and
patch-based attacks[97]. Existing defenses against adversarial attacks have
proven ineffective against stronger methods, creating a continual cat-and-
mouse game between attackers and defenders where attackers continually devise
stronger attacks [81], and defenders attempt to provide robustness against
these attacks citeb111. Empirical and heuristic defenses include denoising
autoencoders [98], using training-based defenses like adversarial training
[99], and defensive distillation[100]. Despite efforts to fortify ML models,
it has been suggested that creating DNNs inherently robust to adversarial
examples may be inevitable [101], [102]. Some approaches include those
explicitly based on the architecture of the DNN or otherwise [106, 84].
Further, it has been shown that enhancing robustness might come at the cost of
a drop in accuracy [73, 78]. This ongoing struggle has led researchers to
explore certified robustness as an alternative.

###  I-A Adversarial Examples

Adversarial examples are subtle input perturbations causing the classifier to
give incorrect outputs. Consider a classifier from $\mathbb{R}^{d}$ to classes
$C$, mathematically defined as, $f:\mathbb{R}^{d}\rightarrow[C]$, that assigns
a label to an input $x\in X$, we define an adversarial example $x_{0}$ as one
where $D(x,x_{0})<\epsilon$ for a small $\epsilon>0$, and $f(x)\neq f(x_{0})$.
Here, $D(\cdot,\cdot)$ represents a distance metric, often expressed using an
$l_{p}$ norm, with $l_{1}$, $l_{2}$ and $l_{\infty}$ norms being the most
commonly used in the literature.

###  I-B Empirical and Certified Robustness

Given a classifier $f$, We say $f$ is adversarially robust if, when provided
with an input $x$ with the actual label $y$, it can consistently classify all
inputs within a certain $p$-norm ball ($B_{p,r}(x)$) of radius $r$ centered at
$x$ correctly. In simpler terms, $f$ is robust if it correctly classifies
nearby inputs. Further, we define empirical and certified defenses. Empirical
defenses against adversarial examples refer to strategies implemented to
safeguard machine learning models from adversarial examples. These empirical
strategies are developed and validated based on experimental findings rather
than theoretical guarantees. In contrast, certified defenses against
adversarial examples refer to strategies that provide mathematically provable
assurances that a machine learning model can withstand adversarial attacks
within certain constraints. Empirical robustness is often determined by
attempting to find inputs ($x_{0}$) within the ball $B_{p,r}(x)$ that are
misclassified by $f$, providing an upper estimate of the classifier’s actual
robustness. On the other hand, certified robustness serves as a provable lower
bound on the classifier’s robustness, ensuring a certain level of correctness
within the specified region.

###  I-C Randomized Smoothing

Randomized smoothing [72, 2] has emerged as a powerful certification-based
defense against adversarial attacks. The fundamental idea behind randomized
smoothing is to create a smoothed classifier by applying a convolution with
Gaussian noise to the base classifier. Given a base classifier $f$, We create
a smoothed version of this classifier, denoted as $g$, which predicts the most
likely class $c$ that the base classifier $f$ will predict for a noised
version of the input $x+\epsilon$, where
$\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$. Thus, $g$ can be defined as:

$g(x+\epsilon)=\arg\max_{c\in[C]}P(f(x+\epsilon)=c)\text{, where
}\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$ (1)

Figure 1:  This figure showcases the decision boundaries for $l_{1}$, $l_{2}$,
and $l_{\infty}$ norms, visually representing their sensitivity to adversarial
perturbations. The diamond, circle, and square-shaped boundaries signify
$l_{1}$, $l_{2}$, and $l_{\infty}$ norms, respectively, showcasing the
technique’s impact on different normative spaces for a given certified radius.

Lecuyer et al. [72] and Li et al. [2] showed that the smoothed classifier $g$
will consistently classify within a certified radius around the input $x$
under $l_{2}$ norm considerations. However, the guarantees provided by these
papers were loose due to a noticeable gap between the theoretical lower bounds
and the empirical accuracy, suggesting the existence of a tighter radius
around the input $x$ than those predicted.

Cohen et al. [1] was the first paper to prove tight robustness guarantees for
a randomized smoothing classifier against adversarial attacks constrained
under the $l_{2}$ norm. Given the top two classes, $c_{A}$ and $c_{B}$, that
the base classifier is most likely to predict for the sample, the robust
radius $r$ is given by:

$\displaystyle r=\frac{\sigma}{2}(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B}))$ (2)

where $p_{A}=P(f(x+\epsilon)=c_{A})$ and $p_{B}=P(f(x+\epsilon)=c_{B})$, with
the condition that $p_{A}>0.5$ and $\Phi$ represents the CDF of the standard
Gaussian distribution. This demonstrates that if $g$ correctly predicts the
input $x$, we can provide provable $l_{2}$ robustness of our model in a
probabilistic sense. However, Cohen et al. [1] highlighted that it is
practically not possible to calculate the exact values of the top two class
probabilities, i.e., $p_{A}$ and $p_{B}$. Hence, they introduce a modified
version of the above statement that utilizes the Clopper-Pearson bounds for
$p_{A}$ and $p_{B}$. For $p_{A}$, the Clopper-Pearson lower bound, denoted as
$\underline{p_{A}}$, and for $p_{B}$, the Clopper-Pearson upper bound, denoted
as $\overline{p_{B}}$, can be calculated using Monte-Carlo sampling. To
theoretically prove that using this combination of Clopper-Pearson and Monte-
Carlo sampling will give us a lower bound on the actual certifiable radius
$r$, they use Neyman-Pearson lemma (NP lemma). Furthermore, to reduce time
complexity, they approximate $\overline{p_{B}}$ with $1-\underline{p_{A}}$,
meaning that if the base classifier correctly classifies the input $x$, then
any example $x_{0}$ within the $l_{2}$ distance of x,
$D(x,x_{0})<\sigma\Phi^{-1}(\underline{p_{A}})$ will be correctly classified
by the smoothed classifier $g$.

Following Cohen et al.’s seminal work [1], the concept of randomized smoothing
has spurred a proliferation of studies. This paper endeavours to provide a
comprehensive summary of these works, elucidating significant challenges,
notable advancements and extracting key insights. The organization of the
survey is structured into three main sections. Section II critically examines
the major issues associated with randomized smoothing, categorizing these
challenges into three broad domains. Subsequently, a detailed discussion
ensues on these challenges, followed by an exploration of future research
directions.

Moving to Section III, we delve into significant advancements that focus on
enhancing radius certifications beyond those outlined in Cohen et al. [1].
This section also addresses the challenges presented in Section II, providing
discussions for the same. Section IV broadens the perspective by discussing
applications of randomized smoothing, which extend beyond the original focus
of Cohen et al. [1], which was primarily limited to image classification
tasks.

Rethinking Scalability in Randomized Smoothing: An Analytical Perspective Due
to its theoretical guarantees, randomized smoothing is commonly hailed as a
crucial certification-based defense mechanism. However, through our analysis,
we raise a fundamental question: Despite all the theoretical assurances, is
randomized smoothing truly scalable? Throughout our examination, we highlight
the limitations of existing works that predominantly emphasize theoretical
guarantees while overlooking the critical aspect of computational complexity,
especially during inference, and dimensionality considerations. This concern
holds significant weight, particularly for machine learning applications
requiring minimal inference time, where randomized smoothing may fall short as
a practical solution. Hence, in addition to serving as a survey of randomized
smoothing techniques, we scrutinize each work from the perspective of
scalability. At the end of each section, we offer insights and discussions on
how the various works discussed within that section may influence the
scalability of randomized smoothing.

##  II Challenges

Randomized smoothing is a powerful architecture-independent technique for
certified robustness, and it has only gained popularity over the years;
however, as with any other method, it also has its limitations. In the
following subsections we define and discuss three significant challenges in RS
that commonly encountered in literature. These challenges affect the
scalability and applicability of RS in many domains, which has currently
offered promising empirical results in certified robustness.

###  II-A Curse of Dimensionality

In their work, Cohen et al. [1] left the case of general $l_{p}$ norms as an
open problem, suspecting that smoothing with other noise distributions might
provide robustness guarantees for these cases, and only discussed randomized
smoothing in the context of $l_{2}$ norms. Additionally, they state that,
despite the certified radius being independent of the input dimension $d$,
randomized smoothing can be easily scaled to higher dimension images as in the
case of higher dimension images, we can increase the variance of the noise,
which will eventually lead to increase in the robust radius. This approach has
its issues, as will be discussed in the next section. Later, two independent
works, Blum, Avrim, et al. [7] and Kumar, Aounon, et al. [11], showed that as
the dimension of the input increases, it becomes increasingly difficult to
defend against the general $l_{p}$ norm cases for $p>2$ as the certified
radius decreases.

Blum, Avrim, et al. [7] showed that, given any noise distribution
$\mathcal{D}$ and the noise vector $\epsilon\sim\mathcal{D}$, 99% pixels of
the noise vector, must satisfy
$\mathbb{E}\epsilon_{i}^{2}=\Omega(d^{1-\frac{2}{p}}r^{2}\frac{1-\delta}{\delta^{2}})$,
where $r$ is the robust radius and $\delta$ is the difference between the
probability scores of the top two classes predicted by the smoothed classifier
(highest score-class $c_{A}$ and runner-up class $c_{B}$). They further proved
that the problem of finding the certified radius in the $l_{\infty}$ case can
be approximated as finding the $l_{2}$ radius times $1/\sqrt{d}$ of that
radius.

Subsequently, Kumar, Aounon, et al. [11] show, in the specific case of a
generalized Gaussian distribution, tighter bounds than those attained by Blum,
Avrim, et al. [7]. Their work states that the certified radius for an $l_{p}$
norm decreases as $O\left(d^{\frac{1}{2}-\frac{1}{p}}\right)$ with data
dimension $d$ for $p>2$. The family of distributions discussed in this paper
includes the Laplacian, Gaussian, and uniform distributions, commonly employed
in literature for randomized smoothing techniques. Wu, Yihan, et al. [75] then
extend the discussion for the case of spherical symmetric distributions (which
includes the Gaussian distribution) and present upper bounds for $p>2$. It
also discusses upper bounds for $p=2$ for many popular smoothing
distributions, which have yet to be discussed. Yang, Greg, et al. [4] go into
more detail about $l_{1}$, $l_{2}$, and $l_{\infty}$ threat models to derive
from the class of i.i.d. distributions, the most optimal smoothing
distribution using the concept of Wulff Crystals. Overall, their results in
this regard can be summarised as follows: the uniform distribution is the most
optimal choice for $l_{1}$ attacks, the Gaussian distribution, as mentioned by
Cohen et al. [1], is the most optimal for $l_{2}$ attacks, and that for
$l_{\infty}$, the Gaussian distribution performs best using appropriate
approximations. There is a tight
$O\left(\min\left(1,d^{\frac{1}{2}-\frac{1}{p}}\right)\right)$ dimensionality
bound for $l_{p}$ norms without using any additional information other than
the Neyman-Pearson technique.

Ettedgui, Raphael, et al. [66] provide a different perspective and argue about
the information-theoretic limitations faced by RS and how they are not
intrinsic but a byproduct of the current certification methods. They further
discuss that these certificates need to include more information about the
classifier and ignore the local curvature of the decision boundary, which
leads to sub-optimal robustness guarantees as the dimension of the problem
increases. It is possible to overcome this by generalizing the Neyman-Pearson
Lemma and collecting more information about the classifier. The paper shows
that it is possible to approximate the optimal certificate with arbitrary
precision by probing the decision boundary with several noise distributions.
More specifically, the paper achieves this without sampling in high dimensions
by combining uniform and Gaussian distribution and leveraging the isotropic
properties of the latter. Further, this process retains natural accuracy as it
is executed at certification time. The paper then gives theoretical insight
into how to mitigate the computational cost of a classifier-specific
certification.

Pfrommer, Samuel et al. [41] present notable work in the sense that they
implicitly propose a solution to the curse of dimensionality, suggested by
Blum, Avrim, et al. [7]. It combines the limitations of randomized smoothing
in light of the curse of dimensionality with the manifold hypothesis [74] and
shows that using various dimensionality reduction techniques improves robust
guarantees in theory, as opposed to heuristic approaches in previous works by
Mustafa, Aamir, et al. [76] and Kurakin, Alexey et al. [77].

So far, only Li, Linyi, et al. [3] have provided proofs and a possible
solution to the issue of the curse of dimensionality using a technique called
double sampling randomized smoothing (DSRS). They utilize a primary
distribution in the form of a general Gaussian distribution and additional
information in the form of a sampled probability from a secondary truncated
distribution that is not necessarily different from the primary distribution.
For $l_{2}$ norm, they provide a tighter radius and prove that their method
can certify $\Theta\left(\sqrt{d}\right)$ robust radius bounds. As mentioned
by Cohen et al. [1], for the $l_{\infty}$ case, the certified radius is
equivalent to $1/\sqrt{d}$ times the $l_{2}$ robust radius, which on using [3]
would remove the dependency on the dimensions of the input.

We note that there has been an in-depth theoretical exploration of the issue
termed the curse of dimensionality. The base conclusion of all papers remains
that there is a tight bound on certified radii that decreases with increasing
dimensionality, which arises from statistical, probabilistic, and information-
theoretic perspectives based on the existing methodology for RS. While we
certainly encourage more research into that aspect, we notice the dire lack of
solutions for the same. Apart from DSRS, no major breakthrough has been
achieved to solve this issue. As a result, we encourage works to explore
various solutions to this issue.

###  II-B Robustness-Accuracy Trade-off

In adversarial robustness literature, not limited to RS, there is a focus on
increasing the robustness bounds of a classifier. While this seems to be an
optimal goal, there has been literature suggesting that increasing robustness
comes with a tradeoff in accuracy [73], [78]. It has been studied for
adversarial robustness in much detail, including theoretical considerations.
In [78], the authors study the accuracy costs of improving robustness in a
model. This was further explored in [73] and [80]. Both empirically and
theoretically, it is seen that robustness and accuracy exist in a trade-off,
contrary to what one would expect intuitively. Randomized smoothing is also
vulnerable to this trade-off, and there is much to explore in this regard,
leaving this an important open aspect of research for randomized smoothing
techniques. Naturally, this can be seen in RS as well. Randomized smoothing
involves convoluting, or smoothing, the base classifier with Gaussian noise.
While this provides certified robustness, it can be inferred that there is
some loss in accuracy due to noisy inputs. Termed as the robustness-accuracy
tradeoff, we explore this issue concerning RS in this subsection.

Specific to RS, the theoretical and numerical aspects of Gaussian smoothing
are explored in the work by Mohapatra, Jeet, et al. [51], along with which
they provide theoretical results showing the limitations of RS in terms of
classification accuracy. Mainly, they characterize and identify the conditions
under which Gaussian smoothing leads to a decrease in classification accuracy,
provide theoretical lower bounds for the magnitude of this effect, numerically
inspect the behaviour of the certified radius, and use tools from information
theory to analyse the effects of Gaussian smoothing during training
augmentation, concluding that it leads to information loss and finally
validate their results empirically.

A theoretical analysis of robustness-accuracy in terms of the benign risk
associated with applying randomized smoothing on a classifier trained using
noise augmentation for the base classifier is given by Pal, Ambar et al. [33].
This arises from the observation of improved performance when using a noise-
augmented base classifier instead of one without any such augmentation. They
derive an upper bound for any data distribution used for smoothing, which
suggests randomized smoothing harms the classifier’s accuracy. This practice
has pervaded most literature with ample empirical support. The paper then
suggests certain distributions where smoothing may be beneficial based on the
separation regime. Also, it suggests optimisation for randomized smoothing,
using different noise parameters to train the base classifier. They also
discuss the theoretical intuition behind this, viz., the empirical observation
that real data lies on a lower dimension than the actual data dimension.

A compositional architecture termed ACES, which aims to tackle this
robustness-accuracy trade-off, is introduced in [49]. It decides on a per-
sample basis whether to use the robust-but-less-accurate smoothed model or the
accurate-but-less-robust base classifier for prediction using a learnable
selection algorithm that can again be made robust by further smoothing. This
approach improves the trade-off between robustness and accuracy in current
models and can be used as an orthogonal optimisation to other methods. This is
done in the light of optimising randomized smoothing specific robustness and
accuracy using compositional architectures, as introduced and proposed earlier
by Mueller, Mark Niklas et al. [93].

A notable work by Mohapatra, Ko, et al. [32] articulates and proves two major
limitions regarding RS: (I) the decision boundary of the smoothed classifier
will shrink, resulting in a discrepancy in class-wise accuracy, and (II)
applying noise augmentation in the training process does not resolve the
shrinking issue because of inconsistent learning objectives. The paper
proceeds to review adversarial robustness certification, exposes the
significant hidden cost of RS, which includes biased predictions using
evidence from both real-life and synthetic datasets, provides a comprehensive
theory exposing the root of the biased prediction-shrinking phenomenon and
then discusses the effects of data augmentation on the shrinking phenomenon
and its implications. In essence, they arrive at two observations - the need
to limit the use of high values of smoothing factor $\sigma$ and a data
geometry-dependent augmentation scheme to counteract the shrinking effect
caused by smoothing properly. This challenges what we already know about
randomized smoothing, which, as introduced by Cohen et al., uses data-
independent noise parameters. Namely, the Gaussian noise,
$\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$ which is convoluted with the base
classifier is data-independent and $\sigma$ can be thought of as a
hyperparameter representing a trade-off between accuracy and robustness. Too
low of a value will give smaller certified radii, which are given, after
appropriate approximations, as the certified radius
$r=\sigma\Phi^{-1}(\underline{p_{A}})$, which is directly proportional to
$\sigma$. Using too large of a value for $\sigma$ will reduce the accuracy in
calculating $\underline{p_{A}}$ due to highly noisy training inputs.

Overall, we notice ample theoretical and empirical evidence supporting the
existence, and its pervasivity in most RS techniques. However, there is very
little literature aimed at actually tackling this problem. We strongly suggest
more works to explore solutions to this challenge and improve existing methods
like ACES using newer techniques and methodology, not just for RS but also for
adversarial robustness in general.

###  II-C High Inference Cost

Randomized smoothing utilizes Monte Carlo sampling, which requires multiple
passes of the noisy samples through the model, leading to high inference
costs, at the same time it has been shown that certified radius increases with
the no. of passes or no. of samples ($n$) and for significant radius size
typically $10^{5}$ or more samples are required [1]. This implies that during
inference we need to do a forward pass to have a significant certified radius
and essentially increases the computational cost by a large margin.

A controlled way to trade off the average certified radius (ACR) with the
number of samples required was introduced by Chen, Ruoxin, et al. [23]. They
changed their sampling scheme from an input-agnostic scheme to an input-
specific scheme. To achieve this input-specific sampling, first a relatively
loose two-sided Clopper-Pearson interval is calculated for a given input using
a smaller sample size. Then, a mapping of sample size to the relative decline
in average radius is computed for the input. This mapping shows a trade-off
between the number of samples and the average certified radius.

Another way of reducing the computation cost could be by lowering the
inference time of the smoothed model by techniques such as pruning,
quantization of the base model, or knowledge transfer. But this essentially
means we have changed the actual model and the theoretical guarantees may not
hold. Ugare, Shubham, et al. [10] study this scenario and formulate an
incremental certification technique for randomized smoothing called
Incremental Randomized Smoothing (IRS). This improves performance on
probabilistic techniques like randomized smoothing compared to existing
deterministic techniques for incremental certification. In particular,
incremental certification deals with certifying robustness bounds for the
smoothed classifier of a given modification of a base classifier, reusing
information from the smoothed classifier of the base classifier to reduce
computational costs. It does so based on the disparity between the classifiers
and certain approximation techniques. On a related note, Vaishnavi, Pratik, et
al. [120] propose a similar knowledge transfer scheme, Certified Robustness
Transfer (CRT), for randomized smoothing for training $l_{2}$ certifiably
robust image classifiers with comparable levels of robustness using a pre-
trained classifier that is certifiably robust as a teacher. Both techniques
demonstrate significantly reduced costs, indicating the empirical
effectiveness of their methods.

It is pretty clear from the number of works in this section that this aspect
of randomized smoothing is virtually untouched and has a lot of scope for
improvements and future directions.

Challenges in the Scalability of RS In this section, we explored the
challenges which affect RS. While the robustness-accuracy tradeoff, as noted,
is a challenge which affects the entire field of adversarial robustness and
even ML as a whole, the other two, viz., the curse of dimensionality and the
issue of high inference costs, expressly limit the scalability of RS. Further,
on a broad level, we note these challenges are acknowledged and understood in
their impact, whether implicitly, as is true for computational costs, or
explicitly, as is seen for the curse of dimensionality. However, contrary to
expectations, little research is devoted to developing solutions that truly
address these issues and improve the scalability of RS.

##  III Improving Randomized Smoothing

Randomized smoothing offers a tight lower bound on the certified radius for
any classifier. As with any certified robustness technique, these bounds are
lower than the upper bounds arising from empirical verification techniques,
which are based on heuristics and empirical evidence instead of theoretical
guarantees. Thus, there has been much research into improving the performance
of randomized smoothing and improving its certified radii to an optimal limit.
Further, there is a need to address the challenges faced in RS and develop
various techniques. In this section, we explore specific optimisations that
improve the robustness certificates given by RS and solve various issues
encountered in RS.

###  III-A Randomized Smoothing for Training

The idea of incorporating randomized smoothing objectives in adversarial
training [87] roots from the intuition that doing so will result in boosted
performance and improved robustness. Further, addressing the challenge of
training a good base classifier that is accurate and robust when smoothed [34]
led to significantly better results as discussed in this section. Salman et
al. [87] consider a smoothed classifier which is a generalization of equation
(2), to soft classifiers, namely, functions $f:\mathbb{R}^{d}\rightarrow P(y)$
where $P(y)$ is the set of probability distributions over $y$. They then train
a hard classifier which essentially takes the argmax of the soft classifier,
using adversarial examples generated by describing an adversarial attack
against the smoothed soft classifier [108, 109]. This results in a boosted
empirical robustness and substantially improved certifiable robustness using
the certification method of Cohen et al. [1]. Feng et al. [34] improved upon
this by deriving a new regularized risk in which the regularization can
’adaptively encourage’ the training of the base classifier. Specifically, they
proposed ADRE (ADaptive Radius Enhancing regularizer), which penalizes
examples misclassified by the smoothed classifier while encouraging the
certified radius of the correctly classified examples. It is computationally
efficient and can be implemented in parallel with other empirical defense
methods, under standard (non-adversarial) and adversarial training schemes.
They also designed a new certification algorithm, T-CERTIFY, that can leverage
the regularization effect to provide tighter robustness and lower bounds that
hold high probability. Alfarra, Motasem, et al. [13] challenged these attack-
dependent and time costly adversarial training techniques [1, 87] by
introducing an algorithm called MACER, which learns robust models without
using adversarial training. More specifically, they break the standard
training loss into two subsequent losses: a standard cross-entropy loss and a
hinge-based loss function applied to the robust radius. A modified version of
the original randomized smoothing obtains the robust radius. Since it is a
non-differentiable method, to make it differentiable, they take expectation
over the probability scores each time a noisy sample is passed through the
model and then take the maximum over all the classes. It is observed that
MACER also outperforms Feng, Huijie, et al. [34] by a significant margin in
terms of Certified top-1 accuracy on CIFAR-10 at various $l_{2}$ radii. On
Imagenet, however, the latter gives better accuracy.

Thus, the challenge of training a base classifier that is accurate and robust
stands resolved [34] along with some noteworthy contributions [13] that
ultimately prove that adversarial training is not a must for robust training
and larger average certified radii can be achieved in less training time than
state-of-the-art adversarial training algorithms.

###  III-B Improving Performance of Pre-Trained Classifiers

Improving the performance of pre-trained classifiers by turning them from non-
robust into provably robust ones is desired to maintain their confidentiality,
integrity, or availability. For example, it might be beneficial to public
vision API providers and users. In their work towards achieving this, Salman,
Hadi, et al. [18] apply randomized smoothing to pre-trained classifiers by
attaching a denoiser before the pre-trained model. Intuitively, they remove
the Gaussian noise added in the randomized smoothing, unlike traditional
methods that focus on increasing the quality of images. They train the
denoiser with a modified loss function, which, instead of using the usual MSE,
uses cross-entropy loss to train the combined denoiser and pre-trained
classifier architecture, keeping the pre-trained classifiers’ weights frozen.
This process also increases the classification accuracy. The methodology can
be extended for other $l_{p}$ cases by simply changing the noise used during
training to a noise sampled from the distribution corresponding to the
specific $l_{p}$ case. Denoised smoothing can be applied to both white and
black box settings, making it the state-of-the-art approach to defending pre-
trained classifiers. Sheikholeslami, Fatemeh, et al. [54] challenge the low
natural accuracy of this state-of-the-art approach and contribute further to
the methodology by Salman, Hadi, et al. [18] by augmenting the joint system
with a “rejector” and exploiting adaptive sample rejection, i.e.,
intentionally abstain from providing a prediction. The reject class is used,
through Monte Carlo (MC) sampling, to reject noisy samples whose prediction is
inconsistent with the prediction of the clean sample. This approach to
preventing misclassified examples in the non-rejected classes has
substantially improved the natural accuracy and the certification radius for
computationally inexpensive denoisers. They achieve considerably better
accuracy with their rejection methodology on CIFAR10 with both DnCNN-based
denoising and MemNet-based denoising [110, 111]. Lee, Kyungmin, and Seyoon Oh.
[46] also improve on previous works [18, 54] by introducing an improved score-
based architecture for denoisers instead of classification loss, however,
faced challenges concerning the novelty of their work and the possibility that
the proposed method might exacerbate the weakness of randomized smoothing
(i.e., slow prediction), especially in high-dimensions. Hence, while they
produced higher certified accuracy of ResNet-110 on CIFAR-10 at various
$l_{2}$ radii compared to previous works [1, 18], they failed to achieve
similar improvements in certified accuracy of ResNet-50 on ImageNet,
indicating that their method seems to be effective for low-resolution images
only. While the work so far in this domain seems somewhat promising, there
remains scope for future research to further improve the certified accuracy of
high-dimensional datasets with increasing $\sigma$ ($\sigma$ as defined in
section I, subsection C).

###  III-C Leveraging Local Information

The original randomized smoothing technique makes use of Monte-Carlo sampling
to derive certified radii. This information is fully summarised for an input
$x$ by $p_{A}(x)$, the probability of the top class, and does not require any
other information beyond the standard deviation $\sigma$ of the Gaussian.
Levine et al., [14] propose the use of additional gradient information, viz.
$p_{A}^{\prime}(x)$, in a technique known as second-order smoothing (SoS) to
provide more robust bounds. Their approach is based on the Lipschitz property
of randomized smoothing classifiers [112], which globally bounds the Lipschitz
constant of the gradient of a smoothed network. Thus, instead of using the
Lipschitz bounds directly on the classifier, it utilizes the Lipschitz bounds
on the gradient to obtain what the paper terms as second-order smoothing
certificates, which can be used to compute a lower bound on the distance of a
point to its closest adversarial example and improve robustness certificates.
It also introduces Gaussian dipole smoothing, which is an optimisation based
on SoS and Gaussian randomized smoothing to provide similar radius bounds. The
results in this paper are significant as they show that all randomized
smoothing-based classifiers suffer from this curvature constraint, restricting
their application and prompting further research into certificates obtained
using higher-order derivative information. This is what Mohapatra, Ko, et al.
[24] do by extending the usage of gradient information to provide a general
framework for evaluating more optimal certified radii using higher-order
derivatives around the input. They do so by reformulating radius calculation
as an optimisation problem. It also evaluates the certified radii obtained
using Gaussian-smoothed classifiers, which utilize zeroth and first-order
local information for general $l_{p}$ attacks. It also introduces a
theoretical result for Gaussian-smoothed classifiers, which states that it is
possible to achieve arbitrarily tight bounds using sufficient local
information, thereby addressing the curse of dimensionality, which is a major
challenge in RS and is discussed later on. Anderson et al. [20] utilize a
locally optimal robust classifier based on Weierstrass transformations using
decision boundary information. Their model not only improves on local
information methods mentioned here but also addresses the issue of the
robustness-accuracy trade-off for smoothing classifiers as discussed
previously. Their study is limited to binary classifiers but remains
unexplored for other cases, and this is a potential area for future works to
explore.

Thus, one can see that there is an improvement in certified bounds using local
information, such as the gradient and Hessian, and there is a possibility to
explore and apply this approach orthogonally to other optimisations for
randomized smoothing. A drawback of this approach is that the computational
overheads associated with calculating local information add heavily to the
already expensive smoothing convolution despite the gains being limited, as
they also are tightly bound.

###  III-D Ensemble-based methods

Randomized smoothing bounds can be improved further using ensemble-based
methods. These methods work by aggregating the results of multiple
classifiers, somewhat similar to how RS involves smoothing the base classifier
with multiple noisy inputs and using those results to create the base
classifier.

Horváth, Müller, et al. [57] theoretically motivate why ensembles are a
particularly suitable choice as base models for RS and then empirically verify
this choice, obtaining state-of-the-art results in multiple settings. The
insight around which their work revolves is that reduced variance of ensembles
over the perturbations introduced in RS leads to significantly more consistent
classifiers. Additionally, they introduce a data-dependent adaptive sampling
scheme for RS that enables a significant decrease in sample complexity of RS
for predetermined radii, thus reducing its computational overhead. The
modeling approach is mathematically related to the work by Tumer & Ghosh [91],
which focuses on analyzing data and model choices to reduce classifier
correlation for all ensemble methods, not just randomized smoothing.

RS requires augmenting data with large amounts of noise, which leads to a drop
in accuracy. To overcome this, there is a training-free, modified smoothing
approach, Smooth-Reduce, that leverages patching of images and aggregation to
improve classifier certificates [27]. This approach is different from a simple
ensemble technique, which is computationally expensive, and rather involves
patch sampling. For this, the authors study two aggregation schemes and show
that both approaches provide better certificates in certified accuracy
compared to concurrent approaches. They also provide theoretical guarantees
for such certificates and empirically show significant improvements over other
methods that require expensive retraining and even extend this approach to
videos.

The Smoothed WEighted ENsembling (SWEEN) scheme improves the robustness of RS
classifiers using ensemble techniques that generally can help achieve optimal
certified robustness [45]. The authors make use of a $\gamma$-robustness index
as a measure of optimality. Theoretical analysis further proves that the
optimal SWEEN model can be obtained from training under mild assumptions.
Additionally, SWEEN does not limit how individual candidate classifiers are
trained. The model adopts a data-dependent weighted average of neural networks
to serve as the base model for smoothing. To find the optimal SWEEN model, one
must minimize the surrogate loss of $g_{ens}$ over the training set and obtain
appropriate weights. The major drawback of ensembling is the high execution
cost during inference, for which the paper also develops an adaptive
prediction algorithm to reduce the prediction and certification cost of the
models.

From here, we see that ensemble-based methods for randomized smoothing have
empirical and theoretical guarantees. Further, despite the prohibitive costs
of ensemble training, adaptive algorithms for their training have been shown
to reduce the computational overhead. Overall, ensemble methods provide a
satisfactory approach to improve robustness guarantees with reduced costs as
compared to other similarly expensive approaches. As with other approaches, we
encourage the orthogonal application of these approaches and also a study on
how to reduce ensemble training overheads further, possibly by advantageously
using the noise augmentation already employed for randomized smoothing.

###  III-E Input Specific Information

As discussed previously, RS uses a data-independent hyperparameter, $\sigma$,
for the Gaussian noise $\epsilon\sim\mathcal{N}(0,\sigma^{2}I)$ to be
convoluted with the base classifier. Even though this forms a basis of the
robustness-accuracy tradeoff, it is also important to note that the issue of
an optimal choice of $\sigma$ is important to improve certified robustness
using TS. To deal with this, Alfarra et al. [15] propose the use of additional
information, as is suggested in the curse of dimensionality section, which can
be extracted from the data itself, in a scheme known as Data Dependent
Randomized Smoothing (DDRS). DDRS aims to improve the choice of the
hyperparameter $\sigma$ to achieve a larger certified radius, a parameter
traditionally fixed in the original Randomized Smoothing (RS) method.
Specifically, DDRS addresses this by solving an optimisation problem,
$\sigma_{x}^{*}=\arg\max_{x}\;R(x,\mu)$.

This optimisation is performed using gradient ascent, and it defines the
smoothed classifier G by introducing sampling noise
$\mathcal{N}(0,{\sigma_{x}^{*}}^{2}I)$ for each input x. This approach has
empirically demonstrated improved certified isotropic regions for individual
data points. [44] also develop a related sample-wise choice of $\sigma$ which
they term as Insta-RS along with adaptive training optimisations for the same.
A major difference is that Insta-RS uses a multi-search, gradient-free
paradigm, while DDRS assumes concavity and opts for gradient ascent.

The concept of anisotropic smoothing aims to improve further on the results
given by DDRS, which only certifies isotropic boundaries ([17], [115]).
Anisotropic smoothing aims to certify, as the name suggests, different
certified radii along each axis, essentially acting as a hyperelliptic curve
instead of a hypersphere when considering the $l_{2}$ norm. Where normal
randomized smoothing uses a constant variance noise of the form
$\mathcal{N}\left(0,\sigma^{2}I\right)$ and DDRS uses a data-dependent
variance of the form $\mathcal{N}\left(0,\sigma_{x}^{2}I\right)$ to certify
robust bounds, anisotropic smoothing uses $\mathcal{N}\left(\mu,\Sigma\right)$
where $\Sigma$ is a diagonal matrix of variance generated using data-dependent
techniques. Both papers follow a similar approach, differing only in the fact
that in [115], $\mu=0$ is fixed, and they term their algorithm as ANCER. Their
methodology is such that the certified bounds along each direction exceed not
only the bounds presented in Cohen et al. [1], but also encapsulate the bounds
given by isotropic data-dependent smoothing as in [15].

In an unrelated but still data-dependent approach, Wang et al. [60] propose a
smoothing algorithm that optimises the noise level choice (measured as the
variance of the isotropic Gaussian noise) by dividing the input space into
multiple regions and optimizing the noise level for each region, pre-training
and fine-tuning the model using testing data. This approach allows one to
create a sample-wise robust classifier that addresses the accuracy-robustness
trade-off and improves the certified radii. Their approach maintains
robustness in each region of the input space as per Cohen’s results without
affecting other regions.

Súkeník et al. [22] offers a concise overview of issues associated with a
fixed global $\sigma$ value including (I) Using lower confidence bounds for
class probability estimation, leading to smaller certified radii, (II)
Balancing the trade-off between robustness and accuracy, as previously
discussed and (III) The effect of Randomized Smoothing (RS) on the
classifier’s decision boundary, where bounded or convex regions contract with
increasing $\sigma$ while unbounded and anti-convex regions expand. The paper
then tackles these issues by introducing Input-Specific Randomized Smoothing
(ISRS) which employs the Neyman-Pearson lemma in a general case. However, they
also state the effect of the curse of dimensionality and propose a framework
to evaluate the efficacy of data-dependent RS methods in high dimensionality.
It is a fundamental work in that it identifies the shortcomings of previous
works like DDRS, Insta-RS, ANCER, and [60] which do have significant empirical
results, but weak theoretical foundations.

Riemannian data-dependent randomized smoothing (RDDRS) [38] further optimises
the approach in anisotropic smoothing by allowing it to be robust to
rotations. It does so using Riemannian optimisation to obtain $\mathcal{C}$, a
covariance matrix that is not restricted to a scalar matrix (as in normal
randomized smoothing and DDRS) nor a diagonal matrix (as in anisotropic
randomized smoothing). Here, the smoothened classifier is constructed using
Gaussian noise of the form $\mathcal{N}\left(0,\mathcal{C}\right)$. RANCER
[116] also employs a non-axis-aligned approach. These methods empirically
improve on the certified bounds introduced by even anisotropic smoothing
techniques. As can be seen, there is clearly a pattern on increasing the
complexity of the covariance matrix for the Gaussian noise to derive better
results. As motivated by [22], however, we also note the weak theoretical
justifications and encourage future work to analyse strongly the theoretical
foundations to potentially justify and back the empirical results of
approaches like DDRS, Insta-RS, ANCER, RDDRS, and RANCER.

Geometrically Informed Certified Robustness [5] is an approach which exploits
the underlying geometric properties of a network using information around a
point, such as the certified radii of nearby points, and exploits the
transitivity of certifications. It is an optimisation that can be combined
orthogonally with previous approaches, which only certify the region around a
point without using any local information. We strongly suggest future
empirical work to explore GICR in conjuction with other optimisations.

Randomized smoothing has primarily been applied to single output cases. [61]
propose a localised smoothing algorithm for multi-output settings instead of
using independent RS schemes. Their approach combines anisotropic smoothing
and also segments each input into various parts, where different anisotropic
noise distributions are used for smoothing. In practice, they utilise soft
locality, i.e. when the entire input influences the output but specific
subsets have higher importance, to optimise the certified bounds and aggregate
the result for the overall classifier. Their approach is a novel approach
which extends and optimises RS for the multi-output scenario, and can be
explored further, potentially with non-axis aligned distributions as well,
similar to how RANCER extends ANCER.

One of the issues mentioned in [22] is that of fairness where class boundary
disparities affect classwise prediction accuracy and robustness. This also
relates heavily to the discussion in robustness-accuracy tradeoff, where a
paper highlighted the need to limit data geometry-dependent augmentation
schemes for similar reasons [32]. Addressing this, Kumar et al. [21] use the
average prediction score of a class and the margin by which the average
prediction score of one class exceeds that of another. Following this, using a
modified version of the Neyman-Pearson lemma, which forms the basis of RS and
IDRS, a procedure is designed to compute the certified radius where the
confidence is guaranteed to stay above a certain threshold, thus achieving a
significantly better-certified radius, as is empirically shown. They raise a
valid point regarding certifying confidence (soft classifiers) instead of
labels (hard classifiers), as has been the primary focus of most RS based
techniques so far. We urge further exploration and extension of this notion of
understanding classifier confidence and base classifier properties and
leveraging them for RS.

Addressing the high cost challenge in RS, Quasi-Convexity-based Randomized
Smoothing (QCRS) [59] presents an optimisation which exploits the
quasiconcavity condition for the radius-variance curve in randomized
smoothing, which is a weaker form of concavity. While DDR assumed concavity
for the certified radii, empirically, it is seen that this is not the case
despite it showing significant certified radii improvements. On the other
hand, quasiconcavity is shown to hold for most data points. Based on this,
QCRS is presented as a computationally efficient approach with less overheads
compared to other input-specific inference-based optimisation methods.
Further, it is an entirely orthogonal approach to many other optimisation
techniques in randomized smoothing, and as with other orthogonal approaches,
we encourage empirical testing with other methods.

Noting the dearth of inference cost-reducing methods like [59], particularly
for input-specific techniques which add a significant overhead to RS, which
itself is computationally expensive, we also encourage works to work towards
reducing these costs, since they prohibit scalable applications of RS.
Further, even though many techniques use information beyond the Neyman-Pearson
lemma, such as classifier-specific information [21], data-dependent
information and local geometric information [5], there is not much research to
say that this works towards addressing the curse of dimensionality in the
input-specific case. Further, these input-specific schemes also suffer from
robustness-accuracy issues as with base RS and there should be more research
into addressing this issue.

###  III-F Other Methods

Prior works on randomized smoothing against $l_{1}$ adversarial attacks use
additive smoothing noise and provide probabilistic robustness guarantees,
which provide a certain level of confidence but lack absolute certainty.
Levine et al. [90] propose a $l_{1}$ certification method based on data
quantization. They term this method SSN, Smoothing with Splitting Noise. They
also propose a de-randomized version of SSN, DSSN, which yields deterministic
certificates instead of probabilistic certificates in normal randomized
smoothing. Whether this non-additive smoothing technique can be extended to
other $l_{p}$ norms remains unexplored. Another work [43], presents a
technique to obtain larger $l_{1}$ certificates when using randomized
smoothing. Current $l_{1}$ methods augment the data with noise beyond the
domain constraints in most problems like image classification which is trivial
to detect. They show that leveraging the domain constraint that input points
have to lie in the image domain $[0,1]^{d}$ improves $l_{1}$ certificates
significantly without the need to adapt the classifiers or change smoothing
distributions. However, there remains a gap to what seems possible in
empirical $l_{1}$ robustness giving way for future research. Both works
essentially improve $l_{1}$ certificates with the differences lying in their
core methodology.

So far, randomized smoothing has only been used for $l_{p}$ robustness for
$p>=1$ in the majority of research, and techniques have been developed to
provably guarantee the robustness of a classifier to adversarial perturbations
of bounded $l_{1}$ and $l_{2}$ magnitudes by using randomized smoothing. This
has been extended considerably in works that focus on offering adversarial
robustness guarantees for cases where the adversary is $l_{0}$ bounded [89],
[83]. Lee, Guang-He, et al. [89] consider a distribution where random noise,
$\sigma\sim\\{0,1\\}^{d}$, is multiplied by the image. This multiplication is
done pixel-wise; hence, they are masking the pixels out. Moreover, they
theoretically prove the superiority of this discrete distribution against
Gaussian noise to provide a better-certified radius for $l_{0}$ attacks. They
empirically show that their certificates are consistently better than the ones
derived from the Gaussian distribution. Further, their model outperforms other
models by a large margin across different radii measures. Challenging these
results, Levine, Alexander, et al. [83] introduce a novel method that
addresses $l_{0}$ attacks within the framework of randomized smoothing,
deviating from the conventional use of additive Gaussian noise. They propose a
unique $l_{0}$ ablation scheme, wherein pixels of the image are randomly
ablated. They also introduce an encoding of the ablated classifier,
representing the absence of information, which is carefully designed to ensure
unbiased representation in the classifier’s training process. This
modification is used in sparse adversarial attacks, for $l_{0}$ attacks where
additive noise is not useful, and for data with a sparse structure. They point
out that in the scheme by Lee et al. [89] each pixel is retained with a fixed
probability $\kappa$ and is otherwise assigned to a random value from the
remaining possible pixel values in $S$, leading to considerably lower median
certified robustness compared to Levine, Alexander, et al. [83], on the
datasets used in both works. These works provide robustness guarantees in
various resolutions and perspectives, from a point-wise certificate to a
regional certificate, and open up many avenues for future extensions at
different levels.

Another concept that is focused on improving adversarial robustness is that of
colored noise injection-based smoothing (CNI smoothing) [113]. It comes from
extending the idea of adding white Gaussian noise to the network weights and
activations during adversarial training (PNI) [114] to the injection of
colored noise for defense against common white-box and black-box attacks and
is exploited by Nemcovsky, Yaniv, et al. [42]. They present an inference-only
method for improving empirical adversarial robustness by taking into account
the spatial information in the area of the data points As an adversarial
defense technique, CNI smoothing is based on noise injection to the model’s
weights or parameters using multivariate Gaussian noise. When used in
constructing an RS-based approach where both the inputs and parameters have
Gaussian noise added to them, this technique yields improved adversarial
robustness compared to CNI, improving model performance. However, at the same
time, it does not provide a proper ablation approach which can be pursued by
future studies. Another point of concern is that the performance of this
method declines as the number of attack iterations increases. Overcoming this
comes at a cost of increased computational complexity which paves a path for
future work in this domain twoards lowering costs.

Coming back to the challenge of designing an efficient classifier with a
sufficient certified radius, Delattre, Blaise, et al. [58] show that the
variance introduced by the Monte-Carlo sampling in the randomized smoothing
procedure estimate closely interacts with two other important properties of
the classifier, i.e. its Lipschitz constant and margin. They utilize the
Lipschitz constant for the base classifier to further improve the bounds on
the Lipschitz constant for the smoothed classifier [86]. They also present a
novel technique named Lipschitz-Variance-Margin Randomized Smoothing (LVM-RS)
based on optimizing the variance-margin trade-off in the base classifier to
improve the certified robust radius while maintaining reliability. This is
based on the relation between the variance of the smoothed classifier, the
Lipschitz constant, and the margin of the base classifier. This new
certification method encourages the use of pre-trained models in addition to
randomized smoothing, leading to improvement in the current certification
radius. This also brings into the picture the scope of integrating LVM-RS with
margin maximization strategies.

Other works ([6], [56]) propose a solution to improve the certified bounds
obtained using generalized Gaussian distributions and formulating non-Gaussian
distributions. While this does not address the curse of dimensionality
directly, it optimises the bounds obtained despite this issue. The former [6]
optimises the distribution for each $l_{p}$ threat model, whereas the latter
[56] generalizes and provides a universal robustness certification framework
by the name of Universally Approximated Certified Robustness which can also be
used to derive optimal certified radii against $l_{p}$ perturbation generated
by a continuous probability distribution.

The necessity of certified robustness for top-k predictions, instead of just
the top prediction as has been the case for RS methods till now, has been
pointed out in the work by Jia et al. [62] along with the need to derive tight
robustness in the $l_{2}$ norm for the same using Gaussian noise. They address
the technical challenges faced in implementing the same, which can majorly be
summarised as (I) difficulty in computing the probability $p_{l}$ that a label
$l$ is verifiably among the top-k labels predicted by the smoothed classifier,
(II) difficulty in computing the k-largest probabilities $p_{i}$ for the top-k
labels and (III) finding an analytical solution to the equation for the
certified radius of each label. They overcome these challenges using
simultaneous confidence intervals of the label probabilities and an algorithm
to solve the equation to obtain a lower bound of the certified radius. As
noted in the work itself, there needs to be future work to derive similar
bounds for $l_{1}$ and $l_{0}$ attacks and the optimal noise distributions for
the case of top-k predictions.

Dvijotham, Krishnamurthy Dj, et al. [92] introduce a way to provide robustness
guarantees for arbitrary smoothing distributions using f-divergences. They
formulate the task of verification in a way so that it becomes solvable using
a simple optimisation problem. They were mainly focused on binary classifiers.
Their approach reframes the problem in the space of probability measures,
employing f-divergences to define tractable constraint sets. Kou, Yiwen et al.
[31] discuss an extension of this: they utilize distance-based likelihood
metrics, Wasserstein distance and total-variation distance to solve the
optimisation problem introduced in the work by Dvijotham, Krishnamurthy Dj, et
al. [92]. They also show a comparison of different uniform probability
measures over different norm-based attacks and show a comparison of their
performances. They also show that the curse of dimensionality exists even for
distance-based metrics.

Anderson, Brendon G. et al. [36] discuss randomized smoothing with the
consideration of generic smoothing distributions, which can be input-
dependent. They theoretically discuss that the main task of randomized
smoothing is to maximize the average certified radius, where, in actuality,
this problem is an infinite dimensional optimisation problem, which can be
lower bound by cone-based linear programming if the confidence intervals of
the classes are used. They provide a semi-infinite approach to solving this
problem and mainly focus on the theoretical side with a simple yet unpractical
experiment as a proof of concept.

Improving Randomized Smoothing for Scalability Throughout our examination in
this section, we observe that most new optimizations in randomized smoothing
do not directly address the curse of dimensionality or the issue of high
inference costs. Instead, they tend to introduce new techniques, each with its
own computational overhead and dimensionality challenges, and then propose
solutions for that additional cost. One such example is that of input-
dependent techniques, which add input-specific components over an already
costly randomized smoothing process, as pointed out in that specific
subsection. While this certainly helps improve the applicability of a
technique individually, it does not enhance the overall scalability of
randomized smoothing, hence this foundational issue persists.

##  IV Diverse applications of Randomized Smoothing

In this section, we discuss applications of randomized smoothing in various
fields. While introducing these applications, domain-specific optimisations to
improve RS for that particular application have also been discussed. While we
have tried to group some related application cases and present them in a
consolidated manner, certain use cases stand out with no proper classification
possible. For those papers and applications, we simply present a summary of
the work without elaborating on the domain and required background.

###  IV-A RS in other types of Adversarial Attacks

Patch attacks involve strategically placing visually imperceptible
modifications on images leading to misclassifications and compromised system
security. Levine, Alexander, et al. [23] deal with (De-) Randomized Smoothing
for certifiable defense against Patch Attacks, which utilizes the fact that
patch attacks are more constrained than general sparse attacks. This paper
achieves much better results than Chiang et al. (2020), who defend against
patch attacks using interval-bound propagation. They propose a structured
ablation scheme (block smoothing and band smoothing). Experimentally, their
method produces higher certified accuracy than $l_{0}$ randomized ablation.
This method stands out as it even scales to larger datasets like Imagenet,
unlike previous works.

Malware-based attacks pose a serious cybersecurity threat, making robust
malware detection imperative to safeguard against data breaches, system
compromise, and potential economic and operational disruptions. Zhang, Jiawei,
et al. [67] introduce DRSM (De-randomized smoothed MalConv), a certified
defense created by redesigning the de-randomized smoothing technique for the
domain of malware detection through executables [94]. It is found that DRSM
faces a marginal accuracy drop at the cost of robustness. DRSM proves to be
empirically robust to some extent against a diverse set of attacks.

Adversarial label-flipping attacks manipulate the labeling of data to deceive
machine learning models, leading to incorrect predictions and compromising the
system’s integrity. Rosenfeld, Elan, et al. [52] propose a strategy to build a
linear least squares classifier based on pre-trained deep features
incorporated with the Chernoff inequality that are certifiably robust against
a strong variant of label flipping where the adversary targets each test
example independently. They do so without additional runtime cost over
standard classification. Notably, although they employ a randomized approach,
the final algorithm does not use random sampling but relies on a convex
optimisation problem to compute the certified robustness.

A major vulnerability of RS against adversarial attacks is where the attacker
can backdoor even the randomness in a model. This applies to many
randomization-based methods, particularly RS, seeing its widespread usage for
security purposes. Dahiya, Pranav, et al. [103] demonstrate that there exist
PRNG-attacks in which an attacker can alter the randomness of the model ever
so slightly such that it cannot be detected by existing standards of
randomness [104], but affect the performance of randomized smoothing by
overestimating certification bounds. This prompts research into developing
more extensive randomness tests, particularly in the backdrop of adversarial
robustness, specifically for randomness in RS, but even for machine learning
models in general.

###  IV-B Watermark Neural Networks

Watermarks are a strategy to preserve a creator’s intellectual rights over
their property. This has led to the development of watermarking strategies
using neural networks that aim to prevent adversaries from removing
watermarks. However, these models fail when stronger or fine-tuned attacks are
used. Thus, as in the general field of adversarial ML, there was a shift to
certified robustness, so was this change observed in watermark networks.
Randomized smoothing is one of the techniques that can be used for this
purpose [28]. Their certified bounds, based on $l_{2}$ adversary attacks,
guarantee watermark persistence and provide state-of-the-art robustness
against adversarial attacks.

Ren, Jiaxiang, et al. [48] extend the use of randomized smoothing for
watermark neural networks [28] for better application against $l_{p}$ attacks
for any $p>1$, which, as mentioned earlier, suffer from the curse of
dimensionality. Their approach leverages Mollifier theory and the dimension-
independent Lipschitz constant to develop a smoothing technique that gives
dimension-independent bounds. Notably, they also developed an efficient
version of their proposed classifier, Certified Watermarks, using
approximations, which performs effectively and efficiently. Thus, they have
tried to adapt and overcome both the curse of dimensionality and high
inference costs. We encourage those interested in this domain to test some of
the above-mentioned optimisations to improve the application of RS for
watermark neural networks.

###  IV-C Differential Privacy and Federated Learning

Randomized smoothing and certified robustness can also be viewed from the lens
of differential privacy and federated learning in the context of AI security.
For federated learning, Chen, Cheng, et al. [55] present a randomized
smoothing approach in existing frameworks to enable certified robustness. Its
performance is comparable to existing certifiably robust models trained by
centralized training. However, there is much to explore regarding how
randomized smoothing can be implemented for more complex federated learning
frameworks.

In the context of differential privacy, Wang, Wenxiao, et al. [53] propose
DPlis, which improves differentially private stochastic gradient descent. It
does so by smoothing the learning function to become less irregular and more
noise-tolerant. The paper, focusing on DP-SGD, also opens the door for
randomized smoothing to be applied to other differential privacy techniques
like the private aggregation of teacher ensembles (PATE) by realizing that the
fundamental idea behind PATE is noisy data labeling and the parameter noise
during training, which is essentially the label noise itself, can be smoothed
using RS.

###  IV-D Graph Neural Networks

Graph Neural Networks (GNNs) are a powerful class of neural networks that rely
on graph-based data representation through nodes and edges. Like other
technologies, they are not immune to adversarial attacks, such as structural
perturbations that affect graph and node classification. Since randomized
smoothing is an architecture-independent approach to introduce certified
robustness, it certainly can be used for GNNs. A few papers have been
published for certifying robustness in GNNs, but much remains to be explored.
Wang, Binghui, et al. [47] develop a robustness guarantee for randomized
smoothing in GNNs. They note that their bounds apply for both node and graph
classification and any classifier with binary data without making any
assumptions about its architecture. Bojchevski et al. [121] extend RS for
discrete and sparse data, highlighting its relevance as a new approahc to RS
by applying their method to GNNs, which often deal with such data.

A message-interception randomized smoothing approach to improve robustness in
GNNs [63] is specific to the commonly used architecture of message-passing
neural networks [82]. This is based on a gray box, since some knowledge of the
classifier is known, certification method where adversarial messages are
intercepted so as not to affect any target nodes containing sensitive data.
They use the concept of randomized ablation to mask nodal features and deleted
edges. Randomized ablation is a less explored technique which is based on
randomized smoothing and offers sufficient protection against various attacks,
including $l_{0}$ attacks. We encourage more work to identify and use
randomized ablation in other applications alongside theoretical studies of the
same.

###  IV-E Reinforcement Learning

Reinforcement learning (RL) has found usage in many domains like robotics,
trading, and autonomous driving. It is concerned with how an intelligent agent
should act in a dynamic environment to maximize the cumulative reward. The
sensitivity of its applications makes it essential to make RL robust to
adversarial attacks, and RS is successful in doing so. This also represents a
new approach to RS for dynamic cases, as are commonly encountered in RL,
instead of just static problems. Kumar, Aounon, et al. [85] discuss the
application of RL policy smoothing to provide robustness by adding Gaussian
noise to the input data. Their approach offers robust certificates against
adversaries, which aim to minimize the reward. Their guarantees ensure rewards
stay above a certain threshold, even if intermediary steps may be non-optimal.
They also utilise and prove an adaptive version of the Neyman-Pearson lemma,
which forms the base of RS, to protect against adaptive adversarial attacks.
CROP [86] is a generalised framework based on randomized smoothing to certify
robustness in RL policies, which extends to [85] by allowing certified
robustness for cumulative reward and action. They provide empirical results
for CROP. We encourage the use of the adaptive RS, as introduced in these
papers, for other applications and propose further theoretical and empirical
research into RS for RL.

###  IV-F Miscellaneous

Tree-based models are used in domains such as finance and medicine, where
robustness is paramount. Constructing robust tree-based models helps reduce
overfitting, improve generalization, and enhance the model’s resilience to
variations in the data. Horváth, Miklós, et al. [69] propose a novel
(De-)Randomized Smoothing approach for the same, with deterministic $l_{p}$
norm guarantees. The critical insight of their work is that they leverage the
nature of decision stump ensembles to obtain deterministic certificates
instead of probabilistic ones. A minor limitation in their work is that DRS
can not handle arbitrary ensembles of decision trees.

Another interesting usage of RS is in the convergence of stochastic
optimisation procedures. Duchi et al. [30] and Yousefian et al. [37] present
two techniques to discuss this: accelerated gradient techniques and convex
analysis. In [117], the authors propose randomized Differential Dynamic
Programming (DDP) for RL and optimal control theory (OC), which extends the
applicability of the classic Differential Dynamic Programming in OC for non-
smooth dynamic deterministic systems. Minin et al. [50] discuss the problem of
optimisation of near-convex functions, which can be represented as a sum of
strongly convex and bounded functions. The paper presents an algorithm for
minimizing such functions using the RS technique. This technique theoretically
justifies the global optimisation properties of SPSA(Simultaneous Perturbation
Stochastic Approximation)-like algorithms. In the work by Ding, Liang, et al.
[19], randomized smoothing is presented as a form of regularisation that
prevents overfitting by adding noise and forcing the model to learn
generalized features. Thus, using various noise distributions, one can treat
it as a convolution-based smoothing kernel. They obtain estimators with fast
convergence, irrespective of the dimension, using techniques like early
stopping and weight decay. They present future research areas for
classification and other models beyond standard gradient descent. The
application of randomized smoothing further extends to automatic speech
recognition task [16]. Unlike image classification, automatic speech
recognition is a sequential task; the main challenge lies in the fact that as
the input size increases, the no. of outputs becomes difficult and hence it
becomes difficult to provide the most likely class. Their work does not change
the theoretical model of randomized smoothing, but it modifies the voting
criteria to ROVER, a voting technique typically utilized in ASR. The drawback
of this approach is the increased time complexity. Fischer, Marc, et al. [8]
modify the existing randomized smoothing technique and apply it in image
segmentation. The downside in their approach is that it is highly dependent on
pixel values, and a slight change in the pixel values can significantly affect
the Clopper-Pearson lower bound, $\underline{p_{A}}$ which they tackle by
considering a threshold $\tau$, which would only provide a class to a pixel if
the highest class probability exceeds $\tau$; abstaining otherwise..

Applications of randomized smoothing in natural language processing are not as
intensively explored as other domains. Zhao, Haiteng, et al. [35] introduce a
novel framework called Causal Intervention by Semantic Smoothing (CISS) to
enhance the robustness of NLP models against adversarial attacks. Other works
[118], [119] introduce RSMI, a novel two-stage framework that combines
randomized smoothing (RS) with masked inference (MI) to improve the
adversarial robustness of text classification models. Gaussian noise
augmentation, a novel certification method that relies on the exact mechanism
as randomized smoothing, has been proposed by Chiang, Ping-yeh, et al. [71],
with the difference being that it introduces median-based smoothing instead of
mean-based smoothing, i.e. using percentiles instead of expectation for
classification. At the same time, it also converts an object detection problem
to a regression problem for a black-box evaluation of certified robustness,
extending RS from classification to regression. In their work, Xu, Xiao, et
al. [40] introduce a modified attention module, extracting attention maps for
noisy samples and then merging these maps of robust features with clean image
features to obtain an attention map focusing more on robust features to
improve certified bounds obtained by RS. Transformation-specific smoothing,
TSS, is a unified framework for certifying ML robustness against general
adversarial semantic transformations presented by Li, Linyi, et al. [64].
Their approach is to divide common transformations into two categories
depending on the properties of each transformation. Transformation-specific RS
strategies obtain strong robustness certification for resolvable
transformations, while for differentially resolvable transformations, which
cover interpolation errors, a novel approach based on stratified sampling is
used. Combined with consistency-enhanced training, TSS provides rigorous
certification of robustness. Muravev, Nikita, et al. [39] discuss the usage of
randomized smoothing for multiplicative parameters, instead of additive ones.
They mainly focus on the case of gamma correction in images. However, in their
certification experiments on large datasets, they failed to approximate actual
robustness while on smaller datasets, a significant drop in accuracy is seen
when they switch from the idealized setting to the realistic one. Both of
these arise from the computational complexity of RS, which highlights the need
to explore solutions to these issues. A practical limitation in RS-based
methods that affects their performance in certain kinds of applications has
been presented by Voráček, Václav et al. [105]. They analyze randomized
smoothing for numerical errors that may arise due to floating-point arithmetic
and show how the current approach is numerically unsound and may overestimate
or underestimate certified radii. Further, they propose a modified version of
randomized smoothing which improves numerical stability however, it comes with
a slight computational overhead.

Applications highlight the need for scalable RS This section underscores the
significance of randomized smoothing by showcasing its widespread adaptation
and utilization across numerous applications. Despite grappling with
theoretical challenges, such as the curse of dimensionality and high inference
costs, directly impacting these applications, addressing these challenges
could substantially enhance the scalability and practicality of randomized
smoothing. We also observe that many empirical verifications for these
applications limit their tests to smaller datasets or less expensive models,
which is a direct consequence of the scalability issues in RS. Hence, this
section well reinforces our assertion that randomized smoothing needs to be
made more scalable.

Limitations and Conclusion: While this paper has thoroughly investigated
randomized smoothing techniques, including their robustness, applications,
limitations, and potential solutions while emphasising on its scalability, it
is important to recognize the boundaries of this research. By concentrating
solely on randomized smoothing, our perspective has become somewhat narrow,
emphasizing it as the dominant state-of-the-art approach for tackling
adversarial attacks in terms of certified robustness. Thus, one limitation of
this exclusive focus is the possibility of missing alternative methods that
could perform just as effectively or even surpass randomized smoothing in
specific applications.

## References

  * [1] Cohen, Jeremy, Elan Rosenfeld, and Zico Kolter. ”Certified adversarial robustness via randomized smoothing.” In international conference on machine learning, pp. 1310-1320. PMLR, 2019.
  * [2] Li, Bai, Changyou Chen, Wenlin Wang, and Lawrence Carin. ”Certified adversarial robustness with additive noise.” Advances in neural information processing systems 32 (2019).
  * [3] Li, Linyi, Jiawei Zhang, Tao Xie, and Bo Li. ”Double sampling randomized smoothing.” arXiv preprint arXiv:2206.07912 (2022).
  * [4] Yang, Greg, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. ”Randomized smoothing of all shapes and sizes.” In International Conference on Machine Learning, pp. 10693-10705. PMLR, 2020.
  * [5] Cullen, Andrew, Paul Montague, Shijie Liu, Sarah Erfani, and Benjamin Rubinstein. ”Double bubble, toil and trouble: enhancing certified robustness through transitivity.” Advances in Neural Information Processing Systems 35 (2022): 19099-19112.
  * [6] Zhang, Dinghuai, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. ”Black-box certification with randomized smoothing: A functional optimisation based framework.” Advances in Neural Information Processing Systems 33 (2020): 2316-2326.
  * [7] Blum, Avrim, Travis Dick, Naren Manoj, and Hongyang Zhang. ”Random smoothing might be unable to certify $l_{\infty}$ robustness for high-dimensional images.” The Journal of Machine Learning Research 21, no. 1 (2020): 8726-8746.
  * [8] Fischer, Marc, Maximilian Baader, and Martin Vechev. ”Scalable certified segmentation via randomized smoothing.” In International Conference on Machine Learning, pp. 3340-3351. PMLR, 2021.
  * [9] Fischer, Marc, Maximilian Baader, and Martin Vechev. ”Certified defense to image transformations via randomized smoothing.” Advances in Neural information processing systems 33 (2020): 8404-8417.
  * [10] Ugare, Shubham, Tarun Suresh, Debangshu Banerjee, Gagandeep Singh, and Sasa Misailovic. ”Incremental Randomized Smoothing Certification.” arXiv preprint arXiv:2305.19521 (2023).
  * [11] Kumar, Aounon, Alexander Levine, Tom Goldstein, and Soheil Feizi. ”Curse of dimensionality on randomized smoothing for certifiable robustness.” In International Conference on Machine Learning, pp. 5458-5467. PMLR, 2020.
  * [12] Alfarra, Motasem, Adel Bibi, Naeemullah Khan, Philip HS Torr, and Bernard Ghanem. ”Deformrs: Certifying input deformations with randomized smoothing.” In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 6, pp. 6001-6009. 2022.
  * [13] Zhai, Runtian, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. ”Macer: Attack-free and scalable robust training via maximizing certified radius.” arXiv preprint arXiv:2001.02378 (2020).
  * [14] Levine, Alexander, Aounon Kumar, Thomas Goldstein, and Soheil Feizi. ”Tight second-order certificates for randomized smoothing.” arXiv preprint arXiv:2010.10549 (2020).
  * [15] Alfarra, Motasem, Adel Bibi, Philip HS Torr, and Bernard Ghanem. ”Data dependent randomized smoothing.” In Uncertainty in Artificial Intelligence, pp. 64-74. PMLR, 2022.
  * [16] Olivier, Raphael, and Bhiksha Raj. ”Sequential randomized smoothing for adversarially robust speech recognition.” arXiv preprint arXiv:2112.03000 (2021).
  * [17] Hong, Hanbin, and Yuan Hong. ”Certified Adversarial Robustness via Anisotropic Randomized Smoothing.” arXiv preprint arXiv:2207.05327 (2022).
  * [18] Salman, Hadi, Mingjie Sun, Greg Yang, Ashish Kapoor, and J. Zico Kolter. ”Denoised smoothing: A provable defense for pretrained classifiers.” Advances in Neural Information Processing Systems 33 (2020): 21945-21957.
  * [19] Ding, Liang, Tianyang Hu, Jiahang Jiang, Donghao Li, Wenjia Wang, and Yuan Yao. ”Random Smoothing Regularization in Kernel Gradient Descent Learning.” arXiv preprint arXiv:2305.03531 (2023).
  * [20] Anderson, Brendon G., and Somayeh Sojoudi. ”Certified robustness via locally biased randomized smoothing.” In Learning for Dynamics and Control Conference, pp. 207-220. PMLR, 2022.
  * [21] Kumar, Aounon, Alexander Levine, Soheil Feizi, and Tom Goldstein. ”Certifying confidence via randomized smoothing.” Advances in Neural Information Processing Systems 33 (2020): 5165-5177.
  * [22] Súkeník, Peter, Aleksei Kuvshinov, and Stephan Günnemann. ”Intriguing properties of input-dependent randomized smoothing.” arXiv preprint arXiv:2110.05365 (2021).
  * [23] Levine, Alexander, and Soheil Feizi. ”(De) Randomized smoothing for certifiable defense against patch attacks.” Advances in Neural Information Processing Systems 33 (2020): 6465-6475.
  * [24] Mohapatra, Jeet, Ching-Yun Ko, Tsui-Wei Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. ”Higher-order certification for randomized smoothing.” Advances in Neural Information Processing Systems 33 (2020): 4501-4511.
  * [25] Chen, Ruoxin, Jie Li, Junchi Yan, Ping Li, and Bin Sheng. ”Input-specific robustness certification for randomized smoothing.” In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 6, pp. 6295-6303. 2022.
  * [26] Salman, Hadi, Saachi Jain, Eric Wong, and Aleksander Madry. ”Certified patch robustness via smoothed vision transformers.” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15137-15147. 2022.
  * [27] Joshi, Ameya, Minh Pham, Minsu Cho, Leonid Boytsov, Filipe Condessa, J. Zico Kolter, and Chinmay Hegde. ”Smooth-Reduce: Leveraging Patches for Improved Certified Robustness.” (2022).
  * [28] Bansal, Arpit, Ping-yeh Chiang, Michael J. Curry, Rajiv Jain, Curtis Wigington, Varun Manjunatha, John P. Dickerson, and Tom Goldstein. ”Certified neural network watermarks with randomized smoothing.” In International Conference on Machine Learning, pp. 1450-1465. PMLR, 2022.
  * [29] Hao, Zhongkai, Chengyang Ying, Yinpeng Dong, Hang Su, Jian Song, and Jun Zhu. ”Gsmooth: Certified robustness against semantic transformations via generalized randomized smoothing.” In International Conference on Machine Learning, pp. 8465-8483. PMLR, 2022.
  * [30] Duchi, John C., Peter L. Bartlett, and Martin J. Wainwright. ”Randomized smoothing for stochastic optimisation.” SIAM Journal on optimisation 22.2 (2012): 674-701.
  * [31] Kou, Yiwen, Qinyuan Zheng, and Yisen Wang. ”Certified adversarial robustness under the bounded support set.” International Conference on Machine Learning. PMLR, 2022.
  * [32] Mohapatra, Jeet, Ching-Yun Ko, Lily Weng, Pin-Yu Chen, Sijia Liu, and Luca Daniel. ”Hidden cost of randomized smoothing.” In International Conference on Artificial Intelligence and Statistics, pp. 4033-4041. PMLR, 2021.
  * [33] Pal, Ambar, and Jeremias Sulam. ”Understanding Noise-Augmented Training for Randomized Smoothing.” arXiv preprint arXiv:2305.04746 (2023).
  * [34] Feng, Huijie, Chunpeng Wu, Guoyang Chen, Weifeng Zhang, and Yang Ning. ”Regularized training and tight certification for randomized smoothed classifier with provable robustness.” In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 3858-3865. 2020.
  * [35] Zhao, Haiteng, Chang Ma, Xinshuai Dong, Anh Tuan Luu, Zhi-Hong Deng, and Hanwang Zhang. ”Certified robustness against natural language attacks by causal intervention.” In International Conference on Machine Learning, pp. 26958-26970. PMLR, 2022.
  * [36] Anderson, Brendon G., Samuel Pfrommer, and Somayeh Sojoudi. ”Towards optimal randomized smoothing: A semi-infinite linear programming approach.” ICML Workshop on Formal Verification of Machine Learning (WFVML). 2022.
  * [37] Yousefian, Farzad, Angelia Nedić, and Uday V. Shanbhag. ”Convex non-differentiable stochastic optimisation: A local randomized smoothing technique.” Proceedings of the 2010 American Control Conference. IEEE, 2010.
  * [38] Labarbarie, Pol, Hatem Hajri, and Marc Arnaudon. ”Riemannian data-dependent randomized smoothing for neural networks certification.” arXiv preprint arXiv:2206.10235 (2022).
  * [39] Muravev, Nikita, and Aleksandr Petiushko. ”Certified robustness via randomized smoothing over multiplicative parameters of input transformations.” arXiv preprint arXiv:2106.14432 (2021).
  * [40] Xu, Xiao, Shiyu Feng, Zheng Wang, Lizhe Xie, and Yining Hu. ”Adversarial Defense via Attention-Based Randomized Smoothing.” In Artificial Neural Networks and Machine Learning–ICANN 2020: 29th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 15–18, 2020, Proceedings, Part I 29, pp. 455-466. Springer International Publishing, 2020.
  * [41] Pfrommer, Samuel, Brendon G. Anderson, and Somayeh Sojoudi. ”Projected randomized smoothing for certified adversarial robustness.” arXiv preprint arXiv:2309.13794 (2023).
  * [42] Nemcovsky, Yaniv, Evgenii Zheltonozhskii, Chaim Baskin, Brian Chmiel, Alex M. Bronstein, and Avi Mendelson. ”Adversarial robustness via noise injection in smoothed models.” Applied Intelligence 53, no. 8 (2023): 9483-9498.
  * [43] Voracek, Vaclav, and Matthias Hein. ”Improving $l_{1}$-Certified Robustness via Randomized Smoothing by Leveraging Box Constraints.” (2023).
  * [44] Chen, Chen, Kezhi Kong, Peihong Yu, Juan Luque, Tom Goldstein, and Furong Huang. ”Insta-RS: Instance-wise Randomized Smoothing for Improved Robustness and Accuracy.” arXiv preprint arXiv:2103.04436 (2021).
  * [45] Liu, Chizhou, Yunzhen Feng, Ranran Wang, and Bin Dong. ”Enhancing certified robustness of smoothed classifiers via weighted model ensembling.” (2020).
  * [46] Lee, Kyungmin, and Seyoon Oh. ”Efficient randomized smoothing by denoising with learned score function.” (2020).
  * [47] Wang, Binghui, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. ”Certified robustness of graph neural networks against adversarial structural perturbation.” In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1645-1653. 2021.
  * [48] Ren, Jiaxiang, Yang Zhou, Jiayin Jin, Lingjuan Lyu, and Da Yan. ”Dimension-independent certified neural network watermarks via mollifier smoothing.” In International Conference on Machine Learning, pp. 28976-29008. PMLR, 2023.
  * [49] Horváth, Miklós Z., Mark Niklas Müller, Marc Fischer, and Martin Vechev. ”Robust and Accurate–Compositional Architectures for Randomized Smoothing.” arXiv preprint arXiv:2204.00487 (2022).
  * [50] Minin, Ivan, and Alexander Vakhitov. ”Randomized smoothing for near-convex functions in context of image processing.” 2012 American Control Conference (ACC). IEEE, 2012.
  * [51] Mohapatra, Jeet, Ching-Yun Ko, Sijia Liu, Pin-Yu Chen, and Luca Daniel. ”Rethinking randomized smoothing for adversarial robustness.” arXiv preprint arXiv:2003.01249 49 (2020).
  * [52] Rosenfeld, Elan, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. ”Certified Robustness to Adversarial Label-Flipping Attacks via Randomized Smoothing.” (2019).
  * [53] Wang, Wenxiao, Tianhao Wang, Lun Wang, Nanqing Luo, Pan Zhou, Dawn Song, and Ruoxi Jia. ”Dplis: Boosting utility of differentially private deep learning via randomized smoothing.” arXiv preprint arXiv:2103.01496 (2021).
  * [54] Sheikholeslami, Fatemeh, Wan-Yi Lin, Jan Hendrik Metzen, Huan Zhang, and J. Zico Kolter. ”Denoised Smoothing with Sample Rejection for Robustifying Pretrained Classifiers.” In Workshop on Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022. 2022.
  * [55] Chen, Cheng, Bhavya Kailkhura, Ryan Goldhahn, and Yi Zhou. ”Certifiably-robust federated adversarial learning via randomized smoothing.” In 2021 IEEE 18th International Conference on Mobile Ad Hoc and Smart Systems (MASS), pp. 173-179. IEEE, 2021.
  * [56] Hong, Hanbin, Binghui Wang, and Yuan Hong. ”Unicr: Universally approximated certified robustness via randomized smoothing.” European Conference on Computer Vision. Cham: Springer Nature Switzerland, 2022.
  * [57] HHorváth, Miklós Z., Mark Niklas Müller, Marc Fischer, and Martin Vechev. ”Boosting randomized smoothing with variance reduced classifiers.” arXiv preprint arXiv:2106.06946 (2021).
  * [58] Delattre, Blaise, Alexandre Araujo, Quentin Barthélemy, and Alexandre Allauzen. ”The Lipschitz-Variance-Margin Tradeoff for Enhanced Randomized Smoothing.” arXiv preprint arXiv:2309.16883 (2023).
  * [59] Kung, Bo-Han, and Shang-Tse Chen. ”QCRS: Improve Randomized Smoothing using Quasi-Concave optimisation.” arXiv preprint arXiv:2302.00209 (2023).
  * [60] Wang, Lei, Runtian Zhai, Di He, Liwei Wang, and Li Jian. ”Pretrain-to-finetune adversarial training via sample-wise randomized smoothing.” (2020).
  * [61] Schuchardt, Jan, Tom Wollschläger, Aleksandar Bojchevski, and Stephan Günnemann. ”Localized Randomized Smoothing for Collective Robustness Certification.” arXiv preprint arXiv:2210.16140 (2022).
  * [62] Jia, Jinyuan, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong. ”Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing.” arXiv preprint arXiv:1912.09899 (2019).
  * [63] Scholten, Yan, Jan Schuchardt, Simon Geisler, Aleksandar Bojchevski, and Stephan Günnemann. ”Randomized message-interception smoothing: Gray-box certificates for graph neural networks.” Advances in Neural Information Processing Systems 35 (2022): 33146-33158.
  * [64] Li, Linyi, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. ”Tss: Transformation-specific smoothing for robustness certification.” In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 535-557. 2021.
  * [65] Szegedy, Christian, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. ”Intriguing properties of neural networks.” arXiv preprint arXiv:1312.6199 (2013).
  * [66] Ettedgui, Raphael, Alexandre Araujo, Rafael Pinot, Yann Chevaleyre, and Jamal Atif. ”Towards Evading the Limits of Randomized Smoothing: A Theoretical Analysis.” arXiv preprint arXiv:2206.01715 (2022).
  * [67] Zhang, Jiawei, Linyi Li, Ce Zhang, and Bo Li. ”CARE: Certifiably Robust Learning with Reasoning via Variational Inference.” In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 554-574. IEEE, 2023.
  * [68] Goodfellow, Ian J., Jonathon Shlens, and Christian Szegedy. ”Explaining and harnessing adversarial examples.” arXiv preprint arXiv:1412.6572 (2014).
  * [69] Horváth, Miklós, Mark Müller, Marc Fischer, and Martin Vechev. ”(De-) Randomized Smoothing for Decision Stump Ensembles.” Advances in Neural Information Processing Systems 35 (2022): 3066-3081.
  * [70] Davenport, Samuel, Thomas E. Nichols, and Armin Schwarzman. ”Confidence regions for the location of peaks of a smooth random field.” arXiv preprint arXiv:2208.00251 (2022).
  * [71] Chiang, Ping-yeh, Michael Curry, Ahmed Abdelkader, Aounon Kumar, John Dickerson, and Tom Goldstein. ”Detection as regression: Certified object detection with median smoothing.” Advances in Neural Information Processing Systems 33 (2020): 1275-1286.
  * [72] Lecuyer, Mathias, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. ”Certified robustness to adversarial examples with differential privacy.” In 2019 IEEE symposium on security and privacy (SP), pp. 656-672. IEEE, 2019.
  * [73] Zhang, Hongyang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. ”Theoretically principled trade-off between robustness and accuracy.” In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
  * [74] Fefferman, Charles, Sanjoy Mitter, and Hariharan Narayanan. ”Testing the manifold hypothesis.” Journal of the American Mathematical Society 29.4 (2016): 983-1049.
  * [75] Wu, Yihan, Aleksandar Bojchevski, Aleksei Kuvshinov, and Stephan Günnemann. ”Completing the picture: Randomized smoothing suffers from the curse of dimensionality for a large family of distributions.” In International Conference on Artificial Intelligence and Statistics, pp. 3763-3771. PMLR, 2021.
  * [76] Mustafa, Aamir, Salman H. Khan, Munawar Hayat, Jianbing Shen, and Ling Shao. ”Image super-resolution as a defense against adversarial attacks.” IEEE Transactions on Image Processing 29 (2019): 1711-1724.
  * [77] Kurakin, Alexey, Ian Goodfellow, and Samy Bengio. ”Adversarial examples in the physical world.” (2016).
  * [78] Tsipras, Dimitris, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. ”Robustness may be at odds with accuracy.” arXiv preprint arXiv:1805.12152 (2018).
  * [79] LeCun, Yann, Yoshua Bengio, and Geoffrey Hinton. ”Deep learning.” nature 521.7553 (2015): 436-444.
  * [80] Yang, Yao-Yuan, Cyrus Rashtchian, Hongyang Zhang, Russ R. Salakhutdinov, and Kamalika Chaudhuri. ”A closer look at accuracy vs. robustness.” Advances in neural information processing systems 33 (2020): 8588-8601.
  * [81] Carlini, Nicholas, and David Wagner. ”Towards evaluating the robustness of neural networks.” 2017 ieee symposium on security and privacy (sp). Ieee, 2017.
  * [82] Gilmer, Justin, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. ”Neural message passing for quantum chemistry.” In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
  * [83] Levine, Alexander, and Soheil Feizi. ”Robustness certificates for sparse adversarial attacks by randomized ablation.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.
  * [84] Raghunathan, Aditi, Jacob Steinhardt, and Percy Liang. ”Certified defenses against adversarial examples.” arXiv preprint arXiv:1801.09344 (2018).
  * [85] Kumar, Aounon, Alexander Levine, and Soheil Feizi. ”Policy smoothing for provably robust reinforcement learning.” arXiv preprint arXiv:2106.11420 (2021).
  * [86] Wu, Fan, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. ”Crop: Certifying robust policies for reinforcement learning through functional smoothing.” arXiv preprint arXiv:2106.09292 (2021).
  * [87] Salman, Hadi, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. ”Provably robust deep learning via adversarially trained smoothed classifiers.” Advances in Neural Information Processing Systems 32 (2019).
  * [88] Dosovitskiy, Alexey, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani et al. ”An image is worth 16x16 words: Transformers for image recognition at scale.” arXiv preprint arXiv:2010.11929 (2020).
  * [89] Lee, Guang-He, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. ”Tight certificates of adversarial robustness for randomly smoothed classifiers.” Advances in Neural Information Processing Systems 32 (2019).
  * [90] Levine, Alexander J., and Soheil Feizi. ”Improved, deterministic smoothing for $l_{1}$ certified robustness.” International Conference on Machine Learning. PMLR, 2021.
  * [91] Tumer, Kagan, and Joydeep Ghosh. ”Error correlation and error reduction in ensemble classifiers.” Connection science 8.3-4 (1996): 385-404.
  * [92] Dvijotham, Krishnamurthy Dj, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. ”A framework for robustness certification of smoothed classifiers using f-divergences.” In International Conference on Learning Representations. 2019.
  * [93] Mueller, Mark Niklas, Mislav Balunović, and Martin Vechev. ”Certify or predict: Boosting certified robustness with compositional architectures.” International Conference on Learning Representations (ICLR 2021). OpenReview, 2021.
  * [94] Raff, Edward, Jon Barker, Jared Sylvester, Robert Brandon, Bryan Catanzaro, and Charles K. Nicholas. ”Malware detection by eating a whole exe.” In Workshops at the thirty-second AAAI conference on artificial intelligence. 2018.
  * [95] Moosavi-Dezfooli, Seyed-Mohsen, Alhussein Fawzi, and Pascal Frossard. ”Deepfool: a simple and accurate method to fool deep neural networks.” Proceedings of the IEEE conference on computer vision and pattern recognition. 2016.
  * [96] Croce, Francesco, and Matthias Hein. ”Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.” International conference on machine learning. PMLR, 2020.
  * [97] Brown, Tom B., Dandelion Mané, Aurko Roy, Martín Abadi, and Justin Gilmer. ”Adversarial patch.” arXiv preprint arXiv:1712.09665 (2017).
  * [98] Gu, Shixiang, and Luca Rigazio. ”Towards deep neural network architectures robust to adversarial examples.” arXiv preprint arXiv:1412.5068 (2014).
  * [99] Miller, David J., Zhen Xiang, and George Kesidis. ”Adversarial learning targeting deep neural network classification: A comprehensive review of defenses against attacks.” Proceedings of the IEEE 108.3 (2020): 402-433.
  * [100] Papernot, Nicolas, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. ”Distillation as a defense to adversarial perturbations against deep neural networks.” In 2016 IEEE symposium on security and privacy (SP), pp. 582-597. IEEE, 2016.
  * [101] Shafahi, Ali, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. ”Are adversarial examples inevitable?.” arXiv preprint arXiv:1809.02104 (2018).
  * [102] Bubeck, Sébastien, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. ”Adversarial examples from computational constraints.” In International Conference on Machine Learning, pp. 831-840. PMLR, 2019.
  * [103] Dahiya, Pranav, Ilia Shumailov, and Ross Anderson. ”Machine Learning needs its own Randomness Standard: Randomised Smoothing and PRNG-based attacks.” arXiv preprint arXiv:2306.14043 (2023).
  * [104] Rukhin, Andrew, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. Vol. 22. US Department of Commerce, Technology Administration, National Institute of Standards and Technology, 2001.
  * [105] Voráček, Václav, and Matthias Hein. ”Sound randomized smoothing in floating-point arithmetics.” arXiv preprint arXiv:2207.07209 (2022).
  * [106] Hein, Matthias, and Maksym Andriushchenko. ”Formal guarantees on the robustness of a classifier against adversarial manipulation.” Advances in neural information processing systems 30 (2017).
  * [107] Madry, Aleksander, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. ”Towards deep learning models resistant to adversarial attacks.” arXiv preprint arXiv:1706.06083 (2017).
  * [108] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint arXiv:1611.01236, 2016.
  * [109] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083, 2017.
  * [110] Zhang, Kai, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. ”Beyond a Gaussian denoiser: Residual learning of deep cnn for image denoising.” IEEE transactions on image processing 26, no. 7 (2017): 3142-3155.
  * [111] Tai, Ying, Jian Yang, Xiaoming Liu, and Chunyan Xu. ”Memnet: A persistent memory network for image restoration.” In Proceedings of the IEEE international conference on computer vision, pp. 4539-4547. 2017.
  * [112] Levine, Alexander, Sahil Singla, and Soheil Feizi. ”Certifiably robust interpretation in deep learning.” arXiv preprint arXiv:1905.12105 (2019).
  * [113] Zheltonozhskii, Evgenii, Chaim Baskin, Yaniv Nemcovsky, Brian Chmiel, Avi Mendelson, and Alex M. Bronstein. ”Colored noise injection for training adversarially robust neural networks.” arXiv preprint arXiv:2003.02188 (2020).
  * [114] He, Zhezhi, Adnan Siraj Rakin, and Deliang Fan. ”Parametric noise injection: Trainable randomness to improve deep neural network robustness against adversarial attack.” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 588-597. 2019.
  * [115] Eiras, Francisco, Motasem Alfarra, M. Pawan Kumar, Philip HS Torr, Puneet K. Dokania, Bernard Ghanem, and Adel Bibi. ”Ancer: Anisotropic certification via sample-wise volume maximization.” arXiv preprint arXiv:2107.04570 (2021).
  * [116] Rumezhak, Taras, Francisco Girbal Eiras, Philip HS Torr, and Adel Bibi. ”RANCER: Non-Axis Aligned Anisotropic Certification with Randomized Smoothing.” In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 4672-4680. 2023.
  * [117] Lidec, Quentin Le, Louis Montaut, Cordelia Schmid, Ivan Laptev, and Justin Carpentier. ”Leveraging randomized smoothing for optimal control of nonsmooth dynamical systems.” arXiv preprint arXiv:2203.03986 (2022).
  * [118] Moon, Han Cheol, Shafiq Joty, Ruochen Zhao, Megh Thakkar, and Xu Chi. ”Randomized Smoothing with Masked Inference for Adversarially Robust NLP Systems.” (2022).
  * [119] Moon, Han Cheol, Shafiq Joty, Ruochen Zhao, Megh Thakkar, and Xu Chi. ”Randomized Smoothing with Masked Inference for Adversarially Robust Text Classifications.” arXiv preprint arXiv:2305.06522 (2023).
  * [120] Vaishnavi, Pratik, Kevin Eykholt, and Amir Rahmati. ”Accelerating Certified Robustness Training via Knowledge Transfer.” Advances in Neural Information Processing Systems 35 (2022): 5269-5281.
  * [121] Bojchevski, Aleksandar, Johannes Gasteiger, and Stephan Günnemann. ”Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more.” In International Conference on Machine Learning, pp. 1003-1013. PMLR, 2020.