# Adaptive Randomized Smoothing: Certifying Multi-Step Defences against
Adversarial Examples

Saiyue Lyu1∗, Shadab Shaikh1∗, Frederick Shpilevskiy1∗, Evan Shelhamer2,
Mathias Lécuyer1
1University of British Columbia, 2Google DeepMind
{saiyuel, shadabs3<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
∗ equal contribution

###### Abstract

We propose Adaptive Randomized Smoothing (ARS) to certify the predictions of
our test-time adaptive models against adversarial examples. ARS extends the
analysis of randomized smoothing using f-Differential Privacy to certify the
adaptive composition of multiple steps. For the first time, our theory covers
the sound adaptive composition of general and high-dimensional functions of
noisy input. We instantiate ARS on deep image classification to certify
predictions against adversarial examples of bounded $L_{\infty}$ norm. In the
$L_{\infty}$ threat model, our flexibility enables adaptation through high-
dimensional input-dependent masking. We design adaptivity benchmarks, based on
CIFAR-10 and CelebA, and show that ARS improves accuracy by $2$ to $5\%$
points. On ImageNet, ARS improves accuracy by $1$ to $3\%$ points over
standard RS without adaptivity.

##  1 Introduction

Despite impressive accuracy, deep learning models still show a worrying
susceptibility to adversarial attacks. Such attacks have been shown for a
large number of tasks and models (Costa et al., 2023; Chakraborty et al.,
2018), including areas where security and safety are critical such as fraud
detection (Pumsirirat and Liu, 2018) or self-driving (Cao et al., 2021).

Several rigorous defences have been proposed to certify robustness. Randomized
Smoothing (RS) (Lécuyer et al., 2019; Cohen et al., 2019) does so by averaging
predictions over noisy versions of the input at test time, and as such can
scale to large deep learning models. However, RS has its limitations: it is
inflexible and either degrades accuracy or only certifies against small
attacks.

To address these shortcomings and improve robustness, there has been a recent
push to develop defences that adapt to inputs at test time Croce et al.
(2022), including for RS (Alfarra et al., 2022a; Súkeník et al., 2021; Hong et
al., 2022). Most such adaptive defences are heuristic, unproven, and subject
to improved attacks (Croce et al., 2022; Alfarra et al., 2022a; Hong et al.,
2022), running the risk of reverting to a hopeless cat and mouse game with
attackers (Athalye et al., 2018; Tramer et al., 2020), or only provide limited
adaptivity (Súkeník et al., 2021; Hong et al., 2022) and gain (§5).

We (re)connect RS to Differential Privacy (DP), after its abandonment for a
tighter analysis via hypothesis testing (Cohen et al., 2019), and introduce
Adaptive Randomized Smoothing (ARS) to provide test-time adaptivity while
preserving rigorous bounds. Specifically, we analyze RS through the lens of
$f$-Differential Privacy ($f$-DP), and use this connection to leverage a key
strength of DP: the end-to-end analysis of multi-step adaptive computation
using composition results (§2).

We use ARS to design two-step defence against $L_{\infty}$ adversaries on
image classification (Figure 1), which is a challenging setting for RS Blum et
al. (2020). The first step computes an input mask that focuses on task-
relevant information. This reduces the dimension of the input, which is then
passed to the second step for prediction. Thanks to this adaptive dimension
reduction, the second step makes its prediction on a less noisy image,
improving the performance and certification radius (§3).

We evaluate our adaptive randomized smoothing method in three settings (§4).
For image classification, we first design a challenging benchmark based on
CIFAR-10, and we show that ARS can improve accuracy by up to $9.9\%$. For
spatially-localized face attribute classification on the CelebA dataset, we
show that ARS improves accuracy by up to $10\%$. For large-scale image
classification on ImageNet, ARS improves the accuracy by $1\%$. At radius
$0.005$, where RS has certified accuracy of $0$ while ARS still has a
certified accuracy of $15\%$.

Figure 1: Two-step ARS for $L_{\infty}$-bounded attacks. Step
$\mathcal{M}_{1}$ adds noise to input $X$ and post-processes the result into a
mask $w(m_{1})$. Step $\mathcal{M}_{2}$ takes masked input $w(m_{1})\odot X$
and adds noise to get $m_{2}$. Base classifier $g$ post-processes a weighted
average of $m_{1},m_{2}$ to output a label. RS reduces to $\sigma_{2}=\sigma$
and $w(.)=1$ (no $\mathcal{M}_{1}$).

##  2 Theory for Adaptivity via Differential Privacy

After introducing the necessary background and known results on RS and DP
(§2.1), we reconnect RS to its DP roots by showing that the tight analysis of
Cohen et al. (2019) can be seen as PixelDP (Lécuyer et al., 2019) using
$f$-Differential Privacy (Dong et al., 2019, 2022), a hypothesis testing
formulation of DP (§2.2). This connection lets us leverage composition results
for $f$-DP to analyze multi-step approaches for provable robustness to
adversarial examples, which we name Adaptive Randomized Smoothing (ARS)
(§2.3). We leverage ARS to design and analyze a two-step defence against
$L_{\infty}$-bounded adversaries (§2.4), which we then instantiate as a deep
network (§3).

###  2.1 Related Work: Adversarial Robustness, Randomized Smoothing, and
Differential Privacy

Adversarial Examples (Szegedy et al., 2014): Consider a classifier
$g:\mathcal{X}\rightarrow\mathcal{Y}$, and input $X$. An adversarial example
of radius $r$ in the $L_{p}$ threat model, for model $g$ on input $X$, is an
input $X+e$ such that $g(X+e)\neq g(X)$, where $e\in B_{p}(r)$, where
$B_{p}(r)\triangleq\\{x\in\mathbb{R}^{d}:\|x\|_{p}\leq r\\}$ is the $L_{p}$
ball of radius $r$. These inputs or attacks are made against classifiers at
test time. For more on the active topics of attack and defence, we refer to
surveys (Li et al., 2023; Costa et al., 2023; Chakraborty et al., 2018) on
current attacks and provable defences. In general, provable defences do not
focus on the largest-scale highest-accuracy classifiers, with the notable
exception of randomized smoothing.

Randomized Smoothing (RS) (Lécuyer et al., 2019; Cohen et al., 2019) is a
scalable approach to certifying model predictions against $L_{2}$-norm
adversaries. Specifically, it certifies robustness to any attack $\in
B_{2}(r_{X})$. The algorithm randomizes a base model $g$ by adding spherical
Gaussian noise to its input, and produces a smoothed classifier that returns
the class with highest expectation over the noise:
$y_{+}\triangleq\arg\max_{y\in\mathcal{Y}}\mathbb{P}_{z\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}^{d})}\big{(}g(X+z)=y\big{)}$.
The tightest analysis from Cohen et al. (2019) uses hypothesis testing theory
to show that, with $\underline{p_{+}},\overline{p_{-}}\in[0,1]$ such that
$\mathbb{P}(g(X+z)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(g(X+z)=y_{-})$, the certificate size $r_{X}$ for prediction
$y_{+}$ is:

$r_{X}=\frac{\sigma}{2}\big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\big{)},$
(1)

where $\Phi^{-1}$ is the inverse standard Gaussian CDF, $\underline{p_{+}}$
lower-bounds the probability of $g(X+z)=y_{+}$ (the most probable class), and
$\overline{p_{-}}$ upper-bounds the probability of other classes.

While sound, RS is static during testing even though attacks may adapt. Recent
work aims to make RS adapt at test time (Súkeník et al., 2021; Alfarra et al.,
2022a; Hong et al., 2022). While pioneering, these works are restricted in
either their soundness or their degree of adaptation and resulting
improvement. Súkeník et al. (2021) soundly adapt the variance for RS by the
distance between test and train inputs. However, this only provides minimal
adaptivity, with only minor improvement to certification. Alfarra et al.
(2022a) adapt the variance for RS to each test input, but the analysis is not
end-to-end, and hence not sound (Súkeník et al., 2021). UniCR (Hong et al.,
2022) adapts the noise distribution for RS, primarily to the data distribution
during training, and optionally to input during testing. The train-time
adaptation is sound, but the test-time adaptation is not due to the same issue
raised by Súkeník et al. (2021). We propose ARS to advance certified test-time
adaptivity: our approach is sound and high-dimensional to flexibly adapt the
computation of later steps conditioned on earlier steps by differential
privacy theory.

Differential Privacy (DP) is a rigorous notion of privacy. A randomized
mechanism $\mathcal{M}$ is $(\epsilon,\delta)$-DP if, for any neighbouring
inputs $X$ and $X^{\prime}$, and any subset of possible outputs
$\mathcal{Y}\subset\textrm{Range}(\mathcal{M})$,
$\mathbb{P}(\mathcal{M}(X)\in\mathcal{Y})\leq
e^{\epsilon}\mathbb{P}(\mathcal{M}(X^{\prime})\in\mathcal{Y})+\delta$.
Following Lécuyer et al. (2019), we define neighbouring based on $L_{p}$
norms: $X$ and $X^{\prime}$ in $\mathbb{R}^{d}$ are $L_{p}$ neighbours at
radius $r$ if $X-X^{\prime}\in B_{p}(r)$.

RS was initially analyzed using $(\epsilon,\delta)$-Differential Privacy
(Lécuyer et al., 2019). Intuitively, the randomized classifier
$\mathcal{M}(X)\triangleq g(X+z),\
z\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}^{d})$ acts as a privacy preserving
mechanism (the Gaussian mechanism) that provably “hides” small variations in
$X$. This privacy guarantee yields a robustness certificate for the expected
predictions.

$\boldsymbol{f}$-DP (Dong et al., 2019) is a notion of privacy that extends
$(\epsilon,\delta)$-DP, and defines privacy as a bound on the power of
hypothesis tests. Appendix A provides more details on $f$-DP. The main result
we leverage is Theorem 2.7 of Dong et al. (2022) that for a Gaussian mechanism
$\mathcal{M}(X)=\theta(X)+z$, $z\sim\mathcal{N}(0,\frac{r^{2}}{\mu^{2}})$,
such that for any neighbouring $X,X^{\prime}$,
$\theta(X)-\theta(X^{\prime})\in B_{2}(r)$ (i.e., the $L_{2}$ sensitivity of
$\theta$ is $r$), we have that $\mathcal{M}$ is $G_{\mu}$-DP with:

$G_{\mu}(\alpha)=\Phi\Big{(}\Phi^{-1}(1-\alpha)-\mu\Big{)}.$ (2)

We leverage two key properties of $f$-DP. First, $f$-DP is resilient to post-
processing. That is, if mechanism $\mathcal{M}$ is $f$-DP,
$\textrm{proc}\circ\mathcal{M}$ is also $f$-DP. Second, $f$-DP is closed under
adaptive composition. We refer to §3 in Dong et al. (2022) for the precise
definition and use their Corollary 3.3: the adaptive composition of two
Gaussian mechanisms $G_{\mu_{1}}$-DP and $G_{\mu_{2}}$-DP is itself
$G_{\mu}$-DP, with:

$\mu=\sqrt{\mu_{1}^{2}+\mu_{2}^{2}}$ (3)

$f$-DP is distinct from the $f$-divergence from information theory. Dvijotham
et al. (2020) use $f$-divergence bounds between the noise distribution centred
on the original input and centred on any perturbed input. This improves RS by
broadening the noise distributions and norm-bounds on the adversary that RS
can support. In contrast we focus on $f$-DP, which captures enough information
to reconstruct any divergence by post-processing (Proposition B.1. in Dong et
al. (2019)). Our main objective is different: we leverage $f$-DP composition
properties to enable multi-step deep learning architectures that adapt to the
input at test time with robustness guarantees.

###  2.2 Randomized Smoothing from $\boldsymbol{f}$-DP

We reconnect RS with DP, using $f$-DP to yield results as strong as that of
Equation 1. We start with a general robustness result on $f$-DP classifiers,
which we later build on for our main result.

######  Proposition 2.1 ($f$-DP Robustness).

Let $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Y}$ be $f$-DP for $B_{p}(r)$
neighbourhoods, and let
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$ be
the associated smoothed classifier. Let $y_{+}\triangleq M_{S}(X)$ be the
prediction on input $X$, and let $\underline{p_{+}},\overline{p_{-}}\in[0,1]$
be such that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then:

$f(1-\underline{p_{+}})\geq 1-f(\overline{p_{-}})\Rightarrow\forall e\in
B_{p}(r),\ M_{S}(X+e)=y_{+}$

###### Proof.

See Appendix B1. ∎

Let us now instantiate Proposition 2.1 for Gaussian RS (see §2.1):

######  Corollary 2.2 (RS from $f$-DP).

Let $\mathcal{M}:X\rightarrow g(X+z),\
z\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}^{d})$, and
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$ be
the associated smooth model. Let $y_{+}\triangleq M_{S}(X)$ be the prediction
on input $X$, and let $\underline{p_{+}},\overline{p_{-}}\in[0,1]$ be such
that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then $\forall e\in B_{2}(r_{x}),\
M_{S}(X+e)=y_{+}$, with:

$r_{X}=\frac{\sigma}{2}\big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\big{)}.$

###### Proof.

See Appendix B2. Sketch: $\mathcal{M}$ is a Gaussian mechanism, and is
$G_{\frac{r}{\sigma}}$-DP for any $r$ ($B_{2}(r)$ neighbourhood). We apply
Proposition 2.1 and maximize $r$ such that
$G_{\frac{r}{\sigma}}(1-\underline{p_{+}})\geq
1-G_{\frac{r}{\sigma}}(\overline{p_{-}})$. ∎

###  2.3 Adaptive Randomized Smoothing

While Proposition 2.1 is new, so far we have only used it to reprove the known
result of Corollary 2.2. So why is this connection between $f$-DP and
robustness useful? Our key insight is that we can leverage adaptive
composition results at the core of DP algorithms to _certify multi-step
methods that adapt to their inputs at test time_. Such adaptive defences have
seen recent empirical interest, but either lack formal guarantees, or provide
only limited adaptivity in practice (§5). For the first time we derive a
_sound and high-dimensional_ adaptive method for certification.

We formalize adaptive multi-step certification as follows. Consider $k$
randomized Gaussian mechanisms $\mathcal{M}_{1},\ldots,\mathcal{M}_{k}$ (our
adaptive steps), such that $m_{i}\sim\mathcal{M}_{i}(X|m_{<i})$, and for all
$r\geq 0$ we have that $\mathcal{M}_{i}$ is $G_{r/\sigma_{i}}$-DP for the
$B_{2}(r)$ neighbouring definition. Note that the computation
$\mathcal{M}_{i}$ can depend on previous results, as long as it is
$G_{r/\sigma_{i}}$-DP. Further consider a (potentially randomized) post-
processing classifier $g(m_{1},\ldots,m_{k})=y\in\mathcal{Y}$.

######  Theorem 2.3 (Main result: Adaptive RS).

Using definitions above, let $\mathcal{M}:X\rightarrow
g(m_{1},\ldots,m_{k})\in\mathcal{Y},\
(m_{1},\ldots,m_{k})\sim(\mathcal{M}_{1}(X),\ldots,\mathcal{M}_{k}(X|m_{<k}))$,
and the associated smoothed model be
$M_{S}:X\rightarrow\arg\max_{m\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$.
Let $y_{+}\triangleq M_{S}(X)$ be the prediction on input $X$, and let
$\underline{p_{+}},\overline{p_{-}}\in[0,1]$ be such that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then $\forall e\in B_{2}(r_{x}),\
M_{S}(X+e)=y_{+}$, with:

$r_{X}=\frac{1}{2\sqrt{\sum_{i=1}^{k}\frac{1}{\sigma_{i}^{2}}}}\Big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\Big{)}.$

###### Proof.

By adaptive composition of Gaussian DP mechanisms (Equation 3), $\mathcal{M}$
is $G_{\mu}$-DP with
$\mu=\sqrt{\sum_{i=1}^{k}\frac{r^{2}}{\sigma_{i}^{2}}}=r\sqrt{\sum_{i=1}^{k}\frac{1}{\sigma_{i}^{2}}}$.
We can then apply Corollary 2.2 with
$\sigma=1/\sqrt{\sum_{i=1}^{k}\frac{1}{\sigma_{i}^{2}}}$. ∎

