Provable Robustness against Wasserstein Distribution Shifts via Input Randomization
Authors: Aounon Kumar
Alexander Levine
Tom Goldstein
Soheil Feizi
Venue: ICLR 2023 poster (2023)
Keywords: Distributional Robustness
Wasserstein Distance
Certified Robustness

Abstract: Certified robustness in machine learning has primarily focused on adversarial perturbations with a fixed attack budget for each sample in the input distribution. In this work, we present provable robustness guarantees on the accuracy of a model under bounded Wasserstein shifts of the data distribution. We show that a simple procedure that randomizes the input of the model within a transformation space is provably robust to distributional shifts under that transformation. Our framework allows the datum-specific perturbation size to vary across different points in the input distribution and is general enough to include fixed-sized perturbations as well. Our certificates produce guaranteed lower bounds on the performance of the model for any shift (natural or adversarial) of the input distribution within a Wasserstein ball around the original distribution. We apply our technique to certify robustness against natural (non-adversarial) transformations of images such as color shifts, hue shifts, and changes in brightness and saturation. We obtain strong performance guarantees for the robust model under clearly visible shifts in the input images. Our experiments establish the non-vacuousness of our certificates by showing that the certified lower bound on a robust model's accuracy is higher than the empirical accuracy of an undefended model under a distribution shift. Moreover, our results also imply guaranteed lower bounds (hardness result) on the performance of models trained on so-called "unlearnable" datasets that have been poisoned to interfere with model training. We show that the performance of a robust model is guaranteed to remain above a certain threshold on the test distribution even when the base model is trained on the poisoned dataset.

Published as a conference paper at ICLR 2023
PROVABLE ROBUSTNESS AGAINST WASSERSTEIN DIS- TRIBUTION SHIFTS VIA INPUT RANDOMIZATION
Aounon Kumar
Alexander Levine
Tom Goldstein University of Maryland
University of Maryland College Park, MD aounon@ wuwioon@umddeeee edu
University of Maryland
College Park, MD a alevinee ne CS umd. edu
College Park, MD
t tomg@cs umd. edu
Soheil Feizi University of Maryland College Park, MD sfeizi@cs umd. edu
ABSTRACT
Certified robustness in machine learning has primarily focused adversarial per- turbations with a fixed attack budget for each sample in the input distribution. this work, present provable robustness guarantees the accuracy of model under bounded Wasserstein shifts the data distribution. We show that a simple procedure that randomizes the input of the model within a transformation space is provably robust to distributional shifts under that transformation. Our frame- work allows the datum-specific perturbation size vary across different points the input distribution and is general enough to include fixed-sized perturbations as well. Our certificates produce guaranteed lower bounds on the performance of the model for any shift (natural or adversarial) of the input distribution within a Wasserstein ball around the original distribution. We apply our technique cer- tify robustness against natural (nesaalveraaria) transformations of images such color shifts, hue shifts, and changes brightness and saturation. We obtain strong performance guarantees for the robust model under clearly visible shifts in the in- put images. Our experiments establish the non- vauuoucuusss our certificates by showing that the certified lower bound robust model's s accuracy is higher than the empirical accuracy of an undefended model under a distribution shift. We also show provable distributional robustness against adversarial attacks. Moreover, our results also imply guaranteed lower bounds (hardness result) on the performance of models trained on so-called "unlearnable" datasets that have been poisoned interfere with model training. We show that the performance of robust model is guaranteed remain above certain threshold on the test distribution even when the base model is trained on the poisoned dataset.
INTRODUCTION
Machine learning models often suffer significant performance loss under minor shifts in the data distribution that do not affect human's ability perform the same tas.- input noise (Dodge
& Karam 2016) Geirhos et al.] 2018), image scaling, shifting and translation (Azulay & Weiss 2019). spatial (Engstrom al. (0119) and geometric transformations (Fawzi & Frossard] 2015 AI-
corn et al. 2019). blurring Vasiljevic et al. Zhou et al.) (017)) acoustic corruptions (Pearce &
Hirsch| 2000) and adversarial perturbations (Szegedy et al. 2014 Carlini & Wagner 2017 Good fellow et al.) 2015) Madry et al.) 2018 Biggio et al. 2013). Overcoming such robustness chal-
lenges a major hurdle for deploying these models in safety-critical applications where reliability is paramount. Several techniques have been developed to improve the empirical robustness of model to data shifts, e.g., diversifying datasets (Taori et al. 2020). training with natural corruptions (Hendrycks & Dietterich 2019), data augmentations Yang et al. 2019), contrastive learning (Kim ct al. Rad0ooRddfordd Radford et al. 2021 Ge et al. I) and adversarial training (Goodfellow et al.) 2015
Madry al. 2018: Tramer & Boneh 2019 Shafahi al. 2019 Maini et al. 2020).
Empirical

---

