summaries: A nice paper that clarifies the difference between the clean accuracy (accuracy of models on non-perturbed examples) and the robust accuracy (accuracy of models on adversarially perturbed examples) and it shows that changing the marginal distribution of the input data P(x) while preserving its semantic P(y|x) fixed affects the robustness of the model. Therefore, testing the robustness of the model should be performed in a careful manner. Comprehensive experiments were performed to show that changing the distribution of the MINST (smoothing) and CIFAR (saturation) data could lead to a significant difference in robust accuracy while the clean accuracy is almost steady. In addition, a set of experiments were performed in an attempt to search for the criteria required for choosing a proper dataset for testing adversarial attack to measure the robustness.

summaries: The paper is interesting and topical: robustness to adversarial input presentation (or shifts in training data itself, even those of the nature described by the authors 'semantic-lossless' shifts). Adversarial inputs are investigated under l-inf bounded perturbations, while multiclass classification on images is the target problem considered. The theoretical parts of the paper, assigning lack of adversarial robustness to the shape of the input distribution (Section 2) is the strongest part of the paper, adding some simple and important insights. Unfortunately, the empirical part of the paper is weakened by an over-reliance of (custom perturbations of ) the popular MNIST and CIFAR10 datasets (which are themselves based on larger sets). Furthermore, the basic conclusion as to causes and remedies of lack of robustness is not evident, and it is not evident that it has been sufficiently investigated. Shape yes, differences in perturbable volume not (how does that concur with Section 2?), and inter-class distance also not. Are we to base these conclusions on 2 perturbed datasets? How are readers to synthesize the final conclusion that robustness is a 'complex interaction of tasks and data', other than what they would already expect? In short, a valiant effort, and a good direction, but one that needs more work.

abstractText: Neural networks are vulnerable to small adversarial perturbations. Existing literature largely focused on understanding and mitigating the vulnerability of learned models. In this paper, we demonstrate an intriguing phenomenon about the most popular robust training method in the literature, adversarial training: Adversarial robustness, unlike clean accuracy, is sensitive to the input data distribution. Even a semantics-preserving transformations on the input data distribution can cause a significantly different robustness for the adversarial trained model that is both trained and evaluated on the new distribution. Our discovery of such sensitivity on data distribution is based on a study which disentangles the behaviors of clean accuracy and robust accuracy of the Bayes classifier. Empirical investigations further confirm our finding. We construct semantically-identical variants for MNIST and CIFAR10 respectively, and show that standardly trained models achieve comparable clean accuracies on them, but adversarially trained models achieve significantly different robustness accuracies. This counter-intuitive phenomenon indicates that input data distribution alone can affect the adversarial robustness of trained neural networks, not necessarily the tasks themselves. Lastly, we discuss the practical implications on evaluating adversarial robustness, and make initial attempts to understand this complex phenomenon.

authors:
A. Athalye
N. Carlini
D. Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

venue: International Conference on Machine Learning, pages 274–283.

authors:
A. Athalye
L. Engstrom
A. Ilyas
K. Kwok

title: Synthesizing robust adversarial examples

venue: arXiv preprint arXiv:1707.07397.

title: An elementary introduction to modern convex geometry

venue: Flavors of geometry, 31:1–58.

authors:
B. Biggio
I. Corona
D. Maiorca
B. Nelson
N. Šrndić
P. Laskov
G. Giacinto
F. Roli

title: Evasion attacks against machine learning at test time

venue: Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer.

title: A computational approach to edge detection

venue: IEEE Transactions on pattern analysis and machine intelligence, (6):679–698.

authors:
N. Carlini
D. Wagner

title: Defensive distillation is not robust to adversarial examples

venue: arXiv preprint arXiv:1607.04311.

title: Towards evaluating the robustness of neural networks

venue: Security and Privacy (SP), 2017 IEEE Symposium on, pages 39–57. IEEE.

authors:
G.W. Ding
L. Wang
X. Jin

title: AdverTorch v0.1: An adversarial robustness toolbox based on pytorch

venue: arXiv preprint arXiv:1902.07623

authors:
A. Erraqabi
A. Baratin
Y. Bengio
S. Lacoste-Julien

title: A3t: Adversarially augmented adversarial training

venue: arXiv preprint arXiv:1801.04055.

authors:
A. Fawzi
O. Fawzi
P. Frossard

title: Analysis of classifiers’ robustness to adversarial perturbations

venue: arXiv preprint arXiv:1502.02590.

title: Shake-shake regularization

venue: arXiv preprint arXiv:1705.07485.

authors:
J. Gilmer
L. Metz
F. Faghri
S.S. Schoenholz
M. Raghu
M. Wattenberg
I. Goodfellow

title: Adversarial spheres

venue: arXiv preprint arXiv:1801.02774.

authors:
I.J. Goodfellow
J. Shlens
C. Szegedy

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572.

authors:
R. Huang
B. Xu
D. Schuurmans
C. Szepesvári

title: Learning with a strong adversary

venue: arXiv preprint arXiv:1511.03034.

authors:
D.P. Kingma
J. Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980.

authors:
A. Kurakin
I. Goodfellow
S. Bengio

title: Adversarial machine learning at scale

venue: arXiv preprint arXiv:1611.01236.

title: The concentration of measure phenomenon

venue: Number 89. American Mathematical Soc.

authors:
A. Madry
A. Makelov
L. Schmidt
D. Tsipras
A. Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083.

authors:
Moosavi-Dezfooli
S.-M.
A. Fawzi
P. Frossard

title: Deepfool: a simple and accurate method to fool deep neural networks

venue: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2574–2582.

authors:
A. Raghunathan
J. Steinhardt
P. Liang

title: Certified defenses against adversarial examples

venue: arXiv preprint arXiv:1801.09344.

authors:
L. Schmidt
S. Santurkar
D. Tsipras
K. Talwar
A. Mądry

title: Adversarially robust generalization requires more data

venue: arXiv preprint arXiv:1804.11285.

authors:
A. Sinha
H. Namkoong
J. Duchi

title: Certifiable distributional robustness with principled adversarial training

venue: arXiv preprint arXiv:1710.10571.

authors:
C. Szegedy
W. Zaremba
I. Sutskever
J. Bruna
D. Erhan
I. Goodfellow
R. Fergus

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199.

title: Computer vision: algorithms and applications

venue: Springer Science & Business Media.

authors:
D. Tsipras
S. Santurkar
L. Engstrom
A. Turner
A. Madry

title: Robustness may be at odds with accuracy

venue: International Conference on Learning Representations.

authors:
D. Warde-Farley
I. Goodfellow

title: 11 adversarial perturbations of deep neural networks

venue: page 311.

authors:
E. Wong
Z. Kolter

title: Provable defenses against adversarial examples via the convex outer adversarial polytope

venue: International Conference on Machine Learning, pages 5283–5292.

authors:
H. Xiao
K. Rasul
R. Vollgraf

title: Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms

venue: arXiv preprint arXiv:1708.07747.

authors:
H. Xu
C. Caramanis
S. Mannor

title: Robustness and regularization of support vector machines

venue: Journal of Machine Learning Research, 10(Jul):1485–1510.

authors:
S. Zagoruyko
N. Komodakis

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146.

heading: 1 INTRODUCTION

text:
Neural networks have been demonstrated to be vulnerable to adversarial examples (Szegedy et al., 2013; Biggio et al., 2013). Since the first discovery of adversarial examples, great progress has been made in constructing stronger adversarial attacks (Goodfellow et al., 2014; Moosavi-Dezfooli et al., 2016; Madry et al., 2017; Carlini and Wagner, 2017). In contrast, defenses fell behind in the arms race (Carlini and Wagner, 2016; Athalye et al., 2017; 2018). Recently a line of works have been focusing on understanding the difficulty in achieving adversarial robustness from the perspective of data distribution. In particular, Tsipras et al. (2019) demonstrated the inevitable tradeoff between robustness and clean accuracy in some particular examples. Schmidt et al. (2018) showed that the sample complexity of “learning to be robust” learning could be significantly higher than that of “learning to be accurate”.
In this paper, we contribute to this growing literature from a new angle, by studying the relationship between adversarial robustness and the input data distribution. We focus on the adversarial training method, arguably the most popular defense method so far due to its simplicity, effectiveness and scalability (Goodfellow et al., 2014; Huang et al., 2015; Kurakin et al., 2016; Madry et al., 2017; Erraqabi et al., 2018). Our main contribution is the finding that adversarial robustness is highly sensitive to the input data distribution:

heading: A semantically-lossless shift on the data distribution could result in a drastically different robustness for adversarially trained models.

text:
Note that this is different from the transferability of a fixed model that is trained on one data distribution but tested on another distribution. Even retraining the model on the new data distribution may give us a completely different adversarial robustness on the same new distribution. This is also in sharp contrast to the clean accuracy of standard training, which, as we show in later sections, is insensitive to such shifts. To our best knowledge, our paper is the first work in the literature that demonstrates such sensitivity.
Our investigation is motivated by the empirical observations on the MNIST dataset and the CIFAR10 dataset. In particular, while comparable SOTA clean accuracies (the difference is less than 3%) are achieved by MNIST and CIFAR10 (Gastaldi, 2017), CIFAR10 suffers from much lower achievable robustness than MNIST in practice.1 Results of this paper consist of two parts. First in theory, we start with analyzing the difference between the regular Bayes error and the robust error, and show that the regular Bayes error is invariant to invertible transformations of the data distribution, but the robust error is not. We further prove that if the input data is uniformly distributed, then the perfect decision boundary cannot be robust. However, we also manage to find a robust model for the binarized MNIST dataset (semantically almost identical to MNIST, later described in Section 3). The certification method by Wong and Kolter (2018) guarantees that this model achieves at most 3% robust error. Such a sharp contrast suggests the important role of the data distribution in adversarial robustness, and leads to our second contribution on the empirical side: we design a series of augmented MNIST and CIFAR10 datasets to demonstrate the sensitivity of adversarial robustness to the input data distribution.
Our finding of such sensitivity raises the question of how to properly evaluate adversarial robustness. In particular, the sensitivity of adversarial robustness suggests that certain datasets may not be sufficiently representative when benchmarking different robust learning algorithms. It also raises serious concerns about the deployment of believed-to-be-robust training algorithm in a real product. In a standard development procedure, various models (for example different network architectures) would be prototyped and measured on the existing data. However, the sensitivity of adversarial robustness makes the truthfulness of the performance estimations questionable, as one would expect future data to be slightly shifted. We illustrate the practical implications in Section 4 with two practical examples: 1) the robust accuracy of PGD trained model is sensitive to gamma values of gamma-corrected CIFAR10 images. This indicates that image datasets collected under different light conditions may have different robustness properties; 2) both as a “harder” version of MNIST, the fashion-MNIST (Xiao et al., 2017) and edge-fashion-MNIST (an edge detection variant described in Section 4.2) exhibit completely different robustness characteristics. This demonstrates that different datasets may give completely different evaluations for the same algorithm.
Finally, our finding opens up a new angle and provides novel insights to the adversarial vulnerability problem, complementing several recent works on the issue of data distributions’ influences on robustness. Tsipras et al. (2019) hypothesize that there is an intrinsic tradeoff between clean accuracy and adversarial robustness. Our studies complement this result, showing that there are different levels of tradeoffs depending on the characteristics of input data distribution, under the same learning settings (training algorithm, model and training set size). Schmidt et al. (2018) show that different data distributions could have drastically different properties of adversarially robust generalization, theoretically on Bernoulli vs mixtures of Gaussians, and empirically on standard benchmark datasets. From the sensitivity perspective, we demonstrate that being from completely different distributions (e.g. binary vs Gaussian or MNIST vs CIFAR10) may not be the essential reason for having large robustness difference. Gradual semantics-preserving transformations of data distribution can also cause large changes to datasets’ achievable robustness. We make initial attempts in Section 5 to further understand this sensitivity. We investigated perturbable volume and inter-class distance as the natural causes of the sensitivity; model capacity and sample complexity as the natural remedies. However, the complexity of the problem has so far defied our efforts to give a definitive answer.

heading: 1.1 NOTATION AND PROBLEM SETUP

text:
We specifically consider the image classification problem where the input data is inside a high dimensional unit cube. We denote the data distribution as a joint distribution P(x, y), where x ∈ [0, 1]d, d is the number of pixels, and y ∈ {1, 2, . . . , k} is the discrete label. We assume the support of x is the whole pixel space [0, 1]d. When x is a random noise (or human perceptually unclassifiable image), one can think of P(y |x) being closed to uniform distribution on labels. In the standard setting, the samples (xi, yi) can be interpreted as xi is independently sampled from the marginal distribution P(x), and then yi is sampled from P(x |xi). In this paper, we discuss P(x)’s influences on adversarial robustness, given a fixed P(y|x).
1After PGD adversarial training (Madry et al., 2017), MNIST has 89.3% accuracy under perturbation δ with ‖δ‖∞ ≤ 0.3 under the strongest PGD attack, but CIFAR10 has only 45.8% accuracy, even under a much smaller δ with ‖δ‖∞ ≤ 8/255.
In our experiments, we only discuss the whitebox robustness, as it represents the “intrinsic” robustness. We use models learned by adversarially augmented training (Madry et al., 2017) (PGD training), which has the SOTA whitebox robustness. We consider bounded `∞ attack as the attack for evaluating robustness for 2 reasons: 1) PGD training can defend against `∞ relatively well, while for other attacks, how to train a robust model is still an open question; 2) in the image domain `∞ attack is the mostly widely researched attack.
Let H denote the universal set of all the measurable functions. Given a joint distribution P(x, y) on the space X × Y , we define the Bayes error R∗ = infh∈H EP(x,y)L(y;h(x)) = R∗(P(x, y)), where L is the objective function. In other words, Bayes error is the error of the best possible classifier we can have, h∗, without restriction on the function space of classifiers. We further define (adversarial) robust error RR(h) = EP(x,y) max‖δ‖∞< L(y;h(x+ δ)) = RR(P(x, y)). We denote RR∗ = RR(h∗) to be the robust error achieved by the Bayes classifier h∗. For simplicity, we assume our algorithm can always learn h∗, which reduces clean accuracy to be (1 − Bayes error), and robust accuracy of the Bayes classifier to be (1−RR∗).

heading: 2 THEORETICAL ANALYSES AND PROVABLE CASES

text: As mentioned in the introduction, although the SOTA clean accuracies are similar for MNIST and CIFAR10, the robust accuracy on CIFAR10 is much more difficult to achieve, which indicates the different behaviors of the clean accuracy and robust accuracy. The first result in this section is to further confirm this indication in a simple setting, where the clean accuracy remains the same but the robust accuracy completely changes under a distribution shift. Based on results from the concentration of measure literature, we further show that under uniform distribution, no algorithm can achieve good robustness, as long as they have high clean accuracy. On the other hand, we examine the performance of a verifiable defense method on binarized MNIST (pixels values rounded to 0 and 1), and the result suggests the exact opposite: provable adversarial robustness on a MNISTlike dataset is achievable. Such contrast thus suggests the important role of the data distribution in achieving adversarial robustness.

heading: 2.1 DISENTANGLE CLEAN ACCURACY AND ROBUST ACCURACY

text:
One immediate result is that Bayes error remains the same under any distribution shift induced by an injective map T : X → X . To see that, simply note that T−1 exists and h∗ ◦ T−1 gives the same Bayes error for the shifted distribution. However, such invariance property does not hold for the robust error of the Bayes classifier. Furthermore, the following two examples show that Bayes error can have completely different behavior from its robust error. Although both examples have 0 Bayes error, they have completely different robust errors. Example 1. Assume x is uniformly distributed in [0, 1]d and y = 1, for all x with x>e1 > 1/2 and y = 0, for x>e1 ≤ 1/2, where e1 is the one-hot vector. We use the 0-1 loss here. Note that the Bayes error decision boundaries are given by the following hyperplane: HP1 = {x ∈ [0, 1]d : x1 = 0}, and thus
R∗ = 0; RR∗ = 2 ,
under the budget ‖δ‖∞ < . In this case, the robust error is tolerable and relatively robust measured by the fraction of points that are successfully attacked, 2 .
Moreover, consider an injective map T which maps {x : x>e1 > 1/2} to {x : x>1 > d2}, and {x : x>e1 ≤ 1/2} to {x : x>1 ≤ d2}
2. The Bayes error on the new distribution remains 0, as T is invertible. In contrast, the robust error is much worse. In fact,
RR∗ ≥ 1− 1 4d 2 .
Remark 2.1. Note that here the robust error of the Bayes classifier will grow to 1 as the dimensionality increases, for a fixed budget .

heading: 2.2 DIFFICULTY IN ACHIEVING ROBUSTNESS

text:
Example 1 shows that good clean accuracy does not necessary lead to good robust accuracy. In contrast, we will show in this section that achieving a good robust accuracy is impossible given uniformly distributed data, as long as we ask for good clean accuracies. Our tool are classical results from the concentration of measure (Ledoux, 2005).
2Such map can be easily constructed.
Let A := {x ∈ RN |d(x,A) < } denote the -neighborhood of the nonempty set A, where d(x,A) is the distance from x to the set A. Theorem 2.1 provides a lower bound on the mass in A . Theorem 2.1 (Concentration of Measure on the Unit Cube and the Unit Ball). Let [0, 1]d denote the unit d-cube and Bd denote the Euclidean unit d-ball, both equipped with uniform probability distributions. Let > 0. Then for any A ⊂ [0, 1]d with P(A) ≥ 1/2, we have:
P(A ) ≥ Φ( √ 2π + Φ−1(P(A))) ≥ 1− e−π 2
(1)
For any B ⊂ Bd, with P(B) ≥ 1/2,
P(B ) ≥ 1− 1
P(B) (1− δ`2( ))2d ≥ 1−
1
P(B) e−2d(
2− √
3 3 ) 2
(2)
where δ`2( ) = 1− √ 1− 24 and Φ is the standard normal cumulative distribution function.
Based on Theorem 2.1 we can now show that under some circumstances, no algorithm that achieves can perfect clean accuracy can also achieve a good robust accuracy. Example 2 (Vulnerability Guarantee). Consider the joint distribution P(x, y), where the input data x is uniformly distributed on [0, 1]d and label y has 10 classes. Further assume the marginal distribution of y is also uniform3. Theorem 2.1 implies that under `2 adversarial attack with = 0.5, at least 94 % of the samples are ether wrongly classified or can be successfully attacked for a classifier with perfect clean accuracy.
Furthermore, if d = 3× 32× 32, A parallel calculation for P(x, y) on the Bd domain gives: under `2 adversarial attack with = 0.09 , at least 97 % of the the samples are ether wrongly classified or can be successfully attacked for a classifier with perfect clean accuracy.
On the one hand, Theorem 2.1 and Example 2 suggest that the uniform distribution on [0, 1]d enjoys more robustness than the uniform distribution on Bd, and it is not affected by the high dimensionality. This may partially explain why MNIST is more adversarially robust than CIFAR10, as the distribution of x in CIFAR10 is “closer” to Bd than to [0, 1]d. On the other hand, while not completely sharp, they also suggest the intrinsic difficulty in achieving good robust accuracy.
Note that one limit of Theorem 2.1 and Example 2 is the uniform distribution assumption, which is surely not true for natural images. Indeed, although rigorously developed, Theorem 2.1 and Example 2 do not explain certain empirical observations. Following Wong and Kolter (2018), we train a provably4 robust model on a binarized MNIST dataset (bMNIST) 5. Our experiments shows that the learned model achieves 3.00% provably robust error on bMNIST test data, while maintaining 97.65% clean accuracy. Details of this experiment in described in Appendix B.2.
The above MNIST experiment and Example 2 suggest the essential role of the data distribution in achieving good robust and clean accuracies. While it is hard to completely answer the question what geometric properties differentiate the concentration rates between the ball/cube in high dimension and the distribution of bMNIST, we remark that one obvious difference is the distance distributions in both spaces. Could the distance distributions explain the differences in clean and robust accuracies? Note that the same method can only achieve 37.70% robust error on original MNIST data, and even higher error on CIFAR10, which further supports this hypothesis. In the rest of this paper, we further investigate the dependence of robust accuracy on the distribution of real data.

heading: 3 ROBUSTNESS ON DATASETS VARIANTS WITH DIFFERENT INPUT DISTRIBUTIONS

text:
Section 2.2 clearly suggests that the data distribution plays an essential role in the achievable robust accuracy. In this section we carefully design a series of datasets and experiments to further study its influence. One important property of our new datasets is that they have different P(x)’s while keep P(y|x) reasonably fixed, thus these datasets are only different in a “semantic-lossless” shift. Our experiments reveal an unexpected phenomenon that while standard learning methods manage to achieve stable clean accuracies across different data distributions under “semantic-lossless” shifts, however, adversarial training, arguably the most popular method to achieve robust models, loses this
3but their joint distribution is not necessary uniform. 4“Provably” means that the robust accuracy of the model can be rigorously proved. 5It is created by rounding all pixel values to 0 or 1 from the original MNIST
desirable property, in that its robust accuracy becomes unstable even under a “semantic-lossless” shift on the data distribution.
We emphasize that different from preprocessing steps or transfer learning, here we treat the shifted data distribution as a new underlying distribution. We both train the models and test the robust accuracies on the same new distribution.

heading: 3.1 SMOOTHING AND SATURATION

text:
We now explain how the new datasets are generated under “semantic-lossless” shifts. In general, MNIST has a more binary distribution of pixels, while CIFAR10 has a more continuous spectrum of pixel values, as shown in Figure 1a and 1b. To bridge the gap between these two datasets that have completely different robust accuracies, we propose two operations to modify their distribution on x: smoothing and saturation, as described below. We apply different levels of “smoothing” on MNIST to create more CIFAR-like datasets, and different levels of “saturation” on CIFAR10 to create more “binary” ones. Note that we would like to maintain the semantic information of the original data, which means that such operations should be semantics-lossless and not arbitrarily wide.
Smoothing is applied on MNIST images, to make images “less binary”. Given an image xi, its smoothed version x̃i(s) is generated by first applying average filter of kernel size s to xi to generate an intermediate smooth image, and then take pixel-wise maximum between xi and the intermediate smooth image. Our MNIST variants include the binarized MNIST and smoothed MNIST with different kernel sizes. As shown in Figure 1c, all MNIST variants still maintain the semantic information in MNIST, which indicates that P(y | x̃(s)) should be similar to P(y |x). It is thus reasonable to assume that yi is approximately sampled from P(y | x̃(s)), and as such we assign yi as the label of x̃(s). Note that all the data points in the binarized MNIST are on the corners of the unit cube. For the smoothed versions, pixels on the digit boundaries are pushed off the corner of the unit cube.
Saturation of the image x is denoted by x̂(p), and the procedure is defined as below:
x̂(p) = sign(2x− 1) |2x− 1| 2 p
2 +
1 2 ,
where all the operations are pixel-wise and each element of x̂(p) is guaranteed to be in [0, 1]. Saturation is used to generate variants of the CIFAR10 dataset with less centered pixel values. For different saturation level p’s, one can see from Figure 1d that x̂(p) is still semantically similar to x in the same classification task. Similarly we assign yi as the label of x̂ (p) i . One immediate property about x̂ (p) is that it pushes x to the corners of the data domain where the pixel values are either 0 or 1 when p ≥ 2, and pull the data to the center of 0.5 when p ≤ 2. When p = 2 it does not change the image, and when p =∞ it becomes binarization.

heading: 3.2 EXPERIMENTAL SETUPS

text:
In this section we use the smoothing and saturation operations to manipulate the data distributions of MNIST and CIFAR10, and show empirical results on how data distributions affects robust accuracies of neural networks trained on them. Since we are only concerned with the intrinsic robustness of neural networks models, we do not consider methods like preprocessing that tries to remove perturbations or randomizing inputs. We perform standard neural network training on clean data to measure the difficulty of the classification task, and projected gradient descent (PGD) based adversarial training (Madry et al., 2017) to measure the difficulty to achieve robustness.
By default, we use LeNet5 on all the MNIST variants, and use wide residual networks (Zagoruyko and Komodakis, 2016) with widen factor 4 for all the CIFAR10 variants. Unless otherwise specified, PGD training on MNIST variants and CIFAR10 variants all follows the settings in Madry et al. (2017). Details of network structures and training hyperparameters can be found in Appendix B.
We evaluate the classification performance using the test accuracy of standardly trained models on clean unperturbed examples, and the robustness using the robust accuracy of PGD trained model, which is the accuracy on adversarially perturbed examples. Although not directly indicating robustness, we report the clean accuracy on PGD trained models to indicate the tradeoff between being accurate and robust. To understand whether low robust accuracy is due to low clean accuracy or vulnerability of model, we also report robustness w.r.t. predictions, where the attack is used to perturb against the model’s clean prediction, instead of the true label. We use `∞ untargeted PGD attacks (Madry et al., 2017) as our adversary, since it is the strongest attack in general based on our
(a) Pixel value histogram (log scale in y) of MNIST variants, from left to right: original, smoothed with kernel size 2, 3, 4, 5 (b) Pixel value histogram (log scale in y) of CIFAR10 variants, from left to right: original, saturation level 4, 8, 16, 64
experiments. Unless otherwise specified, PGD attacks on MNIST variants run with = 0.3, step size of 0.01 and 40 iterations, and runs with = 8/255, step size of 2/255 and 10 iterations on CIFAR10 variants , same as in Madry et al. (2017). We use the PGD attack implementation from the AdverTorch toolbox (Ding et al., 2019).

heading: 3.3 SENSITIVITY OF ROBUST ACCURACY TO DATA TRANSFORMATIONS

text:
Results on MNIST variants are presented in Figure 2a 6. The clean accuracy of standard training is very stable across different MNIST variants. This indicates that their classification tasks have similar difficulties, if the training has no robust considerations. When performing PGD adversarial training, clean accuracy drops only slightly. However, both robust accuracy and robustness w.r.t. predictions drop significantly. This indicates that as smooth level goes up, it is significantly harder to achieve robustness. Note that for binarized MNIST with adversarial training, the clean accuracy and the robust accuracy are almost the same. Indicating that getting high robust accuracy on binarized MNIST does not conflict with achieving high clean accuracy. This result conforms with results of provably robust model having high robustness on binarized MNIST described in Section 2.
CIFAR10 result tell a similar story, as reported in Figure 2b 6. For standard training, the clean accuracy maintains almost at the original level until saturation level 16, despite that it is already perceptually very saturated. In contrast, PGD training has a different trend. Before level 16, the robust accuracy significantly increases from 43.2% until 79.7%, while the clean test accuracy drops only in a comparatively small range, from 85.4% to 80.0%. After level 16, PGD training has almost the same clean accuracy and robust accuracy. However, robustness w.r.t. predictions still keeps increasing, which again indicates the instability of the robustness. On the other hand, if the saturation level is smaller than 2, we get worse robust accuracy after PGD training, e.g. at saturation level 1 the robust accuracy is 33.0%. Simultaneously, the clean accuracy maintains almost the same.
Note that after saturation level 64 the standard training accuracies starts to drop significantly. This is likely due to that high degree of saturation has caused “information loss” of the images. Models trained on highly saturated CIFAR10 are quite robust and the gap between robust accuracy and robustness w.r.t. predictions is due to lower clean accuracy. In contrast, In MNIST variants, the
6 Exact numbers are listed in Table 2 and 3 in Appendix C.
robustness w.r.t. predictions is always almost the same as robust accuracy, indicating that drops in robust accuracy is due to adversarial vulnerability.
From these results, we can conclude that robust accuracy under PGD training is much more sensitive than clean accuracy under standard training to the differences in input data distribution. More importantly, a semantically-lossless shift on the data transformation, while not introducing any unexpected risk for the clean accuracy of standard training, can lead to large variations in robust accuracy. Such previously unnoticed sensitivity raised serious concerns in practice, as discussed in the next section.

heading: 4 PRACTICAL IMPLICATIONS

text: Given adversarial robustness’ sensitivity to input distribution, we further demonstrate two practical implications: 1) Robust accuracy could be sensitive to image acquisition condition and preprocessing. This leads to unreliable benchmarks in practice; 2) When introducing new dataset for benchmarking adversarial robustness, we need to carefully choose datasets with the right characteristics.

heading: 4.1 ROBUST ACCURACY IS SENSITIVE TO GAMMA CORRECTION

text:
The natural images are acquired under different lighting conditions, with different cameras and different camera settings. They are usually preprocessed in different ways. All these factors could lead to mild shifts on the input distribution. Therefore, we might get very different performance measures when performing adversarial training on images taken under different conditions. In this section, we demonstrate this phenomenon on variants of CIFAR10 images under different gamma mappings. These variants are then used to represent image dataset acquired under different conditions. Gamma mapping is a simple element-wise operation that takes the original image x, and output the gamma mapped image x̃(γ) by performing x̃(γ) = xγ . Gamma mapping is commonly used to adjust the exposure of an images. We refer the readers to Szeliski (2010) on more details about gamma mappings. Figure 3a shows variants of the same image processed with different gamma values. Lower gamma value leads to brighter images and higher gamma values gives darker images, since pixel values range from 0 to 1. Despite the changes in brightness, the semantic information is preserved.
We perform the same experiments as in the saturated CIFAR10 variants experiment in Section 3. The results are displayed in Figure 3a. Accuracies on clean data almost remain the same across different gamma values. However, under PGD training, both accuracy and robust accuracy varies largely following different gamma values.
These results should raise practitioners’ attention on how to interpret robustness benchmark “values”. For the same adversarial training setting, the robustness measure might change drastically between image datasets with different “exposures”. In other words, if a training algorithm achieves good robustness on one image dataset, it doesn’t necessarily achieve similar robustness on another semantically-identical but slightly varied datasets. Therefore, the actual robustness could either be significantly underestimated or overestimated.
This raises the questions on whether we are evaluating image classifier robustness in a reliable way, and how we choose benchmark settings that can match the real robustness requirements in practice. This is an important open question and we defer it to future research.

heading: 4.2 CHOICE OF DATASETS FOR EVALUATING ROBUSTNESS

text:
As discussed, evaluating robustness on a suitable dataset is important. Here we use fashion-MNIST (fMNIST) (Xiao et al., 2017) and edge-fashion-MNIST (efMNIST) as examples to analyze characteristics of “harder” datasets. The edge-fashion MNIST is generated by running Canny edge detector (Canny, 1986) with σ = 1 on the fashion MNIST images. Figure 3b shows examples of fMNIST and efMNIST. We performed the same standard training and PGD training experiments on both fMNIST and efMNIST as we did on MNIST. Figure 3b shows the results. We can see that fMNIST exhibit similar behavior to CIFAR10, where the test accuracy is significantly affected by PGD training and the gap between robust accuracy and accuracy is large. On the other hand, efMNIST is closer to the binarized MNIST: the accuracy is affected very little by PGD training, along with an insignificant difference between robust accuracy and accuracy.
Both fMNIST and efMNIST can be seen as a “harder” MNIST, but they are harder in different ways. One one hand, since efMNIST results from the edge detection run on fMNIST, it contains less information. It is therefore harder to achieve higher accuracy on efMNIST than on fMNIST, where richer semantics is accessible. However, fMNIST’s richer semantics makes it better resembles natural images’ pixel value distribution, which could lead to increased difficulty in achieving
adversarial robustness. efMNIST, on the other hand, can be viewed as a set of “more complex binary symbols” compared to MNIST or binarized MNIST. It is harder to classify these more complex symbols. However, it is easy to achieve high robustness due to the binary pixel value distribution.
To sum up, when introducing new dataset for adversarial robustness, we should not only look for a “harder” one, but we also need to consider whether the dataset is “harder in the right way”.

heading: 5 ATTEMPTS TO UNDERSTAND THE PHENOMENON

text: In this section, we make initial attempts to understand the sensitivity of adversarial robustness. We use CIFAR10 variants as the running example, but these analyses apply to MNIST variants as well. Saturation pushes pixel values towards 0 or 1, i.e. towards the corner of unit cube, which naturally suggests two potential factors for the change in robustness. 1) the “perturbable volume” decreases; 2) distances between data examples increases. Intuitively, both could be related to the increasd robustness. We analyze them and show that although they are correlated with robustness change, none of them can fully explain the observed phenomena. We then further examine the possibility of increasing robust accuracy on less robust datasets by having larger models and more data.

heading: 5.1 ON THE INFLUENCE OF PERTURBABLE VOLUME

text: Saturation moves the pixel values towards 0 and 1, therefore pushing the data points to the corners of the unit cube input domain. This makes the valid perturbation space to be smaller, since the space of perturbation is the intersection between the -`∞ ball and the input domain. Due to high dimensionality, the volume of “perturbable region” changes drastically across different saturation levels. For example, the average log perturbable volume 7 of original CIFAR10 images are -12354, and the average log perturbable volume of∞-saturated CIFAR10 is -15342, which means that the perturbable volume differs by a factor of 22990 = 2(−12352−(−15342)). If the differences in perturbable volume is a key factor on the robustness’ sensitivity, then by allowing the attack to go beyond the domain boundary 8, the robust accuracies across different saturation levels should behave similarly again, or at least significantly differ from the case of box constrained attacks. We performed PGD attack allowing the perturbation to be outside of the data domain boundary, and compare the robust accuracy to what we get for normal PGD attack within domain boundary. We found that the expected difference is not observed, which serves as evidence that differences in perturbable volume are not causing the differences in robustness on the tested MNIST and CIFAR10 variants.

heading: 5.2 ON THE INFLUENCE OF INTER-CLASS DISTANCE

text:
When saturation pushes data points towards data domain boundaries, the distances between data points increase too. Therefore, the margin, the distance from data point to the decision boundary,
7Definition of “log perturbable volume” and other detailed analysis of perturbable volume are given in Appendix D.1 and Table 7.
8So we have a controlled and constant perturbable volume across all cases, where the volume is that of the -`∞ ball
could also increase. We use the “inter-class distance” as an approximation. Inter-class distance 9 characterizes the distances between each class to rest of classes in each dataset. Intuitively, if the distances between classes are larger, then it should be easier to achieve robustness. We also observed (in Appendix D.2.1 Figure 5) that inter-class distances are positively correlated with robust accuracy. However, we also find counter examples where datasets having the same inter-class distance exhibit different robust accuracies. Specifically, We construct scaled variants of original MNIST and binarized MNIST, such that their inter-class distances are the same as smooth-3, smooth-4, smooth-5 MNIST. The scaling operation is defined as x̃(α) = α(x − 0.5) + 0.5, where α is the scaling coefficient. When α < 1. each dimension of x is pushed towards the center with the same rate. Table 1 shows the results. We can see that although having the same interclass distances, the smoothed MNIST is still less robust than the their correspondents of scaled binarized MNIST and original MNIST. This indicates the complexity of the problem, such that a simple measure like inter-class distance cannot fully characterize robustness property of datasets, at least on the variants of MNIST.

heading: 5.3 ON THE REQUIRED MODEL CAPACITY AND SAMPLE COMPLEXITY

text:
In practice, it is unclear how far robust accuracy of PGD trained model is from adversarial Bayes error RR∗ for the given data distribution. In the case RR∗ is not yet achieved, there is a nonexhaustive list that we can improve upon: 1) use better training/learning algorithms; 2) increase the model capacity; 3) train on more data. Finding a better learning algorithm is beyond the scope of this paper. Here we inspect 2) and 3) to see if it is possible to improve robustness by having larger model and more data. For model capacity, we use differently sized LeNet5 by multiplying the number of channels at each layer with different widen factors. These factors include 0.125, 0.25, 0.5, 1, 2, 4. On CIFAR10 variants, we use WideResNet with widen factors 0.25, 1 and 4. For sample complexity, we follow the practice in Section 3 except that we use a weight decay value of 0.002 to prevent overfitting. For both MNIST and CIFAR10, we test on 1000, 3000, 9000, 27000 and entire training set. Both model capacity and sample complexity results are shown in Figure 4.
For MNIST, both training and test accuracies of clean training are invariant to model sizes, even we only use a model with widen factor 0.125. In slight contrast, both the training and test accuracy of PGD training increase as the model capacity increases, but it plateaus after widen factor 1 at an almost 100% accuracy. For robust accuracy, training robust accuracy kept increasing as model gets larger until the value is close to 100%. However, test robust accuracy stops increasing after widen factor 1, additional model capacity leads to larger (robust) generalization gap. When we vary the size of training set, the model can always fit the training set well to almost 100% clean training accuracy under standard training. The clean test accuracy grows as the training set size get larger. Training set size has more significant impact on robust accuracies of PGD trained models. For most MNIST variants except for binarized MNIST, training robust accuracy gradually drops, and test robust accuracy gradually increases as the training set size increases. This shows that when training set size is small, PGD training overfits to the training set. As training set gets larger, the generalization gap becomes smaller. Both training and test robust accuracies plateau after training set size reaches 27000. Indicating that increasing the training set size might not help in this setting. In conclusion, for MNIST variants, increasing training set size and model capacity does not seem to help beyond a certain point. Therefore, it is not obvious on how to improve robustness on MNIST variants with higher smoothing levels.
CIFAR10 variants exhibit similar trends in general. One notable difference is that for PGD training, the training robust accuracy does not plateau as model size increases. However the test robust accu-
9The calculation of “inter-class distance” and other detailed analyses are delayed to Appendix D.2.1 and Fig 5. Also note that our inter-class distance is similar to the “distinguishability” in Fawzi et al. (2015), which also measures the distance between classes to quantify easiness of achieving robustness on a certain dataset.
racy plateaus after widen factor 1. Also when training set size increases, the training robust accuracy drops and test robust accuracy increases with no plateau present. These together suggest that having more training data and training a larger model could potentially improve the robust accuracies on CIFAR10 variants. One interesting phenomenon is that binarized MNIST and∞-saturated CIFAR10 has different sample complexity property, despite both being “cornered” datasets. This indicates that the although binarization can largely influence robustness, it does not decide every aspect of it, such as sample complexity. This complex interaction between the classification task and input data distribution is still to be understood further.

heading: 6 CONCLUSION

text:
In this paper we provided theoretical analyses to show the significance of input data distribution in adversarial robustness, which further motivated our systematic experiments on MNIST and CIFAR10 variants. We discovered that, counter-intuitively, robustness of adversarial trained models are sensitive to semantically-preserving transformations on data. We demonstrated the practical implications of our finding that the existence of such sensitivity questions the reliability in evaluating robust learning algorithms on particular datasets. Finally, we made initial attempts to understand this sensitivity.
Acknowledgement We thank Marcus Brubaker for many helpful discussions. We also thank Junfeng Wen and Avishek (Joey) Bose for useful feedbacks on early drafts of the paper.

heading: A PROOFS