We focus on Gaussian RS, but a similar argument applies to general $f$-DP
mechanisms for which we can compute $f_{i}$ at any $r$, and the composition
$f_{i}\otimes\cdots\otimes f_{k}$, potentially using numerical techniques such
as that of Gopi et al. (2021). For Gaussian noise, Theorem 2.3 leverages
strong results from DP to provide a perhaps surprising result: there is no
cost to adaptivity, in the sense that $k$ independent measurements of input
$X$ with Gaussian noise (without adaptivity) of respective variance
$\sigma_{i}^{2}$ can be averaged to one measurement of variance
$\sigma^{2}=1/\sum_{i=1}^{k}\sigma_{i}^{-2}$. To show this, we can use a
weighted average to minimize variance (see e.g., Equation 4 in Honaker
(2015)), with $c_{j}=\sigma_{j}^{-2}/\sum_{i=1}^{k}\sigma_{i}^{-2}$ yielding
$\sigma^{2}=\sum_{j=1}^{k}c_{j}^{2}\sigma_{j}^{2}=\sum_{j=1}^{k}\sigma_{j}^{-2}/\big{(}\sum_{i=1}^{k}\sigma_{i}^{-2}\big{)}^{2}=1/\sum_{i=1}^{k}\sigma_{i}^{-2}$.
The ARS $r_{X}$ from Theorem 2.3 is identical to that of one step RS from
Corollary 2.2 using this variance: _adaptivity over multi-step computation
comes with no decrease in certified radius_.

###  2.4 ARS against $L_{\infty}$-Bounded Adversaries

How can we leverage the multi-step adaptivity from Theorem 2.3 to increase
certified accuracy? We focus on two-step certified defence against
$L_{\infty}$-bounded attacks to increase accuracy by adaptivity. Previous work
already notes that RS applies to $L_{\infty}$-bounded attackers (Lécuyer et
al., 2019; Cohen et al., 2019), using the fact that $\forall
X\in\mathbb{R}^{d},\|X\|_{2}\leq\sqrt{d}\|X\|_{\infty}$, and hence that
$X-X^{\prime}\in B_{\infty}(r^{\infty})\Rightarrow X-X^{\prime}\in
B_{2}(\sqrt{d}\cdot r^{\infty})$. Using Corollary 2.2, this yields:

$r^{\infty}_{X}=\frac{\sigma}{2\sqrt{d}}\big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\big{)}.$
(4)

While $L_{\infty}$-specific RS theory exists (Yang et al., 2020), further work
by Blum et al. (2020) has found that Gaussian RS performs advantageously in
practice. However, Blum et al. (2020); Kumar et al. (2020); Wu et al. (2021)
show that the $\sqrt{d}$ dependency cannot be avoided for a large family of
distributions, leading the authors to speculate that RS might be inherently
limited for $L_{\infty}$ certification of predictions on high dimensional
images. To side-step this issue, we use two-steps adaptivity to first select
subsets of the image important to the classification task (thereby reducing
dimension), and then make the prediction based on the selected subset.
Formally:

######  Proposition 2.4 (Adaptive RS for $L_{\infty}$).

Define the following pair of (adaptive) mechanisms:

$\displaystyle\begin{split}\mathcal{M}_{1}:X\rightarrow X+z_{1}\triangleq
m_{1},\hskip
22.76228ptz_{1}\sim\mathcal{N}(0,\sigma_{1}^{2}\mathbb{I}^{d})\end{split}$ (5)

Then, with any function $w:\mathbb{R}^{d}\rightarrow[0,1]^{d}$ (interpreted as
a mask):

$\displaystyle\begin{split}\mathcal{M}_{2}:(X,m_{1})\rightarrow w(m_{1})\odot
X+z_{2}\triangleq m_{2},\hskip
22.76228ptz_{2}\sim\mathcal{N}(0,\frac{\|w(m_{1})\|_{2}^{2}}{d}\sigma_{2}^{2}\mathbb{I}^{d})\end{split}$
(6)

where $\odot$ is the element-wise product; and the final prediction function
$g:m_{1},m_{2}\rightarrow\mathcal{Y}$.

Consider the mechanism $\mathcal{M}$ that samples $m_{1}\sim\mathcal{M}_{1}$,
then $m_{2}\sim\mathcal{M}_{2}$, and finally outputs $g(m_{1},m_{2})$; and the
associated smoothed classifier
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$.
Let $y_{+}\triangleq M_{S}(X)$ be the prediction on input $X$, and let
$\underline{p_{+}},\overline{p_{-}}\in[0,1]$ be such that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then $\forall e\in
B_{\infty}(r_{X}^{\infty}),\ M_{S}(X+e)=y_{+}$, with:

$r_{X}^{\infty}=\frac{1}{2\sqrt{d\big{(}\frac{1}{\sigma_{1}^{2}}+\frac{1}{\sigma_{2}^{2}}\big{)}}}\Big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\Big{)}.$
(7)

###### Proof.

Consider any $X,X^{\prime}$ s.t. $X-X^{\prime}\in B_{\infty}(r^{\infty})$. We
analyze $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ in turn.
$\|X-X^{\prime}\|_{2}\leq\sqrt{d}\|X-X^{\prime}\|_{\infty}$, so
$X-X^{\prime}\in B_{2}(\sqrt{d}r^{\infty})$, and $\mathcal{M}_{1}$ is
$G_{\mu_{1}}$-DP with $\mu_{1}=\frac{r^{\infty}\sqrt{d}}{\sigma_{1}}$.

$\|w(m_{1})\odot X-w(m_{1})\odot
X^{\prime}\|_{2}=\|w(y_{1})\odot\big{(}X-X^{\prime}\big{)}\|_{2}\leq\|w(y_{1})\|_{2}\|X-X^{\prime}\|_{\infty}$
so $X-X^{\prime}\in B_{2}(\|w(y_{1})\|_{2}r^{\infty})$ and $\mathcal{M}_{2}$
is $G_{\mu_{2}}$-DP with
$\mu_{2}=\frac{\|w(y_{1})\|_{2}r^{\infty}}{\|w(y_{1})\|_{2}\sigma_{2}/\sqrt{d}}=\frac{r^{\infty}\sqrt{d}}{\sigma_{2}}$.

Applying Theorem 2.3 with
$\sqrt{\frac{(r^{\infty})^{2}d}{\sigma^{2}_{1}}+\frac{(r^{\infty})^{2}d}{\sigma^{2}_{2}}}=r^{\infty}\sqrt{d\big{(}\frac{1}{\sigma^{2}_{1}}+\frac{1}{\sigma^{2}_{2}}\big{)}}$
concludes the proof. ∎

Important remarks. 1. $w(.)$ is a masking function, adaptively reducing (if
$w_{i}(m_{1})\ll 1$) the value of $X_{i}$ and thereby the attack surface of an
$L_{\infty}$ attacker. This reduces the effective dimension of the input to
$\mathcal{M}_{2}$. 2. Reducing the dimension enables a reduction in the noise
variance in $\mathcal{M}_{2}$, at fixed privacy guarantee $G_{\mu_{2}}$. The
variance reduction is enabled for all dimensions in the input, even those that
are not masked ($w_{i}(m_{1})\approx 1$). As a result, the variance of the
noise in $\mathcal{M}_{2}$ scales as $\|w(m_{1})\|_{2}^{2}\leq d$. The more
masking, the lower the variance. It may help to consider the change of
variables $\sigma\leftarrow\sigma/\sqrt{d}$ in Equation 4, and
$\sigma_{1,2}\leftarrow\sigma_{1,2}/\sqrt{d}$ in Proposition 2.4, to remove
$d$ from $r^{\infty}_{X}$ and scale the noise variance with $d$. For RS
(Equation 4), the noise variance scales as $d$. For ARS, only Equation 5 (the
first step) suffers from variance scaled by $d$, while the second step’s
variance (Equation 6) scales as $||w(m_{1})||_{2}^{2}$, which can be much
smaller than $d$ when a large part of the image is masked. Reduced variance
translates into higher accuracy, as well as $\underline{p_{+}}$ and
$\overline{p_{-}}$ being further apart, for a larger $r^{\infty}_{X}$. 3. The
variance reduction due to masking applies in the translation from the
$B_{\infty}(r^{\infty})$ bound on the attack to the $B_{2}(r)$ sensitivity
used in ARS. This variance reduction would not apply to an $L_{2}$-bounded
adversary. Hence, our two-steps ARS architecture for $L_{\infty}$-bounded
adversaries does not reduce to bounding $L_{\infty}$ with $L_{2}$ as the
traditional RS application does, and our gains come explicitly from variance
reduction enabled by adaptive masking.

##  3 Two-Step ARS for $\boldsymbol{L_{\infty}}$ Certification of Image
Classification