Published as a conference paper at ICLR 2023
robustness techniques designed to protect model against particular type of shift or adversary (e.g.. by introducing similar shifts during training) and may not be effective against new ones. For instance, adversarial defenses have been shown to break down under newer attacks (Carlini & Wag-
ner 2017 Athalye et al. 2018 Uesato et al., 2018 Laidlaw & Feizi 2019
Laidlaw et al. 2021)
Certifiable robustness methods, on the other hand, seek to produce provable guarantees on the bustmess of a model which hold for any perturbation within a certain neighborhood of the input instance regardless of the strategy used to generate this perturbation. A robustness certificate pro- duces a verifiable lower bound on the size of the perturbation required to fool a model. Apart from being a guarantee on the robust performance, these certificates may also serve as metric com- pare the robustness of different models that is independent of the mechanism producing the input perturbations. However, the study of provable robustness has mostly focused on perturbations with a fixed size budget (e.g., an f--ball of same size) for all input points (Cohen et al. 2019 Lécuyer
al. 2019 Li et al.) 2019] [Salman et al.) 2019 Gowal et al. 2018 Huang et al., 2019 Wong & Kolter 2018 Raghunathan et al. 2018 Singla & Feizi 2019 2020 Levine & Feizi 202 I 2020a b).
Among provable robustness methods, randomized smoothing based procedures have been able to successfully scale up high- tigh-dimensional problems (Cohen et al. 2019 Lécuyer et al. 2019 Li
jet al.] 2019; Salman et al.] 2019) and adapted effectively to other domains such as reinforcement learning (Kumar et al. 2021 Wu al. (221) and models with structured outputs (Kumar & Gold- stein 2021) as in segmentation tasks and generative modeling. However, these techniques cannot be extended to certify under distribution shifts as the perturbation size for each instance in the input distribution need not have a fixed bound. For example, stochastic changes in the input images of vision model caused by lighting and weather conditions may vary across time and location. Even adversarial attacks may choose to adjust the perturbation size depending on the input instance.
A standard way of describing a distribution shift is to constrain the Wasserstein distance between the original distribution D and the shifted distribution 2 to be bounded by a certain amount e, i... (T, D) S e, for an appropriate distance function d. The Wasserstein distance is the minimum expectation of the distance function d over all possible joint distributions with marginals D and D. Wasserstein distance is standard similarity measure for probability distributions and has been extensively used to study distribution shifts (Courty et al.) 2017 Damodaran et al., 2018 Lee & Raginsky 2018 Wu et al., 2019). Certifiable robustness against Wasserstein shifts is an interesting problem study in its own right and a useful tool to have in the arsenal of provable robustness techniques in machine learning.
In this work, we design robustness certificates for distribution shifts bounded by a Wasserstein dis- tance of e. We show that by simply randomizing the input in transformation space, it is possible to bound the difference between the accuracy of the robust model under the original distribution D and the shifted distribution D as a function of their Wasserstein distance e under that transformation. Given a base model μ., we define a robust model j which replaces the input of μ with randomized version sampled from a "smoothing" distribution around the original input. Let h be a function denoting the performance of the robust model j formal definition). Then, our main theoretical result in Theorem 1 shows that
input-output pair (æ, y) (see Section 3 for
E ((r [M(1,, 91)1 E (12)))))) [7(22, (1(22.02))1 s (c().
where s concave function that bounds the total variation between the smoothing distributions at two input points as function of the distance between them (condition ( in Section 3). Such an upper bound always exists for any smoothing distribution as the total variation remains between zero and one as the distance between the two distributions increases. We discuss how to find the appropriate şi for different smoothing distributions in Appendix G
We apply our result to certify model performance for families of parameterized distribution shifts which include shifts in the RBG color balance of an image, the hue/saturation balance, the bright- ness/contrast, and more. Our method does not make any assumptions on the model and applies to both natural and adversarial shifts of the distribution. It does not increase the computational require- ments of the base model it only samples one randomized input per robust prediction, making it scalable to high-dimensional problems that require conventional deep neural network architec- tures. The sample complexity for generating the Wasserstein certificates over the entire distribution is roughly the same as obtaining adversarial certificates for a single input instance using existing randomized smoothing based techniques (Cohen et al. 2019 Salman al. 2019)
2

---

Published as a conference paper at ICLR 2023
Wasserstei Certified Distance Accuracy
Original
Color Shift
0.5
78.5%
Hue Shift
90
87.6%
SV Shift
1.0
59.8%
Figure 1: Certified accuracies obtained for different natural transformations of CIFAR-10 10 images such as color shifts, hue shifts and changes in brightness and saturation. The Wasserstein distance of each distribution shift from the original distribution is defined with respect to the corresponding distance function.
Color Shift
Hue Shift
SV Shift
Twaned Al Naxoo
A/e
0.8
0.0
0.0
Accurscy
044
0.4
0.-
Trannd Nobe
Noles
Cartifed Accurecy
Carlifed Accurecy
00
00g
0.0g
Wicoerstii Boand (epasta))
Wesserdaann Boundl (spoallon)
Wenverstein Boand (epslaa))
Figure 2: Comparison between the empirical performance (dashed lines) two base models (trained on CIFAR-IO images with and without noise in transformation space) and the certified accuracy (solid line) of a robust model (noise-trained model smoothed using input randomization) under dis- tribution shifts. The certified accuracy often outperforms the undefended model and remains rea- sonably close (almost overlaps for hue shift) to the model trained under noise for small shifts in the distribution.
Robustness under distribution shifts is fundamental problem in several areas of machine learn- ing and our certificates could be applicable multitude of learning tasks. We demonstrate the usefulness of our main theoretical result (Theorem I in the following domains:
(i) Certifying model accuracy under natural shifts (Section 5) We consider three image trans- formations: color shift, hue shift and changes in brightness and saturation (SV shift). Figure ( visualizes CIFAR-10 (Krizhevsky et al.) images under each of these transformations and reports the corresponding certified accuracies obtained by our method. Figure 2 plots the accuracy of two base models (trained on CIFAR-10 10 images with and without noise in the transformation space) under a shifted distribution and compares it with the certified accuracy of robust model (noise- trained model smoothed using input randomization). These results demonstrate that our certificates are significant and non-vacuous (see appendix | for more details). In figures (3) and (4). we plot the certified accuracies for different values of training and smoothing noise- first for the CIFAR-10 dataset and then confirm our results on the SVHN dataset (Netzer et al. (011).
(ii) Certifying population level robustness against adversarial attacks (Section 6 The distri- bution of instances generated by an adversarial attack can also be viewed as a shift in the input distribution within Wasserstein bound. Unlike existing certification techniques which assume fixed perturbation budget across all inputs (Cohen et al., 2019 Lécuyer et al.) 2019 Li et al. 2019 Salman et al., 2019), our guarantees work for a more general threat model where the adversary is allowed to choose the perturbation size for each input instance as long as it respects the constraint on the average perturbation size over the entire data distribution. Also, our procedure only requires one sample from the smoothing distribution per input instance which makes computing population level certificates significantly more efficient than existing techniques. The certified accuracy we obtain significantly outperforms the base model under attack (figure 7ap.
Huang et al. (2021) proposed method to make regular datasets unusable for modern deep learning models by poisoning them with adversarial perturbations to interfere with the training of the model. The intended purpose is to increase privacy for sensitive data such as personal images uploaded to social media sites. The dataset is poisoned in such a way that a model that minimizes the loss on this data distribution will have low accuracy clean test samples. We show that our framework can obtain verifiable
(iii) Hardness results for generating "unlearnable" datasets (Section 7):
3

---

Published as a conference paper at ICLR 2023
lower bounds the performance of model trained on such unlearnable datasets. Our certificates guarantee that the performance of the robust model (using input randomization) will remain above certain threshold on the test distribution even when the base model is trained on the poisoned dataset with a smoothing noise of suitable magnitude. This demonstrates a fundamental limitation in producing unlearnable datasets.
2 RELATED WORK
Several methods for introducing corruptions during training have been shown to improve the em- pirical robustness of machine learning models (Hendrycks & Dietterich] 2019; Yang et al. 2019) Goodfellow et al. 2015 Madry et al., 2018). Training with input transformations, such as blurring, cropping and rotations, ods do not produce any guarantees on the performance of the model with respect to the amount of shift added the distribution. Our method applies random input transformations during inference to make the model provably robust against any distribution shift within a certain Wasserstein distance. It is independent of the model architecture and training procedure, and be coupled with robust training techniques, such as noise or adversarial training, to improve the certified performance.
improve test accuracy against these corruptions. However, these meth-
Randomized smoothing based approaches that aggregate model predictions over a large number of noised samples of the input (Cohen et al. 2019, Lécuyer et al. 2019:) Li et al. 2019; (Sllman et al.) 2019) and that use input randomization (Pinot et al.) 2021 have been studied the context of cer- tified adversarial robustness. Provable robustness for parameterized transformations on images also exist (Fischer et al.) 2020). These techniques produce instance- wise fixed-budger certificates and do not generate robustness guarantees over the entire data distribution or allow varying perturba- tion sizes for different instances. Our work also differs from instance-wisg wise adversarial attacks and defenses (Wong al. 2019 Levine & Feizi 2019) that use the Wasserstein distance (instead of conventional Ep distances) to measure difference between an image and its perturbed version. In contrast, certificates consider the Wasserstein distance between data distributions from which images themselves are sampled.
Robustness bounds the population loss against Wasserstein shifts under the fa-distance (Shen eet al. 2018 Sinha et al. 2018) have been derived assuming Lipschitz-continuity of the base model. These bounds depend on the Lipschitz constant for the underlying model, which can grow rapidly for deep neural networks. We produce guarantees on the accuracy of an arbitrary model without requiring any restrictive assumptions or a global Lipschitz bound. Additionally, our approach can certify robustness against non-f, changes, such as visible color shifts, for which the f2-norm of the perturbation the image space will be very large. Another line of work proves generaliza- tion bounds with for divergence-basee measures of distribution shift (Ben-David et al. [2066] Zhao al. 2019 Mehra et al., [202]] Weber et al.) 2022) like KI.-divergence, total variation distance and Hellinger distance. Divergence measures between two distributions become arbitrarily large (e.g. KL-divergence becomes infinity) or attain their maximal value (e.g. total variation and Hellinger distances become equal to one) when their supports do not coincide. This drawback makes them unsuitable for measuring out-of-distrrbuute support. Wasserstein distance, the other hand, captures the spatial separation of two distributions and produces a more meaningful measure of the distance even when their supports are disjoint.
data shifts which by definition have ovnroleaaa
PRELIMINARIES AND NOTATIONS
Let D be the data distribution representing machine learning task over input space X' and an output space )r We define distribution shift as a covariate shift that only changes the distribution of the input element in samples (Ir, y) E X'x) drawn from D and leaves the output element unchanged, i.., (x, y) changes to (ž. y) under the shift. Given distance function dx : X' x X - R>0 over the input space, we define the following distance function between two tuples
(x1, v1) and
72 (x2, 32) to capture the above shift:
(dx(11)
yf 4/2 otherwise.
d(T T2)
(1)
100
4

---

Published as a conference paper at ICLR 2023
Let D denote shift in the original data distribution D such that the Wasserstein distance under d between D and D is bounded by (i.e., (D D) s e). Define the set of all joint probability distributions with marginals μrD and PD as follows:
I(D,D) - {1 s.t. /
= pD(TT) and / Jxxx 7(T, ra)dT - (
Jxxy
The Wasserstein bound implies that there exists an element 7" E (TD,, D such that
(d(T) S.
(2)
Let S X + A(X) be function mapping each element X' smoothing distribution S(x)., where ((X) is the set of all probability distributions over X' For example, smoothing with an isometric Gaussian noise distribution with variance o² can be denoted as S(x) M(x o2 Let the total variation between the smoothing distributions at two points I2 and 22 be bounded by concave increasing function & of the distance between them, i.e.,
TV(S(a1), S(22)) S (x1x)(11222))
For example, when the distance function d is the f2-norm of the difference of 21 and ø2, and the smoothing distribution is an isometric Gaussian .V (0))) with variance σ², vi(-) aef(-/2222) valid upper bound on the above total variation that is concave the positive domain (see Ap- pendix G for more examples).
Consider a funetion h : X' y - [0 that represents the performance (e.g., accuracy) of model over all possible input-output pairs. For example, in the case of a classifier μ X + y that maps inputs from space X' to a class label y h(2, y) == 1(((x) = y) could indicate whether the prediction of fa on matches the desired output label y or not. Another example could be that of segmeenattion/ddeectiin tasks, where represents a region on an input image I. Then, h(x, y) IoU(u(z), 2 could represent the overlap between the predicted regions u(x) and the ground truth y. The overall accuracy of the model μu under 'D is then given by (( (Mr,, y)]- Now, define a robust model jı(x)= = u(x') where x' S(x) which simply applies the base model on randomized version of the input x sampled from smoothing distribution S(x). Our goal
is to bound the difference in the expected performance of the robust model between the original
distribution D and the shifted distribution D. Let h be the performance function for the robust model jú defined as
h(a, v) Egr 1h(2',)))
(4)
Then, the accuracy of the robust model z under D is given by E (h(,, v)]. Our result in Theorem 1 bounds the difference between the expectation of h under 'D and D with vb()).
3.1 PARAMETERIZED TRANSFORMATIONS
We apply our distributional certificates to produce guarantees on the accuracy of an image classifier under natural transformations such as color shifts, hue shifts and changes in brightness and satu- ration. We model each transformation as a function T : X x + X' over the image space X and a parameter space P. It takes an image E X and parameter vector 0 E P as inputs and outputs a transformed image x' = T(x, 0) Y. An example of such a transformation could be color shift in an RGB image produced by scaling the intensities in the red, green and blue chan- ( defined as CS 0) = (2"x {a.] }, 20 {- 2 {a /MAXXX for a tuple 8 = (fn. 0G. 0B), where MAX is the maximum of all the RGB values after scaling. Ad- ditive perturbations in the input space can also be captured parameterized transformations, e.g., VT 0) = x + 0. We assume that the transformation returns x if the parameters are all zero, i.e., T(x, 0) x and that the composition of two transformations with parameters 0, and 0g is transformation with parameters 0g + 02 (additive composability). i.e.,
nels x = ((=ī] ). ). {x
T(T 01), T(x, 0, + 02).
(5)
ToU stands for Intersection over Union
5

---

Published as a conference paper at ICLR 2023
Given norm follows:
|| in the parameter space P, define distance function in the input space X as dr (2(,
min [00n T(x,, 0) 02) if 30 s.t. T(x1, 0)
(6)
x
otherwise.
Now, define smoothing distribution S(x) = T(x, ((0)) for some distribution Q in the parameter
space of such that V0 E 2 - 0 @(0) is the distribution of 0 where 2(0), and
TV(Q(0), 2(0)) S ((10))) for a concave function vh. For example, 2(-) of,,0²1) satisfies
these properties for v²()) erf(-/2/2o)) Then, the following lemma holds (proof in Appendix B Lemma 1, For two points Iı, D2 E X' such that dy (21, x22) is finite,
TV(S(z)), S (bld (x1,
4 CERTIFIED DISTRIBUTIONAL ROBUSTNESS
In this section, we state our main theoretical result which shows that the difference in the expectation of the performance function h of the robust model (equation (4) under the original distribution DD and any shifted distribution 2 within Wasserstein distance of from D is bounded by vb(c). where & the concave upper bound on the total variation between the smoothing distributions at two points 2 and 22 defined in condition (3)
Theorem 1. Given a function & : x + [0, 1}, define its smoothed version as h(x,y)
E(x))(a) [h(x', 4)}. Then,
s.S. (D(
BLILINDD (F v1)l ((02,)))- (202, (2)] I (()).
We defer the proof to Appendix A Note that this certificate does not require us to compute the Wasserstein distance between D and D. Given a value for it holds for all distributions D such that (D, D)
Our certified guarantees hold for the entire input distribution (potentially continuous) and not just for a finite set of samples. The intuition behind the above bound is that if the overlap between the smoothing distributions between two individual points does not decrease rapidly with the distance between them, then the overlap between D and D augmented with the smoothing distribution is high when the Wasserstein distance between them is small. The key observation here that the total variation of the individual smoothing distributions can be upper bounded by a convex function oi and this upper bound can then be generalised over the entire distribution using Jensen's 's inequality. The above guarantee implies that for any distribution DD that is within Wasserstein distance of c from the original distribution D, the accuracy of the model under D can be bounded as (( >D (12, w/]] 2 (B (1 91)] (b))..
4.1 COMPUTING THE CERTIFICATE AND EMPIRICAL EVALUATIONS
Given a target Wasserstein bound e and an appropriate function v we simply need to cal- culate the expected performance of the robust model E(e.))>> [h11, J1)]. Since we only have sample access to the original distribution D, we esti- mate the expected performance on D, i.e. )= /hn///>///a 31) 3, using a finite number of samples. In our experiments, we compute a high-confidence lower bound of this quantity using the Clopper- Pearson method (Clopper & Pearson 1934) that holds with (usually 0.001). Note that although we calculate the bound with finite number of samples from the distribution D, this lower bound holds for the expectation over the entire distribution and not just for the samples. See Appendix [ for pseudocodes of the prediction and certification steps.
the original distribution DD i.e.,
probability, for some a > 0
To compare our certified guarantees against the empirical performance of an undefended model un- der distribution shifts, we design shifted distributions using natural and adversarial transformations on the original distribution. We ensure that the constructed distribution shift is within the desired Wasserstein distance using two methods:
1.
By construction: We analytically guarantee beforehand that the applied transformation does not exceed the Wasserstein bound. For example, in Figure 2 we report the empirical per- formance of the base models under distribution shifts constructed by adding noise vector

---

Published as a conference paper at ICLR 2023
Taiting
Park
Voda
cateer howe 2.
Cont of
Cott
Reanlussdino 15
Weseesten
(a) Color -
Color Stft
Color St
Coler Srth
Color Shift
le Matio 5.3
ma 180
Cettrnl
Confict
Messemtein Bandd lepal
Wartercter tepakoe)
Bound Hqpilc)
Wasserdien bound (epalar))
(b) Color Shift-SVHN
Figure 3: Certified accuracy under color shifts for (a) CIFAR-10 and (b) SVHN. Each plot corre- sponds to a particular training noise and each curve corresponds to a particular smoothing noise.
from a fixed distribution like a Gaussian distribution of a certain variance in the transfor- mation space (see Appendix Db.
2. By estimation: We compute high-confidence bound on the average perturbation added to finite number of samples to bound the Wasserstein distance. For example, in Section 6 when reporting the undefended baseline performance, we measure E B[][Adv(z) - ø=|2] on the test set, and use Hoeffding's 's inequality to derive from this a 99% confidence upper bound on the true, population expectation ER-D [[]Ad((z) x ell2). By Equation 8 this is a (high-probability) upper bound on the Wasserstein distance of the distribution shift.
In the following sections, we apply main theoretical result to obtain certified robustness guaran- tees against several different distribution shifts - natural shifts, unlearnable distributions and adver- two image classification datasets, namely CIFAR-10 (Krizhevsky eet al.) and SVHN (Netzer et al.] 2011), and observe that the our certificates can obtain meaningful performance guarantees and exhibit similar trends for both datasets.
sarial shifts. We experiment
5 CERTIFIED ACCURACY AGAINST NATURAL. TRANSFORMATIONS
We certify the accuracy of ResNet- 1 10 model and a ResNet-20 model trained on CIFAR- 10 and SVHN images respectively under three types of transformations: color shifts, hue shifts and vari- ation in brightness and saturation (SV shift). We train our models with varying levels of noise in the transformation space and evaluate their certified performance using smoothing distributions of different standard deviations. For color and SV shifts, we show how the certified accuracy varies as function of the Wasserstein distance as we change the training and smoothing noise. For hue shift, we use a smoothing distribution (with fixed noise level) that is invariant to rotations in hue space because of which the certified accuracy remains constant with respect to the corresponding Wasser- stein distance. We train the ResNet- 1 11 models for 90 epochs which takes a few hours on a single NVIDIA GeForce RTX 2080 Ti GPU and the ResNet-20 models for 40 epochs which takes around twenty minute on the same GPU, Once the models have been trained, computing the distribution level Wasserstein certificates using 10s samples with 99.9% confidence takes only about 25 seconds for each model.
5.1 COLOR SHIFTS
Denote an RGB image x as an H x W array of pixels where the red, green and blue components of the pixel in the ith row and jth column are given by the tuple æiy = (r. b))z- Let Tmax Imax and bmax be the maximum values of the red, green and blue channels, respectively. Assume that the RGB values are in the interval [0, 1] normalized such that the maximum over all intensity values is one, i.e., max(r maxx Jraax ) = 1. Define color shift of the image for a parameter vector 0 E R as
(2 2n0 g. 00.2000 b)sg
HxW
CS 0) =
max 1lax(2RRT (2 max. 29c 9max, 20 b
7

---

Published as a conference paper at ICLR 2023
Taiting
Vota
Cont
Cotte
15
Brightness and Saturation Shift CIFAR-10
Pssning holse 0.0
The ning Molo 2.0
Training holte 4.0
Tahing Hoise a
8.0
le Matio 6-3
Cettrnl Acourey
Cotfaee
Messemtein band lepi
Wantenteer lound Lepekon)
Musernsi Bound tepelce)
Wassertenn baund (epalar)
(b) Brightness and Saturation Shift- SVHN
Figure 4: Certified accuracy under brightness and saturation changes for (a) CIFAR-10 and (b) SVHN images. Each plot corresponds to a particular training noise and each curve corresponds particular smoothing noise.
which scales the intensities of each channel by the corresponding component of 0 raised to the power of two and then normalizes the scaled image that the maximum intensity is one. For example, 0 = -1,0) would first double all the red intensities, halve the green intensities and leave the blue intensities unchanged, and then, normalize the image so that the maximum intensity value over all the channels is equal to one. The above transformation can be shown to satisfy the additive composability property in condition (5). See Appendix H for proof.
Given an image H, we define smoothing distribution around x in the parameter space as CS(x,, 6) where
(2 Define the distance function des as described in (6) using the l2- norm in the parameter space. For a distribution D within a Wasserstein distance of c from the original distribution D. the performance of the smoothed model on D can be bounded as (0 >ーu (x2, V2]] 2 EE bn (1(11, yı)l erf(e/2/2o). Figure 3 plots the certified ac- curacy under color shift with respect to the Wasserstein bound for different values of training and smoothing noise. In Appendix [K] we consider a smoothing distribution that randomly picks one color channel achieving a constant certified accuracy of 87. 1% with respect to e.
5.2 BRIGHTNESS AND SATURATION CHANGES
Define the following transformation in the HSV space of image that shifts the mean of the satu- ration (S) and brightness (V) values for each pixel by a certain amount:
SV(x, 0) = -((1
8 + (20s- 1)8mean
v + (28v
1)meaa
HxW
MAX
MAX
where Smean: Smax, Umean and Umax are the means and maximums of the saturation and brightness values respectively before the shift is applied and MAX = max(Smax + (2 mmsan: Vmax + (2"r - 1) mmean) is the maximum of the brightness and saturation values after the shift. Similar to color shift, the SV transformation can also be shown to satisfy additive composability (Appendix H+). Figure plots the certified accuracy under saturation and brightness changes with respect to for different values of training and smoothing noise. The smoothing distribution is uniform in the range [0, a]2 in the parameter space, the distance function is the & norm and (E) = min(e/a, 1).
6 POPULATION-LEVER CERTIFICATES AGAINST ADVERSARIAL ATTACKS
In this section, we consider the lnddistance in the image space to measure the Wasserstein distance instead of a parameterized transformation (see Appendix D for a detailed version). We use a pixel- space Gaussian smoothing distribution S(x) = Nxx oT to obtain robustness guarantees under this metric. To motivate this, consider an adversarial attacker Adv : X' + X, which takes an image x and computes perturbation Adv(x:) to try and fool model into misclassifying the input. If
8

---

Published as a conference paper at ICLR 2023
(ar ~ D, define D to be the distribution of the tuples (Adv(z)) y). Defining dl in using dx E2 it is easy to show that:
(D, < Ex>Dllldd( - x=|2]
Results on CIFAR-10 are presented in Figure 5 and results on SVHN are available in Appendix D For CIFAR-10, we use ResNet-1 10 models trained under noise from [Cohen et al. (2019). The solid lines represent certified accuracies for dif- ferent smoothing noises and the black dashed line represents the empirical performance of an undefended model under at- tack. For the undefended baseline, we give the performance of an undefended model against a strategic attacker, which first finds minimal E2 attack for each sample via (Carlini & Wag- ner, (017). If this attack is too large in magnitude (22 > a threshold ?), it instead chooses not to attack the sample. This "saves" the attack budget (i.e., the average attack magnitude and therefore the Wasserstein shift) for easier samples. The size of the Wasserstein shift can be adjusted by varying 7
Adversar Dittribttion
Sober
62
Figure 5: Distributional certifi- cates against adversarial attacks on CIFAR-10.
7 HARDNESS RESULTS ON UNLEARNABILITY
In this section, we show that the pixel-space &g- fg-Wasserstein distributional robustness certificate shown above can also be applied to establish a hardness result in creating provably "unlearnable" datasets (Huang et al., 202I). These datasets contain "poisoned" samples which make any classifier trained on the released data achieve a high training and validation accuracy, but low test accuracy on non-poisoned samples from the original data distribution. This technique has legitimate applica- tions, such as protecting privacy by preventing one's personal data from being learned, but may also have malicious uses (c.g., a malicious actor could sell a useless classifier that nevertheless has good performance on provided validation set.) We can view the "clean" data distribution as D, and the distribution of the poisoned samples (i.e., the unlearnable distribution) as D. If the magnitude of the | implies that the accuracy on D and D must be similar, implying
perturbations is limited, Theorem that our algorithm is provably resistant to unlearnablility attacks, effectively establishing provable hardness results to create unlearnable datasets.
In order to apply our guarantees, we make a few modifications to the attack proposed in Huang et al. (202T). First, we bound each poisoning perturbation on the released dataset within an c-radius E2 ball, rather than an lo ball. From Equation & this ensures that W (D, D) c. Second, we consider an "offline" version of the attack. In the original attack (Huang et al. 2021 perturbations for the entire dataset are optimized simultaneously with a proxy classifier model in an iterative manner. This makes the perturbations applied to each sample non-I.I.D., (they may depend on each other through proxy-model parameters) which makes deriving generalizable guarantees for it difficult.
However, this simultaneous proxy-model training and poisoning may not always represent a realistic threat model. In particular, an actor releasing "unlearnable" data at scale may not be able to constantly update the proxy model being used. For example, consider an "unlearnability" module in a camera, which would make photos unusable as training data. Because the camera itself has access to only a small number of photographs, such a module would likely rely on a fixed, pre-trained proxy classifier model to create the poisoning perturbations. To model this, we consider a threat model where the proxy classifier is first opti- mized using an unrelcased dataset: the released "un- learnable" samples are then perturbed independently using this fixed proxy model. We see in Figure 6 that modified attack is still highly effective at making data unlearnable, as shown by the high validation and low test accuracy of the undefended baseline.
ts 'Unleamebility" Distribution Shift
1.0
DS.
no.
02
02
CA
0.5
0.8
1.0
Wassarstain Bound (opsiton)
Figure 6: Distributional certificates for unlearnable datasets on CIFAR-10. The smoothing noise used is 0.4. Results for other values are reported in the appendix.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This project was supported in part by Meta grant 23010098, NSF CAREER AWARD 1942230, HR00111950022 (GARD), ONR YIP award N0001422-1-2271, Army Grant No. W911NF2120076, a capital one grant, NIST 6ONANB20D134, and the NSF award CCF2212458.
REFERENCES
Michael A. Alcorn, Qi Li, Zhitao Gong, Chengfei Wang. Long Mai, Wei-Shinn Ku, and Anh Nguyen. Strike (with) pose: Neural networks are easily fooled by strange poses of familiar objects. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA. USA, June 16-20, 2019, pp. doi: 10.10990VPR.2201.000999
Computer Vision Foundation / IEEE, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pp. 274 283, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize so poorly to small image transformations?? Journal of Machine Learning Research, 20(184):1-25, 2019. URL
httt:://fmlr.or http:/ww..rrrppppppp.oaam http://apess////////// 1ttp:////1191111111 htmml
Shai Ben-David, John Blitzer, Koby Crammer; and Fernando Pereira. Analysis of representations for Advances Advacssdssssee in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pp. 137-144. MIT Press, 2006. URL httpttpspppppcppp.pnnggoooeeeeee neurips. cct.cc//.ccccccc..cccc.o wtt.:ettt.ttttttt..ttt....
domain adaptation. In Bernhard Schölkopf. John C. Platt, and Thomas Hofmann
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdic, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Hen- drik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (eds.), Machine Learning and Knowledge Discovery in Databases- European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III, volume 8190 of Lecture Notes in doi: 10. 10.10077978-3--424409999 wrg.oogggg.o.o 1007 Bttps://6bb..org/00100////3-3--3 000--442-4994-33 25
Computer Science, pp. 387-402. Springer, 2013.
URL
Nicholas Carlini and David A. Wagner. Adversarial examples not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec CCS 2017, Dallas, TX, USA, November 3, 2017, pp. 3-14, 2017.
J. Clopper and E. S. Pearson. The use of confidence fiducial limits illustrated in the of the binomial. Biometrika, 26(4):404 1934. ISSN 00063444. URL http: http::/wwww /wwww//ww//////////////////. istor.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310-1320, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution op- timal transportation for domain adaptation. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Gamett (eds.). Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Process- ing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3730-3739, 2017.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adapta- tion. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Com- 15th European Conference, Munich, Germany, September 8-14,
puter Vision ECCV 2018
10

---

Published as a conference paper at ICLR 2023
2018, Proceedings, Part IV. volume 11208 of Lecture Notes in Computer Science, pp. 467-483. Springer, 2018. doi: 10.1007/978- 00007999788--030--1222-0-00 URL httptttsss///i.rroo///
978-3-030-01225-11 28
Samuel F. Dodge and Lina Karam. Understanding how image quality affects deep neural networks. 04004
CoRR, abs/1604.04004 2016.
Logan Engstrom, Brandon Tran, Dimitris Tsipras. Ludwig Schmidt, and Aleksander Madry. Ex- ploring the landscape of spatial robustness. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML, 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 1802 PMLR, 2019. URL http:::://rocrccinggs.. ml http:paaeiinnng......rssss/// engstroml 9a. html
Alhussein Fawzi and Pascal Frossard. Manitest: Are classifiers really invariant? abs/1507.06535, 2015. URL http:::/aaxl...o/////b//////////
CoRR,
Mare Fischer, Maximilian Baader, and Martin T. Vechev. Certified defense to image transforma- tions via randomized smoothing. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
songwei Ge, Shlok Mishra, Haohan Wang. Chun-Liang Li, and David W. Jacobs. Robust contrastive learning using negative samples with diminished semanties. CoRR, abs/21 10. 14199, 2021. URI,
https://arxiv org/ atcp//bs//21111 14189
Robert Geirhos, Carlos R. Medina Temme, Jonas Rauber, Heiko H. Schütt, Matthias Bethge, and Felix A. Wichmann. Generalisation in humans and deep neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchie and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 7549-7561, 2018
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovie, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models, 2018
Dan Hendrycks and Thomas G. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:
//openreview. wwt.:/ttt.ooooteo (itpmmmmi==JJJJ d=HJz 6t. Cqym
Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani, James Bailey, and Yisen Wang. Unlearnabee examples: Making personal data unexploitable. In ICLR, 2021.
Po-Sen Huang, Robert Stanforth, Johannes Welbl, Chris Dyer, Dani Yogatama, Sven Gowal, Krish- namurthy Dvijotham, and Pushmeet Kohli. Achieving verified robustness to symbol substitutions via interval bound propagation. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019, pp. 4081 4091, 2019. doi: 18.118/3/v 1/D19-/1//19911999 URL
1419
Minseon Kim, Jihoon Tack, and Sung Ju Hwang. Adversarial self-supervisedd contrastive learning. In Hugo Larochelle, Mare Aurelio Ranzato. Raia Hadsell, Maria-Florin Balcan, and Hsuan- issan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
11

---

Published as a conference paper at ICLR 2023
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced re- search). Uttht::://www. http:://www.cc toronto. ccuu-kriz/cifar.aae
Aounon Kumar and Tom Goldstein. Center smoothing: Certified robustness for networks with structured outputs. Advances in Neural Information Processing Systems, 34, 2021.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust rein- forcement learning. CoRR, abs/2106. 1 1420, 2021. htthtttp:///arrll.ooo//aaas///
11420
Cassidy Laidlaw and Soheil Feizi. Functional adversarial attacks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'AlchéBBue, Emily B. Fox, and Roman Gar- nett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancou- n ps. cc/pcc///eee /aper/
ver, BC, Canada, pp- 10408-10418, 2019. URL htttp://papen 9228 funct ional waw.onaaaavvvarrrriaaaa
attacks
Cassidy Laidlaw, Sahil Singla, and Soheil Feizi. Perceptual adversarial robustness: Defense against unseen threat models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL SRR.itttss://ppnrreet net//ooum? (.GGdEFBBSAJJKK
Mathias Lécuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 JEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19-23, 2019, pp. 656-672, 2019.
Jaeho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Ro- man Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 269222222222 2701, 2018.
Alexander Levine and Soheil Feizi. Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks, 2019.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a.
Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020. The Shcroy-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI
2020, New York, NY. USA, February 7-12, 2020, pp. 4585 4593, AAAI Press, 2020b. URL
kittps:/aaae org/ /tt.///////...... /s/ index.iixx. http:///ppp/aaaaaaiille/e/////// 5888
Alexander Levine and Soheil Feizi. Improved, determmnsteee smoothing for L1 certified robustness. CoRR, abs/2103. 2021.
10834
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 9459-9469, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Confer- ence Track Proceedings, 2018
12

---

Published as a conference paper at ICLR 2023
Pratyush Maini, Eric Wong. and J. Zico Kolter. Adversarial robustness against the union of multiple perturbation models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. (650-6650. PMLR, 2020. htt.:httpp/ppooee n 20a html
ngs. mlr press//1s//////
Akshay Mehra, Bhavya Kailkhura, Pin- Yu Chen, and Jihun Hamm. Understanding the limits of unsupervised domain adaptation via data poisoning. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual,
pp. 17347-17353 2021. URL http:://proceddngg hash
www.ings..nurii...ommm cctppprr/ppp////// o html
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http:///fldll.. stanford.eds. Nousemumbrrs/nte nss001 housenumbers......mmo........... .ddf
Maria-Irina Nicolae, Mathieu Sinn, Minh Ngoc Tran, Beat Buesser, Ambrish Rawat, Martin Wis- tuba, Valentina Zantedeschi, Nathalie Baracaldo, Bryant Chen, Heiko Ludwig, Ian Molloy, and Ben Edwards. Adversarial robustness toolbox v1.2.0. CoRR, 1807.01069, 2018. URL https: /aa/aaiivv....////// wwwp//////////. 1807
wttp///////..1..1. 01069
David B. Pearce and Hans-Günter Hirsch. The aurora experimental framework for the perfor- mance evaluation of speech recognition systems under noisy conditions. In INTERSPEECH, 2000.
Rafael Pinot, Laurent Meunier, Florian Yger, Cédric Goul-Pailler Yann Chevaleyre, and Jamal Atif. On the robustness of randomized classifiers to adversarial examples. CoRR, abs/2102.10875, 2021. URL httpt:ttts/:tii....ect
abs / 10875
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and llya Sutskever. Learning transferable visual models from natural language supervision. In Ma- rina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Ma- chine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Ma- PMLR, 2021. URL http::ttp//// http::::/ppcceeddngg.e mmr.
chine Learning Research, pp. press/v139/ https//adffoddddd..... html
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Semidefinite relaxations for certifying bustness to adversarial examples. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 10900-10910, Red Hook, NY. USA, 2018 Curran Associates Inc.
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sébastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Informa- fion P Processing Systems 2019, NeurIPS 2019, 8- 14 December 2019, Vancouver, BC, Canada, pp- 11289-11300, 2019.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John P. Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Gamett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3353-3364, 2019.
Jian Shen, Yanru Qu Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Sheila A. Mellraith and Kilian Q. Weinberger (eds.), Pro- ceedings of the Shioty-Second AAAI Conference Artificial Intelligence, (AAAI-18), the 30th
13

---

Published as a conference paper at ICLR 2023
innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Sympostum Ed- ucational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, Febru- ary 2-7, 2018. pp. 4058 4065. AAÅI Press, 2018. URL https:/ /ttp://wwwww. www.. .rg. ocs/ index. /htp:/AAA/AAAAATa/ppppp////leeee
Sahil Singla and Soheil Feizi. Robustness certificates against adversarial examples for relu networks. CoRR, abs/1902.01235, 2019.
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks. In Pro- ceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learming Research, pp. 8981-8991 PMLR, 2020. URL
ngs mir. wwwps/eessssseeee wttpss//11//singn/2222 /
html
Aman Sinha, Hongseok Namkoong, and John C. Duchi. Certifying some distributional robustness with principled adversarial training. In 6th International Conference on Learning Representa- tions, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceed- net/ forum? 2dd=
ings. OvenReview.net, 2018. BRLhhttss://ppeeett
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 62, 2020, virtual, 2020.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Allhé-BBcc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 5858 5868, 2019.
Jonathan Uesato, Brendan O' O'Dongguu,, Pushmeet Kohli, and Aäron van den Oord. Adversarial risk and the dangers of evaluating against weak attacks. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10- 15, 2018, pp. 5032-5041, 2018.
Igor Vasiljevic, Ayan Chakrabarti, and Gregory Shakhnarovich, Examining the impact of blur on recognition by convolutional networks. CoRR, abs/161 1. 1.05660, 2016. URL http::/arxxx org/abs 1 1611.11111111 05760
Maurice Weber, Linyi Li, Boxin Wang, Zhikuan Zhao, Bo Li, and Ce Zhang. Certifying out- of-domain generalization for blackbox functions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, ICML, 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 23527-23548. PMLR, 2022. URL. https: /pprocediing. mlr www.s/.resssiii... http:///111/eeeee222..a atml
Eric Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssdässan Stockholm, Sweden, July 10-15, 2018, pp.
2018.
Eric Wong, Frank R. Schmidt, and J. Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6808- 6817. PMLR, 2019. htt.:httt://peee
ngs ml wtw.:mmrr.p.......mmmm
press. / 99 wong1 9a html]
14

---

Published as a conference paper at ICLR 2023
Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. CROP: certifying robust policies for reinforcement learning through functional smoothing. CoRR, abs/2106.09292, 2021.
org/ abs 09292
Yifan Wu, Ezra Winston, Divyansh Kaushik, and Zachary C. Lipton. Domain adaptation with usymmettrically-rracce distribution alignment. In Kamalika Chaudhuri and Ruslan Salakhutdi- nov (eds.), Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 6872-6881 PMLR, 2019. URL wul html
Fanny Yang, Zuowen Wang. and Christina Heinze-Deml. Invariance-inducing regularization using worst-case transformations suffices boost accuracy and spatial robustness. In Hanna M. Wal- lach, Hugo Larochelle, Alina Beygelzimer, Florence A'Ach---uc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 14757-14768, 2019.
Han Zhao, Remi Tachet des Combes, Kun Zhang, and Geoffrey J. Gordon. On learning invari- ant representations for domain adaptation. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9- 15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research. pp. 7523-7532. PMLR, 2019. URL http: http:://proceedings.co mir V zhaol ht.ml
Yiren Zhou, Sibo Song, and Ngai-Man Cheung. On classification of distorted images with deep convolutional neural networks. CoRR, abs/1701.01924, 2017. URL http: http:///axxvvooo
abs/1701, 01924
A PROOF OF THEOREM
Statement. Given a function h : X x y + [0, 1]. define its smoothed version as h(x,v) =
Ey'~S(n) (o(aly)), Then,
E [ B(n (1 U1) B u2)1 s (c))
Proof: Let (z1, v1) and 72 (I2, U2) denote the input-output tuples sampled from D and D
respectively. Then, for the joint distribution 7" E I(D, D) in 2 we have
[h<D) B(r,r [m(m)] and E B (T(2) (( [M(22)]
This is because when (51, r2) sampled from the joint distribution y", Ti and Ta individually have distributions ID and D respectively. Also, since the expected distance between 71 = (I1, v1) and 72 (x2, y22 is finite, the output elements of the sampled tuples must be the same, i.e. y1 3/2 (say). See Lamma@beloo Then,
BRLLD (h(11, 01)]
E ( >D (1(22,
|B [((T))] E, B,
[ (7(T1) h(rz)]l
S B [[((TT) T((72)))
Now, from definition 4 and for 1 and 2,
A(T))) T(,, y) Bet~ [M(2// y)] =Ez;~S(e,) ((x)>((())
can be expressed as the expected value a function X + [0. 1] under distribution S(x;).
Without loss of generality, assume = (gg(()))))))) (egr)((()))) [g((()) Then,
15

---

Published as a conference paper at ICLR 2023
(()))((())) Beg
J (())))(()) J ((x))2(2)dz
(u1 and μ2 are the PDFs of S(x1) and S(x1))
/ (()))u))))-2((000
(())((())) p2(x))dr
g(z)(U2(x) - pi (x))ddr
12222
122
max g( (1) 12(x:))
min ((2)) p (z))
p41 Pp2 W'EN
2'Ex
<
(mI(Z) - 12(2)))
11212
(since max g(x') < 1 and min 2 0)
(2(x)) - (V(((
(since SKi (11 p2(x))drr Spares (12(2) (1)))d Sx (u1(2) pd(x))dr)
= Thus, from ① and 13 we have [k(T:) - - T((2211 s = T2)),, and therefore,
E B(e..))--(((())
E ( y2)l|
S (n (+) (d T2))]
$ v ( (d( r2))
(tb is concave, Jensen's 's inequality)
Hence, from (2) and since vp is non-decreasing, we have
E EL (h0,,, v1)l (o 82)1 s ((e).
Lemma 2. Let Ω = (271,7) s.t. # y2 where Ti = (II,81) and T2 v2)}. Then
P P T2) E Ω 0.
Proof. Assume, for the sake of contradiction, that for some p > From condition
P P(n.))~rl( [(1, T2) [Ω] 2
2 we have
E B (d(TI: Se.
By the law of total expectation
Ey, [d(r), 72)] =E,- (d(T) T2) (Ti, 72) P.- (1, e +R.-- (d(T), 12) (n,,) $ P., (T,,)) 12) $
We replace (TI, 7- with just 7* in the subscripts for brevity. Since both summands are non- negative,
[d(r,, 72) (7, 72) E 2 P,- r2) E st] S c. Consider a real number > c/p. Then, for any (21,7) E Ω, from definition and because y1 # y2, d(T), T2) 2 1. Therefore, [.-[[((T. (T)) E Q] 2 and
(TT. E 2] < Ey (d(T), (7))7) E 9 P. [(T, T2) E ? (P.. ! <
P-- T2) e Ω $ e/ll <pp
which contradicts initial assumption.
16

---

Published as a conference paper at ICLR 2023
Algorithm Prediction
Algorithm 2 Certification
Input: Model μ,, input instance x.
Input: Accuracy function h, data distribution
Output: Robust prediction y.
D. Wasserstein bound c, integer and a >>
Randomize input: x' ~ ((z).
Output: Certified accuracy for bound e.
Evaluate model: y = p(r').
sum
Return y.
for in 1... do
Sample (x. y) ~ D.
Sample x' S(z).
Compute h(x', yy)
sum sum h(2', ,))
end for
Compute confidence lower-bound h of (( (7 y)] using sum and n.
Return (c)..
B PROOF LEMMA
Statement. For points 21, X such that (x1 (211 x22) finite,
TV(S(z1); S (x1,
Proof. Consider the 0 for which dr |0]]. Then, T(x1, 0) 22.
S((2)) = TV(T(z, Q00),, Q(0)))
TV(T(z, (((,,, (()))
((),, TVV(T(z,
(additive composability, equation (5)
(definition of Q)
Let A be the event in the space M that maximizes the difference in the probabilities assigned to A by T(x, ((0)) and T(x, (())). Let u P- [0, 1] be function that returns the probability (over the randomness of T) of any parameter 7 E P being mapped to point in A, i.e., u(T) P(T(x, 1)) e A}. For a deterministic transformation T, is a 0/1 function. Then, the probabilities assigned by T(x, Q(0)) and T(x, Q(0)) to A is equal to 2(0) [u(n)) and ((0) [u(n)). Therefore,
TV(S(a), E))2(0) (u())] E [()]
S TV(@(0), 2(0))
I ((100])) = xd)((11,22).
(definition of Q and dr)
C PSEUDOCODE FOR PREDICTION AND CERTIFICATION
Algorithm D and Algorithm describe the prediction and certification steps our method.
D POPULATION-LEVEL CERTIFICATES AGAINST ADVERSARIAL ATTACKS
In this section, we consider the -ddisttncc in the image space to measure the Wasserstein distance instead of a parameterized transformation. We pixel-space Gaussian smoothing distribution S(x) = (x, o²I) to obtain robustness guarantees under this metric. To motivate this, consider an adversarial attacker Adv X X. which takes image and computes perturbation Adv(z) to try and fool model into misclassifying the input. If (I, y) D. define D to be the distribution of the tuples (Adv(z), y). Defining d in using dx = l2, it is easy to show that:
(D, Bew x=12]]
(8)
17

---

Published as a conference paper at ICLR 2023
&t Adversarial Distribution Shift
Adversarial Distribution Shift
1.0
1.0
Semoething
Smoothing
Smroothing
Smrothhnng
Serroz7ing
Smooohhnng Neise 0.5
0.8
Smmposhingg
Smooohhing 1.0
Listtriened
Unndrrended
Accurso
0.6
Accurocy
0.6
0.2
0.2
0%
Wasserstein Bound (epsilon)
Wasserstein Bound (epsilon)
(a) CIFAR- 10.
(b) SVHN
Figure 7: Distributional certificates against adversarial attacks on (a) CIFAR-10 and (b) SVHN. The solid lines represent certified accuracy of the robust models and the dashed lines represent the adversarial accuracy of undefended models.
So, if the average magnitude of perturbations induced by Adv is less than (i.e., Adv x111a] < e), then W (D, D)- < which means that can apply Theorem|] the gap in the expected accuracy between x ~ D and Adv(x) ~ DD will be most e²(c). Note that, under this threat model, Adv can be strategic in its use of the average perturbation "budget": if a certain point x would require a very large perturbation be misclassified, is already misclassified, then Adv(z) can save the budget by simply returning x and use it to attack a greater number of more vulnerable samples.
Note that method differs from sample-wise certificates against Ea adversarial attacks which use randomized smoothing, such as Cohen et al. (2019). Specifically, we use only one smoothing pertur- bation (and therefore only one forward pass) per sample. Our guarantees are on the overall accuracy of the classifier, not on the stability of any particular prediction. Finally, as discussed, our threat model different, because we allow the adversary to strategically choose which samples to attack, with the certificate dependent on the Wasserstein magnitude of the distributional attack.
Results on CIFAR-10 and SVHN are presented in Figure 7 For CIFAR-10, we use ResNet- 10 models trained under noise from Cohen et al. (219)) For S SVHN we train our own models using the same training schedule as used for CIFAR- 10 by Cohen et al. (2019), but we use ResNet-20 place of R10. The solid lines represent certified accuracies for diffferent smoothing noises and the black dashed line represents the empirical performance of an undefended model under attack. For the undefended baseline (on undefended classifier g), first apply Carlini and Wagner &g attack to each sample x (Carlini & Wagner 2017), generating adversarial examples x'. Define this attack as the function CW(-), such that x'' CW (I. y: g), where y is the ground-truti label. (If the attack fails, CW (1,, y; g) = 3). We then define a strategic adversary Adv,, that returns CW (Jr, y5 g)) if ||CW (Ir, 35.9) x1|2 7, otherwise it returns sr.
By not attacking samples which would require the largest f2 perturbations to cause misclassification, this attack efficiently balances maximizing misclassification rate with minimizing the Wasserstein distance between D and D. The threshold parameter y controls the tradeoff between misclassifcation rate and the Wasserstein perturbation magnitude. Note that our attacker here is strategic in a way that takes more advantage of the distributional threat model than simply finding the minimal perturbation for each sample: by choosing to not attack at all on robust samples, it can successfully attack larger number of more vulnerable samples. The 'Undefended' baseline in Figure plots the accuracy on attacked test samples under adversary Adv., for sweep of values of y, against an upper bound on the Wasserstein distance, given by Eg~D [ii=>|||AAc [||Adv,, (x))<11z))) =||2]] (In order to estimate Eg- Eg-DD||Ad [||Adv,, ar]la], we compute the average perturbation size over the test set and use Hoeffding inequality to the population expectation with 99% confidence.) We can observe a large gap between this undefended model performance under attack, and the certified robustness of our model, showing that our certificate is highly nonvacuous. In Appendix [E] robustness of the smoothed classifiers under an "adaptive" attack, based the attack sample-
we include results to show the empirical
18

---

Published as a conference paper at ICLR 2023
wise lg smoothing proposed by Salmaan al. (2019). We also test an alternate form strategic attacker on the baseline model that does not requires us to estimate the average perturbation size empirically (Appendix FD
E
EMPIRICAL ATTACKS ON E3-DISTRIBUTIONAL ROBUSTNESS.
b)
Adversorial Distribution
Adversarial Distribution Shift
Cortiioare Rale 0.1
Coriilozee Potee 633)
Breekur ( 332
Emalical Oode 635
Empiic (Nees 331
Oathooti
Contiitaae ho 1.3
Cartironse Joate 100
Emgarier (Nebe
02-
%
%
Figure 8: Adversarial attack distributionally-smootte classifiers, for CIFAR-10. For smoothed classifiers, we use the PGD attack described in is section; see Section 6 for details on the baseline. The dashed lines represent the empirical performance of the smoothed model for different noise levels. In plot (a), we use the loss function in Equation while in (b) we use Equation I0
8)
b)
Adversarial Distribution
Adversarial Distribution
1.0
1.0
0.1%
Carilizaa 0.1%
Erakical Mobe 6.321
Emgaiial (Nbe 5321
0.25
Gerl Ecate hale 0.0
Cartiiaate Pulie 0.5
Mebe
1.1
Frquiral dhake 121
Frrelina (halos 11
880
"/a
Wassersteh Sound legsioon
Wasserstein Bound Depsioon
Figure 9: Adversarial attack on distributionally-smooone smoothed classifiers, for SVHN. For smoothed clas- sifiers, we use the PGD attack described in is section; see Section & for details on the baseline. The dashed lines represent the empirical performance of the smoothed model for different noise levels. In plot (a), we use the loss function in Equation g while in (b) we use Equation 10
In this section, we describe an empirical attack on fz-distributional smoothing. Our attack is based on the attack from (Slmann et al. (2019), and we use the code for PGD attack against smoothed classifiers from that work as a base, but there are few considerations we must make.
First, while the goal of the attacker in Salman et al.) (2019) is to change the output of a classifier that uses the expected logits, the goal in our case is to instead reduce the average classification accuracy of each noise instance. Concretely, [Salman et al. (2019) uses an attacker loss function for each sample of the following form:
max Cross Eat.
E (0~2(00021
[ol( + 53)
Where we use f to represent the SoftMax-ed logit function. However, because in our case, the classifier under attack is not Es-N(0.0=1 + +c+5)) but rather fo(a + c 8) itself, we instead
considered the loss function:
Cenus Emt. (Fo(s + + ++++++++))))))
E
(10)
20
Empirically, we find the choice of loss function make very little difference: Figures and
19

---

Published as a conference paper at ICLR 2023
We also must consider how to correctly make the attacker "strategic": that is, how to allocate attack magnitude so as to attack most effectively while minimizing Wasserstein distance. This more difficult than in the undefended case, because it is no longer true that for each sample æ, we can identify the magnitude |[CW (2r g; - æ||2 such that an attack of this magnitude is guaranteed to be successful, while smaller attack is unsuccessful and hence is not attempted. Rather, for given attack magnitude, there is instead a probability of success, over the distribution of 6.
In order deal with this, we perform PGD range of attack magnitudes, specifically E {i/8)i E [1,..., }. Let (G, Vi 9) be the result of the attack at magnitude e E E. We then define the adaptive attacker as:
(x) PGD,.
(11)
Where:
6* == maxe E E such that
Es Loy1 (F, + 6).8) - Es Cay1 (fo(z (0(x+66),))
(12)
In other words, we use the largest attack such that the increase in misclassification rate per unit attack magnitude is above the threshold 7, this not the case for any e E E, we elect not to As was described in the main text for the baseline case, sweep over a range of threshold values " when reporting results. When evaluating the expectations in Equation 12 we use sample of 100 noise instances. However, once is identified, we then use a different sample of 100 noise instances per training sample x when reporting the final accuracy: this is to de-correlate the attack generation of (1v.(x)) with the evaluation of the attack. (However, noise instances are kept constant over the sweep of ?). When reporting results (the upper bounds of the Wasserstein distances), we use as an upper bound on ||PGD, (I,, yi g) - =1|2, rather than using I|PGD.. (I, yi 9) æl|2 directly, Also, we upper bound the population expectation of e* (and therefore of || [|PG em (I. y: g) -x1l2) for each y with 99% confidence using the empirical expectation on the test set using Hoeffding bound, using the fact that 0 S e* S (2in)21177)
attack, and set (x)
Attack hyperparameters are taken from Salman et al. (2019): We use 20 attack steps, a step size of e e/10, and use 128 noise instances when computing gradients. We evaluate using 10% of each dataset.
F EXPERIMENT DETAILS FOR SECTION
As mentioned, for the certified models, use the released pre-trained ResNet1 10 models from Cohen et al. (2019) for CIFAR- 10 and train ResNet20 models in a similar manner for SVHN, using the same level of Gaussian Noise for training and testing. For empirical results, use the imple- mentation the & Carlini and Wagner (Carlini & Wagner 2017) attack provided by the IBM ART package (Nicolae et al. (2018) with default parameters (except for batch size which we 256 to increase processing speed.)
We also tested alternative attack, which is still strategic but does not require that measure the Wasserstein distance empirically. In this attack, we define Adv that if |[CW (at, y: g) - xiIe2 S ? always returns CW (x. yi g). and if |[CW(z, yi - x||2 > 7, instead returns x with probability ( Note that in this case, the perturbation | (2, yi g) - æ||2 is guaranteed to less than or equal to y in expectation for all x,, so y can be used as an upper bound on the Wasserstein distance. Results are shown in Figure 10
G FUNCTION P FOR DIFFERENT DISTRIBUTIONS
For an isometric Gaussian distribution (0,,
TV
erf( =
Proof. Due to the isometric symmetry of the Gaussian distribution and the lg norm, we may assume, without loss of generality, that A/ o2T) is obtained by shifting N/, a² T) only along the first
20

---

Published as a conference paper at ICLR 2023
Ez Adversarial Distribution Shift (Probabilistic Attacker)
1s Adversarial Distribution Shift (Probabilistic Attacker)
1.0
1.0
Smooth ing
Smoothing
Smosehing ing Notse 025
Smoothing Naise 0.23
Smooehing Noise 0.5
Smoothing Waise 0.5
Sencodi ing Nois 1.0
Smoothing Noise 1.0
Un undetended
Undeterded
Accurory
Accuracy
0.8
0.4
880
0.6
08
04
1.0
Wasserstein Bound (epsilon)
Wasserstain Bound (epailon)
(a) CIFAR-10
(h) SVHN
Figure 10:
Certified robustness to & Wasserstein distributional attacks. The undefended baseline
baseline is here attacked using the alternative attack formulation Adv' described in Section F
dimension. Therefore, the total variation of the two distributions is equal to the difference in the probability of normal random variable with variance o² being less than ||0||2/2 and ||012222 i... (2/oo) - ((-1|01|2/ot where & is the standard normal CDF.
OV 12)) = 4 (101l1/20)) - o ([-1|0||//00)
2 20(110|2/20) -
erf 2
=
For uniform distribution (4(0, b) between 0, and 0, + each dimension for b 2 (as used for the SV shift transformations), TV(2/(0, b), ()0 |101l1/b. When |001| is constrained, the volume of the overlap Letween/((0, b) and 6) minimized when the shift is only along one dimension.
H ADDITIVE COMPOSABILITY OF NATURAL TRANSFORMATIONS
In this section, we prove that the natural transformation CS, HS and SV defined in the paper all satisfy the additive composability property in condition (5)
Lemma 3. The transformation CS satisfies the additive composability property, ie, Vr M, 01 0g R33
CS(CS(z,,)), 01), = CS(2, 01 + 02).
((r'. b) HXW = CS(x, 01) and x" {(r"." "".""""""""""""""""""" b")()) HXX = CS(x', 02). We need to show that x" = CS(x, 01 + +2). Let Tmax, Jmax and brax be the maximum values of the red, green and blue channels respectively of and I maxx I'axx and by braax the same for z' From the definition of CS in Section 5.1 we have:
Proof. Let x = [(r, () H ") x'
2
20 Dij
20 bij
MAX Sip
MAX
MAX
2 r and r
28 g's
2 VV
94
by
MAXI
MAX
MAXI
where MAX
max (
Tmaxx 2 Jmnx , 29th b
and
MAX
max(2 pd 0 Imaxx 20 b ). From the definition of maxx have:
max:
28 rij
20 max Tay
20 F Fmax
Y'ax max = max
MAX
MAX
MAX
21

---

Published as a conference paper at ICLR 2023
Similarly,
f Jmax
20. bmax
Fmax
and
MAX Umax
MAX
Therefore,
max (2 02 mmax:
20 200
Imax, 20T +02 bmax)
MAX'
MAX
Substituting oy and MAX the expression for kj we get:
2 20t Ti
2 +02 T4
MAX'MAX
max
T maxx, 20 +
9max 201 +0 bmax)
Similarly,
2 209+08 96g
20 +00 big
3 max +0 Tmaxx 20
and K9
Imaxx 20 mmax)
max roa Tiaax 2 +00
Imax: 2 +0 b
Hence, x" CS(x, 01 + 02).
Lemma 4. The transformation SV satisfies the additive composabilityy property, i.e, Ve M, 01 0g E 1220
(v(SV(z,01). 02) = SV( O1 02).
Proof. Let F = {(h, 8, { d' = {(h, 8 )')e)) {(h, ) H.W =V((x' 02) in HSV format. We need to show that x" = SV(x, 0 + f2). Let Smean, Smax, Umean and Umax be the means and maximums of the saturation and brightness values of x and means maax U'maan and V Vaxx be the same for x', From the definition of SV in Section 5.2 have:
= SV(x,, 01) and x" =
8ij + (2 1) 1)8mean $/
r Vig + (2 1 1)
MAX 8/ + (2 1)smn
MAX
J 2// + (20 1)2mean
and
"
MAX'
MAX'
where MAX- max(smax (205
1) 8meany Umnax
(2 1)nmna)) and MAX' max($ +
(20) m)s'm Umax + (20)' 1)o'neau). From the definitions of s'meen and 8 we have:
8ig + (20
1)8mean mean 85j + (2 1)8mean 20 8mean
mean mean s/y = mean
MAX
MAX
MAX
Szj (2 1)smesn
max 8tj + (2 1) smean
Smax + (2
1) mean
5 max max 5/1 = max
MAX
MAX
MAX
Similarly,
20Y Umean
(20 1)unaa
V Umax
and
mean
MAX
MAX
Therefore,
MAX' = max S /max + -
1)s'mean mmax + (2 - 1)e'mean)
max Smax + (20)
1)8mean + (285 1)20(" Smean omnax + (2 1) -1)onean))
MAX
maxx mmax + (208+ +o. 1) 1)mmean
V + (2
1)bneea))
MAX
022
1)smean Vmax + (20 - -1)umesu + (208 1)2o8 ('eaa)) "mean)/MAX
max( S Smax
max Smax (2
1)8meau Unaax (2 +0% 1) 1)Unnaa)) ) /MAX.
22

---

Published as a conference paper at ICLR 2023
Substituting si mean and MAX in the expression for s'j, we get:
Sty + (2 m + (2 1)2a Smean
MAX'MAX
(20 -0 1) Smean
Sij
m (2
1) Smean: Umax (20% +02 1 meann)
Similarly,
Oij + (20% +0x 1)mmaa
1j m5 (299 +0
mmaan: Umax (20Y +02 1 Umman)
Hence, x² (xr 01 02).
I DETAILS FOR PLOTS IN FIGURE 2
The distribution shifts used to evaluate the empirical performance of the base models in Figure have been generated by first sampling an image from the original distribution D and then ran- domly transforming it images from the original distribution by adding a noise in the corresponding transformation space. The Wasserstein bound of these shifts be calculated by computing the expected perturbation size of the smoothing distribution. For example, the expected f2-norm of a 3-dimensional Gaussian vector is given by 2v/2 / V and expected -nomr a 2-dimensional vector sampled uniformly from [0, 6)2 is b.
The training and smoothing noise levels used for color shift, hue shift and SV shift are (0.8, 10.0), (180%, 180%) and (8.0, 12.0) respectively.
J
HUE SHIFT
Any RGB image can be alternatively represented in the HSV image format by mapping the (r, g, b) tuple for each pixel to point (h, 8, in a cylindrical coordinate system where the values h, and e represent the hue, saturation and brightness (value) of the pixel. The mapping from the RGB coordinate the HSV coordinate takes the [0, 1]3 color cube and transforms it into cylinder of unit radius and height. The hue values are represented as angles in [0, 2x) and the saturation and brightness values are in [0, 1]. Define hue shift of H x W sized image æ by angle 0 E [- v) in the HSV space that rotates each hue value by an angle and wraps around to the [0, 2T)) range. In appendix J] we show that the certified accuracy under hue shifts does not depend on the Wasserstein distance of the shifted distribution and report the certified accuracies obtained by various base models trained under different noise levels.
Define hue shift of an H x W sized image by an angle O E [- π] in the HSV space as:
HxW
HS(r, 0) = (w(h + s,),
I 2T
where w(x) = x 2x
which rotates each hue value by an angle 0 and wraps it around to the [0, 2x) range. It is easy to show that this transformation satisfies additive composability in condition (5) The Wasserstein distance is defined using the corresponding distance function dHs by taking the absolute value of the hue shift 10).
Lemma 5. The transformation HS satisfies the additive composability property, i.e., Vz M. 0, 02 m).
HS(HS(,, 0z), HS(,, 0, 02).
Proof. Let h be the hue value of the (i.j)th pixel of the image æ. Since the transformation only affects the hue values, ignore the other coordinates. The hue value after the transformation
23

---

Published as a conference paper at ICLR 2023
Hue Shift
0.8
Certined
0.-
900
100
Training Noise (max angle)
Figure 11: Certified accuracy under hue shift for different levels training noise. Since, the certified accuracy remains constant with respect the Wasserstein distance (c) of the shifted distribution, plot the certified accuracy of models trained with different noise levels 33.
HS(HS(z,,1), is given by
2 h A1
w(w(h +02) 02) = w h 01
+ 02
2x
Define a smoothing distribution that applies a random huc rotation sampled uniformly from the range [-m, ær. Since HS wraps the hue values around in the interval, the distributions of d and (h++0) 0) + for two hue values shifted by an angle f are both uniform in [0, 2x]. Thus, the smoothing distribution for two hue shifted images is the same which implies that e/ (d((1), x2)) 0 whenever d(<1, 22) )22)) is finite. Hence, from Theorem 1 we have (= (2 U2)] ] 2 (izi..))=((M for hue shifts. Since, the certified accuracy remains constant with respect to the Wasserstein distance of the shift, we just plot the certified accuracies obtained by various base models trained under different noise levels in Figure II] We plot the certified accuracies obtained by various models trained using random hue rotations picked uniformly from the range [-8, 38] for different values of the maximum angle 3 in the range. The certified accuracy roughly increases with the training noise achieving maximum of 87.9% for max angle 3 180 for the training noise level.
K RANDOM CHANNEL SELECTION
Consider a smoothing distribution that randomly picks one of the RGB channels with equal proba- bility, scales it so that the maximum pixel value in that channel is one and sets all the other channels to zero. This smoothing distribution invariant to the color shift transformation CS and thus, sat- isfies (/(d7 (x1, x22)
have [a-5(((2)] > Ex-D [z]) under this smoothing distribution for all Wasserstein bounds with re- spect to des. Figure plots the certified accuracies, using random channel selection for smoothing. achieved by models trained using Gaussian distributions of varying noise levels in the transforma- tion space. The certified accuracy roughly increases with the training noise achieving maximum of 87.1% for training noise of 0.8.
O whenever (21, is finite. Therefore, from Theorem
L EXPERIMENTAL DETAILS FOR SECTION 7
Our experimental setting is adapted from the "sample-wise perturbation" CIFAR-10 experiments in Huang et al. 2021) 1): hyperparameters are the same as in that work unless otherwise stated. For back- ground, Huang et al. (2021) creates unleamable dataset by performing the following "bi-level" minimization, to simultaneously train a proxy classifier model and create unlearnable examples:
min min (ct....,e.)
L(folx: +).
(13)
24

---

Published as a conference paper at ICLR 2023
Random Channel Selection
0.8
Certined Accuracy
02-
0000
Training Noise
Figure 12: Certified robustness against color shift using random channel selection as the smoothing distribution. Since, the certified accuracy remains constant with respect the Wasserstein distance (c) of the shifted distribution, we plot the certified accuracy of models trained with various levels of Gaussian noise in the transformation space.
In other words, in contrast with standard training, both the samples and the proxy classifier optimized to decrease the loss. New classifiers trained on the resulting samples fail to generalize unperturbed samples. In the experiments, as in Huang et (202I), the inner minimization over perturbations is performed for 20 steps over the entire dataset, for every one batch update step of the outer minimization. Training stops when training accuracy reaches a threshold value of 99%.
We now detail differences in experimental setup from Huang et al. (021
L.1 ADAPTATION TO & ATTACK SETTING
After each optimization step, we project e; 's into an l ball (of radius given by the Wasserstein bound e) rather than loo ball. We also use an Eg PGD step:
V.)((-)
e = e; + (.)12
(14)
Step size 7 was set as 0.1 times the total & e bound.
L.2 ADAPTATION TO OFFLINE SETTING
As discussed the test, we modify the algorithm such that the simultaneous training of the proxy model and generation of perturbations does not introduce statistical dependencies between perturbed training samples. This is especially important because, the victim later makes a train-validation split, this would introduce statistical dependencies between training and validation samples, making hard to generalize certificates to a test set.
To avoid this, construct four data splits:
Test set (10000 samples): The original CIFAR-10 test set. Never perturbed, only used in final model evaluation.
Proxy training set (20000 samples): Used for the optimization of the proxy classifier model parameters 0 in Equation and discarded afterward.
Training (20000 samples): Perturbed using one round of the the standard 20 steps of the inner optimization of Equation 13 while keeping 0 fixed.
Validation set (10000 samples): Perturbed using the same method as the "Training set."
The victim model is trained on the "Training Set" and evaluated on the "Validation set" and "Test set". We also tested on the clean (unperturhed) version of the validation set.
25

---

Published as a conference paper at ICLR 2023
L.3 ADAPTIVE ATTACK SETTING
When testing our smoothing algorithm, we tested two types of attacks:
Non-adaptive attack: the proxy model trained and perturbations are generated using undefended models without smoothing: only the victim policy applies smoothing noise
during training and evaluation.
Adaptive attack: In the minimization of Equation 13 the loss term L(fe(z; + ez). v.) is replaced by the expectation:
C(fo + + 6).
(15)
(0,
In other words, this models the expectation of smoothed model, like the victim classifier. This smoothed optimization is used in both the proxy model training. as well as the gener- ation of the training and validation sets. Following [alman al. (2019), which proposed similar adaptive attack for sample-wise smoothed classifiers we approximate the expecta- tion using small number of random perturbations, which are held fixed for the 20 steps of the inner optimization. In our experiments, we use 8 samples for approximation. Because, at large smoothing noises, this makes the attack much less effective, 20 steps of the outer maximization, rather than relying on the accuracy to reach 99%. (the maximum number of steps required to converge observed for the non-adaptive attack was 15).
cut off training after
L.4 RESULTS
Complete experimental results are presented Figure 13 All results are means of 5 independent runs, and error bars represent standard errors of the means.
M CONCLUSION
We show that it is possible to certify the distributional robustness of a general deep neural network without increasing its computational requirements. We obtain robustness guarantees with respect the Wasserstein distance of the distribution shift which is more suitable metric for out-of- distribution shifts than divergence measures such as KL--divergence and total variation. We only consider predefined distance functions in this work which may not be suitable for capturing more sophisticated distribution shifts such as perceptual changes. A future direction of research could be adapt our certificates for learnable transformations for domain generalization and adaptation.
26

---

Published as a conference paper at ICLR 2023
Undefended
1.0
Accuracy
0.4
0.2
Validation Acouracy
++-
Clean Test Accuracy
0.0
04
1.0
Wasserstein Bound (epsiion)
Non-Adaptive Attack, a
Adaptive Attack, 0.1
Accuracy
Accuracy
0.4
0.4
0.2
Unicamable Validation Accuracy Clean Test Accuracy
02
Unicamable Validation Accuracy Clean Test Accuracy
Certiteed Acourscy
Certitie Accuracy
8.00
8.0
Wasserstein Bound (epsilon)
Wasserstein (epsilan)
Non-Adaptin Adaptive Attack, 0.2
Adaptive Attack, 0.2
1.0
10
0.8
0.8
Accuracy
0.6
Accuracy
0.6
Unicamable dalioation Acourciy
Unkcamable Valization Accuracy
Clean Val dation Accuracy
Clean Valization Accuracy
Test Accuracy
Clean Test
Accurscy
Accuracy
08.0
622
0.4
0.8
1.0
08.0
022
0.6 Wassersteln Bound (epsilan)
0.4
0.8
1.0
Wasserstein Bound (epsilan)
Non-Adaptive Attack, a 0.4
Adaptive Attack, a
+
Unkkamabble Validation Accuracy
Unkeamatle Validation Accuracy
Clean Validation
Accuracy
Accuracy
Certifi tetiifed Accuracy
Certified Accuracy
Accuracy
Accuracy
0.4
0.2
02
88.0
3.0
08.
Wasserstein Bound (epsilon)
Bound (epsilan)
Figure 13: Complete Experimental results for unlearnaiility experiments.
27


Reviews:
[{"review_id": "zh9DaiK_pr", "reviewer": "Reviewer_fyNV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "From a high level viewpoint, the main result of this paper is a robustness guarantees on models under \"smoothing\": the paper makes the claim that by smoothing inputs, the difference between smoothed expectations under D and D' with a Wasserstein distance within epsilon is bounded by some function psi of epsilon satisfying a TV-distance \"lipshitz type bound\" for the smoothing operation. Some applications and discussions on color shifts, hue shifts, brightness shifts, etc., are provided in the paper. ", "summary_of_the_review": "Overall, I think the paper is well written but with several concerns as listed above. I would be happy to adjust my score after discussions with other reviewers and the authors. ", "strength_and_weaknesses": "Overall, the paper is adequately clear. \n\nSome comments on strengths are:\n1. The paper discusses the importance of robustness in machine learning with many examples and references to literature. \n2. The problem in question itself is an important topic and relevant to ICLR. The paper further contributes to the field by providing interesting insights and results.\n\nSome comments on weaknesses:\n1. Why is a bound between the difference of the expectations of smoothed versions meaningful? From a practical view, would it be more reasonable and interesting to have a result that somehow bounds a smoothed expectation with the original, unsmoothed expectation?\n2. Taking a brief look at the proof of Theorem 1, it appears that a concave increasing psi is required as an artifact of the proof; is there any additional insight/comments on other reasons why a concave increasing psi is necessary for the definition of (3) and its impact on Theorem 1?\n3. More insights can be added to the experiments. In particular, the paper provides calculations of certified accuracy for various examples, but comparisons are lacking. It is difficult to see if the \"certifications\" are tight. The practicality of these certifications also can use some more explanation.\n4. It would be helpful to include discussions on novelties in proof techniques, if any, within the main text.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RobwpchfpH", "reviewer": "Reviewer_ait3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the recent certified robustness theory with a simple procedure that randomizes the input of the model within a transformation space. It abandons the  $l_p$ distance change assumption, and does not need any restrictive assumptions or global Lipshitz. With the above theoretical analysis, this paper can provide performance guaranteed on the lower bound on the performance with distribution shift (Both OOD problem and adversarial attack). Experiments give specific guarantees for three natural shifts. Further experiments on the poisoned dataset also show empirical success.", "summary_of_the_review": "The work quality is good. In terms of methodology, this paper is an extension from the robustness domain. The theoretical results are interesting. Some experiments should be extended correspondingly.", "strength_and_weaknesses": "Strength:\n- The paper extends the certified robustness into the certified distribution shift robustness.\n- The paper proposes a very novel new scenario for the guarantee on the natural distribution shift.\n- The method is simple and the theory is solid which can even work on the unlearnable scenario.\n​\nWeakness:\n- The paper majorly focuses on how to extend the certified robustness into natural transformation. ​However, more discussions about what properties of models can impact the OOD robustness is also appreciated.\n- The experiment on the OOD data can be more comprehensive. Typically, many results are all drawn with the theoretical proof. The empirical analysis is not sufficient. With only CIFAR10 and SVHN datasets, it is not convincing enough to say whether those problems are a practical OOD problem. We can not say that the model trained with a larger dataset, imagenet, really suffers from this kind of natural shift problem. It is possible that the empirical performance can always have higher performance that the theoretical lower bound. In that way, the provable robustness may not be so important.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GzSGN1gDbiQ", "reviewer": "Reviewer_Ne1j", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The work proposes to certify for a network the robustness to change in the input distribution for bounded Wasserstein shift.", "summary_of_the_review": "The idea isn't groundbreaking but important and worthy of publication. Unfortunately, the authors use most of the paper on less important parts of the work and skip the important parts.", "strength_and_weaknesses": "Strength:\n- The paper is well-written and mostly easy to follow\n- The problem of provable-robustness guarantees is important, especially for DNN.\n- Giving a bound using Wasserstein distance can be stronger as it handles shifts that change the support\n\nWeaknesses:\n-  The work, more or less, reduces the Wasserstein distance to total variation (whose robustness was already explored previously by Ben-David et al) by smoothing. One issue is that smoothing can reduce performance, thus the robustness is on the smoothed classifier and not on the original classifier.\n- The paper talks about adversarial attacks but does not show these results in the main paper. I think these results are much more important than the results presented in the paper on color etc. and must be in the main paper.\n- All results should be compared to the empirical robustness (although maybe with fewer plots at once as it is too cluttered to understand). \n- I found sec. 6 trivial and misleading. If a classifier is guaranteed to be robust, then of course trying to fool it will fail. It is also misleading as hardness to learn normally is distributions over $(x,y)$ that learning algorithms fail to learn from which isn't the case. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster