Adversarially Robust Generalization Just Requires More Unlabeled Data
Authors: Runtian Zhai
Tianle Cai
Di He
Chen Dan
Kun He
John E. Hopcroft
Liwei Wang
Venue:  (2020)
Keywords: Adversarial Robustness
Semi-supervised Learning

Abstract: Neural network robustness has recently been highlighted by the existence of adversarial examples. Many previous works show that the learned networks do not perform well on perturbed test data, and significantly more labeled data is required to achieve adversarially robust generalization. In this paper, we theoretically and empirically show that with just more unlabeled data, we can learn a model with better adversarially robust generalization. The key insight of our results is based on a risk decomposition theorem, in which the expected robust risk is separated into two parts: the stability part which measures the prediction stability in the presence of perturbations, and the accuracy part which evaluates the standard classification accuracy. As the stability part does not depend on any label information, we can optimize this part using unlabeled data. We further prove that for a specific Gaussian mixture problem, adversarially robust generalization can be almost as easy as the standard generalization in supervised learning if a sufficiently large amount of unlabeled data is provided. Inspired by the theoretical findings, we further show that a practical adversarial training algorithm that leverages unlabeled data can improve adversarial robust generalization on MNIST and Cifar-10.

Under review as a conference paper at ICLR 2020
ADVERSARIALLY ROBUST GENERALIZATION JUST REQUIRES MORE UNLABELED DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Neural network robustness has recently been highlighted by the existence of ad- versarial examples. Many previous works show that the learned networks do not perform well on perturbed test data, and significantly more labeled data is re- quired to achieve adversarially robust generalization. In this paper, we theoret- ically and empirically show that with just more unlabeled data, we can learn a model with better adversarially robust generalization. The key insight of our re- sults is based on a risk decomposition theorem, in which the expected robust risk is separated into two parts: the stability part which measures the prediction sta- bility in the presence perturbations, and the accuracy part which evaluates the standard classification accuracy. As the stability part does not depend any la- bel information. we can optimize this part using unlabeled data. We further prove that for a specific Gaussian mixture problem illustrated by (Schmidt al. (2018). adversarially robust generalization can be almost as easy as the standard gener- alization in supervised learning a sufficiently large amount of unlabeled data is provided. Inspired by the theoretical findings, we further show that practical ad- versarial training algorithm that leverages unlabeled data can improve adversarial robust generalization on MNIST and Cif
INTRODUCTION
Deep learning (LeCun al. 2015), especially deep Convolutional Neural Network (CNN) (LeCun et al. 1998), has led to state-of-the-ar results spanning many machine learning fields, such as im-
age c classification (Simonyan
Zisserman, 2014| He et al. 2016 Huang et al., 2017, Hu et al.]
2017). object detection (Ren et al.] 2015| Redmon et al.
2016: Lin et al.] 2018), semantic segmen-
lation
(Long et al. 2015: Zhao et al. 2017 Chen et al. 2018 and action recognition (Tran et al.,
2015
Wang et al. 2016 2018).
Despite the great success numerous applications, recent studies show that deep CNNs are vulner- able to some well-designed input samples named Adversarial Examples (Szegedy et al. 2013 Biggio et al.) 2013). Take image classification as an example, for almost every commonly used well-performed CNN, attackers able to construct small perturbation perturbation is almost imperceptible to humans but can fool the model to make a wrong prediction. The problem is serious some designed adversarial examples can be transferred among different kinds of CNN architectures (Papernot et al. 20166), which makes it possible to perform black-box attack: an attacker has access the model parameters or even architecture, but can still easily fool a machine learning system.
an input image. The
There is rapidly growing body of work on studying how to obtain a robust neural network model. Most of the successful methods are based on adversarial training (Szegedy et al.) 2013 Madry et al.) 2017 Goodfellow et al. 20155 |Huang et al. (0155.. The high-level idea of these works is that during training, we predict the strongest perturbation to each sample against the current model and use the perturbed sample together with the correct label for gradient descent optimization. However, the learned model tends to overfit on the training data and fails to keep robust on unseen testing data. For example, using the state-of-the-ar adversarial robust training method (Madry et al.) (017). the defense success rate of the learned model on the testing data is below 60% while that on the train- ing data is almost 100%. which indicates that the robustness fails to generalize. Some theoretical results further show that it is challenging to achieve adversarially robust generalization. Fawzi al.

---

Under review as a conference paper at ICLR 2020
2018 proves that adversarial examples exist for any classifiers and can be transferred across dif- ferent models, making it impossible to design network architectures free from adversarial attacks. Schmidt al. (2018) shows that adversarially robust generalization requires much more labeled data than standard generalization in certain cases. [Tsipras et al. | (2019) presents an inherent trade-off between accuracy and robust accuracy and argues that the phenomenon comes from the fact that robust classifiers learn different features. Therefore it is hard to reach high robustness for standard training methods.
Given the challenge of the task and previous findings, in this paper, we provide several theoretical and empirical results towards better adversarially robust generalization. In particular, we show that we can learn an adversarially robust model which generalizes well if we have plenty of unlabeled data, and the labeled sample complexity for adversarially robust generalization (2018) can be largely reduced if unlabeled data is used. First, we show that the expected robust risk can be upper bounded by the sum of two terms: a stability term which measures whether the model can output consistent predictions under perturbations, and accuracy term which evaluates whether the model can make correct predictions on natural samples. Given the stability term does not rely on ground truth labels, unlabeled data can be used to minimize this term and thus improve the generalization ability. Second, we prove that for the Gaussian mixture problem defined in [Schmidt et al. (2018), if unlabeled data be used, adversarially robust generalization will be almost as easy as the standard generalization in supervised learning (i.e. using the same number of labeled samples under similar conditions). Inspired by the theoretical findings, we provide a practical algorithm that can learn from both labeled and unlabeled data for better adversarially robust generalization. Our experiments on MNIST and Cifar-10 show that the method achieves better performance, which verifies our theoretical findings.
SSchiidt et al.
Our contributions are in three folds.
In Section 3.2.1 we provide theorem show that unlabeled data can be naturally used to improve the expected robust risk in general setting and thus leveraging unlabeled data is a way improve adversarially robust generalization.
In Section 3.2.2 we discuss a specific Gaussian mixture problem introduced in (Shhidt et al. (2018). In Schmidt et al.] (2018). the authors proved that in this case, the labeled sample complexity for robust generalization is significantly larger than that for standard generalization. As an extension of this work, we prove that in this case, the labeled sample complexity for robust generalization can be the same as that for standard generalization we have enough unlabeled data.
Inspired by our theoretical findings, we provide an adversarial robust training algorithm using both labeled and unlabeled data. Our experimental results show that the algorithm achieves better performance than baseline algorithms on MNIST and Cifar- 10, which em- pirically proves that unlabeled data can help improve adversarially robust generalization.
2 RELATED WORKS
Adversarial attacks and defense Most previous works study how to attack a neural network model using small perturbations under certain norm constraints, such as Loo norm or l2 norm. For the Loo constraint, Fast Gradient Sign Method (FGSM) (Goodfellow et al. 2015) finds a direction to which the perturbation increases the classification loss at an input point to the greatest extent; Projected Gradient Descent (PGD) (Madry et al. (017)) extends FGSM by updating the direction of the attack in an iterative manner and clipping the modifications in the norm range after each iteration. For the la constraint, DeepFool Moosavi--ezfooll et al. (016) iteratively computes the minimal norm of an adversarial perturbation by linearizing around the input in each iteration. C&W W attack (Callini & Wagner 2016) is comprehensive approach that works under both norm constraints. In this work, we focus on learning a robust model to defend the white-box attack, i.e. the attacker knows the model parameters and thus can use the algorithms above to attack the model.
There are a large number of papers about defending against adversarial attacks, but the result is far from satisfactory. Remarkably, (Athalye et al. (201)) shows most defense methods take advantage of so-called " "gradient mask" and provides an attacking method called BPDA to correct the gradients. So far, adversarial training (Madry et al. 2017) has been the most successful white-box defense al-
2

---

Under review as a conference paper at ICLR 2020
gorithm. By modeling the learning problem mini-mas game between the attacker and defender, the robust model can be trained using iterative optimization methods. Some recent papers (Wang et al. 2019; Gao et al. 2019) theoretically prove the convergence of adversarial training. More- over, Shafahi et al. 2019); Zhang et al. (201 9a) propose ways to accelerate the speed of adversarial training. Adversarial logit pairing (Kannan et al. 2018) and TRADES (Zhang et al.) (209b) further improve adversarial training by decomposing the prediction error as the sum of classification error and boundary error, and Wang et al. (2019) proposes improve adversarial training by evaluating the quality of adversarial examples using the FOSC metric.
Semi-supervised learning Using unlabeled data to help the learning process has been proved promising in different applications (Rasmus et al. 2015 Zhang & Shi 201 Elworthy 1994). Many approaches use regularizers called "soft constraints" to make the model "behave" well on unlabeled data. For example, transductive SVM (Joachims) 1999) uses prediction confidence as a soft con- straint, and graph-based SSL (Belkin et al., 2006 Talukdar & Crammer (009) requires the model to have similar outputs at endpoints of an edge. The most related work to ours the consistency- based SSL., It uses consistency as a soft constraint, which encourages the model to make consistent predictions on unlabeled data when small perturbation is added. The consistency metric can be ei- ther computed by the model's 's own predictions, such the II model (Sajjadi et al. (016). Temporal Ensembling (Laine & Aila 2016) and Virtual Adversarial Training (Miyato et al. 2018), or by the predictions of teacher model, such as the mean teacher model (Trvainen & Valpola 2017
Semi-supervised learning for adversarially robust generalization There are three other concur- rent and independent works (Carmon et al. 2019; [eeaat et al. [2019; Najafi et al. (2019) which also explore how to use unlabeled data to help adversarially robust generalization. We describe the three works below, and compare them with ours. See also Carmon et al. (2019) and Uesato et al. (2019)
for the comparison of all the four works from their perspective.
Najafi et al. (2019) investigate the robust semi supervise learning from the distributionally robust optimization perspective. They assign soft labels the unlabeled data according to an adversarial loss and train such images together with the labeled ones. Results on a wide range of tasks show that the proposed algorithm improves the adversarially robust generalization. Both Najafi al. (2019) and we conduct semi-supervisee experiments by removing labels from the training data.
Uesato al. 2019) study the Gaussian mixture model of SShhidd al. (2018) and theoretically show that a sel sell-nninnng algorithm can successfully leverage unlabeled data to improve adversarial robustness. They extend the self- self-training algorithm the real image dataset Cifarl0, augment it with unlabeled Tiny Image dataset and improve state-of-the-eee adversarial robustness. They show strong improvements in the low labeled data regimes by removing most labels from CIFAR- 10 and SVHN. In our work, we also study the Gaussian mixture model and show that a slightly different algorithm can improve adversarially robust generalization as well. We observe similar improvements using our algorithm Cifar-10 10 and MNIST.
Carmon et al. 2019) obtain similar theoretical and empirical results as in Uesato et al. (2019). and offer more comprehensive analysis of other aspects. They show that by using unlabeled data and robust self-training, the learned models can obtain better certified robustness against all possible attacks. Moreover, they study the impact of different training components on the final model performance, such as the size of unlabeled data. We also study the influence of different factors in experiments and have similar observations.
MAIN RESULTS
In this section, we illustrate the benefits of using unlabeled data for robust generalization from a theoretical perspective.
3.1 NOTATIONS AND DEFINITIONS
We consider standard classification task with underlying data distribution Pxy over pairs of examples x E Rd and corresponding labels E (1,2,-.. K). Usually Pxy is unknown and we can only access to S ((11,1); vn), .., (In:yn)} in which (s1, yt) is independent and identically
3

---

Under review as a conference paper at ICLR 2020
drawn from Pxy, i = 1,2, ,n For ease of reference, denote this empirical distribution as Pxy (i.e. the uniform distribution over i.i.d. sampled data). We also assume that we are given suitable loss function 1()(z), y). where f E F is parameterized by 0. The standard loss function the zero-one loss, i.e. 10/1 (v'' y) = Iyy + yl. Due to its discontinuous and non-differentiable nature, surrogate loss functions such as cross-entropy or mean square loss commonly used during optimization.
Our goal is find an f E that minimizes the expected classification risk. Without loss of any generality, our theory is mainly based on the binary classification problem, i.e. K = 2. All theorems
below can be easily extended to the multi-class classification problem. For binary classification problem, the expected classification risk is defined as below.
Definition 1. (Expected classification risk). Let Pxy be probability distribution Rdd {+1}, The expected classification risk R of a classifier f: IRd - { (-1,1] }} under distribution Pxy and loss function is defined
R = 1B=1laaaa (xx ((f v))
We use R(f) to denote the classification risk under the underlying distribution and use R(f) to denote the classification risk under the empirical distribution. We use (f) to denote the risk with the zero-one loss function. The classification risk characterizes whether the model f is accurate.
However, we also care about whether f is robust. For example, when input is an image, we hope a small change (perturbation) to x will not change the prediction of f. To this end, SShmidt et al. 2018) defines expected robust classification risk follows.
Definition 2. (Expected robust classification risk). Let Pxy be probability distribution over Rd x {+1} and B : I + P (IR") be a perturbation set. Then the B-robust classification risk Rg Rg-robust of classifier f: IRd {[1, under distribution Pxx and loss function / is defined
Rg-robust ((.,))~PxY sup I(f(x'),)) x'EB(w)
Again, we use Rg-robus to denote the expected robust classification risk under the underlying distribution and use R8- denote the expected robust classification risk under the empirical distribution. We use R (f) to denote the robust risk with the zero-one loss function. In real practice, the most commonly used setting is the perturbation under e-bounded foo norm constraint (x) = {z' E | 211.0 $ $}. For simplicity, we refer to the robustness defined by this perturbation set as 6x -robusttesss..
3.2 ROBUST GENERALIZATION ANALYSIS
Our first result (Section 3.2. 1) shows that unlabeled data can be used to improve adversarially robust generalization in general setting. Our second result (Section 3.2.2) shows that for a specific learning problem defined Gaussian mixture model, compared to previous work (Schmidt et al.) 2018). the sample complexity for robust generalization can be significantly reduced by using unlabeled data. Both results suggest that using unlabeled data is natural way improve adversarially robust generalization. All detailed proofs of the theorems and lemmas in this section can be found in the appendix.
3.2. GENERAL RESULTS
In this subsection, we show that the expected robust classification risk can be bounded by the sum of terms. The first term only depends on the hypothesis space and the unlabeled data, and the second term is standard PAC bound.
Theorem 1. Let F be the hypothesis space. Let S (I.,, y:) be the set of n i...d. samples drawn from the underlying distribution Pxy- For any function f E F, with probability at least 8 over the random draw of S, we have
log 2
R Rog-ro (f) S EENDx sup (I(f(z') + f(x)) 120 + Rad (F) + +3/ r'E((a)
(3)
2n
(2)
4

---

Under review as a conference paper at ICLR 2020
where (1) is term that can be optimized with only unlabeled data and (2) is the standard PAC generalization bound. Px is the marginal distribution for Pxy and Ra)s(F) is the empirical Rademacher complexity of hypothesis space F.
From Theorem [ we can see that the expected robust classification risk is bounded by the sum of two terms: the first term only involves the marginal distribution Px and the second term is the standard PAC generalization error bound. This shows that the expected robust risk minimization can be achieved by jointly optimizing the two terms simultaneously: we can optimize the first term using unlabeled data sampled from Px and optimize the second term using labeled data sampled from Pxy, which is the same as the standard supervised learning.
While Cullina et al. (0018) suggests that in the standard PAC learning scenario (only labeled data is considered), the generalization gap of robust risk can be sometimes uncontrollable by the capacity of hypothesis space F, our results show that we can mitigate this problem by introducing unlabeled data. In fact, following result shows that with enough unlabeled data, learning robust model can be almost as easy as learning a standard model.
3.2.2 LEARNING FROM GAUSSIAN MIXTURE MODEL
The learning problem defined on Gaussian mixture model is illustrated in (Schmidt et al. (2018) as an example to show adversarially robust generalization needs much more labeled data compared to standard generalization, In this subsection, we show that for this specific problem, just using more unlabeled data is enough to achieve adversarially robust generalization. For completeness, we first list the results in Schmiidt et al. (2018) and then show our theoretical findings.
Definition 3. (Gaussian mixture model (Schmidt et al. 2018)). ). Let l" E Rd be the per-class mean vector and let 0 be the variance parameter. Then the (0", .r) -ausssin mixture model is defined
by the following distribution Pxy over (zz, y) E IR x 1 First, draw a label E } uniformly at random. Then sample the data point x E Rd from N 8", I')).
Given the samples from the distribution defined above, the learning problem is to find a linear classifier to predict label y from SShhmitt et al. (2018) proved the following sample complexity bound for standard generalization.
Theorem 2. (Theorem 4 in Schniddt et al. (2018). Let (I,8) be drawn from the (0' a) a -Gaussian mixture model with |10- /dd and o S c-4 where e is universal constant. Let i E Bdd be the vector = y x. Then with high probability, the expected classification risk of the linear classifier fa using 0-1 loss is at most 1%.
Theorem suggests that we can learn a linear classifier with low classification risk (e.g.. 1%) even if there is only one labeled data. However, the following theorem shows that for adversarially robust generalization under & perturbation, significantly more labeled data is required.
Theorem 3. (Theorem 6 in Schmidt et al. (2018). Let In be any learning algorithm,, iee. a function C1 d244 lett 2 O, and let 0 Rdd be from n samples to binary classifier I'. Moreover, let (a,,r)-Guussian mixture model. Then the drawn from (0, Ia). We also draw n samples from the (0,
expected & robuust classification risk of fn using 0-1 loss at least {1 1/d) if the number of 2'Va labeled data C2 logd" d
As we can see from above theorem, the sample complexity for robust generalization is larger than that of standard generalization by Vd. This shows that for high-dimensional problems, adversarial robustness can provably require a significantly larger number of samples. We provide new result which shows that the learned model can be robust if there is only one labeled data and sufficiently many unlabeled data. Our theorem is stated as follow:
Theorem 4. Let (z". v²) be a labeled point drawn from (8" a")-Gassisinn mixture model PxY with ||0" I|2 = vd. and a = OAd/A)) Let ....... .Ill be unlabeled points drawn from Px- Let E Idd such that E arg max Ei (v 24)22 Let u sign(y- -o TT x Then there exists a constant D such that for any d 2 D, with high probability, the expected E -robust classification risk of fa using 0-1 loss is at most 1% when the number of unlabeled points n = ((d) and S 2-
From Theorem 4, we can see that when the number of unlabeled points is significant, we can learn highly accurate and robust model using only one labeled point.
5

---

Under review as a conference paper at ICLR 2020
Proof sketch The learning process can be intuitively described the following three steps: in the first step, we use unlabeled data to estimate the direction of l although we do not know the label that 0 (or -0") corresponds to. Specifically, quantity Σi=(v (v x; which can be viewed as a measure of the confidence at data points. In the second step.
choose the direction which maximizes the
the given labeled point to determine the sign of 0 with high probability, note that when the direction is correctly estimated in the first step, then the only one labeled point is sufficient give the correct sign with high probability. Finally, we give good estimation of 0 by combining the two steps above and learn robust classifier. The three key lemmas corresponding to the three steps are listed below (c; are constants for 0, 0,3.2.3)
Lemma 1. Under the same setting as Theorem suppose that n > and a
244 ad
Then, 128'
with probability at least 1 - cpe con min{ Vas Viles )?, there is unique unit maximal eigenvector
o of the sample covariance matrix = 1 Di x xt UT such that
0r
02 +
17
Vall2
S
cooV
nd + C3
(4)
Lemma 2. Under the same setting Theorem
4 suppose is unit vector such that 0
0r va
for some constant < 22. Then with probability at least - exp(- d(1 sign(y* . yuu="uuT 8r > 0
have
2n
(5)
Lemma 3. (Lemma 20 in in|Schmidt et al. (2018)) Under the same setting as Theorem 4 for any p 2
and 2 O, and for any unit vector w such that (1i, 0*) 2 <||iilf, where || [1 is the dual norm of
I|- pl the linear classifier f has e, -robust classification risk at most exp ((0,00)- >e 1 m0));)
2n
Our theoretical findings suggest that we can improve the adversarially robust generalization using unlabeled data. In the next section, we will present a practical algorithm for real applications, which further verifies our main results.
Algorithm Generalized Virtual Adversarial Training over labeled and unlabeled data
1: Input: Datasets 8 and S Hypothesis space F. Coefficient A. PGD step size 5. Number of PGD steps k. Maximum Lo norm of perturbation c.
2: for each iteration do
3: Sample a mini-batch of labeled data ŠL from SL.
4: Sample mini-batch of unlabeled data Se from SU.
5: for each x E 5 U S do
6: Fix ff and attack a with PGD-(k, e, 8) on loss / to obtain x'.
7: Perform gradient descent on f over the perturbed samples loss L SSL.
8: end for
9:
end for
4 ALGORITHM AND EXPERIMENTS
4.1 PRACTICAL ALGORITHM
Let 5 {[af ((af.vtt..... (arh, v a set of labeled data and 5 {off... ... , be set of unlabeled data. Motivated by the theory in the previous section, to achieve better adversarially robust generalization, we can optimize the classifier to be accurate on St. and robust on S U US" This is also equivalent to making the classifier accurate and robust on S and robust on S Therefore, design two loss terms on S and S separately.
For the labeled dataset SL, we use the standard e -roustt adversarial training objective function, i...
(ff = 1 Σ
max x (#))
CE (f((x))) v)).
(6)

---

Under review as a conference paper at ICLR 2020
Following the most common setting, during training, the classifier outputs probability distribution over categories and is evaluated by cross-entropy loss defined as
(CE (f(x))) = Σ log fa (x)lly = =
where fx) is the output probability for category k.
For unlabeled data S we use an objective function which measures robustness without ground truth
L2(f.8 1=1
max FC (f(2), 0r). where ú: = arg (fx((f( (x,)
(8)
Putting the two objective functions together, our training loss is defined as a combination of 4 and L2 as follows:
LSST "S,T,,
(") AL)
Here À > 0 is coefficient to trade off the two loss terms. In real practice, we use iterative optimiza- tion methods to learn the function f. In the inner loop, we fix the model and use Projected Gradient Descent (PGD) to learn the attack x' for any æ. In the outer loop, we use stochastic gradient descent to optimize f on the perturbed x's. s. The general training process shown in Algorithm) 1
Remark We notice that Algorithm[iis generalized version of Virtual Adversarial Training (VAT) (Miyato et al. 2018). When setting the PGD step k = 1, the algorithm is almost equivalent to the original VAT algorithm, which is particular useful for improving standard generalization. However, according to our experimental results below, setting t = does not help improve adversarial robust generalization. The improvement of adversarial robust generalization using unlabeled data exists when setting relatively larger k.
4.2 EXPERIMENTAL SETTING
We verify Algorithm| T on MNIST and Cifar- 10. Following Madry et al. (2017). we use the Resnet model and modify the network incorporating wider layers by a factor of 10. This results in net- work with five residual units with (16, 160, 320, 640) filters each. During training, we apply data augmentation including random crops and flips, well as per image standardization. The initial learning rate is 0.1, and decay by a factor of 10 twice during training. In the inner loop, we run 7-step PGD with step size 2 for each mini-batch. The perturbation is constrained be 255 1x norm.
under
255
Following many previous works (Laine & Aila 2016 Tarvainen & Valpola 2017: Miyato et al., 2018 Athiwaratkun et al. 2019), we sample 10k labeled data from the training set and use them as labeled data. We mask out the labels of the remaining images in the training set and use them as unlabeled data. By doing this, conduct two semi-supervised learning tasks and call them 5k/10k experiments. In a mini-batch, we sample 25/50 labeled images and 225/200 unlabeled several different values
images for the 5k/10k experiment respectively. In both experiments, of À as an ablation study for this hyperparameter by setting À = 0.1. 0.2, 0.3. Learning rate is decayed at the 60th and the th epoch. We use the original PGD>-bsee adversarial training (Madry et al. 2017) on the sampled 5k/10k: labeled data as the baseline algorithm for comparison (referred as PGD-adv). Our algorithm is referred as Ours.
4.3 EXPERIMENTAL RESULTS
We list all results of the 5k/10k experiments in Tables I and We use five criteria to evaluate the performance of the model: the natural training/test accuracy (NAtrain and NAtest), the robust training/test accuracy using PGD-7 attack (RAsrain and RAtest) and the defense success rate (DSR).
First, we can see that in both experiments, the robust test accuracy improved when we use un- labeled data. For example, Cifar-10 the robust test accuracy of the models trained under SSL with À = 0.3 for the 5k/10k experiments increase by 3.0/5.0 percents compared to the PGD-adv baselines. We also check the defense success rate which evaluates whether the model is robust given

---

Under review as a conference paper at ICLR 2020
Table SSL. experiment with 5k/10k labeled points on MNIST (%)
NAtrain
NArest
RAtroin
RA
DSR
PGD-adv on 5k:
98.31
98.38
96.95
96.89
98. 98.49
Ours (k 7, 0.1)
98.36
98.54
97.82
97.19
98.63
5k:
Ours (k: 7, A 0.2)
98.43
98.55
98.18
97.28
98.71
Ours (k: À 0.3)
98.56
98.56
98.46
97.31
98.73
PGD-adv on 10k:
98.91
98.83
97.96
97.64
98.80
Ours (k: 7, 0.1)
98.92
98.92
98.55
97.91
98.98
10k
Ours (k: = 7, X 0.2)
98.90
98.89
98.76
97.93
99.03
Ours (h: 7, 0.3)
98.93
98.87
98.77
98.01
99.13
PGD-adv on 50k
99.89
99.44
99.77
98.84
99.40
Table 2: SSL experiment with 5k /10k labeled points on Cifar-10 (%)
NAtrain
NArest
RAtrain
RA
DSR
Rdv on 5k
61.18
60.57
32.40
30.54
50.42
Ours (k 7, X 0.1)
63.24
60.44
32.97
30.90
51.13
5k:
Ours (k: = 7,
0.2)
61.73
60.71
35.20
32.96
54.29
Ours (k: =7, A = 0.3)
61.88
60.46
35.07
33.54
55.47
Ours (k: = 1, 0.3)
68.15
67.14
0.13
0.12
0.00
PGD-adv on 10k:
78.80
73.79
45.60
37.48
50.79
Ours (k: 7, X 0.1)
78.24
72.92
47.96
38.86
53.29
10k
Ours (A: 7, = 0.2)
78.74
73.16
51.20
41.18
56.29
Ours (I: 7, 0.3)
78.95
73.35
52.24
42.48
57.91
Ours (I: 1, 0.3)
81.43
78.64
2.22
2.27
0.03
PGD-adv on 50k
99.91
85.40
96.71
49.99
58.54
the prediction is correct. As we can see from the last column in Tables and 2 the defense success rate models trained using our proposed method is much higher than the baselines. In particular, the defense success rate of the model trained with À 0.3 in the 10k experiment is competitive to the model trained using PGD-ady on the whole dataset. This clearly shows the advantage of our proposed algorithm.
Second, we can also see the influence of the value of The model trained with a larger has higher robust accuracy. For example, in the 10k experiment, the robust test accuracy of the model trained with À = 0.3 is more than 3% better than that with = 0.1. However, we observe that training will become hard to converge À > 0.5.
Third, using larger & produces more robust models. As we can see from the table, in the 1100k experiment, relatively higher natural training/test accuracy can be achieved by setting k = (vanilla VAT algorithm). However, the robust training/testing accuracy are significantly worse and are near zero. This clearly shows that using a stronger attack both labeled and unlabeled data leads to better adversarially robust generalization, which is also consistent with our theory.
CONCLUSION
In this paper, we theoretically and empirically show that with just more unlabeled data, we can learn models with better adversarially robust generalization. We first give an expected robust risk decomposition theorem and then show that for specific learning problem the Gaussian mixture model. the adversarially robust generalization can be almost as easy as standard generalization. Based on these theoretical results, develop algorithm which leverages unlabeled data during training and empirically show its advantage. As future work, we will study the sample complexity of unlabeled data for broader function classes and solve more challenging real tasks.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Cireumventing defenses to adversarial examples. CoRR, abs/1802.00420, 2018.
Ben Athiwaratkun, Mare Finzi, Pavel Izmailov, and Andrew Gordon Wilson. There are many con-
sistent explanations of unlabeled data: Why you should average. In International Conference Learning Representations, 2019.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-24344 2006.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Sindić, Pavel Laskov, Gior- gio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. Joint European conference machine learning and knowledge discovery in databases, pp. 387-402. Springer, 2013.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. CoRR, Abs/1600.00644 2016.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John Duchi. Unlabeled data improves adversarial robustness. arXiv preprint 1rXiv 2019.
Liang-Chiel Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam. Encoder- decoder with atrous separable convolution for semantic image segmentation. arXiv preprint arXiv:1802.. 026. 2018.
Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of evasion adversaries. arXiv preprint (..iv:180060147711 2018.
David Elworthy. Does baum-welch re-estimation help taggers? In Proceedings of the Fourth Conference on Applied Natural Language Processing, ANLC '94, pp. 53-58, Stroudsburg, PA, USA, 1994. Association for Computational Linguistics. doi: 10.311559743389743777 URL
974371
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. Adversarial vulnerability for any classifier. arXiv preprint arXiv: 180.088600 2018.
Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsich, and Jason Lec. Convergence of adversarial training in overparametrized networks. arXiv preprint arXiv: 1906.07916, 2019.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Jie Hu, Li Shen, and Gang Sun. Squeezz-and-eecitation networks. arXiv preprint 0770:770077 7, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, volume 1(2), pp. 3, 2017.
Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with a strong adver- 2015.
sary. arXiv preprint
Thorsten Joachims. Transductive inference for text classification using support vector machines. In Proceedings of the Sixteenth International Conference on Machine Learning, ICMI. '99, pp. 200- 209, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1-55860-612-2.
Harini Kannan, Alexey Kurakin, and lan Goodfellow. Adversarial logit pairing. CoRR, /ts/1803.06333, 2018.

---

Under review as a conference paper at ICLR 2020
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. CoRR, abs/1610.02242,, 2016.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 22222222222, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436, 2015.
Tsung-Yi Yi Lin, Priyal Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. IEEE transactions on pattern analysis and machine intelligence, 2018.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3431-3440, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 1rXiv:1706006065 2017.
Takeru Miyato, Shin-ichi Maeda, Shin Ishii, and Masanori Koyama. Virtual adversarial training: a regularization method for supervised and semi-supervised learning. IEEE transactions pattern analysis and machine intelligence, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012. ISBN 778-0-262-018255
Seyed-Mohsen Koosavi-Dezzfool: Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Amir Najafi, Shin-ichi Maeda, Masanori Koyama, and Takeru Miyato. Robustness to adversarial perturbations in learning from incomplete data. arXiv preprint arXiv:1905. 13021, 2019.
Nicolas Papernot, Patrick D. McDaniel, and lan Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. CoRR, abs/1600 flss/1605.0722 002277,77 2016.
Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko. Semi- supervised learning with ladder networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 3546-3554 Curran Associates, Inc., 2015.
Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unified, real-time object detection. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 779-788, 2016.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91-9999999999 2015.
Mehdi Sajjadi, Mchran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transforma- tions and perturbations for deep semi-supervised learning. CoRR, 0bs/1606.005888 2016.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. Advances in Neural Information Processing Systems, pp. 5019-5031, 2018.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprins arXiv: 12843, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409 1556, 2014.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. CoRR, abs/1312.6199, 2013.
10

---

Under review as a conference paper at ICLR 2020
Partha Pratim Talukdar and Koby Crammer. New regularized algorithms for transductive learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. Springer, 2009.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged con- sistency targets improve semi-supervised deep learning results. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1195-1204. Curran Associates, Inc., 2017.
Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri. Learning spa- tiotemporal features with 3d convolutional networks. In Proceedings of the IEEE international conference on computer vision, pp. 14489-4497222
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representa- lions, 2019.
Jonathan Uesato, Jean-Baptiste Alayrac, Po-Sen Huang, Robert Stanforth, Alhussein Fawzi, and Pushmeet Kohli. Are labels required for improving adversarial robustness? CoRR, abs/1905.13722, 2019. http::/paaa....org///////// wwtp://s......e...e../../ 13725
Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2019. doi: 10.1017/ 9781 10862771..
Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool. Temporal segment networks: Towards good practices for deep action recognition. European Conference on Computer Vision, pp. 20-36. Springer, 2016.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1(3), pp. 4, 2018.
Yisen Wang. Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness adversarial training. In Kamalika Chaudhuri and Ruslan Salakhut- dinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 09-15 Jun 2019, PMLR.
Long Beach, California, USA,
Bing Zhang and Mingguang Shi. Semi-supervised learning improves gene expression-based predic- tion of cancer recurrence. Bioinformatics, 27(21):301733023, 09 2011. ISSN 1367-4803. doi: 10..093/hoinfomaati//bttt0
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Painless adversarial training using maximal principle. arXiv preprint arXiv:1905.000 00877, 2019a.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pp. 7472-7482, Long Beach, California, USA, 09-15 15 Jun 2019b. PMLR.
Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia. Pyramid scene parsing network. In JEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 2881-2890, 2017.
11

---

Under review as a conference paper at ICLR 2020
A BACKGROUND ON GENERALIZATION AND RADEMACHER COMPLEXITY
The Rademacher complexity a commonly used capacity measure for a hypothesis space. Definition 4. Given set S = {I1,.... .... Fn. } of n samples, the empirical Rademacher complexity of function class (mapping from F R) is defined as:
1 Ee n
(Fd
sup FEF
(10)
where == (61,-' Cn) contains i.idd random variables drawn from the Rademacher distribution (n,f((1,-1))
By using the Rademacher complexity, we directly provide upper bound on the generalization error
Theorem 5. (Theorem 3.5 in Mohri et al. 2012 Suppose U(, :) the 0 loss, let S (x,, yt)i= be the set of ii.d samples drawn from the underlining distribution PxY. Let F be the hypothesis space, then with probability at least 1 over S. for any E F:
log
R(f) s R(f) + Rads +0+++) +31
(11)
2n
B PROOF OF THEOREM
Proof. For indicator function 1. we have for any
T(f(x') # v) s T(((x) # v) + T(((x) # f(x1))
(12)
According to Definition 2 we have
Rg-robus (f) = E (Px
sup 1(f(z').v) = B(aN)~PxY sup I(f(x') $ y) x'E((s)
<EB(x>
sup (T(f(x) * 1) + +T(((o) + f(x'))
(13)
e'E((z)
EppPx sup x'E((z)
(I(f(z') * f(z)) (xa) l (ff(x),))
= ExpPx sup x'E((z)
(T(f(z²)) f(x)) + R(J),
where 13 derived from
12
We further use Theorem to bound R(J). It is easy to verify that 0. for any SEZ F:
with probability at least
Rs RB-robuc (f) ExaPx sup (I(f(x') + f(x)) R(f)
of x'E((x)
log
E sup (I(f(z') + f(x)) + R(f) Rods(F) 3// r'E((z)
E
2n
which completes the proof.
C PROOF OF THEOREM
For convenience, in this section, we use a; or cf to denote some universal constants, where i 0, 4.
In the proof of Theorem we will use the concentration bound for covariance estimation in Wain- wright (2019). We first introduce the definition of spiked covariance ensemble.
Definition 5. (Spiked covariance ensemble). A sample E IRd from the spiked covariance ensem- ble takes the form
T₁ vv,00 + wi, where & IR is zero-mean random variable with unit variance, IR is a fixed scalar, 0g Rd is a fixed unit vector and w; e Rdd is a random vector independent of &., with zero mean and covariance matrix It_
(14)
12

---

Under review as a conference paper at ICLR 2020
To see why spiked covariance ensemble model is useful, note that the Gaussian mixture model its special case. Specifically, let x!' be the unlabeled data in Theorem 4 Then œद follows
the Gaussian mixture distribution "N(0", IIIa) + = Ia),,, and x² a is spiked covariance ensemble with parameter o² 5 uniformly distributed on {=1}. w; ~ (O, and 0o = 0- va The following theorem from Wainwright (2019) characterizes the concentration property of spiked covariance ensemble, which we will further use to bound the robust classification error. Intuitively, the theorem says that using the top eigenvector Ô of the sample covariance matrix Σ.
approximately recover Og in the spiked covariance ensemble model
Theorem 6. (Concentration of covariance estimation, see Corollary 8.7 in Wainwright (2019))
Given i.i.d. samples {xi)'=1 from the spiked covariance ensemble with sub-Gaussian tails (which means both E, and wi are sub- sub-Gaussian with parameter at most one), suppose that n >> d and 128 Then, with probability at least 1 - c1e min (in there is unique maximal eigenvector 0 of the sample covariance malrix Σ EE stae such that
e01|2
+
+
(15)
n
Using the theorem above, we can show that for the Gaussian mixture model, one of the top unit eigenvector the sample covariance matrix is approximately o" In other words, we can approxi-
V/"
mately recover the parameter l* up to a sign difference: the principal component analysis of Σ gives either u. while 0- is close to v.
Lemma 4. Under the same setting as Theorem
suppose that n. > d and a a
Then, 128'
with probability at least 1 cie-can can mint Ldrs the sample covariance matrix Σ
y?, there is unique maximal eigenvector of with unit Eg norm such that
1 1 x TT
A
0² 2
S To minocoory
+ C3, /2}
(16)
Vd
nd
Proof. As discussed above, 2f is a spiked covariance ensemble. By Theorem we have with probability at least oie can mint vddeg ,( (vara) there is unique maximal eigenvector é of the UT such that
sample covariance matrix E
D
a x
0"
02 +
S o
nd + cz.
(17)
Vdl
2
Let cio v gz+d and 1.
+ dg. we have
6"
S r. Below we need consider two cases, T S
nd
vd
2
Case 1: r < 1. Let
à |
since both v and
are unit vectors, we have
Va
A+
8
H' = 2
A" Vd
|0||
2(v, Va
22e2(v
(18)
Vd
Recall that
0-
< r. which is equivalent to
2
0"
2( 6"
+
Va
0" Va
|
+
||||| (0,
Rearranging the terms and using AM-GM inequality gives
0"
72
2(v,
> ||||| +
2 2
1- 2
(19)
Vd
|0||
13

---

Under review as a conference paper at ICLR 2020
Therefore, by equation 18
0"
0+
2(u.
vd
Vd
2V 1 72
27²
1+ v1 72
72
S 22
02 +
V2(go
+ tg).
nd
By substituting Co = 22 02 = 2/2 and C3 = /2dg, we complete the proof.
Case 2: T > 1. Let be one of शلā both v and 0* are unit vectors, we have va
such that the the inner product (v. 0*) nonnegative. Since
0+ Vd
0" 2
0+
v
|00| 2
+
Vd
2(U,
vd
vd (u,0") S
(20)
Therefore,
v
8r Val
I V2-
Now we have proved that by using the top eigenvector of Σ, we can recover the 8" up to a sign difference. Next, we will show that is possible determine the sign using the labeled data.
Lemma 5. Under the same setting Theorem suppose Rd is unit vector such that
d(1 15
0" I where S V2. Then with probability at least exp Va have sign(y" T x TT
g > O.
Proof. Since
8"
S
V2, and both and g are unit vectors, we have vT 0. So the
Vol 2
event (sign(y x jr or s 0) is equivalent to the event (y- v TTat s 0).ie.
P|sign(y" u y 0r s <0 = Ply".. . vT xt < 0]
(21)
Recall that æ- is sampled from the Gaussian distribution N(y² 0r, La), where y² is sampled uniformly random from [+1], we have (y'x') follows the Gaussian distribution \/00 o Ia).). Hence,
Ply v x ~0 = P(y wn (w*x4) (y/t)) S 20] = Po-N((.1))
[g s
(22)
σ
Moreover, from
10-
0' || Val
S TO we can get
(0), (0",0) vd(11 _t.
(23)
So, using the Gaussian tail bound P V ni. < -t] < exp(-t? for all t E R, and combining
with equation 2T] equation 22] equation 23
we have
d(1- 3
d(1
(y .o
TT a To < 0J exp
(24)
20
stated in the lemma.
14

---

Under review as a conference paper at ICLR 2020
Armed with Lemma and Lemma we now have precise estimation of 6" in the Gaussian mixture model. Then, we will show that the high precision of the estimation can be translated to low robust risk. To achieve this, need lemma from Schmiitt et al. (2018), which upper bounds the robust classification risk of a linear classifier u in terms of its inner product with 0"
Lemma (Lemma 20 in Schniddt et al. (2018)). Under the same setting as in Theorem 4 for any p 2 1 and 2 O, and for any unit vector v E R such that (w, (0) 2 = where -I ll is the dual norm of || Il.- the linear classifier fo has Cg -robust classification risk at most
(1b.0")-<llee =11001
exp
2
Lemma guarantees that if we can estimate #* precisely, we can achieve small robust classification risk. Combine with Lemma 4 and Lemma [ which provide such estimation, we are now ready to prove the robust classification risk bound stated in Theorem 4 We can actually prove a slightly more general theorem below with some extra parameters, and obtain Theorem 4 as a corollary.
Theorem 7. Let (xt y²) be labeled data drawn from (0" -aG-sssiaann mixture model PXY with |10*|1 Vd. Let ......, ..% be unlabeled data drawn from Px. Let To be as stated in Lemma f and u E pd be the normalized eigenvector (i.e. ||v||| 1) with respect to the maximal eigenvalue of x xf such that | vall To with probability least
1 cje- min Vdos .l Vuea p2) Let v = sign(y" v xt)o. Then with probability at least
1 - cie c2n min Sasa ( (assy) exp(
di1 di1- 181²
the linear classifier fa has e rrbust classi-
2
fication risk at most 3 when
22
0 2
$
(25)
Vd
Proof. By the choice of u have equation 23 holds, i.e.
2 (0", 2 dd(1=
)
(26)
2
with probability at least e can min Videg Vide
can
)2}.
Applying Lemma to yields
sign(y" f. v To " 00,
(27)
with probability at least exp( d(1 2
Notice that v = sign(y" v x²)u. So by union bound on events equation 26 and equation 27 we
have
TO ) (0", w) sign(y* u x00 F) 2 vd(1
(28)
2
with probability at least - eie ogn min viles , Aen )2) exp( d(1
2 20
Since ||20|| 1, we have
| = =| < vd.
(29)
By Lemma 6 we have the E -robust error is upper bounded by
((úr, 0-)
E 01 |
Rs robust (fa) S exp
(30)
20
Combining this with equation 28 equation
29 and the assumption equation 25 we have
0
2
1
T - Vd
I
(0,0' )- - =||10|1 2 vd(1
= o
2
(31)
2
2
Vd
3
15

---

Under review as a conference paper at ICLR 2020
Hence,
(ov log
R
robust (fib) S exp
= 1,
(32)
20
d(1- 18 ), stated in the theorem.
with probability at least 1 - C1e e can can (
exp(
2n
Now we are ready to prove Theorem
Proof of Theorem Let e be a constant such that 0 I c. dd/4 for sufficiently large Notice that the vi in Theorem 4 is same the in Theorem since the maximal eigenveetor of > 2! 24 UT
also maximizes
Ei= (v ) over the unit sphere ||0| 1, Rdd Theorem 7 guarantees that
d(1- 1
with probability at least eie can min Jes
Ses (3 exp(
20 ), e robbsst classification
risk is less then B = 0.01 for
2 log
0
e E
Vd
2log
Tu
1 -
2
d1/4
Choose C3 to be 2. Since n = (d).,
2 S = 000 /
r2+d
+
03
S cs
214 + 2/2 and consequently
T + va by Theorem with probability at least 1-c exp (-c) -exp (-ova).
f -rbust classification risk is less then 0.01 for
C
TO
2
d'/4
cv log
de/4
Since C42 e are numerical constants, there exists a constant D such that when 2 D, E robustt classification risk is less then 3 0.01 for 2, thus we have completed the proof.
16


Reviews:
[{"review_id": "rkguDO1iFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the sample complexity of adversarially robust learning with access to unlabeled samples. Theoretically, they consider the setting of Schmidt et al. 2018 (separating two class-conditional Gaussians) and present an algorithm which can learn a robust classifier with only a few labeled samples and a large number of unlabeled samples (circumventing the sample complexity separation of the original work). Then, the authors propose a modification of the VAT algorithm (Miyato et al. 2018) to train deep networks utilizing unlabeled samples. They find that, empirically, their algorithm achieves better performance compared to standard adversarial training on the labeled samples.\n\nOverall, the paper addresses an interesting problem, studying both a simple theoretical setting and a real-world empirical setting in which the authors achieve an improvement over prior work.\n\nUnfortunately, the paper is concurrent with two other works (which the authors acknowledge: Carmon et al. 2019, Uesato et al. 2019) which have already been accepted for publication at NeurIPS 2019. All of these works are very similar in spirit, proposing an algorithm for the theoretical setting of Schmidt et al. 2018 and an empirical algorithm for real-world settings. Moreover, these works improve over the current manuscript in a number of ways:\n-- The algorithm proposed for the theoretical setting is more general and is essentially the same as the algorithm used for real-world dataset.\n-- The experimental evaluation is significantly more extensive, performing additional ablations, and exploring the methods in more detail. The work of Uesato et al. 2019 is virtually a superset of the results in this manuscript.\n-- Both works collect additional images from an unlabeled and uncurated dataset (Tiny Images) and show that they can utilize them using their proposed approach to improve the state-of-the-art robust accuracy on CIFAR10.\n\nTherefore, given that: a) the results in the current manuscript are essentially a subset of the results appearing in Carmon et al. 2019 and Uesato et al. 2019 and b) these works will have already been published at NeurIPS 2019, 4 months before ICLR 2020, I am afraid I need to recommend rejection.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1xM7hwjFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper summary: This paper seeks to improve robust generalization performance with the help of unlabeled data. The authors first consider the toy model presented in Schmidt et al. and show how the labeled sample complexity in the robust setting can be lowered to match the standard setting if sufficient unlabeled data is available. They then propose a practical algorithm to improve robust test accuracy and evaluate it on the MNIST and CIFAR datasets.\n\nComments: The problem the paper seeks to address (bridging the generalization gap in the adversarial setting) is an important one, and the paper is clear and well-written. \n\nAs the authors discuss, there have been three (other) independent papers that tackle the same problem (which were accepted at NeurIPS). Even though I tried to evaluate this paper keeping in mind that it was written concurrently, I think it falls short in a couple of important aspects which make it hard to recommend acceptance. In particular:\n\n1. Unlike the other papers, the algorithm discussed in the theoretical section (which is able to reduce sample complexity by leveraging unlabeled data) is entirely different from the one used in practice on MNIST/CIFAR. It would make for a more compelling case if the algorithm used experimentally could also work on the toy model or vice versa (which is the case for Carmon et al. and Uesato et al.).\n\n2 . The empirical evaluation is not detailed enough and there is some inconsistency in the baselines. \n\n- In particular, the authors report that VAT attains poor robustness (<2.5% for both 5k and 10k labeled). However, Uesato et al. also benchmark against VAT in a very similar setting of 4k labelled CIFAR data points (with the same eps=8/255) and get ~32% accuracy (cf. Figure 1 from their paper). I could not find any difference between the two baselines except for the fact that Uesato et al. implement VAT with a KL divergence penalty (as suggested in the VAT paper) instead of cross entropy (as is used in this paper). This is somewhat concerning because based on the baselines reported in Uesato et al., the improvement of the approach proposed in this paper (which comes from doing 7 steps instead of 1 to find the adversarial example) are marginal. (Additionally, in this setting the approach of Uesato et al. gets robustness of about ~45% which is significantly better than ~33% reported in this paper.) \n\n- Moreover, this paper evaluates on much fewer benchmarks (only MNIST/CIFAR with few labeled examples) compared to the other papers (which also study for example SVHN and the impact of using unlabeled ImageNet on CIFAR robustness). \n\nThe overlap with concurrent work is unfortunate, and it makes it hard to evaluate this paper. However, my two main concerns are (1) inconsistency in baselines which cast some doubt on the improvements offered by the proposed approach, and (2) the fact that both the algorithm and the experimental evaluation seem to be a subset of that in concurrent work (especially Uesato et al.). Thus, I have to recommend rejection.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1ljO9uCYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of adversarial robustness. The paper shows that (Theorem 1) robust generalization error can be bounded in terms of the standard generalization error and a stability term, that does not depend on the labels. The paper also shows that for a simple classification problem involving learning the separator for a symmetric 2 gaussian mixture data, we can solve this problem robustly without additional labeled examples. The paper suggests that we can use unlabeled data to improve the robust generalization. Towards this the paper regularizer on the unlabeled data, that promotes stability in the model prediction. The paper evaluates this on Mnist and Cifar showing the better performance of the proposed regularization over PGD adversarial training.\n\nThe Theorem 1 in this paper is a triangle inequality on the loss ,and the observation about splitting the robust generalization into standard generalization error and stability, is not particularly new. The earlier work Zhang et al., 2019b show a similar result in their paper. They even propose and experiment with a similar regularizer (see eqs 3 and 5 in Zhang et al., 2019b). The exact implementation while can be different between these two, the paper does not currently compare with this and there is no evidence to prefer this regularizer over the existing one.\n\nThe Gaussian setting considered in this paper is quite simple and the techniques developed there are particular to the symmetric 2 Gaussian mixture problem. Given the other parallel works studying the same setting, it is good to also include a comparison of the exact results (such as sample complexity) for this setup.\n\nOverall I find the contributions of this paper to be not sufficient and cannot recommend acceptance at this stage.\n\nMinor:\nThe last line above theorem 4 and second line after eq 9 are written poorly.\n\n Zhang et al., 2019b  https://arxiv.org/abs/1901.08573", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work starts with a decomposition of the adversarial risk into two terms: the first is the usual risk, while the second is a stability term, that captures the possible effect of an adversarial perturbation. The insight of this work is that this second term can be dealt with using unlabelled data, which is often in plentiful supply. Unfortunately, the same ideas was developed concurrently and independently by several groups of authors.

The reviewer all agreed that this particular version was not ready for publication. In two cases, the authors compared the work unfavorably with concurrent independent work. I will note that the main bound somewhat ignores the issue of overfitting that the second term deals with via the Rademacher bound. Unless one assumes one has unlimited unlabeled data, could one not get an arbitrarily biased view of robustness from the sample. Seems like a gap to fill.
Decision: Reject