Figure 1 shows our deep learning architecture based on Proposition 2.4. The
first step, $\mathcal{M}_{1}$, adds noise to input $X$ and post-processes the
result into a mask $w(m_{1})$. The second step, $\mathcal{M}_{2}$, takes
masked input $w(m_{1})\odot X$ and adds noise. Finally, the base classifier
$g$ post-processes a weighted average of $m_{1},m_{2}$ to output a label. The
whole model is trained end-to-end on the classification task. In RS, only the
path going through $\mathcal{M}_{2}$ is present. This is equivalent to setting
$\sigma_{2}=\sigma$ and $w(.)=1$, with no $\mathcal{M}_{1}$. In both cases,
the final predictions are averaged over the noise to create the smoothed
classifier. The ARS architecture introduces several new components, which we
next describe.

Budget Splitting: the noise budget $\sigma$ (Figure 1; red) is split to assign
noise levels to the two steps $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$. We
parameterize ARS with the same $\sigma$ as standard RS then split it by the
$f$-DP composition formula from Equation 3. In practice, we assign
$\sigma_{1}\geq\sigma$ to $\mathcal{M}_{1}$, and then
$\sigma_{2}=1/\sqrt{\frac{1}{\sigma^{2}}-\frac{1}{\sigma_{1}^{2}}}$. We set
$\sigma_{1}$ by either fixing it to a constant or learning it end-to-end.

Masking: the mask model $w(\cdot)$ takes the noisy image from
$\mathcal{M}_{1}$ and predicts a weighting (one value in $[0,1]$ per input
pixel) that is multiplied with the input element-wise (denoted $\odot$ in
Proposition 2.4). The model is a U-Net architecture, which makes pixel-wise
predictions, and acts as a post-processing of $\mathcal{M}_{1}$ in the $f$-DP
analysis. Our masking enables test-time adaptivity to reduce the noise
variance for $\mathcal{M}_{2}$, via the mask’s dependence on the input through
$m_{1}$.

Mechanism output averaging: to fully leverage both steps’ information, we take
a weighted average of the outputs $m_{1}$ and $m_{2}$ before passing the
result to the base classifier $g$. For a particular input pixel $i$, denote
$X_{i}$ the value of pixel, $w_{i}\in[0,1]$ its mask weight (we omit the
explicit dependency on $m_{1}$ in $w$ for compactness), and $m_{1,i},m_{2,i}$
the respective values output by $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$. Then,
the final value of pixel $i$ in the averaged input will be
$\hat{X}_{i}\triangleq c_{1,i}m_{1,i}+c_{2,i}m_{2,i}$.

We set $c_{1,i},c_{2,i}$ such that $\hat{X}_{i}$ is the unbiased estimate of
$X_{i}$ with smallest variance. First, we set $c_{1,i}+w_{i}c_{2,i}=1$, such
that $\mathbb{E}[\hat{X}_{i}]=c_{1,i}X_{i}+c_{2,i}w_{i}X_{i}=X_{i}$. Second,
we minimize the variance. Notice that
$\mathbb{V}[\hat{X}_{i}]=c^{2}_{1,i}\sigma_{1}^{2}+c^{2}_{2,i}\|w\|_{2}^{2}\sigma_{2}^{2}=(1-w_{i}c_{2,i})^{2}\sigma_{1}^{2}+c^{2}_{2,i}\|w\|_{2}^{2}\sigma_{2}^{2}$:
this is a convex function in $c_{2,i}$ minimized when its gradient in
$c_{2,i}$ is zero. Plugging back into the constraint to get $c_{1,i}$, we
obtain the following weights:
$c_{1,i}=\frac{\|w\|_{2}^{2}\sigma_{2}^{2}}{\sigma_{1}^{2}w_{i}^{2}+\|w\|_{2}^{2}\sigma_{2}^{2}}$,
and
$c_{2,i}=\frac{\sigma_{1}^{2}w_{i}}{\sigma_{1}^{2}w_{i}^{2}+\|w\|_{2}^{2}\sigma_{2}^{2}}$.

The averaged noisy input $\hat{X}$ is finally fed to the base classifier $g$
for prediction. The smoothed classifier $M_{S}$ averages predictions (over
noise draws) over the entire pipeline. The parameters of $w$ and $g$ (and
$\sigma_{1}$ if not fixed) are learned during training and are fixed at
inference/certification time.

##  4 Experiments

We evaluate on certified $L_{\infty}$ and standard test accuracy. Certified
accuracy at radius $r^{\infty}$ is the percentage of test samples that are
correctly classified and have an $L_{\infty}$ certificate radius
$r^{\infty}_{X}\geq r^{\infty}$. Standard accuracy is obtained for
$r^{\infty}=0$.

Datasets We evaluate on CIFAR-10 (Krizhevsky, 2009) in §4.1, CelebA (Liu et
al., 2015) (specifically the unaligned HD-CelebA-Cropper edition) in §4.2, and
ImageNet (Deng et al., 2009) in §4.3. We measure adaptivity on CIFAR-10 and
CelebA by designing challenging benchmarks requiring adaptivity, and measure
scalability on ImageNet.

Models We choose the standard ResNet (He et al., 2016) models as base
classifiers $g$ with ResNet-110 for CIFAR-10 and ResNet-50 for CelebA and
ImageNet. For ARS, our mask model $w$ is a simplified U-Net (Ronneberger et
al., 2015) (see Appendix C for details). For the noise budget, we find that a
fixed budget split performs reliably, and so in all experiments we split by
$\sigma_{1}=\sigma_{2}=\sqrt{2}\sigma$.

Methods We compare to standard and strong static methods, design a baseline
specifically for our masking approach, and evaluate the only sound input-
dependent method prior to ARS. Cohen et al. is the standard approach to RS
(Cohen et al., 2019). UniCR (Hong et al., 2022) learns the noise distribution
for RS during training but is static during testing (while they propose an
adaptive variant, it is not sound, so we restrict our comparison to the
training variant). We tune hyper-parameters, and perform a grid search for
$\beta$ (the parameter of the noise distribution) to maximize certified
accuracy. We find $\beta=2.25$ (close to a Gaussian, with smaller tails) to
perform best. Static Mask is our baseline that learns a fixed mask during
training that does not adapt during testing. The mask is directly
parameterized as pixel-wise weights that we multiply with the input and
optimize jointly with the base classifier. Relative to ARS in Figure 1, this
removes $\mathcal{M}_{1}$, sets $\sigma_{2}=\sigma$, and makes $w(.)=W$ static
parameters rather than an adaptive prediction. Súkeník et al. (2021)
conditions the variance $\sigma$ for RS on the input and is therefore test-
time adaptive. We use code provided by the authors as is. Comparing ARS to the
static baselines measures the value of test-time adaptivity, and comparing ARS
to the variance adaptivity of Súkeník et al. measures the importance of more
high-dimensional and expressive adaptation.

###  4.1 CIFAR-10 Benchmark: Classification with Distractor Backgrounds

Input dimension is a key challenge in $L_{\infty}$ certification using RS (see
§2.4). We design our 20kBG benchmark to vary this parameter without affecting
the task: we superimpose CIFAR-10 images onto a larger background from the
$20k$ background images dataset Li et al. (2022a), split them into train and
test sets, and resize to $k\times k$ pixels. The CIFAR-10 image is placed at
random along the edges of the background image to maximize spatial variation.
The spurious background increases the dimension of the input ($=k\times
k\times 3$), making $L_{\infty}$ certification with RS more challenging, but
it is uninformative for the task of CIFAR-10 by construction. Our mask model
($\mathcal{M}_{1}$) needs to learn to ignore the background to reduce the
effective dimension of the input.

Table 1 summarizes the standard accuracy ($r=0$) of each approach on the
different settings. In the top section, we vary $k$ (i.e. dimensionality) in
$\\{32,48,64\\}$, where $k=32$ corresponds to original CIFAR-10 images. We
keep $\sigma$ fixed to $0.75$ across these experiments. In next two rows, we
vary $\sigma\in\\{0.12,0.5,1.5\\}$ at fixed $k=48$ and $k=64$, respectively.
LABEL:fig:cifar-10-benchmark-plots shows the certified test accuracy at
different radii $r^{\infty}$ for ARS and all baselines we consider.

Setting/Approach | Cohen et al. | Static Mask | UniCR | Súkeník et al.Δ | ARS Δ
---|---|---|---|---|---
$\sigma=0.75$, $k=32$ | 55.5 (0.8) | 57.8 (0.8) | 50.9 (5.9) | 49.8 (1.0) | 57.3 (0.6)
$\sigma=0.75$, $k=40$ | 52.1 (0.4) | 57 (0.7) | 44.3 (1.2) | 48.1 (1.6) | 58.1 (1.8)
$\sigma=0.75$, $k=48$ | 52.5 (1.2) | 56 (0.8) | 49.0 (2.2) | 43.1 (3.1) | 57.6 (1.5)
$\sigma=0.75$, $k=64$ | 49.4 (2.0) | 51.6 (1.0) | - | - | 56.5 (2.6)
$\sigma=0.12$, $k=48$ | 80.1 (0.8) | 80.9 (0.7) | 76.3 (1.9) | 76.1 (4.1) | 83.6 (0.4)
$\sigma=0.5$, $k=48$ | 64.3 (0.2) | 64.1 (1.6) | 54.0 (2.2) | 55.9 (1.4) | 66.0 (0.8)
$\sigma=1.5$, $k=48$ | 30.8 (0.2) | 34.9 (2.4) | 30.7 (0.9) | 26.5 (0.7) | 34.3 (0.2)
$\sigma=0.12$, $k=64$ | 80.9 (1.0) | 81.3 (1.0) | - | - | 82.3 (1.0)
$\sigma=0.5$, $k=64$ | 61.6 (2.7) | 64 (1.4) | - | - | 65.4 (1.8)
$\sigma=1.5$, $k=64$ | 28.3 (0.2) | 25.9 (3.2) | - | - | 30.6 (1.0)

Table 1: Standard Accuracy ($r=0$) on CIFAR-10 (20kBG). Our 20kBG benchmark
places CIFAR-10 images on larger background images. We report the mean
accuracy and standard deviation over three seeds. ARS achieves higher accuracy
across noise $\sigma$ and input dimension $k$. Δ indicates adaptivity.

Figure 10: ARS Masks on CIFAR-10 (20kBG) select the task-relevant input over
the distractor background.

We make three observations. First, in most cases ARS outperforms all the
baselines (static mask is slightly better with no distractor background, and
with very high $\sigma$ when all methods have low accuracy) reaching a
standard accuracy $4.9$ percentage points higher than the best baseline on our
main setup ($k=64,\sigma=0.75$). Hong et al. (2022) and our own static mask
baselines are the best performing, but all are close to Cohen et al. (2019) as
these approaches provide little adaptivity. The improved standard accuracy of
ARS translates to an improved certified accuracy at all certification levels
(again except without distractor backgrounds, and with very high $\sigma$ when
all methods have low accuracy). This is because ARS makes more accurate and
confident predictions on more test examples, leading to a larger radius.

Second, as we grow the input dimension ($k$), the accuracy of ARS remains
stable whereas that of baselines goes down, resulting in an increasing gap.
For $k=32$ the best baseline (static mask) beats ARS by $0.5$ percentage
points, whereas the gap between the same approaches reaches $1.6$ percentage
points in favor of ARS when $k=48$, and $4.9$ points at $k=64$. This is
because ARS’ mask is able to rule out spurious background information,
reducing the noise in the second step, as shown on Figure 10. Thanks to this
masking, ARS is much less sensitive to increases in dimensionality (see Table
1).

Third, we observe that ARS does much better than the baselines in low to
moderate noise regimes ($\sigma=0.5,0.75$) whereas it performs similarly or
even slightly worse in high noise regimes ($\sigma=1.5$). This is because in
the high noise regime, the first ARS step is too noisy for the mask to be
efficient.

ARS training and inference requires additional computation. To certify a
single input ($k=32$), Cohen et al. (2019) takes ${\sim}12$ seconds while ARS
takes ${\sim}26$ seconds (as measured on an NVIDIA A100 80Gb GPU). This
2$\times$ overhead does however yield improved certified accuracy.

###  4.2 CelebA Benchmark: Classification Without Spatial Alignment

Setting/Approach | Cohen et al. | Static Mask | ARS
---|---|---|---
CelebA, $\sigma=0.12$ | 94.7 (0.5) | 95.7 (1.2) | 96.3(0.9)
CelebA, $\sigma=0.75$ | 88.7 (1.2) | 89.0 (1.4) | 92.3(0.9)
CelebA, $\sigma=1.5$ | 77.7 (2.5) | 74.3 (1.7) | 81.0(2.2)
Table 2: Standard test accuracy ($r=0$) on CelebA (unaligned and cropped). ARS
is equal or better. Adaptivity handles the higher spatial dimensions
($160\times 160$) and variation of these inputs.

To evaluate ARS on a more realistic task with natural spatial variation, we
use the CelebA face dataset in its unaligned versio We focus on the “mouth
slightly open” (label 21) binary classification task because mouth location
and shape vary. Furthermore we hypothesize that the necessary input for this
task is well-localized, which affords an opportunity for the masking model to
reduce the effective input dimension. The dataset consists of images with
varied resolution, and meta-data about the position of different features,
including the mouth. To make a more challenging benchmark we randomly crop all
images to $160\times 160$ pixels for more spatial variation. The only crop
constraint is that the mouth is $\geq 10$ pixels from the edge to ensure
sufficient input to solve the task. Figure 13 shows example images from the
test set, their respective masks from ARS, and the baseline static mask.

Figure 13: ARS masks are localized and input specific.

LABEL:fig:celeba-results shows the certified accuracy for ARS, Cohen et al.
(2019), and static mask, for three levels of the noise $\sigma$. First, both
baselines perform very similarly. We can see from Figure 13 that the static
mask is approximately identity (notice the $\geq 0.99$ scale), with only very
slight dimming on the edges. This is because the mouth is not centred in our
benchmark, so there is no one-size-fits-all mask. Second, ARS is able to
predict a sparse mask that focuses on areas likely to have the mouth. The mask
adapts to each input at test time, which is what enables the sparsity without
performance degradation. Third, this sparse mask leads to a large noise
reduction, enabling ARS to drastically improve both standard and certified
accuracy. For instance, with $\sigma=0.75$, ARS improves the accuracy from
$88.7\%$ to $92.3\%$ (a $3.6$ points improvement), while the certified
accuracy at $r^{\infty}=0.005$ jumps from $40.7\%$ to $71.3\%$ (a more than
$30$ points improvement!). At lower noise ($\sigma=0.12$) there is no increase
in accuracy, but certified accuracy increases from $81.7\%$ to $90.0\%$ at
$r^{\infty}=0.001$). At larger noise ($\sigma=1.5$), the static mask struggles
to perform as well, but ARS sees significant increases ($10$ percentage points
in accuracy, and $20.0\%$ to $31.3\%$ in certified accuracy at
$r^{\infty}=0.01$).

###  4.3 ImageNet Benchmark: Classification on the Standard Large-Scale
Dataset

To evaluate the scalability of ARS we experiment on ImageNet with $\sigma=0.5$
(without any modification). We compare with Cohen et al. (2019), which we
reproduce for this large-scale setting. We also compare with static mask, and
random mask (our mask model randomly initialized without training) to evaluate
the effect of blind maksing. We evaluate two versions of ARS: our regular
model, trained end-to-end; and a version in which we fix the base classifier
to that of Cohen et al. (2019) and only train our mask model for $10$ epochs
(with the Adam optimizer and constant learning rate). Figure 14 shows the
certified accuracy for all models. We make three observations. First, by only
training a mask model ARS is able to improve results by $1$ percentage point
(from $57\%$ to $58\%$). Certified accuracy remains close to that of Cohen et
al. (2019) at all radius, but ARS can certify slighlty larger radius: At
$r^{\infty}=0.005$, the certified accuracy of Cohen et al. (2019), static
mask, and random mask are $0$, while that of ARS is still $15\%$ (which drops
to $0$ shortly after).

Figure 14: ImageNet $\sigma=0.5$.

Second, ARS trained end-to-end reaches an accuracy of $60\%$, $3$ points
higher than that of Cohen et al. (2019). The certified accuracy is higher by
similar margins up to $r^{\infty}=0.003$, where it becomes a bit lower than
that of Cohen et al. (2019), before again certifying a slightly better maximum
radius, with $13\%$ accuracy at $r^{\infty}=0.005$. Third, a randomly
initialized mask model yields an accuracy of $49\%$ showing that our ARS model
benefits are not explained by random masking, which is consistent with the
mask learning to reduce the input dimension while preserving input semantics
important to the task. Overall, these results show that ARS is general in that
its adaptivity does not over-specialize to our adaptation benchmarks, and that
it can scale to large datasets and complex classification tasks.

##  5 Discussion

Limitations: The multi-step adaptivity of ARS improves certification at the
cost of increased model size and computation for RS. This impacts both
training and testing computation, and is especially costly in the context of
RS due to the Monte-Carlo estimation of the model’s expected predictions (over
several forward passes at inference time). While we empirically show
improvement by ARS, it would be interesting and important to investigate how
it combines with other RS improvements such as adversarial training (Salman et
al., 2019), consistency regularization (Jeong and Shin, 2020), higher order
certification (Mohapatra et al., 2020), double sampling (Li et al., 2022b),
and denoising by diffusion (Carlini et al., 2022).

Implications: revisiting heuristic adaptive defences (as surveyed in Croce et
al. (2022)) through the lens of ARS could help improve the empirical
performance of provable defences. ARS may require extensions, but could
eventually enable the formal analysis of input purification (e.g., Song and
Kim (2018); Nie et al. (2022); Yoon et al. (2021)), or leverage DP-SGD (Abadi
et al., 2016) to analyze defences that update by test-time optimization
(Alfarra et al., 2022b; Hwang et al., 2022; Mao et al., 2021). Going further,
one could leverage the vast DP literature to extend ARS, enabling fully-
adaptive variance defences inspired by Alfarra et al. (2022a) by leveraging
privacy odometers (Rogers et al., 2016; Lécuyer, 2021; Whitehouse et al.,
2023).

To conclude: we introduced Adaptive Randomized Smoothing (ARS) to reconnect RS
with DP theory, to propose a new two-step defence for deep image
classification, and to rigorously analyze such adaptive defences that
condition on inputs at test time. This framework opens promising avenues for
designing ML models that are adaptively and soundly robust with provable
guarantees about their updates on natural and adversarial inputs.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , 2016.
  * Alfarra et al. (2022a) Motasem Alfarra, Adel Bibi, Philip HS Torr, and Bernard Ghanem.  Data dependent randomized smoothing.  In _Uncertainty in Artificial Intelligence_ , pages 64–74. PMLR, 2022a.
  * Alfarra et al. (2022b) Motasem Alfarra, Juan C. Perez, Ali Thabet, Adel Bibi, Philip H.S. Torr, and Bernard Ghanem.  Combating adversaries with anti-adversaries.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2022b.
  * Athalye et al. (2018) Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In _International conference on machine learning_ , 2018.
  * Blum et al. (2020) Avrim Blum, Travis Dick, Naren Manoj, and Hongyang Zhang.  Random smoothing might be unable to certify $\ell_{\infty}$ robustness for high-dimensional images.  _The Journal of Machine Learning Research_ , 2020.
  * Cao et al. (2021) Yulong Cao, Ningfei Wang, Chaowei Xiao, Dawei Yang, Jin Fang, Ruigang Yang, Qi Alfred Chen, Mingyan Liu, and Bo Li.  Invisible for both camera and lidar: Security of multi-sensor fusion based perception in autonomous driving under physical-world attacks.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , 2021.
  * Carlini et al. (2022) Nicholas Carlini, Florian Tramer, Krishnamurthy Dj Dvijotham, Leslie Rice, Mingjie Sun, and J Zico Kolter.  (certified!!) adversarial robustness for free!  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Chakraborty et al. (2018) Anirban Chakraborty, Manaar Alam, Vishal Dey, Anupam Chattopadhyay, and Debdeep Mukhopadhyay.  Adversarial attacks and defences: A survey.  _arXiv preprint arXiv:1810.00069_ , 2018.
  * Cohen et al. (2019) Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In _international conference on machine learning_ , pages 1310–1320. PMLR, 2019.
  * Costa et al. (2023) Joana C Costa, Tiago Roxo, Hugo Proença, and Pedro RM Inácio.  How deep learning sees the world: A survey on adversarial attacks & defenses.  _arXiv preprint arXiv:2305.10862_ , 2023.
  * Croce et al. (2022) Francesco Croce, Sven Gowal, Thomas Brunner, Evan Shelhamer, Matthias Hein, and Taylan Cemgil.  Evaluating the adversarial robustness of adaptive test-time defenses.  In _International Conference on Machine Learning_ , pages 4421–4435. PMLR, 2022.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 2009.
  * Dong et al. (2019) Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  _arXiv preprint arXiv:1905.02383_ , 2019.
  * Dong et al. (2022) Jinshuo Dong, Aaron Roth, and Weijie J Su.  Gaussian differential privacy.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 2022.
  * Dvijotham et al. (2020) Krishnamurthy (Dj) Dvijotham, 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_ , 2020.  URL https://openreview.net/forum?id=SJlKrkSFPH.
  * Gopi et al. (2021) Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz.  Numerical composition of differential privacy.  _Advances in Neural Information Processing Systems_ , 2021.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016.
  * Honaker (2015) James Honaker.  Efficient use of differentially private binary trees.  _Theory and Practice of Differential Privacy (TPDP 2015), London, UK_ , 2015.
  * Hong et al. (2022) Hanbin Hong, Binghui Wang, and Yuan Hong.  Unicr: Universally approximated certified robustness via randomized smoothing.  In _European Conference on Computer Vision_. Springer, 2022.
  * Hwang et al. (2022) Duhun Hwang, Eunjung Lee, and Wonjong Rhee.  Aid-purifier: A light auxiliary network for boosting adversarial defense.  In _2022 26th International Conference on Pattern Recognition (ICPR)_ , 2022.
  * Jeong and Shin (2020) Jongheon Jeong and Jinwoo Shin.  Consistency regularization for certified robustness of smoothed classifiers.  _Advances in Neural Information Processing Systems_ , 2020.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning multiple layers of features from tiny images, 2009.  URL https://api.semanticscholar.org/CorpusID:18268744.
  * Kumar et al. (2020) Aounon Kumar, Alexander Levine, Tom Goldstein, and Soheil Feizi.  Curse of dimensionality on randomized smoothing for certifiable robustness.  In _International Conference on Machine Learning_. PMLR, 2020.
  * Lécuyer (2021) Mathias Lécuyer.  Practical privacy filters and odometers with rényi differential privacy and applications to differentially private deep learning.  _arXiv preprint arXiv:2103.01379_ , 2021.
  * Lécuyer et al. (2019) Mathias Lécuyer, 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)_ , pages 656–672. IEEE, 2019.
  * Li et al. (2022a) Jizhizi Li, Jing Zhang, Stephen J Maybank, and Dacheng Tao.  Bridging composite and real: towards end-to-end deep image matting.  _International Journal of Computer Vision_ , 2022a.
  * Li et al. (2022b) Linyi Li, Jiawei Zhang, Tao Xie, and Bo Li.  Double sampling randomized smoothing.  In _International Conference on Machine Learning_. PMLR, 2022b.
  * Li et al. (2023) Linyi Li, Tao Xie, and Bo Li.  Sok: Certified robustness for deep neural networks.  In _2023 IEEE symposium on security and privacy (SP)_ , 2023.
  * Liu et al. (2015) Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision (ICCV)_ , December 2015.
  * Mao et al. (2021) C. Mao, M. Chiquier, H. Wang, J. Yang, and C. Vondrick.  Adversarial attacks are reversible with natural supervision.  In _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * Mohapatra et al. (2020) Jeet Mohapatra, 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_ , 2020.
  * Nie et al. (2022) Weili Nie, Brandon Guo, Yujia Huang, Chaowei Xiao, Arash Vahdat, and Animashree Anandkumar.  Diffusion models for adversarial purification.  In _International Conference on Machine Learning_ , 2022.
  * Pumsirirat and Liu (2018) Apapan Pumsirirat and Yan Liu.  Credit card fraud detection using deep learning based on auto-encoder and restricted boltzmann machine.  _International Journal of advanced computer science and applications_ , 2018.
  * Rogers et al. (2016) Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan.  Privacy odometers and filters: Pay-as-you-go composition.  _Advances in Neural Information Processing Systems_ , 2016.
  * Ronneberger et al. (2015) Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _Medical image computing and computer-assisted intervention–MICCAI 2015: 18th international conference, Munich, Germany, October 5-9, 2015, proceedings, part III 18_. Springer, 2015.
  * Salman et al. (2019) Hadi Salman, 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_ , 2019.
  * Song and Kim (2018) Yang Song and Taesup Kim.  Sebastian nowozin stefano ermon nate kushman. pixeldefend: Leveraging generative models to understand and defend against adversarial examples.  In _International Conference on Learning Representations_ , 2018.
  * Súkeník et al. (2021) Peter Súkeník, Aleksei Kuvshinov, and Stephan Günnemann.  Intriguing properties of input-dependent randomized smoothing.  _arXiv preprint arXiv:2110.05365_ , 2021.
  * Szegedy et al. (2014) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  In _International Conference on Learning Representations_ , 2014.  URL http://arxiv.org/abs/1312.6199.
  * Tramer et al. (2020) Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry.  On adaptive attacks to adversarial example defenses.  _Advances in neural information processing systems_ , 33:1633–1645, 2020.
  * Whitehouse et al. (2023) Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, and Steven Wu.  Fully-adaptive composition in differential privacy.  In _International Conference on Machine Learning_ , 2023.
  * Wu et al. (2021) Yihan Wu, 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 _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , Proceedings of Machine Learning Research. PMLR, 2021.  URL https://proceedings.mlr.press/v130/wu21d.html.
  * Yang et al. (2020) Greg Yang, 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_. PMLR, 2020.
  * Yoon et al. (2021) Jongmin Yoon, Sung Ju Hwang, and Juho Lee.  Adversarial purification with score-based generative models.  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021.