text:
A.1 PROOF FOR EXAMPLE 1
Proposition A.1 (Existence of Non-Adversarially Robust Decision Boundary). Let x be uniformly distributed on [0, 1]d and y = 1, for all x such that x>1 > d2 and y = 0 otherwise. Consider adversarial attack under budget ‖δ‖∞ < . Then for zero-one loss L:
RR∗ = EP(x,y) max ‖δ‖∞< L(Y ;h∗(x+ δ)) ≥ 1− 1 4d 2
Proof. The argument is well-known in concentration of measure. We provide here for the sake of completeness and adapt it to the context. The hyperplane HP2 = {x ∈ [0, 1]d : X>1 = d2} defines the decision boundary. We first compute the orthogonal distance of a given point y = (y1, y2, · · · , yd) = (x1 + δ1, x2 + δ2, · · · , xd + δd) to HP2. The point y is the perturbed point within budget ‖δ‖∞ < . The vector 1 is orthogonal to HP2. Pick any point x ∈ HP2, the orthogonal distance from y to HP2 is:
`2(y,HP2) = ‖Proj1(y − x)‖ = ‖1 (y − x)>1
1>1 ‖
= |y >1− x>1 ‖1‖ |
= |δ >1 ‖1‖ |
= | y>1− d2√
d |
The last two equations show that the `2 distance under an `∞ attack can grow at the rate of √ d, for this particular hyperplane HP2.
Now we take the expectation over [0, 1]d, and note that expectation of the uniform distribution over a product space [0, 1]d is the same as taking expectation on each dimension (Fubini’s theorem), picking each random variable coordinatewise uniformly from [0, 1].
E[`22(y,HP2)] = E[( y>1− d2
d )2] =
1 d E[( d∑ i=1 yi − d 2 )2]
= 1
d V[ d∑ i=1 yi] = 1 d d∑ i=1 V[yi] = 1 4
Then we apply Markov’s inequality, for all real number t > 0:
P(`2(x,H) ≥ √ t) = P(`2(x,H)2 ≥ t) ≤ 1
4t Finally, we observe that the longest (in terms of `2 norm) such `∞ attacks vector to HP2 are parallel to the normal vector 1 to HP2. They have `2 distance √ d. The set these attacks cover is
characterized by {x ∈ [0, 1]d : `∞(x,H) ≤ } = {x ∈ [0, 1]d : `2(x,H) ≤ √ d}.
Let t = 2d, we have:
P(`2(x,H) ≥ √ t) = P(`2(x,H)2 ≥ t) ≤ 1
4t =
1
4 2d
In the case of zero-one loss, RR∗ = P(`2(x,H) ≤ √ d) ≥ 1− 14 2d .
A.2 PROOF FOR THEOREM 2.1
Proof. (First Inequality for Cube) The proof here follows that of Ledoux (2005), but we track of the tight constants so as to give tighter adversarial robustness calculations.
Let Φ be one dimensional standard normal cumulative distribution function and let µd denote d dimensional Gaussian measures. Consider the map T : Rd −→ (0, 1)d:
T (x1, · · · , xd) = (Φ(x1), · · · ,Φ(xd))
T pushes forward µd defined on Rd into a probability measure P on (0, 1)d:
P(A) = µd(T−1(A))
for A ⊂ (0, 1)d. Next we have the following Gaussian isoperimetric/concentration inequality (Ledoux, 2005): µd(B ) ≥ Φ(Φ−1(µd(B)) + ) for all B ⊂ Rd measureable. Now for A ⊂ (0, 1)d, we have:
P(A ) = µd(T−1(A )) ≥ µd(T−1(A) √2π) ≥ Φ(Φ −1(µd(T
−1(A)) + √ 2π ))
where the first inequality follows from that T has Lipschitz constant 1√ 2π , and thus T−1 has Lips-
chitz constant √ 2π; and the second one follows from Gaussian isoperimetric inequality.
When P(A) ≥ 1/2,
Φ(Φ−1(µd(T −1(A)) + √ 2π )) ≥ Φ(Φ−1( √ 2π ))
Additionally, the inequality Φ(x) ≥ 1− e x 2 2 implies the last inequality in the theorem.
(Second Inequality for Ball) We first define the notion of modulus of convexity for a normed space, in this case `2:
δ`2( ) = inf{1− ‖ x+ y
2 ‖ : ‖x‖ = ‖y‖ = 1, ‖x− y‖ ≥ } = 1− √ 1− 2
4
The important property about δ`2( ) is that there is a constant C such that:
δ`2( ) ≥ C 2
By elementary algebraic calculuation, We can take C = 2− √ 3
3 .
By Equation (2.25) in (Ledoux, 2005),
P(A ) ≥ 1− 1
P(B) (1− δ`2( ))2d ≥ 1−
1 P(A) e−2dδ`2 ( ) = 1− 1 P(A) e−2d(
2− √
3 3 ) 2

heading: B DETAILED SETTINGS FOR TRAINING

text:
B.1 DETAILED SETTINGS OF ADVERSARIAL TRAINING
The LeNet5 (widen factor 1) is composed of 32-channel conv filter + ReLU + size 2 max pooling + 64-channel conv filter + ReLU + size 2 max pooling + fc layer with 1024 units + ReLU + fc layer with 10 output classes. We do not preprocess MNIST images before feeding into the model.
For training LeNet5 on MNIST variants, we use the Adam optimizer with an initial learning rate of 0.0001 and train for 100000 steps with batch size 50.
We use the WideResNet-28-4 as described in Zagoruyko and Komodakis (2016) for our experiments, where 28 is the depth and 4 is the widen factor. We use “per image standardization” 10 to preprocess CIFAR10 images, following Madry et al. (2017).
For training WideResNet on CIFAR10 variants, we use stochastic gradient descent with momentum 0.9 and weight decay 0.0002. We train 80000 steps in total with batch size 128. The learning rate is set to 0.1 at step 0, 0.01 at step 40000, and 0.001 at step 60000.
We performed manual hyperparameter search for our initial experiment and do not observe improvements over the above settings. Therefore we used these settings throughout the all the experiments in the paper unless otherwise indicated.
B.2 LP ROBUST MODEL DESCRIBED IN SECTION 2
For the linear programming based provably robust model (Wong and Kolter, 2018) (LP-robust model). We trained a ConvNet identical to the one in the original paper. It has 2 convolutional layers, with 16 and 32 channels, each with a stride of 2; and 2 fully connected layers, the first one maps the flattened convolution features to hidden dimension 100, the second maps to 10 logit units. We use ReLUs as the nonlinear activation and there is no max pooling in the network.
We train for 100 epochs with batch size 50. The first 50 epochs are warm start epochs where epsilon increases from 0.01 to 0.3 linearly. We use Adam optimizer (Kingma and Ba, 2014) with a constant learning rate of 0.001.

heading: C DETAILED EXPERIMENTAL RESULTS

text:
We listed exact numbers of experiments involved in the main body in Table 2, 3, 4 and 5.
10https://www.tensorflow.org/api_docs/python/tf/image/per_image_ standardization

heading: D DETAILED ANALYSES

text:
D.1 DETAILED ANALYSIS OF EFFECTS OF DATA DOMAIN BOUNDARY
One natural hypothesis about the reason of achieving better robustness could be that it is the effect of the boundaries. Indeed, if the data distribution is closer to the data domain boundary, the valid perturbation space, the -`∞ ball may be restricted since it will intersect with the boundary. We then test the correlation between “how close the data distribution is to the boundary” and its achievable robustness, by examining the volume of the allowed perturbed box across different datasets.
The intersection of the data domain, unit cube [0, 1]d, with the allowed perturbation space, -`∞ ball [xi − , xi + ]d, is the hyperrectangle [max{xi − , 0},min{xi + , 1}]d, where i = 1, · · · , d are the indexes over input dimensions. The size of the available perturbation space at x and is defined by the volume of this hyperrectangle:
Vol(x, ) = d∏ i=1 (min{xi + i, 1} −max{xi − i, 0})
In high dimensional space, when is fixed, this volume varies greatly based on the location of x. For example, if x is on one of the corners of the unit cube, Vol(xcorner, ) = d. If each dimension of x is at least away from all the data boundaries, then the volume of the hyperrectangle is Vol(xinside, ) = (2 )
d. Therefore there can be 2d times difference of perturbable space between different data points. As shown in the average log perturbable volumes Table 6, we can see that different variations of datasets has significantly different perturbable volumes, with the same trend with previously described. It is notable that for the original CIFAR10 datasets has log volume -12354, which is very close to the -12270. The different of 84 bits indicates on average, the perturbation space is 284 smaller than the full -`∞ ball if there is no intersection with the data domain boundary. Volume differences between different saturation or smooth level can be interpreted in the similar
way. Note that for CIFAR10 images with large saturation, although they appear similar to human, they actually have very large differences in terms of perturbable volumes.
If the perturbable volume hypothesis holds, then we should observe significantly lower accuracy under PGD attack if we allow perturbation outside of data domain boundary. Since this greatly increases the perturbable volume. We measure the accuracy under PGD attack with and without considering data domain boundary for both MNIST and CIFAR10 variants. The results are shown in Table 7. “With considering boundary” corresponds to regular PGD attacks. We can see that allowing PGD to perturb out of bound do not reduce accuracy under attack. This means that PGD
is not able to use the significantly larger additional volumes even for binarized MNIST or highly saturated CIFAR10, whose data points are on or very close to the corner. In some cases, allowing perturbation outside of domain boundary makes the attack slightly less effective. This might be due to that data domain boundary constrained the perturbation to be in an “easier” region. This might seem surprising considering the huge difference in perturbable volumes, these results conform with empirical results in previous research (Goodfellow et al., 2014; Warde-Farley and Goodfellow, 2016) that adversarial examples appears in certain directions instead of being distributed in small pockets across space. Therefore, the perturbable volume hypothesis is rejected.
D.2 DETAILED ANALYSES OF INTER-CLASS DISTANCE
D.2.1 CALCULATION OF INTER-CLASS DISTANCE
We calculate the inter-class distance as follows. Let D = {xi} denote the set of all the input data points, Dc = {xi|yi = c} denote the set of all the data points in class c, and D¬c = {xi|yi 6= c} denote all the data points not in class c. Our goal is to calculate d(Dc, D¬c) for all the classes, where d(Dc, D¬c) approximates the margin between class c and the rest. To estimate d(Dc, D¬c), we first compute the margin for each data point x in class c. To do that, we calculate the average ‖x− xj‖2, where xj ∈ D¬c is one of x’s 10% nearest neighbors inD¬c. Lastly, the inter-class distance of class c, d(Dc, D¬c), is then calculated as the average of smallest 10% d(x,D¬c) for x ∈ Dc. Note that we choose `2 distance for inter-class distance, instead of using the `∞ which measures the robustness. This is because `∞-distance between data examples is essentially the max over the per pixel differences, which is always very close to 1. Therefore the `∞-distance between data examples is not really representative / distinguishable.
Figure 5 shows the inter-class distances (averaged over all classes) calculated on MNIST and CIFAR10 variants. The binarized MNIST has a significantly larger inter-class distance. As smoothing kernel size increases, the distance also decrease slightly. On CIFAR10 variants, as the saturation level gets higher, the inter-class distance increases monotonically. We also directly plot inter-class distance vs robust accuracy on MNIST and CIFAR10 variants. In general, inter-class distance shows a strong positive correlation with robust accuracy under these transformations. With one exception that original MNIST has smaller inter-class distance, but is sightly more robust than smooth-2 MNIST. This, together with the counter examples we gave in Table 1, suggests that inter-class distance cannot fully explain the robust variation across different dataset variants.
D.2.2 INTER-CLASS DISTANCE COULD POTENTIALLY INFLUENCE REQUIRED MODEL CAPACITY
We attempt to understand the relation between the inter-class distance of a dataset and its achievable robustness in this section. We first illustrate our intuition in a synthetic experiment, where a ReLU network is trained to perfectly separate 2 concentric spheres (Gilmer et al., 2018), as shown in Figure 6. Here the inter-class distance is the width of the ring between two spheres. In such example, adversarial training is actually closely related to the inter-class distance of the data. In fact, in the simple setting where the classifier is linear, it has been shown in Xu et al. (2009) that adversarial training, as a particular form of robust optimization, is equivalent to maximizing the classification margins. Following this intuition, one can easily see that the effect of adversarial training is to push two spheres close to each other, and requires the network to perfectly separate the new spheres with much smaller inter-class.
Intuitively, when the inter-class distance is large, i.e. the gap between two spheres are large, a reasonable model should be able to achieve good standard accuracy. We have also observed such phenomenon on original MNIST and saturated CIFAR10 (say level 16). As the inter-class distance gets smaller, although the model capacity could still be enough for the standard training, it may no longer be enough for adversarial training, upon which we would observe that although the test accuracies stay similar, accuracies under adversarial attack significantly would drop. We have also seen similar behavior on smooth MNIST data and smaller level of saturated CIFAR10 data. Finally, when the inter-class distance is so small such that even a high clean test accuracy may be difficult to achieve.
Considering robust accuracy as the clean accuracy with a smaller gap between the spheres, the next theorem provides a theoretical guarantee in relating together the difficulty of attaining good accuracy under attack and the model capacity (Ball, 1997), verifying our intuition above. Note that one way to measure the capacity of a ReLU network is by counting the number of its induced piece-wise linear region, which is closely related to the number of facets of its decision boundary. Theorem D.1. Let d(K,L) between symmetric convex bodies K and L denote the least positive d for which there is a linear image L̃ of L such that L̃ ⊂ K ⊂ dL̃. Let K be a (symmetric) polytope in Rn with d(K,Bn2 ) = d. Then K has at least en/(2d
2) facets. On the other hand, for each n, there is a polytope with 4n facets whose distance from the ball is at most 2.
The above analysis is partially supported by our experiments on model capacity in Section 5.3. However, as we’ve shown in Section 5.2, the nature of the problem is complex and more conclusive statements requires further research.


summaries: Authors present a new normalization technique called Equi-Norm and experimentally show its fast convergence properties over its popular competitors Batch-norm and Group-norm. The main idea in the paper is the EquiNorm method modifies the weights of a layer before forward propagating through it such that the contribution from positive and negative kernel weights to the output is same. In the experimental section, their approach is shown to be more accurate than Batch-norm and group norm on all datasets except, Imagenet. Is there any reasoning why this method performed slightly poorly on this particular dataset.

summaries: This manuscript introduces a new layer-wise transform, EquiNorm, to improve upon batch normalization. As with batch normalization and related techniques, the idea is to introduce a simple linear transform at each layer to reduce the dependency of the features to the data. Unlike batch normalization, the procedure does not modify the inputs to the layers but rather the layer weights. For this purpose, a scaling factor and a shift is computed on a mini batch, separating positive and negative weights to compute easily both running estimates of shift and of spread (here in the l1 sense). The method is compared to BatchNorm and GroupNorm on several classic computer vision datasets. Empirically, the method converges faster in the beginning of the optimization, in the sense that in the first few epochs the test accuracy is higher than for BatchNorm. However, this benefit decreases with more epochs and when the results are close to peak performance the difference between methods is a small. In addition, test accuracy can decrease at the end of the optimization, which the authors interpret as a sign of increased overfit, and tackle with clever data augmentation. The paper reads well.

abstractText: We introduce a new normalization technique that exhibits the fast convergence properties of batch normalization using a transformation of layer weights instead of layer outputs. The proposed technique keeps the contribution of positive and negative weights to the layer output in equilibrium. We validate our method on a set of standard benchmarks including CIFAR-10/100, SVHN and ILSVRC 2012 ImageNet.

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV),

title: Identity mappings in deep residual networks

venue: Technical report, Microsoft Research Asia,

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

title: Batch renormalization: Towards reducing minibatch dependence in batchnormalized models

venue: 31st Conference on Neural Information Processing Systems (NIPS 2017),

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: Proceedings of the 32nd International Conference on Machine Learning (ICML 2015),

authors:
Kevin Jarrett
Koray Kavukcuoglu
Marc’Aurelio Ranzato
Yann LeCun

title: What is the best multi-stage architecture for object recognition

venue: International Conference on Computer Vision,

title: Learning multiple layers of features from tiny images

venue: Technical report,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E. Hinton

title: Imagenet classification with deep convolutional neural networks

venue: 26th Conference on Neural Information Processing Systems

authors:
Siwei Lyu
Eero P. Simoncelli

title: Nonlinear image representation using divisive normalization

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y. Ng

title: Reading digits in natural images with unsupervised feature learning

venue: NIPS Workshop on Deep Learning and Unsupervised Feature Learning,

authors:
Tim Salimans
Diederik P. Kingma

title: Weight normalization: A simple reparameterization to accelerate training of deep neural networks

venue: 30th Conference on Neural Information Processing Systems

authors:
Shibani Santurkar
Dimitris Tsipras
Andrew Ilyas
Aleksander Madry

title: How does batch normalization help optimization? (no, it is not about internal covariate shift)

authors:
Leslie N. Smith
Nicholay Topin

title: Super-convergence: Very fast training of neural networks using large learning rates

venue: Technical report, U.S. Naval Research Laboratory,

authors:
Vikas Verma
Alex Lamb
Christopher Beckham
Aaron Courville
Ioannis Mitliagkas
Yoshua Bengio

title: Manifold mixup: Encouraging meaningful on-manifold interpolation as a regularizer

venue: Technical report, Montreal Institute for Learning Algorithms,

authors:
Hongyi Zhang
Moustapha Cisse
Yann N. Dauphin
David Lopez-Paz

title: mixup: Beyond empirical risk minimization

venue: International Conference on Learning Representations,

heading: 1 INTRODUCTION

text:
The introduction of normalizing layers to neural networks has in no small part contributed to the deep learning revolution in machine learning. The most successful of these techniques in the image classification domain is the batch normalization (BatchNorm) layer (Ioffe & Szegedy, 2015), which works by normalizing the univariate first and second order statistics between layers.
Batchnorm has seen near universal adoption in image classification tasks due to its surprisingly multifaceted benefits. Compared to an unnormalized network, its has been widely observed that using batch norm empirically results in:
• Stability over a wide range of step sizes • Faster convergence (particularly with larger step sizes) • Improved generalization
The multiple effects of BatchNorm make it both hard to replace and hard to analyze. In this paper we introduce Equilibrium Normalization (EquiNorm), a normalization that works in weight space and still uses a form of batch statistics unlike previous weight space approaches. EquiNorm results in very rapid convergence, even more so than BatchNorm, however as we will show in our experiments, this also results in a tendency to overfit. When combined with additional regularisation, EquiNorm can significantly outperform BatchNorm, which benefits less from this additional regularisation.

heading: 2 RELATED WORK

text:
A number of normalization layers have been proposed that can be considered alternatives to batch normalization. Batch normalization has also been extended as batch renormalization (Ioffe, 2017) to handle smaller batch sizes.
Layer/Instance Normalization A simple modification of BatchNorm involves computing the statistics independently for each instance, so that no averaging is done across each mini-batch, instead averaging either across channels (layer norm) or separately for each channel (instance norm). Unfortunately these techniques are known to not generalize as well as batch norm for convolutional neural networks (Sec 6.7; Sec 4.1. Jimmy Lei Ba, 2016; Yuxin Wu, 2018).
Group Normalization A middle ground between layer and instance normalization can be found by averaging statistics over small groups of channels. This has been shown empirically to be superior to either approach, although there is still a gap in generalization performance (Yuxin Wu, 2018). Like the approaches above, it avoids a dependence on batch statistics, allowing for potentially much smaller batches to be used without a degradation in generalization performance.
Weight Normalization Additional stability can be introduced into NN training by constraining the norm of the weights corresponding to each output channel/neuron to be one. When this is done by an explicit division operation in the forward pass, rather than via an optimization constraint, this is known as weight normalization (Salimans & Kingma, 2016). An additional learnable scaling factor is also introduced. Unfortunately, to match the generalization performance of BatchNorm on image classification tasks such as CIFAR-10, this technique needs to be used together with partial (additive only) BatchNorm (Section 5.1, Salimans & Kingma, 2016).
Local Response Normalization A precursor to batch norm, local normalization methods (Jarrett et al., 2009; Lyu & Simoncelli, 2008) played an important part in the seminal AlexNet architecture (Krizhevsky et al., 2012), and were widely used before batch norm was introduced. LR normalization has similarities to group norm in that it uses a group of neighboring channels (with ordering set arbitrary at initialization) for normalization. Although it aids generalization in a similar manner to BatchNorm, it does not accelerate convergence or allow for larger step sizes to be used (Sec 4.2.1, Ioffe & Szegedy, 2015).

heading: 3 ASSUMPTIONS

text:
The EquiNorm method functions by modifying the weights of a convolution before it is applied. For justifying the form of our method, we make the following assumptions about this convolution, which we will discuss relaxing after detailing the method:
1. All inputs to the convolutional layer are positive, such as when the layer is preceded by a ReLU.
2. The convolution has stride one.
3. Cyclic padding is used.
4. All weights are non-zero, and there exists at least one positive and one negative weight per output channel.

heading: 4 METHOD

text:
Consider initially for simplicity a convolutional layer with a single input and output channel. Let
w : kernelheight× kernelwidth,
be the weight kernel for this neuron, and let
x : batchsize× height× width,
be the input tensor for a single mini-batch. We will compute scalar quantities s and b that modify the weights as follows:
w′′ = sw′ = s (w + b) .
This transformation will be fully differentiated through during the backwards pass (using automatic differentiation) so that the gradient of w is correct. As with BatchNorm, we also include an additional affine transformation after the convolution to ensure no expressivity is lost due to the normalization operation.
The core idea of equilibrium normalization is to balance the contribution of positive and negative weights to the output of the convolution. To this end, we introduce additional notation to address the positive and negative weights separately. Let superscripts +/− (i.e. w+/w−) indicate sums of the positive/negative elements respectively. Also, let v be the sum of the input data to the layer,
v = ∑ i,j,k xijk.
As we have two constants to determine, we need two constraints that we wish to be satisfied. The first constraint we introduce is common with batch normalization, a constraint on the mean of the
output. Since under the cyclic padding assumption, each weight is multiplied by each input element, we can constrain the mean of the output to be zero by requiring that:
vs ∑ j,j (wjk + b) = 0,
∴ b = −mean(w). The second constraint controls the magnitude within the total output of the layer, of the positive weight elements:
vsw′+ = r,
∴ s = r
vw′+ .
The constant r is set so that the contribution is of average 1 per output element, which is achieved by setting r to the product of batch-size, output width and output height. Note that due to the mean constraint, this automatically results in the negative weight contribution also being of magnitude r.

heading: 4.1 FULL CASE

text:
When multiple input channels are used, each weight no longer multiples each input, rather they each multiply only inputs from a single channel. To compensate for this we need to compute per-channel sums vc (where c is the channel index) and change the second constraint as follows:
channelsin∑ c vcsw ′+ c = r.
The first constraint changes in the same fashion.
When multiple output channels are used, we just duplicate this procedure applying it to each channel’s weights separately. We thus maintain a s and b value per output channel, and compute as intermediate values a w′+ of matrix shape. For completeness we give the full equations below. All summations are over the full range of the summed indexes.
Tensor shapes w :channelsout× channelsin× kernelheight× kernelwidth x :batchsize× channelsin× heightin× widthin
w′+ :channelsout× channelsin v :channelsin
s, b :channelsout
Updates:
vc = ∑ i,j,k xicjk,
wdc = ∑ j,k wdcjk,
r = batchsize× heightout× widthout× stride2 bd = − ∑
c vcwdc (kernelheight× kernelwidth) ∑ c vc ,
w′+dc = ∑ j,k (wdcjk + bd) I[wdcjk + bd > 0],
sd = r∑
c vcw ′+ dc
,
w′′dcjk = sd (wdcjk + bd) .
At test time, we follow the technique used in BatchNorm of using a running estimate of the data statistics (vc in our method) that is computed during training time.

heading: SINGLE PASS FORMULATION

text:
The above calculation requires two passes over the weights, first to compute b, then to compute the sum of positive elements after the addition of b. We can do an approximate computation using only one pass by assuming the sign of each element does not change after the addition of b. The s calculation changes as follows:
n+dc = ∑ j,k I[wdcjk > 0],
sd = r∑ c vc ( w+dc + bdn + dc ) . We use this variant in all experiments that follow.

heading: 5 DISCUSSION

heading: 5.1 CONTROLLING COVARIATE SHIFT

text:
The original justification for batch normalization is its ability to minimize covariate shift, although there is some debate on whether or not this is the main contributing factor to its effectiveness, see Santurkar et al. (2018). In this context, covariate shift refers to the change between steps of the statistics of the outputs of a layer.
Like batch normalization, the approach we propose also controls the shift in the outputs of a layer between steps, just in a different way. Our approach is motivated by a hypothesis that it is not necessary to control the mean and variance precisely; other notions of scale and shift may work as well or better. Santurkar et al. (2018) show that normalizing by other norms, such as L1, can work well, supporting this hypothesis.
The sum of the output from positive and negative weights is a form of L1 control which can be contrasted with the L2 control that Batchnorm uses. This control can be motivated by Young’s convolution inequality, which bounds the output of a convolution operation in terms of the norm of the input:
‖x ∗ w‖r ≤ ‖w‖p ‖x‖q ,
where 1
p +
1 q = 1 r + 1.
Note that p, q, r ≥ 1 is also required, and that this only applies directly when there is a single input and output channel, which we assume in the remainder of this section for simplicity.
For EquiNorm, we have assumed that the input is positive, so that our input sum is equivalent to the L1 norm of the input. Additionally, after subtracting off the mean, the weight vector w′ has L1 norm equal to w′+ − w′− = 2w′+, so we are also normalizing the weights by the L1 norm. In effect, we are applying Young’s convolution inequality with p = q = r = 1.
It is also possible to apply the above inequality with p = 2, q = 1 and r = 2. I.e. normalize the weights using the L2 norm, giving a bound on the L2 norm of the output in terms of the L1 norm of the input. This is less satisfying as one convolution’s output is the input of another convolution (after passing through scaling & a nonlinearity) so we would like to use the same norm for both inputs and outputs. The related weight normalization (WN, Salimans & Kingma, 2016) method normalizes weights by their L2 norm, and differs from our method by centering outputs using an additional mean-only output batchnorm. Additionally, since it doesn’t normalize by the input norm, the output norm can be correspondingly large. These differences have a significant effect in practice.

heading: 5.2 ASSUMPTIONS

heading: INPUT TO THE CONVOLUTIONAL LAYER IS POSITIVE

text: This assumption is not necessary for the implementation of our method, rather it ensures that the output is more constrained than it otherwise would be. When ReLU nonlinearities are used in the standard fashion, this assumption holds except in the first layer of the network where input pixels are usually in the range [-1,1], due to pre-normalization. We recommend this pre-normalization is removed, as it is unnecessary when normalization happens immediately inside the first convolution. Recommendations in the literature that suggest input normalization is beneficial are usually referring to networks without per-layer normalization.

heading: NON-STRIDED CONVOLUTIONS

text: A strided convolution can thought of as a non-strided convolution with the extra output values thrown away. If Equilibrium normalization is used with a strided convolution, the contribution to the output from positive and negative weights will no longer be exactly balanced. In practice the violation will be small if the output of the non-strided version of the convolution is smooth.

heading: CYCLIC PADDING

text: Our equations for b and s assume that each weight for an input channel is multiplied by each input value for that channel. Most deep learning frameworks use zero-padded convolutions instead of cyclic padding, which violates this assumption. In practice we do not find this violation to be troublesome, as it only affects edge pixels, and has a dampening effect as it only reduces the output contribution of the positive or negative weights.

heading: ALL WEIGHTS ARE NON-ZERO, AND THERE EXISTS AT LEAST ONE POSITIVE AND ONE NEGATIVE WEIGHT PER OUTPUT CHANNEL

text:
We avoid the use of an parameter such as used in BatchNorm, as the denominator of our normalization factor is only zero if every weight for every input channel is simultaneously positive (or all negative), or the weights become extremely small. The later case does not appear to happen in practice. Nevertheless, we find it helps to initialize the weights in a balanced fashion, so that no channel’s
weight kernel is all positive or all negative. We do this by modifying the default initialization by resampling any such kernel-weight’s signs.

heading: 6 EXPERIMENTS

text: In our plots we show a comparison to BatchNorm and GroupNorm. We omit a comparison to Layer/Instance Normalization as our initial experiments were consistant with findings in the literature that show that they are inferior to GroupNorm and BatchNorm, at least for the convolutional architectures we consider below (Yuxin Wu, 2018). We also performed a comparison against the WeightNorm method, however despite significant efforts we were not able to get it to reliably converge when using very deep architectures such as ResNet-152 that we choose for our experiments. We could not find any results in the literature where it is sucessfully applied to state-of-the-art deep networks, and we believe this is a real limitation of the method.

heading: 6.1 CIFAR-10/100

text:
The CIFAR-10 dataset (Krizhevsky, 2009) is considered a standard benchmark among image classification tasks due to its non-trivial complexity, requiring tens of millions of weights to achieve state-of-the-art performance, and also its tractable training times due to its small size (60,000 instances). The downside of this small size is that significant care must be taken to avoid overfitting. This overfitting can be partially avoided using data augmentation, and we followed standard practice of using random horizontal flips and crops (pad 4px and crop to 32px) at training time only.
Our initial experiments involving a non-bottleneck wide ResNet network with 20 convolutions, 96 initial planes after first convolution and 9.7m parameters. The hyper-parameters used were LR: 0.1, SGD+Mom: 0.9, decay: 0.0001, batch-size: 128, 1 GPU, 10 fold learning reductions at epochs 150 and 225, and standard fan out normal initialization following He et al. (2015). These parameters are defaults commonly used with BatchNorm and were not tuned.
Our experiments indicated that our EquiNorm approach converged significantly faster than BatchNorm, but also overfit significantly more (Figure 2).
We believe this is caused by the batch statistics having less noise with EquiNorm than BatchNorm, rather than the faster initial convergence, as experiments involving reduced step sizes did not further improve generalization. Similarly, we were not able to achieve comparable fast initial convergence by using larger step-sizes with BatchNorm.
We found instead that we could match the generalization of BatchNorm using either of the following two approaches:
1. Using fewer instances to compute the batch statistics. Using the first quarter of the batch to compute the statistics used for the full batch successfully fixed the overfitting seen in Figure 2, resulting in higher test accuracy for EquiNorm (95.8%) over BatchNorm (94.7%) and no overfitting visible in test loss.
2. Using mixup (Zhang et al., 2018) or manifold mixup (Verma et al., 2018), which introduce activation noise of a similar nature.
We recommend the use of manifold mixup, as it significantly improves test accuracy for both BatchNorm and EquiNorm, although it does result in higher test loss in some cases.
Following closely the approach of Verma et al. 2018, we applied both EquiNorm and BatchNorm to the larger near state-of-the-art pre-activation ResNet-152 architecture (He et al. 2016a, 58.1m parameters, [3,8,36,3] bottleneck blocks per layer respectively, 64 initial channels), using a modified
version of their published code and the hyper-parameters listed above, with manifold mixup used for each method. As Figure 4a shows, the test set performance is essentially the same at the final epoch, but EquiNorm converges significantly faster at the early epochs.

heading: CIFAR100

text:
We also achieved a similar performance on the CIFAR-100 dataset (which has similar properties to CIFAR10) as shown in Figure 4b, where we used the same hyper-parameters and network architecture as for CIFAR10.
6.2 SHORTER DURATION TRAINING
Given the encouraging results above during the early stages of optimization, we investigated if EquiNorm was superior when training is restricted to 30 epochs instead of 300. We used a “super convergence” learning rate schedule as suggested by Smith & Topin (2017), consisting of a 5 fold ramp in learning rate (starting at 0.1) from epochs 1 to 13, then a 5 fold ramp down to epoch 26, followed by further annealing by 100x down over the remaining epochs. Momentum follows a reverse pattern, from 0.95 to 0.85 to 0.95, and fixed at 0.85 after epoch 26. Manifold mixup was used again for both methods. Using this schedule EquiNorm shows a 94.0% (IQR 0.22) median test accuracy compared to 93.3% for BatchNorm (IQR 0.77).

heading: 6.3 STREET VIEW HOUSE NUMBERS

text: The SVHN+EXTRA dataset (Netzer et al., 2011) is much larger than CIFAR-10/100 (73,257 + 531,131 training instances), so we trained across 2 GPUs, using 2× larger mini-batches (size 256) so as to keep the batch statistics noise (which are computed on a per-gpu basis) the same. Other hyper-parameters were also kept the same, with the exception that we trained for fewer epochs (with LR reductions moved to epochs 80 and 120). Figure 4c shows that EquiNorm achieves essentially the same generalization performance as BatchNorm. On this problem GroupNorm appears inferior, although this may be due to the default group-size of 32 being suboptimal here.

heading: 6.4 ILSVRC 2012 IMAGENET

text: We also ran some preliminary experiments on the ILSVRC 2012 ImageNet classification task using the standard ResNet50 architecture (He et al., 2016b). Our results here show a generalization gap between EquiNorm and BatchNorm/GroupNorm. It may be possible to eliminate this gap using additional regularisation as in the CIFAR-10 case, however we found manifold mixup to not yield such an improvement.

heading: 6.5 REPORTING TRAINING VARIABILITY

text: We are careful to report results aggregated over enough runs involving different RNG seeds so that run-to-run variability does not effect our conclusions. This is absolutely necessary for the smaller test problems above as the differences between runs can be comparable to the difference between the compared normalization methods, and indeed differences in reported results in the literature. We report median and inter-quartile statistics (i.e. our plots include point-wise 25% and 75% percentile ranges of the values seen), as these are more representative of actual performance, and particularly the asymmetry of test accuracy variability. The more commonly used two-standard-deviation bars based on a normal assumption can show values both below and above actually seen data (such as > 100% accuracy upper bounds), and are not supported by statistical theory for small samples such as the ten used here.