##  Appendix A $\boldsymbol{f}$-DP Background

For this background we use the DP mechanism terminology. A mechanism
$\mathcal{M}(.)$ is a randomized computation taking an input and returning one
sample from the distribution of outputs for this input: $m\sim\mathcal{M}(x)$
with input $x$ and output $m$. In ARS, each model step corresponds to an
$f$-DP mechanism.

Definitions. Dong et al. [2019, 2022] formalize privacy as a bound on the
power of hypothesis tests. Consider any two neighbouring inputs: in the most
common DP applications, $X,X^{\prime}$ are two databases differing in one
element; in the case of ARS against an $L_{p}$ adversary,
$X,X^{\prime}\in\mathbb{R}^{d}$ are any two inputs such that $X-X^{\prime}\in
B_{p}(r)$. Intuitively a randomized mechanism $\mathcal{M}$ is private if, for
any such neighbouring inputs, the distributions $\mathcal{M}(X)$ and
$\mathcal{M}(X^{\prime})$ are hard to distinguish. That is, by looking at a
sample output from mechanism $\mathcal{M}$, it is hard to guess whether
$\mathcal{M}$ ran on $X$ or on $X^{\prime}$.

In $f$-DP [Dong et al., 2019, 2022] “hard to distinguish” is defined by a
hypothesis testing problem:

$\mathcal{H}_{0}:\textrm{the input was}\ X\hskip 28.45274pt\textrm{vs.}\hskip
28.45274pt\mathcal{H}_{1}:\textrm{the input was}\ X^{\prime}.$

The output $m\sim\mathcal{M}$ serves as input to a rejection rule
$\phi(.)\in[0,1]$ (note: to preserve typical notations, lower-case $\phi$ is
the rejection rule, and upper-case $\Phi$ is the standard normal CDF). The
rejection rule rejects $\mathcal{H}_{0}$ with probability $\phi(m)$, so
$\phi(m)=0$ predicts that $X$ was the input, and $\phi(m)=1$ that $X^{\prime}$
was.

Given a rejection rule $\phi$, we define its Type I error $\alpha_{\phi}$ and
type II error (or one minus the power of the rule) $\beta_{\phi}$ as:

$\alpha_{\phi}\triangleq\mathbb{E}_{m\sim\mathcal{M}(X)}[\phi(m)]\hskip
28.45274pt\beta_{\phi}\triangleq
1-\mathbb{E}_{m\sim\mathcal{M}(X^{\prime})}[\phi(m)]$

Intuitively, $\alpha_{\phi}$ is the expected amount of rejection of
$\mathcal{H}_{0}$ when the hypothesis is correct ($X$ was in input, but we
think $X^{\prime}$ was), also called the level of the rejection rule. On the
flip side, $\beta_{\phi}$ is the expected amount of non-rejection under
$\mathcal{H}_{1}$ ($X^{\prime}$ was in input, but we think $X$ was).
$1-\beta_{\phi}$ is called the power of the rejection rule.

For any two distributions $\mathcal{M}(X)$ and $\mathcal{M}(X^{\prime})$, we
define the trade-off function
$T\big{(}\mathcal{M}(X),\mathcal{M}(X^{\prime})\big{)}:[0,1]\rightarrow[0,1]$
that quantifies the minimum amount of type II error achievable at each value
of type I error by any (measurable) rule; or equivalently the maximum power of
any rule at each level:

$\forall\alpha\in[0,1],\
T\big{(}\mathcal{M}(X),\mathcal{M}(X^{\prime})\big{)}(\alpha)=\inf_{\phi}\\{\beta_{\phi}:\alpha_{\phi}\leq\alpha\\}$

Now we define $f$-DP: for any trade-off function $f$, a mechanism
$\mathcal{M}$ is $f$-DP if, for any neighbouring inputs $X,X^{\prime}$,

$T\big{(}\mathcal{M}(X),\mathcal{M}(X^{\prime})\big{)}\geq f$

These definitions are the main technical tools we need to prove Proposition
2.1. Corollary 2.2 only adds the formula for $f$ for the Gaussian mechanism,
given in Section 2.1.

Composition. All other results rely on the above plus the adaptive composition
of $f$-DP mechanisms. Such composition is key to all DP theory and algorithm
design. Consider a sequence of $N$ mechanisms $\mathcal{M}_{i}$, such that
each mechanism is $f_{i}$-DP with regards to $X,X^{\prime}$, and depends on
the neighbouring input as well as the output of all previous mechanisms. More
formally, under $\mathcal{H}_{0}$ we have
$m_{i}\sim\mathcal{M}_{i}(X,m_{<i})$, and under $\mathcal{H}_{1}$ we have
$m_{i}\sim\mathcal{M}_{i}(X,m_{<i})$, where
$m_{<i}\triangleq(m_{1},\ldots,m_{i-1})$. Concretely, each $\mathcal{M}_{i}$
is $f_{i}$-DP with regards to $X,X^{\prime}$ for $f_{i}$ known in advance, but
the actual computation made by $\mathcal{M}_{i}$ can depend on $m_{<i}$ (as
long as it is $f_{i}$-DP). We leverage this adaptivity to lower the noise
variance in our method’s second step while keeping $f_{2}$ fixed (see §3).

We need two more results to define the composition of a sequence of
mechanisms. First, Proposition 2.2 in Dong et al. [2019, 2022] shows that for
any trade-off function $f$, there exist two distributions $P_{f},Q_{f}$ such
that $T(P_{f},Q_{f})=f$. Call any such pair of distributions a representative
pair of $f$. Second, we define the composition operator $\otimes$ by $f\otimes
g=T(P_{f}\times P_{g},Q_{f}\times Q_{g})$. That is, the composition operator
between two trade-off functions is the trade-off function between the product
distributions on their representative pair. Then Theorem 3.2 in Dong et al.
[2019, 2022] shows that:

$\mathcal{M}:X\rightarrow(\mathcal{M}_{1}(X),\ldots,\mathcal{M}_{N}(X,y_{<i}))\
\textrm{is}\ f_{1}\otimes\ldots\otimes f_{N}\textrm{-DP}.$

Concretely, the mechanism that returns the sequence of results for all compute
adaptive $\mathcal{M}_{N}$ is $f_{1}\otimes\ldots\otimes f_{N}$-DP. The
previous definitions, as well as this composition result, is what we use to
prove Theorem 2.3 and Proposition 2.4.

##  Appendix B Proofs

###### Proposition 2.1 ($\boldsymbol{f}$-DP Robustness).

Let $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Y}$ be $f$-DP for $B_{p}(r)$
neighbourhoods, and let
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$ be
the associated smooth classifier. Let $y_{+}\triangleq M_{S}(X)$ be the
prediction on input $X$, and let $\underline{p_{+}},\overline{p_{-}}\in[0,1]$
be such that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then:

$f(1-\underline{p_{+}})\geq 1-f(\overline{p_{-}})\Rightarrow\forall e\in
B_{p}(r),\ M_{S}(X+e)=y_{+}$

###### Proof.

Let us first consider any runner-up class $y_{-}$. Calling $M$ the random
variable for $\mathcal{M}$’s prediction, consider the rejection rule
$\phi=\mathds{1}\\{M=y_{-}\\}$, where $\mathds{1}$ is the indicator function.
Denoting $\alpha\triangleq\mathbb{E}_{\mathcal{M}(X)}(\phi)$, and using the
fact that $\mathcal{M}$ is $f$-DP for $B_{p}(r)$ neighbourhoods, we have that
$\forall e\in B_{p}(r)$:

$\displaystyle\begin{split}\mathbb{P}(\mathcal{M}(X+e)=y_{-})&=\mathbb{E}_{\mathcal{M}(X+e)}(\phi)\\\
&\leq 1-f(\alpha)\leq 1-f(\overline{p_{-}}),\end{split}$ (8)

where the last inequality is because
$\alpha=\mathbb{E}_{\mathcal{M}(X)}(\phi)=\mathbb{P}(\mathcal{M}(X)=y_{-})\leq\overline{p_{-}}$,
and $f$ is non-increasing so $f(\alpha)\geq f(\overline{p_{-}})$ and hence
$1-f(\alpha)\leq 1-f(\overline{p_{-}})$.

Let us now consider the predicted class $y_{+}$. Keeping the same notations,
and defining the rule $\phi^{\prime}=\mathds{1}\\{M\neq
y_{+}\\}=1-\mathds{1}\\{M=y_{+}\\}$. Then
$\alpha^{\prime}=\mathbb{E}_{\mathcal{M}(X)}(\phi^{\prime})=1-\mathbb{P}(\mathcal{M}(X)=y_{+})\leq
1-\underline{p_{+}}$, and $\mathbb{E}_{\mathcal{M}(X+e)}(\phi^{\prime})\leq
1-f(\alpha^{\prime})\leq 1-f(1-\underline{p_{+}})$, yielding:

$\begin{split}\mathbb{P}(\mathcal{M}(X+e)=y_{+})&=1-\mathbb{E}_{\mathcal{M}(X+e)}(\phi^{\prime})\\\
&\geq f(1-\underline{p_{+}}).\end{split}$ (9)

Putting Equations 8 and 9 together, we have that
$\mathbb{P}(\mathcal{M}(X+e)=y_{+})\geq f(1-\underline{p_{+}})\geq
1-f(\overline{p_{-}})\geq\mathbb{P}(\mathcal{M}(X+e)=y_{-})$ and thus
$m_{S}(X+e)=y_{+}$. ∎

Note that we do not have to chose a rule $\phi\in\\{0,1\\}$, but could instead
return any number in $[0,1]$, such as the logits of the base classification
model, yielding the following definition for the smoothed classifier
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{E}(\mathcal{M}(X)_{y})$.

###### Proposition 2.2 (RS from $\boldsymbol{f}$-DP).

Let $\mathcal{M}:X\rightarrow g(X+z),\
z\sim\mathcal{N}(0,\sigma^{2}\mathbb{I}^{d})$, and
$M_{S}:X\rightarrow\arg\max_{y\in\mathcal{Y}}\mathbb{P}(\mathcal{M}(X)=y)$ be
the associated smooth model. Let $y_{+}\triangleq M_{S}(X)$ be the prediction
on input $X$, and let $\underline{p_{+}},\overline{p_{-}}\in[0,1]$ be such
that
$\mathbb{P}(\mathcal{M}(X)=y_{+})\geq\underline{p_{+}}\geq\overline{p_{-}}\geq\max_{y_{-}\neq
y_{+}}\mathbb{P}(\mathcal{M}(X)=y_{-})$. Then $\forall e\in B_{2}(r_{x}),\
M_{S}(X+e)=y_{+}$, with:

$r_{X}=\frac{\sigma}{2}\big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\big{)}.$

###### Proof.

$X:\rightarrow X+z,\ z\sim\mathcal{N}(0,\sigma^{2})$ is a Gaussian mechanism.
By Equation 2, for the $B_{r}(r)$ neighbouring definition, it is
$G_{\frac{r}{\sigma}}$-DP. By post-processing $\mathcal{M}$ is also
$G_{\frac{r}{\sigma}}$-DP.

Applying Proposition 2.1, we have that
$G_{\frac{r}{\sigma}}(1-\underline{p_{+}})\geq
1-G_{\frac{r}{\sigma}}(\overline{p_{-}})\Rightarrow\forall e\in B_{2}(r),\
m_{S}(X+e)=y_{+}$. Let us find $r_{X}=\sup\
\\{r:G_{\frac{r}{\sigma}}(1-\underline{p_{+}})\geq
1-G_{\frac{r}{\sigma}}(\overline{p_{-}})\\}$. Since $G_{\frac{r}{\sigma}}(.)$
as a function of $r$ is monotonously decreasing this will happen at
$G_{\frac{r_{X}}{\sigma}}(1-\underline{p_{+}})=1-G_{\frac{r_{X}}{\sigma}}(\overline{p_{-}})$,
that is:

$\displaystyle\Phi\Big{(}\Phi^{-1}(\underline{p_{+}})-\frac{r_{X}}{\sigma}\Big{)}=1-\Phi\Big{(}\Phi^{-1}(1-\overline{p_{-}})-\frac{r_{X}}{\sigma}\Big{)}$
$\displaystyle\Rightarrow\
\Phi^{-1}(\underline{p_{+}})-\frac{r_{X}}{\sigma}=-\Phi^{-1}(1-\overline{p_{-}})+\frac{r_{X}}{\sigma}$
$\displaystyle\Rightarrow\
\Phi^{-1}(\underline{p_{+}})-\frac{r_{X}}{\sigma}=\Phi^{-1}(\overline{p_{-}})+\frac{r_{X}}{\sigma}$
$\displaystyle\Rightarrow\
r_{X}=\frac{\sigma}{2}\big{(}\Phi^{-1}(\underline{p_{+}})-\Phi^{-1}(\overline{p_{-}})\big{)},$

where the first implication holds because by symmetry of the standard normal
$1-\Phi(x)=\Phi(-x)$, and because $\Phi$ is strictly monotonous ; the second
because similarly, $\Phi^{-1}(1-p)=-\Phi^{-1}(p)$. ∎

##  Appendix C Mask Architecture

Figure 15 shows the architecture of our Mask model $w$ ($\mathcal{M}_{1}$). We
adapt a UNet architecture to preserve dimensions, and use a Sigmoid layer at
the end of the model to output values between 0 and 1 for mask weights. We set
up our UNet hyperparameters as : in_channels=3, out_channels=1 (to out put a
mask), base_channel=32, channel_mult={1,2,4,8}.

Figure 15: UNet structure

##  Appendix D Experiment Details

| CIFAR-10 | CelebA | ImageNet
---|---|---|---
GPU | single 24G RTX4090 | single 24G RTX4090 | single 80G A100
epoch | 100 | 24 | 100(10+90)
train batch size | 256 | 64 | 250
test batch size | 20 | 100 | 25
| base channel | 32 | 64 | 16
| optimizer | AdamW | SGD | AdamW
Mask | lr | 1e-3 | 5e-2 | 1e-3
Model | weight decay | 1e-4 | - | -
(UNet) | momentum | 0.9 | - | -
| step size | 30 | 100 | 40
| gamma | 0.5 | 1.0 | 0.5
| model | ResNet110 | ResNet50 | ResNet50
| optimizer | AdamW | SGD | SGD
Base | lr | 1e-2 | 5e-2 | 1e-3
Classifier | weight decay | 1e-4 | - | 1e-4
| momentum | 0.9 | - | 0.9
| step size | 30 | 3 | 30
| gamma | 0.1 | 0.8 | 0.1
Table 3: Hyperparameters for training ARS.

Table 3 provides the details of our ARS models’ hyper-parameters.

We also tune hyper-parameters for the Hong et al. [2022] baseline on our 20kBG
benchmark, focusing on $\sigma=0.75$, at $k=48$. We perform grid search on
$\beta$ (the parameter of the generalized normal distribution for the noise),
and find that $\beta=2.25$ (close to a Gaussian, but with a wider more and
shorted tails) performs best. We also tune other hyper-parameters. In all
settings we use training batch size 400, 90 epochs, and Adam optimizer. For
the $\sigma=0.75,0.5$ settings be use learning rate 0.001. For the
$\sigma=0.12,1.5$ settings we use learning rate 0.0005 with a step learning
rate scheduler (30 step size and $\gamma=0.2$).

##  Appendix E Additional Results on CelebA

Figure 16: The localized ARS masks produce un-noised mouth regions after
averaging.

Figure 16 shows how adaptive masking reduces the noise around areas that are
important to classification. The images follow our architecture visualized
Figure 1. The mask model is provided the first query noised images as input.
The learned masks, presented in the bottom left, are sparse and highly
concentrated around the area of interest—the mouth area. The second query
noised images (after weighted average) use the mask to clearly reduce the
noise around the mouth. This large noise reduction enables ARS to outperform
static masking and Cohen et al. [2019], as shown on LABEL:fig:celeba-results.