When Covariate-shifted Data Augmentation Increases Test Error And How to Fix It
Authors: Sang Michael Xie*
Aditi Raghunathan*
Fanny Yang
John C. Duchi
Percy Liang
Venue:  (2020)
Keywords: data augmentation
adversarial training
interpolation
overparameterized

Abstract: Empirically, data augmentation sometimes improves and sometimes hurts test error, even when only adding points with labels from the true conditional distribution that the hypothesis class is expressive enough to fit.  In this paper, we provide precise conditions under which data augmentation hurts test accuracy for minimum norm estimators in linear regression. To mitigate the failure modes of augmentation, we introduce X-regularization, which uses unlabeled data to regularize the parameters towards the non-augmented estimate. We prove that our new estimator never hurts test error and exhibits significant improvements over adversarial data augmentation on CIFAR-10.

Under review as conference paper at ICLR 2020
WHEN COVARIATE-SHIFTED DATA AUGMENTATION INCREASES TEST ERROR AND How TO FIX IT
Anonymous authors Paper under double-blind review
ABSTRACT
We study covariate-shifted data augmentation where the augmented targets are drawn from the true predictive distribution but the inputs are shifted. Empirically, some forms of data augmentation such adversarial training improve robustness, but increase test error. We provide precise conditions under which data augmentation can increase test error for minimum norm interpolation estimators in linear regres- sion. As a fix, we propose X- X-regularization which uses unlabeled data to regularize the parameters towards the non-augmented estimate. We prove that augmentation with X-regularization never increases test error in linear regression. Empirically, X- X-regularization consistently improves both robustness and standard test error across different adversarial training algorithms and perturbations on CIFAR- 10.
INTRODUCTION
Adversarial training improves the robustness of neural networks to perturbations, commonly referred to adversarial examples (Goodfellow al. 2015 Szegedy et al. 2014 Biggio et al. (003)). However, adversarial training also causes an undesirable increase in the error on the unperturbed images (test error). How do we obtain both robust and accurate networks? At the core, adversarial training is form of data augmentation where we augment the training set with worst-case perturbations of each training image within ball defined by the attack model. In this work, we study the general question of how to train classifiers on augmented training data without causing an increase in test error, while simultaneously preserving the benefits of augmentation such as robustness.
First, we analyze why some forms of data augmentation such with adversarial Loo perturbations increase error. Previous works (Tsipras al. 2019 Zhang et al. 2019 Fawzi et al. 2018 Nakkiran 2019) provide simple constructions to explain the increase in test error with adversarial perturbations, but rely on assumptions, such as incorrect labeling of the adversarial perturbations or insufficient complexity of the hypothesis class, that we do not expect to hold in practice. We seek a simple theoretical setup that can shed light on why augmentation, even with label tabel-preserving perturbations in well-specified setting, causes increase in test error. On the surface, it seems like we have only added information about the label distribution, so why does the test error increase?
In this work, we theoretically study minimum norm interpolation in well-specified linear regression, and show that data augmentation with label-preserving perturbations can increase the test error in some regimes, even when the targets are noiseless. For example, Figure I illustrates function interpolation problem via cubic splines which exemplifies this phenomenon. Without data augmentation, the estimated predictor (dashed blue) is a line that captures the global structure and obtains low eтror. Data augmentation with local perturbations (crosses) encourages the predictor to fit the local structure of the high density points but compromises the global structure on the tail (solid orange) [Figure[[b)). We show that this tension between local and global fit stems from the estimator having the wrong inductive bias. In particular, the minimum norm estimator minimizes a generic parameter norm while the test error is measured by possibly different norm the parameter error vector which depends on the data distribution (Section Further, one might expect augmentation to be most helpful in low data settings. We show that linear regression, this is also exactly the regime where augmentation can be most harmful. On real datasets, we similarly observe that data augmentation can be more detrimental with a smaller original training set (Section(5).
Motivated by our analysis of interpolation in linear regression, we propose a new estimator for data augmentation based on X-regularization (Section 6). X-regularization encourages the data augmented

---

Under review as conference paper at ICLR 2020
Std
Aug
Xreg
Kay
Xai
2
0 2 6
2
4
0
2
We consider perfectly fitting training points using cubic splines while minimizing smoothness of the function. (Left) depicts the true function I and the mass Pay on each point (x.y) size of the circles) (Middle) With a small number of standard training samples (circles) from the distribution depicted in (a), augmentating the dataset with local perturbations (crosses) causes the augmented estimator to have larger enror than the standard estimator due to being maximally smooth while also fitting the augmented local perturbations. (Right) Our proposed X-regularization regularizes the model predictions towards the predictions of standard model (trained without perturbations) on unlabeled data, allowing for fitting both the local and global structure.
Figure 1:
interpolant to stay close the original interpolant while fitting the extra augmented points. We prove that X-regularization eliminates the increase in test error upon data augmentation in the case of noiseless linear regression. See Figure for its effect on the spline interpolation problem.
X- X-regularization naturally extends more general losses and complex models and is closely related to self-training (Scudder 1965), the classical semisupervised learning algorithm. For the particular setting of robustness, E-regularization applied to adversarial training takes the form of robust self-training (RST) that was recently proposed in (Carmon et al. 2019 Najafi et al. 2019 Uesato et al. 2019). The previous works view RST way to beat the sample complexity barrier of robustness. By showing that RST is an instantiation of X-regularization, we motivate RST as an appropriate data dependent regular- izer that improves both standard accuracy and robustness. We evaluate the effect of RST standard and robust accuracy with different adversarial training losses and perturbations on CIFAR- 10 in Section 6.3 With lo perturbations, even improving the robustness achieved by the vanilla adversarial training counterpart. With random and adversarial rotations, RST improves standard accuracy by ~ 1% and robust accuracy by 1 -3%. Our experiments suggest that RST, and more broadly using unlabeled data with X X-regularization, is a promis- ing approach to mitigate the undesirable drop standard accuracy when training robust networks.
find that RST improves standard accuracy by 6% while maintaining or
RELATED WORK
The detrimental effect of data augmentation has been previously studied in the context of "tradeoff" between accuracy and robustness.
Understanding the tradeoff. In an attempt to explain the tradeoff between robustness and accuracy, Tsipras et al. (2019); et al. (2019) Fawzi et al. (2118) Nakkiran (2019) provide simple constructions that showease inherent tension between these objectives even the limit of infinite data. These constructions rely on either non-label loblleel-preserving perturbations or insufficient model complexity to express robust and accurate classifier. However, in practice, we typically augment with "imperceptible" perturbations that do not change the label, and we assume large neural networks used in practice to be expressive enough to contain a robust and accurate classifier. We address both these insufficiencies by studying covariate-shifted data augmentation where the extra data is labeled according to the same predictive distribution as the original data, and well-specified linear regression.
Mitigating the tradeoff. Existing proposals to mitigate the observed increase in standard error caused by adversarial augmentations are based on finding better architectures via Neural Architecture Search (Cubuk al. 2017) changing the neural net training algorithm (Lamb et al. 2019). While these methods have shown some success, they are restricted to neural networks. We complement this line of work by studying this tradeoff more generally and also provide some theoretical justification.
2

---

Under review as conference paper at ICLR 2020
3 SETUP
3.1
COVARIATE-SHIFTED DATA AUGMENTATION.
Let Pay denote the underlying distribution of (x.y) pairs, Px its marginal on R and P. (x) the conditional distribution of the targets given inputs.
We refer to the training data from the underlying distribution Pay by standard training data. Formally, have n pairs (It,3)) Pay forming the measurement matrix X = (21,22)--- R and target vector !/sdd = 31......... ERR
Analogously we consider augmenting the training set with "extra" training points denoted by Xex - [1 , [m. [R with associated targets yext - [ .m. E ER.. We focus on covariate-shifter data augmentations which includes most forms of data augmentations used in practice
Here, the targets you are drawn from the same underlying predictive distribution Py(: x) as the standard data, while the extra inputs Xex could be arbitrary.
Examples. Typically the "extra" training points are constructed as follows: 2; (x;), 9: ys- where T is some label-preserving transformation thereby enforcing that the extra targets are as if sampled from (- 2z). Example transformations include translations, horizontal flips, small rotations, small foo perturbations in vision, and replacing words with their synonyms in NLP. However, our treatment of data augmentation in this work is more general where Xext is not necessarily obtained via transformations of Xsd. Empirically, our main focus is on mitigating the increase in test error upon adversarial training. Most popular forms of adversarial training are instances of covariate-shiee shifted data augmentation. Consider projected gradient adversarial training (PG-AT) (Madry al. 2018) which confers robustness to adversarial examples (Szegedy et al. 2014) but also causes an increase in standard test error. PG-AT can be viewed form of iterative data augmentation that falls in framework above. Formally, let (xx) be the set of perturbations of æ that we would like to be robust against. We assume that the label is constant over (xr). The transformation step I of the training for data point x; is (x,,) = argmax ((0)),,.3)i,, where 0g are the model parameters at time step t. ze B(,))
The worst-case (max loss) perturbation is approximated via the projected gradient method.
3.2 MINIMUM NORM INTERPOLATION IN WELL-SPECIFIED LINEAR REGRESSION
Consider a regression task where the targets y E R are drawn from the conditional distribution =((1x)))((x> 0*,a), for some vector 0* E R.. Our goal is to learn a linear predictor fa(x) =xx
In this work, we focus on interpolating estimators, which draws motivation from modern machine learning models that achieve near zero training loss (on both standard and extra augmented points).
Interpolating estimators for linear models are analyzed in many recent works (Ma et al.) 2018 Belkin al. 2018 Hastie et al. 2019 Liang & Rakhlin 2018 8 Bartlett al. 2019). We present our results for interpolating linear regression estimators with minimum Euclidean norm, but our analysis directly applies to more general Mahalanobis norms via suitable rotations. See Appendix A Given inputs X E xd xd and corresponding targets Y R as training data, we define the following minimum norm interpolation estimator
i = arggmin 1101: 8
particular, we compare the following estimators : (i) the standard estimator Oua which has [aal as training data and (ii) the data augmented estimator &aog with X [Xaadi = [Baad Bext] as training data:
8rd = argmmin [10]12: Xuu0= you and = [10112
yru yax Mexs
(2)
4 BIAS AND VARIANCE OF MINIMUM NORM INTERPOLANTS
We evaluate the two estimators described in Equation using the error on a random sample Tiest drawn from Px. Let E be the covariance of Px. We focus the error conditioned on X sut Xex which
3

---

Under review as conference paper at ICLR 2020
decomposes into bias and variance term as follows
R(O) = E [ Tex (0-0)) 0²) - E(0-0")
E 0*) E(E 0" +r tr((Cor(0))
Bias
B(O)
Variance V(0)
where the expectation is taken over the randomness Jiest and targets Y/sdd yext conditioned on Xsa, Nex. In this section, we treat X as fixed quantities. However, since Xsu consists of samples from Ps. the number of samples dictates some structure Xsu- We touch upon this aspect in Section ?? where we study how the effect of augmentation varies with the number of samples in the original training set, both theoretically and empirically.
4.1 BIAS MINIMUM NORM INTERPOLANTS
For minimum norm interpolant with X,Y as training data, the bias term B(O) can be expressed as follows. On expectation (over targets Y), any interpolating estimator recovers 0 in the column space of X, but is unconstrained in Null(XX X). The minimum norm interpolant sets the component in Null(X X) to zero. Formally,
E xx =()
11 0
where 11 (I-(((XXX))(
is the projection matrix onto Null(X X)..
We now compare the bias of the standard and data augmented estimators (defined in Equation 2p. convenient define End X Saddxx Xau and Eng = X X + Xext Let IT = -- Σ Sus and
11 aug = Dingg mag be the projection matrices onto Null and Null(Enug respectively. Then,
mug 0* B(Osa)= = - II EII and B(0aug)= =6 II- EI-
(4)
Remark 1. Note that the bias in parameter error is ||[ 00 Null( S. Null(E we have [ng 0 < 1 1 and data augmentation always re- duces the bias in parameter error. However, the bias in test error upon augmentation B B(0mgg) could be larger or smaller than B(Qma))
01
Since
4.1.1 SIMPLE LINEAR PROBLEM I WHERE ADDING DATA INCREASES BIAS
The following example illustrates how the interaction between the column spaces standard inputs X extra inputs X and the underlying true parameter 0" could cause data augmentation to increase bias.
For simplicity, we choose Σ = diag((>s )2, Asl) with A2 > A1. Xss = e3 and additional data Xext = é1 + where e1,e2,e3 denote the standard bases in R For brevity in notation, we denote [[0a by and and E[Qang] by Oaug.
Recall that by virtue of being minimum norm interpolants, (0au - 8*) E Null(Esa) = R22 and (0mg - 00)) ENull (p(e)-02) E IRJ. Figure 2 depicts these parameter errors for different choices of 6*
Bias under different seifereentettingsssffo #* Plugging these terms into the bias expression in Equation 4 yields
B(dsa)= = X +0;02x X2 and B(0ang)= (1/4) - (1
Since in our construction of Σ we have >2 Å₁, the bias expression is dominated by the coefficient on Ag, which is the projection of the parameter error on e2 (red lines in Figure Depending on 0*, B(fang) could be larger or smaller than B(6 In particular,
(i) when 0 8 in Fig. 2 (a), augmenting with X increase bias B(Qany) > B((au). Even though the augmented estimator has lower parameter error overall (Ilêmug - 1- S I| 8* (*)) the increase in parameter error along e2 dominates the effect the bias because X2 \1.
(ii) when 0 > 8 in Fig. 2 (b), the same Xex causes B(Oagg) to be smaller than B(Q.)). Here the augmented estimator has smaller parameter error along e2 and hence decreasing bias despite an increase along e1-
4

---

Under review conference paper at ICLR 2020
E2]
e2) Bud
0"
e1
Banx 6*
Fect
std
Ban
6*
Bed
6N
(a) 01 02
(b) >> 01
(c) -=diag([1,4)
(d) Σ Σ ((,
Figure 2: Illustration of the 3-D example described Sec. 4.1.1 In (a), (b) we depict the errors dang 0r (green solid) and sdd fr (blue solid) projected onto (Esa) that is spanned by eigenvectors é₁ and e2 of Σ with X2 > A1_ Red lines depict the projection of parameter errors on 62 which determines the bias. In (a) 0 > 02 and bias increases upon augmentation. (b) 0 >> and bias decreases upon augmentation. (c), (d)The space of safe augmentation directions (orange) that don't t increase bias for a given O are cone-shaped, where the cone width depends on the alignment of (0 with eigenvectors of Σ and the skew in eigenvalues of Σ.
In summary, the minimum norm interpolant treats all unobserved dimensions in the null space "equally". In contrast, the bias is dominated by the components of the parameter error along the top cigenvectors of Σ. This mismatch could lead to settings where decreasing the null space of the training points via augmentation increases the error along top eigenvectors of Σ. We formalize this intuition and present general characterization below.
4.1.2 GENERAL CHARACTERIIZATIONS
We now study the biases of the standard and augmented estimators in general. Recall that IT and I1 the projection matrices onto Null and Null (ull(Emug) respectively, where Egs X Xas and X X sud +X
X
Xeatt Xext- Since Null (aagg) S Null Esu), can decompose I into orthogonal
components TT l and w aaa Tug Substituting this decomposition into Equation 4 get the following exact characterization for when data augmentation increases bias.
Theorem 1. The augmented estimator 0ang has larger bias i.e., B(Qaug) > B(lna) ) if and only if
v T Euv Ev,
(5)
where 1am and 11 0
The proof of Theorem is in Appendix B.
We see that condition (5) depends 0* which is typically unknown. Hence, we cannot determine apriori a particular form of augmentation would be "safe" and not increase error (like random translations in CIFAR- 10) or harmful (like random rotations in CIFAR-10) 10). However, we can make the following statements about when data augmentation is safe (for any 0*) in some restricted settings.
1. When Σ I, the condition (5) is always met (since 1 v) and hence data augmentation is always safe and never increases bias for any 8*. This suggests that data augmentation increases bias when there is mismatch between the norm being minimized during interpolation and the norm of the parameter error that determines test error.
2. When Xex spans the entire nullspace of Ead such that Eang is invertible, w w= for all 0* and data augmentation never increases bias.
3. In the simple where Xoxt is rank-one, data augmentation is safe for all 0* if and only if I1 Xext is an eigenvector of Σ. See Appendix B. B.4 for proof.
Finally, we illustrate the safe augmentation directions Xex in the nullspace of Egu for the simple 3-D problem discussed above for two different choices of Σ and fixed #* (Figure (c). (d)). The safe aug- mentations lie in cones around the eigenvectors while the width and alignment of the cones depends on the alignment between 0* and the eigenvectors of Σ. As the eigenvalues of Σ become more skewed,
5

---

Under review conference paper at ICLR 2020
Figure 3: Top 4 eigenvectors of the splines problem, representing wave functions in the input space. The eigenvalues corresponding to "global" eigenvectors which vary less over the domain larger, making errors in global dimensions costly in terms test error.
the space of safe augmentations shrinks. We present dual perspective Theorem in Appendix B which characterizes the effect of augmentation on the bias in terms of properties of the true parameter H*.
Local vs. global structure. Finally, we tie our analysis back the spline staircase problem from Figure I The inputs can be appropriately rotated so that the cubic spline interpolant is the minimum Euclidean norm interpolant (as in Equations 2). Under this rotation, the different eigenvectors of Null(Esa) measure either the fit in the "local" high frequency components or "global" low frequency components (See Figure 3 Any augmentation that encourages fitting local components (Enl(E could lead to worse fit of the global structure, leading to increased test error (See Figure B). This suggestive of a similar trade-off phenomenon in practice where adversarial training (with say for perturbations) encourages neural networks to fit the high-frequency components of the signal while compromising on overall global structure causing an increase in test error.
4.2 VARIANCE OF MINIMUM NORM INTERPOLANTS
The main focus this work is on the effect of data augmentation on the bias minimum norm interpolants. For completeness, present increases or decreases variance. For a more complete treatment, please refer to Appendix C Let Xadd be the standard training data, with points ;ex and let IT denote the projection matrix onto Null( X
conditions under which the data augmentation
std X
Theorem 2. For the minimum norm interpolants defined in Equation 2 the following hold.
1. When IT Xext = O such that the extra points lie in the column space of original standard training data, ((amgg) (Q
2. When X 1 Xasts such that the extra points lie entirely in Null(X Xma), we have (( 2 V V(saa).
In general, when Xex E Null(X interpolants could increase upon data augmentation, shedding some light why data augmentation sometimes increases standard error in practice.
std xaa). we see that both the bias and variance of minimum norm
5 EFFECT OF SIZE OF THE ORIGINAL TRAINING SET
In this section, study how the effect of data augmentation varies vary the size of the original standard training set. We first briefly study this the setting of minimum norm interpolation in linear regression. We then empirically evaluate the effect of adversarial training vary the number of original training samples in CIFAR- 10 and observe that the empirical trends mirror the trends dictated by analysis linear regression.
5.1 MINIMUM NORM INTERPOLATION SMALL AND LARGE DATA REGIMES.
Without loss of generality. we assume that Σ. the population covariance of 2 is invertible since the test eиror only depends on columnspace of Σ.
Large data regime. In the large data regime where the number of standard training points n oc, the empirical covariance of the original training points Exu = X 2 nX is invertible with IT = 0. Both de and i my unbiased (from Equation From Theorem variance of dang is never larger than

---

Under review as conference paper at ICLR 2020
Test Emr(Aug) Test Test Enr((td) (96)
Teat ErrAug) -Tsst Eritkel
< 37555
AT.
X-Rea, 188
0.75
6
0.50
-06- X-Req, 6
0.25
0.00
10
10'
Number of labeled samples
Number labeled samples
(a) Spline Staircase
(b) (AT)
(c) CIFAR-IO (AT)
Figure Effect of data augmentation on test error as we vary the number of training samples. We plot the difference in errors of the augmented estimator and standard estimator. In both the spline staircase simulations and data augmentation with adversarial Lo perturbations via adversarial training (AT) on CIFAR-10 10, we find that as we increase the number of samples, the increase in test ertor decreases.
that of std. Putting together, the test error never increases upon augmentation in the large sample regime matching the common intuition that more data from the correct target distribution should never hurt.
Small data regime. In the small data regime, where r is much smaller than d, the empirical covariance Esi could be far from invertible. As we increase the number of samples, the null space Null shows that for fixed 6*, the magnitude of possible increase in both bias and variance decreases as IT Xex decreases (See Appendix E for details). This suggests that as the size of Xaa increases, the increase in test error due to augmentation decreases. We run simulations of the spline staircase example from Figure find that this trend holds (Figure a); see Appendix D)
shrinks. Our analysis in Section 4
5.2 EMPIRICAL OBSERVATIONS ON THE EFFECT OF SAMPLE SIZE.
Do the trends in linear regression also hold for classification with more complex models and real world datasets? For our empirical study, focus adversarial training (Madry et al.] (018)). iterative data augmentations with adversarial Eo perturbations of different magnitudes e. We train - (Zagoruyko & Koooddkii 2016) CIFAR-10 10 training set subsampled by varying amounts. We plot the difference in the test errors of the augmented and standard estimators as function of training set size Figure We find that augmentation less detrimental to test error with increase in sample size (Figure|4 b)), matching the trends predicted by our analysis of linear regression. Extrapolating the plot, we see that there should be no tradeoff between robustness and accuracy in the infinite data limit cet---aottttinnnng the toy examples studied in (Tsipras et al. [2099 Zhang et al.
2019 Nakkiran 2019) which we discussed in Section 2
MITIGATING THE INCREASE IN BIAS UPON AUGMENTATION
To this point, the paper focuses on understanding why data augmentation could increase error by analysing the setting of minimum norm interpolation in linear regression. However, data augmentation (c.g.. via adversarial perturbations) often comes with desirable benefits such as robustness of estimators. In this section, we leverage our understanding from linear regression to design a new estimator for interpolating augmented data that mitigates the increase in test error while preserving the benefits. To this end, we introduce X- x-regularization, and prove that X-regularization eliminates the increase in bias upon augmentation for noiseless linear regression (Section(6.) 6. In Section we show that this estimator naturally generalizes to arbitrary losses and complex models and is closely connected to the classical semi- sumi-super self eeffnirainngg algorithm (Scudder) 1965). We empirically evaluate the performance of this general X-regularization X- X-regularization causes a smaller increase in standard error while maintaining or simultancously improving the robustness of neural networks trained on CIFAR-10.
adversarial training in 6.3) In nutshell,
7

---

Under review as conference paper at ICLR 2020
6.1 X-REGULARIZATION FOR LINEAR REGRESSION
Our development considers stylized setting of interpolation in linear regression with noiseless observations from linear model, = 0", where the dimension is (much) larger than the number of observations. Let int--ad interpolate the initial data, satisfying stddmnn--sd = Y/td. We use int-aud to construct new data augmented estimator 2x.mng that interpolates both the standard data and augmented extra data while satisfying R(Ox-ang) S R[(0mn-sdd)
Given Σ and initial interpolant Oint-std, we propose the X-regularized data augmentation estimator
Ox-aug E Eargmin -in--st)
xaa0 - =ydd, X yext
(6)
The X-regularized estimator & axaugg optimizes for small error on the labeled data (X Bsa) and (Xext.Box)) while keeping the predictions of 6x-aug close to those of fint-std over unlabeled inputs drawn from P.. To motivate our estimator, recall our discussion on the effect of data augmentation on the bias (test error in noiseless case) of minimum norm interpolants in Section 4.1 By fitting extra dimensions of Xexi the data augmented estimator could have larger parameter error than ma important directions of Σ, and consequently higher test error (Figure 2). A natural strategy to mitigate this increase, then, is to fit Xex while staying close to 0int-sud weighted by Σ, which leads to the estimator defined in Equation 6 This intuition can be formalized to prove that the X-regularized interpolant i aug never has higher test error than fin std-
Theorem 3. Assume the noiseless linear model y x==x0== 0*, Let Oun--us be arbitrary interpolant of the standard data, i.e. Xm sid Vadd Let Ox. be the X-regularized interpolant (6). Then
R(6 S R(( ((mm
See Appendix ?? for proof. To provide some graphical intuition for the result, consider the spline interpolant ana Fig. iillustrates where Xext consists of local perturbations. The X-regularized estimator matches the standard interpolant 6an points outside the training thereby capturing global structure while simultaneously fitting local structure on the training set via Xexi-
Note that discussion the effect of sample sizes in S that larger labeled standard training set would mitigate the drop in standard error due to augmentation. However, our development of X-regularizztion suggests that we only need unlabeled data, which is much cheaper obtain in practice. Unlabeled data is often used to improve standard test error in the semi-supervised learning paradigm. Here, we motivate the use of unlabeled data to mitigate the possible increase in test error from data augmentation.
6.2 ROBUST SELF-TRAINE GELE-TRANIING AS X X-REGULARIZATION
ROBUSTNESS
To motivate using X-regularization for general models and losses, note that the expression of the objective function for the X-regularized estimator in (6) can be rewritten in more general form:
(9-6 (m-em--sdd) E(0 mm Ep, (<x T 8-2" (m E 11 (z)mfom (z))).
where Ex the squared loss between the predictions of the model (z with the predictions (pseudo-labels) of given interpolant fo A generalized version of X-regularization replaces ly with some general loss that include classification losses such as the logistic loss. Written this way, X-regularization regularizes the predictions of an augmented estimator towards the predictions of the standard interpolant, similarly to the classical semi-supervised self-training algorithm (Scudder 1965).
The main motivation of our work is to fix the the drop in standard test performance from augmentation strategies that seek to enforce robustness by adding pabee-pres transformations of existing inputs. With augmentations take the form of some aabel-preserving transformations T. it is natural to consider transformations both the labeled and unlabeled data as the set of "extra" points, that constitute Xea- Generalizing the linear regression estimator of Equation to use arbitrary losses and transformation
8

---

Under review as conference paper at ICLR 2020
Method
Robust Test Ace.
Standard Test
Method
Robust Test Acc.
Standard
Standard Training
0.8%
95.2%
Test
Standard Self-Triining
0.3%
96.4%
(Madry al. 2018
87.3%
Standurd Training
0.2%
94.6%
RST PG-AT
58.5%
91.8%
Worst-of- 10
73.9%.
95.0%
TRADES (hang
55.4%
84.0%
RST Worst-of-10
75.1%
95.8%
ctal. 2019
Random
67.7%
95.1%
RS TRADES
63.1 %
89.7%
RST + Random
70.9%
95.8%
al. 2019
Worst-of-I0
69.2%
91.3%
Interolatedd
45.1 1%
93.6%
Engstrom al. 2019
Lamb et al. 2019
Random Yang ot al. 2019
58.3%
91.8%
Neural Search
50.1% %%
93.2%
Cubuk al. 2017
Table 1: Performance of X-regularization instantiated as robust self-training (RST) applied to different perturbations and adversarial training algorithms. (Left) CIFAR-10 standard test accuracy and robust test accuracy against &oo perturbations of size = 8/255. All methods use e 8/255 while training. Robust accuracies are against PG based attack with 20 steps. (Right) CIFAR-10 standard test accuracy and robust test accuracy against grid attack of rotations up to 30 degrees and translations up to to~ 10% of the image size, following (Engstrom et al. 2019). All adversarial and random methods use rotations and translations with these same parameters during training. For both tables, all shaded rows make use of 500K unlabeled images from 80M Tiny Images sourced in (Carmon et al. 2019). RST improves both the standard and robust accuracy over the vanilla counterparts for different algorithms (AT and TRADES) as well as different perturbations (foo and rotation/translation)))
based augmentations, get,
0x-ang: arramnnnnn
N
Σ
(x.y)E((eat.nnll
+ Am
+) (2)))
(7)
We note that the general X-regularized estimator above is the Robust Self-iraining (RST) algorithm proposed and studied recently by [Cammon et al. (2019) when applied to arbitrary transformations. Variants of RST were also studied in (Najafi et al. 2019 Uesato al. 2019). By deriving RST via X- regularization, we provide some theoretical justification for why RST would improve standard accuracy.
6.3 EMPIRICAL EVALUATION OF X- X-REGULARIZATION AS RST
For our empirical investigation, we evaluate the effect of X- X-regularization on the commonly observed tradeoff between robustness and standard accuracy when augmenting the training set with transformations. We recall that X-regularization when applied to transformation based augmentations leads to Robust Self Training. Therefore, we refer X-regularization and RST synonymously through this section. We instantiate the robust self-training estimator defined in Equation 7 on both PG-AT and TRADES; exact loss functions appear in Appendix F2) All of our experiments are on CIFAR-10. and RST estimators use 500K unlabeled images sourced from Tiny Images in (Carmon et al. 2019 addition to the labeled training set.
In our first experiment, we use the same settings as our experiments on effect of sample size in CIFAR-11 10 in Section S We compare the error of RST+PG-AT and standard training in Figure We find that RST+PG-AT has lower standard test error than the standard training, while simultaneously fitting the training data robustly and achieving higher robustness (see Appendix G.2.TT. We also see the maximum gains from RST+PG-AT are in the small data regime where adversarial training has the most affect on standard error.
In our next experiment, we compare with other methods in the literature. We train larger WRN-28- 10 model with the entire labeled CIFAR- 10 training set and 500K unlabeled images. Table left) summarizes the results. While there is still drop accuracy compared to standard training, RST has higher standard accuracy than the vanilla counterparts without sacrificing robustness, in both PG-AT and TRADES. The gains are comparable to gains from other measures to improve the tradeoff between

---

Under review as conference paper at ICLR 2020
robustness and accuracy such Interpolated Adversarial Training and Neural Architecture Search. RST could be integrated with the above training algorithms to see further gains; we leave this to future work.
Finally, test the effect of RST different family of perturbations. We consider adversarial (worst of 10) and random augmentations using simultancous rotations and translations of the input image. Table rright) presents the results. While the augmented estimators marginally improve standard accuracy for these perturbations, applying RST increases both robust and standard accuracies beyond that of the augmented estimator in both cases. This shows that RST is beneficial even when data augmentation does not decrease standard test error.
7 DISCUSSION
Semi-supervised setting. General X-regularization leverages unlabeled data to mitigate the possible harmful effect of data augmentation. The traditional setup of semi-supervised learning involves only one objective: improve the standard accuracy the underlying population. We revisit the semi-supervised setting with a different focus. For several applications, standard supervised deep learning provides highly accurate classifiers, but they are surprisingly brittle. Attempts improve robustness typically lower accuracy. Training robust and accurate classifiers remains an open challenge. and semi-supervised learning is emerging as a promising approach. Recent work (Carmon al. 2019 et al., 2019; Uesato et al. 2019) has studied the benefits of semi--suppee comi--upervised learning in improving robustness. In our work, we bolster this line of work by demonstrating that sup-ssueeeeseed learning can simultaneously improve the accuracy, while maintaining robustness.
Self-training. In this work, we study X-regularization which is closely related to self leff-training, perhaps the oldest eupesuupee learning algorithm (Scudder 1965). In the traditional setting of improving standard accuracy, self-training has shown some success, but other approaches perform significantly bet- ter; see survey (Oliver et al. 2018). However, in the regime where we care about both robustness and ac- curacy, we see that self trainin based approaches such as X-regularization offer significant benefits. We provide detailed comparison of X- regulariizatinn to other semi-supervised learning algorithms in Ap- pendix[H] Variants of self-training are also gaining prominence in the related but different setting of unsu- pervised domain adaptation. Here, the unlabeled data is from the "target" distribution, while the labeled data is from a different "source" distribution and the goal is to perform well on the target distribution.
Interpolation in linear regression. Analysis of the interpolation regime has recently gained promi- nence with the observation that neural networks obtain zero training error. Previous works (Hastie et al., 2019 Bartlett al. 2019 Belkin et al. 2019) study the performance of minimum norm interpolants in overparameterized linear regression in an attempt to explain the generalization properties of neural net- works that are not explained by the classical perspective on interpolation and overfitting. In our work, we show that the same overparameterized setting also sheds light on the empirical observation that data aug- mentation sometimes helps and sometimes harms test performance. In contrast, in the classical under- parameterized regime, data augmentation never harms test performance common statistical intuition would suggest. Studying interpolation in the overparameterizze regime even in simple settings such as linear regression thus seems to be valuable in understanding the properties of neural networks in practice.
Conclusion. We studied adversarial training through the lens of data augmentation with the goal of training robust and accurate classifiers. We analyzed general data augmentation in stylized setting and proved that unlabeled data can climinate possible increase in test error. This motivated general estimator based on self-training combined with adversarial training that shows promise in improving both the accuracy and robustness of neural networks in practice. While using unlabeled data via simple self-training has shown improve both accuracy and robustness, how to best utilize unlabeled data in this context is an open question. Further, can we obtain highly robust and accurate networks by simply using large amount of unlabeled data, or do we need further innovations in neural network architectures and training?
REFERENCES
P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler. Benign overfitting in linear regression. arXiv, 2019.
M. Belkin, S. Ma. and S. Mandal. To understand deep learning we need to understand kernel learning. In International Conference Machine Learning (ICMI.,, 2018.
10

---

Under review as conference paper at ICLR 2020
M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. arXiv, 2019.
B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Smniić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pp. 387-402, 2013.
Y. Carmon, A. Raghunathan, L. Schmidt, Liang, and C. Duchi. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
E. D. Cubuk, B. Zoph, S. S. Schoenholz, and Q. V. Le. Intriguing properties of adversarial examples. arXiv preprint arXiv: 1.02446, 2017.
Diamond and Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Leurning Research (JMLR), 17(83):1-5, 2016.
L. Engstrom, B. Tran, D. Tsipras, L. Schmidt, and A. Madry. Exploring the landscape of spatial robustness. In International Conference on Machine Learning (ICML), pp. 1802-1811, 2019.
A. Fawzi, O. Fawzi, and P. Frossard. Analysis of classifiers robustness to adversarial perturbations. Machine Learning, 107(3):481-508 2018
J. Friedman, T. Hastie, and R. Tibshirani. The elements of statistical learning, volume 1. Springer series in statistics New York, NY, USA: Springer series in statisties New York, NY, USA: 2001.
I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015.
Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises high- high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.088
2019.
P. Kovanic. On the pscudoinverse of a sum of symmetric matrices with applications to estimation. Kybernetika, 15, 1979.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1097-1105, 2012.
S. Laine and T. Aila. Temporal ensembling for semi-supervised learning. In International Conference on Learning Representations (ICLR), 2017.
A. Lamb, V. Verma, J. Kannala, and Y. Bengio. Interpolated adversarial training: Achieving robust neural networks without sacrificing too much accuracy. arXiv, 2019.
Liang and Rakhlin. Just interpolate: Kernel" ridgeless" regression can generalize. arXiv preprint arXiv: /808.0088. 201 8.
S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern parammttreer learning. In International Conference on Machine Learning (ICML), 2018.
2018.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations (ICLR), 2018.
T. Miyato, S. Maeda, S. Ishii, and M. Koyama. Virtual adversarial training: regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 2018
A. Najafi, S. Maeda, M. Koyama, and T. Miyato. Robustness to adversarial perturbations in learning from incomplete data. arXiv preprint 1905v /3021, 2019.
Nakkiran. Adversarial robustness may be at odds with simplicity. arXiv preprint arXiv: 1OXiv:1901.00 190100032, 2019.
A. Oliver, A. Odena, C. A. Raffel, E. D. Cubuk, and I. Goodfellow. Realistic evaluation of deep semi-supervised learning algorithms. In Advances Neural Information Processing Systems (NeurIPS), pp. 3235-3246, 2018.
11

---

Under review as conference paper at ICLR 2020
M. Sajjadi, M. Javanmardi, and T. Tasdizen. Regularization with stochastic transformations and perturbations for deep semi-supereised learning. In Advances in Neural Information Processing Systems (NeurIPS). pp. 1163-1171, 2016.
H. Scudder. Probability of еттоr of some adaptive pattern machines. JEEE Transactions on Information Theory, 11(3):363-371, 1965.
C. S..eegedy W. Zaremba,, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing prop- erties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry. Robustness may be odds with accuracy, In International Conference Learning Representations (ICLR), 2019.
J. Uesato, J. Alayrac, P. Huang, R. Stanforth, A. Fawzi, and P. Kohli. Are labels required for improving adversarial robustness? arXiv preprint WxXiv:1955.13255 2019.
Q. Xie, Z. Dai, E. Hovy, M. Luong, and Q V. Le. Unsupervised data augmentation. arXiv preprint arXiv:1904. 12848, 2019.
L. Yaeger, R. Lyon, and B. Webb. Effective training of neural network character classifier for word recognition. In Advances in Neural Information Processing Systems (NeurIPS), pp. 807-813, 1996.
Yang, Z. Wang. and C. Heinze-Deml Invariance lbvariance-inducing regularization using worst-case transfor- mations suffices to boost accuracy and spatial robustness. arXiv preprint arXiv:1906.1/235, 2019.
S. Zagoruyko and N. Komodakis. Wide residual networks. In British Machine Vision Conference, 2016.
H. Zhang, Y. Yu, J. Jiao, E. P. Xing. L. E. Ghaoui, and M. I. Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference Machine Learning (ICMI.), 2019.
A TRANSFORMATIONS TO HANDLE ARBITRARY MATRIX NORMS
Consider a more general minimum norm estimator of the following form. Given inputs X and corresponding targets Y as training data, study the interpolation estimator,
i -= argmin { ::: M0:X0-Y]
(8)
where .M is a positive definite (PD) matrix that incorporates prior knowledge about the true model. For simplicitly, we present our results in terms of the l norm (ridgeless regression) as defined in Equation 8 However, all our results hold for arbitrary M-norms via appropriate rotations. Given an arbitrary PD matrix M, the rotated covariates x + A 1/22g and rotated parameters 0 <- 1M20 maintain = xx++xxa (O,TT) and the M-norm of parameters simplifies |
||@||2.
B BIAS OF MINIMUM NORM INTERPOLANTS
B. PROOF OF THEOREM
Inequality (5) follows from
B(0ang) B(Qsa) (0" -00- -mug) E(0' Gang) 1 -aa) T((0- -
=III- aug 9r) III- mug 0r (1 -'
w D'w - (w+v) (
2 T -v-v" Ev
by decomposition of 01 v where w= 11 Umgg 0* and - 11_1 1I that the bias difference does scale with ||0
th 0*. We also want to note
12

---

Under review as conference paper at ICLR 2020
B.2 BIAS INCREASE REQUIRES COMPLEX TRUE ESTIMATORS
dual perspective on Theorem | leads the following proposition that characterizes the properties of the true function 0+ that leads to harmful augmentations.
Proposition 1. For given XndxXexs Xea, a bias increase of B(0mag) B(0aa)= e>> O via augmentation with Xea is possible only 0 is sufficiently more complex than O Oud in the Eg norm, i.e.
110' 112 10mmll
(10)
for some scalar that depends X Xeu,
B.2.1 PROOF OF INEQUALITY
10
The proof of inequality TO is based the following two lemmas that are also useful for characterization purposes in Corollary |
Lemma 1. a PSD matrix E has non-equal eigenvalues, one can find two unit vectors w.o for which the following holds
w Tv= and w Ev
(11)
Hence, there exists combination of original and augmentation dataset Xud; Xext such that condition for two directions u (a and w E + bug)) Col(Ul aug).
aug
Note that neither nor can be eigenvectors of Σ order for both conditions in equation 11 to hold. Given population covariance, fixed original and augmentation data for which condition holds, we can now explicitly construct 0 for which augmentation hurts bias.
Lemma Assume E, X Xex are fixed. Then condition (TT) holds for two directions 2 cfor some
Col(IL and w Col bug) ifff there exists 6 such that Furthermore, the lo norm of needs to satisfy the following lower bounds with == |10 112 -1
sud
110-11--110mmp B10 1 C1
c²
110- 110 12:11222+++0 231 (31+1)a
(12)
C1
where 3 are constants that depend on Xen,
Inequality (10) follows directly from the second statement of Lemma by minimizing the bound 12 with respect to Cj which is free parameter to be chosen during construction of 0* (see proof of Lemma (2. The minimum is attained for = ())3ce") We hence conclude that 0* needs
be sufficiently more complex than a good standard solution, i.e. | l| |10 ye where > is a constant that depends on the Xext-
B.3 PROOF oF TECHNICAL LEMMAS
In this section we prove the technical lemmas that are used to prove Theorem
B.3.1 PROOF OF LEMMA
Any vector 1 E Nua)(E,a) can decomposed into orthogonal components 1 I bug 0 + II= 0. Using the minimum-norm property, we can then always decompose the (rotated) augmented estimator dang E (Col(11+ - -Cl( and true parameter 0 by
dwng - + Σ Sor
My Eext
0+ d + Σ Enwr,
wy Erest
13

---

Under review as conference paper at ICLR 2020
where we define "ext" the set of basis vectors which span Col and respectively "rest" for (Eng() Requiring the bias increase to be some constant c>> can be rewritten using identity (9) as follows
B(Oang) - -B(0sa) =c
Σ
(20s) (
(:u;) tc= -2( Σ
{5w Σ ((0s)
by Eext
eext
Wy Erest
(roz) E
Says) +c=
Σ
Ee;
(13)
U. Eext
2: Eext
ey
The left hand side of equation 113) is always positive, hence it is necessary for this equality hold with any c.> O, that there exists at least one pair i.j such that w) Deg # and one direction of the iff statement proved.
For the other direction, we show that if there exist v E Ia and w E aa for which condition (11) holds (wlog assume that the w T Ev<() inequality (5) Theorem Tholds as follows:
aug
construct 0 for which the
It then necessary by our assumption that EyGm) Eu; 0 for at least some i.j. We can then set Ç such that 000nggg - 222 II<|i== c1 > 0, i.c that the augmented estimator is not equal to the standard estimator (else obviously there can be no difference in bias and equality (13) cannot be satisfied for any desired bias increase e>>0) 0).
The choice of & minimizing ||0* 0augl 1| Σ3 23 that also satisfies equation 13
is an appropri-
ately scaled vector the direction of = W EVC where we define W == [w1,-. Wpsst]] and
:: [==[ui...., [xx]] Defining co = V V for convenience and then setting
Co tc 2 2
(14)
which is well-defined since + O, yields 8* such that augmentation hurts. It thus necessary for B(0ang) Bfaau) that
(co+e) = WWW EVC
EVS+
W EVCI
(VVVV
6²
15 VWTW EVC 4CTVTEWWTEIE EVC
9 2 (VTEV (VV.
à²
+ 4c 22
12 mnxx
(W VVV
(W WVV
By assuming existence i.j such that E _ Ev; of O, we are guaranteed that X2 (W (VVVV >0.
Note due construction have ||0* 112 1mmdl E. E,e} and plugging in the choice of E in equation (14) we have
2 (VTEV)
6²
|00113 ||0uua
12 01
1 +
412 ( WTEV
4X2
(W T EV) c
Setting 31 1 (V 538)
.2 4x2 (W ΣV) yields the result.
4X (W ΣV)
B.3.2 PROOF OF LEMMA
Let ' Ap....AAm be the m non choose to be any combination of eigenvectooss v UB where U = [#) Mmm where at least (3,8, +
non-zero zero eigenvalues of Σ and u, be the corresponding eigenvectors. Then
14

---

Under review as conference paper at ICLR 2020
for A We next tz= UVa by choosing as follows such that the inequality in holds:
Bg
0x
B
= 8 $3
and 04 = 0 Kij. Then we have that a 3= 0 and hence w T v=0. Simultaneously
w -v +
3,3,
-)x 3 + #0
which concludes the proof of the first statement.
We now prove the second statement by constructing Esd X X Eest X Xext Yext using w, We can then obtain X using any standard decomposition method to obtain X We construct Lad: Yes using w, Without loss of generality, we can make them simultaneously diagonalizable. We construct a set of eigenvectors that is the same for both matrices paired with different eigenvalues. Let the shared eigenvectors include w,u. Then if we set the corresponding eigenvalues (2en)) = 0, (Zin( > and Xw (Eiss) = O, A (Lista) = O, then Xw (Saug) = 0 such that This shows the second statement. With this, we can design f for which augmentation hurts in Lemma
w E Col aug and v
B.4 CHARACTERIZATION COROLLARY
simpler case to analyze is when we only augment with one extra data point. The following corollary characterizes which single augmentation directions lead to higher prediction error for the augmented estimator.
The following characterizations hold for augmentation directions that do not cause the bias of the augmented estimator be higher than the original estimator.
Corollary 1.
(a) (in terms of ratios of inner products) For a given 8*, data augmentation does not increase the bias of the augmented estimator for single augmentation direction Text if
Fen Il EI Je
(II (IIssSee)) EII
<0
(15)
T.y Tex
I. 00
(b) (in terms of eigenvectors) Data augmentation does not increase bias for any 0* if l is an eigenvector E. However if one augments in the direction of mixture of eigenvectors of Σ with different eigenvalues. differenteigemaaluss. there exists 6* such that augmentation hurts.
(c) (depending on well-conditioning Σ) If Amnas no augmentations Tex increase bias.
and O is an eigenvector E., then Amin
The form in Equation (15) compares ratios of inner products of II Hed and II 0 in two spaces; the one in the numerator is weighted by Σ whereas the denominator the standard inner product. Thus, if Σ scales and rotates rather inhomogeneously. then augmenting with Tea may hurt bias. Here again, i = for 7 > 0, then the condition must hold.
B.4.1 PROOF OF COROLLARY (A)
Note that for single augmentation point X I the orthogonal decomposition of 11 0" into CIT bng and ( is defined by II ||T! Fext and w I v respectively.
8*
Plugging back into into identity 9 then yields the following condition for safe augmentations:
2(v IT 0' 0¹) Ee E0
(16)
2' Ev -Ev-2(TT) 2(TT 0-) E
|TT Texa 1|2 Il 11 Tent 0+
Tex
EII- Dex S 2 (T EII Text
15

---

Under review conference paper at ICLR 2020
Rearranging the terms yields inequality 115
Safe augmentation directions for specific choices of 6 and Σ are illustrated in Figure
B.4.2 PROOF OF COROLLARY
Assume that IT I Fext is eigevector of E with eigenvalue A O. We have
T
Li Mi Tox)
E1 =-x-
Ten
Text
Te IT_, 0* std
srd
for any 0*, Hence by Corollary E for any 6*
(a), the bias doesn't increase by augmenting with eigenvectors of
When the single augmentation direction e eigenvector Σ, by Lemma Tone can find w such that w Σ O. The proof in Lemma gives an explicit construction for w such that condition holds and the result then follows directly by Lemma
B.4.3 PROOF OF COROLLARY 1
Suppose III 0+ 0 for some Amin (2) SAS Amax (E). Then starting with the expression 15
T 11 add Ta
2 teu) E11
Fext 11 2il 2A
2x Text
2 11 -
Text 2d
SAmax (2) 22
by applying
Amax (2) Amin (2) 2. Thus when 11 0 is eigenvector of Σ, there are augmentations Zext that increase the bias.
C VARIANCE OF MINIMUM NORM INTERPOLANTS
In this section, we consider the case where the noise is non-zero, and compute the variances of the two estimators of interest: the standard estimator Oes and data augmented estimator mmg- The following the- orem provides a general characterization of the relation between variance the standard estimator and variance of the augmented estimator. Theorem L jss corollary of this general result that we present first. Theorem (Variance). The difference in the variances of standard and augmented estimator can be expressed as follows:
(Q ((@m)))= =tr car (
ou (I+
Xew
(17)
Ts: Variance increase
Ta: Variance reduccioo
where Xex del II X Xem the component of Nen in the null space of Esst-
Proof. Recall from (3) that the V(0) = tr( (Cov(( Xea-Xea)E). For the minimum norm interpolation estimators Oed and Dang in Equation have the following expressions for the variances of the
estimators.
((bma)= =o't
Σ I)
V V( ((0mm))=0² -02 Et E)
where End = XTT Xsna and Emng X X XT. Note that since End, are unnormalized, the quantities I and >iting decay with with the variances V V also decay with n as expected. In order to compare V(Qgus) and V(Ô (( we need to compare Σt and Eing- Torder to do this, we leverage the result from Kovanic (1979) on the pseudo-inverss
the sum of two symmetric matrices:
(Eead + X Xxx)) E El X XI X Il x
D +Xi
D
where recall that X is the component of Xex: the null space of Ema- Multiplying each term by E. and using linearity of trace, get the required expression.
[]
16

---

Under review as conference paper at ICLR 2020
Proof of Theorem 2 Theorem follows directly from the general result above (Theorem Note that the terms Ti and T2 are traces of PSD matrices and hence non non-negative, and capture the magnitude of variance increase and variance reduction respectively. From Theorem we see that (i) if X is entirely in the span of Sdd making Xext = Ti =0 making V (00mg) S (Oaa) (ii) On the other extreme, eea is entirely in the null space with E exx = 0, 72 = O and hence V(O ) 2 ((Qua)-
D DETAILS FOR SPLINE STAIRCASE
We describe the data distribution, augmentations, and model details for the spline experiment in Figure[Jand toy scenario in Figure Finally, we show that we can construct simplified family of spline problems where the ratio between test errors of the augmented and standard estimators increases unboundedly as the number of stairs.
D.1
TRUE MODEL
We consider finite input domain
(18)
for some integer corresponding the total number of "stairs" in the staircase problem. Let Thme [ 1}. We define the underlying function f : Ra-Ras ff (*) = [t]. This function takes staircase shape, and linear when restricted to Thie-
Sampling training data Xsu We describe the data distribution in terms of the one ine-dimensional input t, and by the one-to-one correspondence with spline basis features x x= (t), this also defines the distri- bution of spline features E X. Let w E A, define distribution over Time where A, is the probability simplex dimension s. We define the data distribution with following generative process for one sample t. First, sample a point from Time according to the categorical distribution described by w, such that i~ Categorical (w) Second, sample by perturbing i with probability such that
w.p. 1-8 fi i=(i+e
1=
lite w.p. 6.
The sampled in Time with probability 1 1-6 and Time with probability 8, where we choose to be small.
Sampling augmented points Xext For each element t in the training set, augment with
T; = 3.... B(+)),, an input chosen uniformly random from B(t:)= = [L4) +e]. Recall that in work, we consider data augmentation where the targets associated with the augmented points are from the ground truth oracle. Notice that by definition, / /14)== f (4,) for all E B(4). and thus can set the augmented targets to be U = y/- This is similar to random data augmentation in images (Yaeger
1996 Krizhevsky
2012), where inputs are perturbed in way that preserves the label.
D.2 SPLINE MODEL
We parameterize the spline predictors as fo(t) Xt) where X R Rd the cubic B-spline feature mapping (Friedman et al. 2001 and the norm of fe(t) can be expressed as 0 MO for a matrix M that penalizes large second derivative norm where [M] f (u)x (u)y. Notice that the splines problem is a linear regression problem from ndd to I in the feature domain X (t), allowing direct application of Theorem I As a linear regression problem, we define the finite domain as X' (t): T containing 2s elements in Rd There a one-to-one correspondence between and ((), such that X is well-defined. We define the features that correspond to inputs in Time as X (x:X- E Time) Using this feature mapping, there exists 0* such that fo- (1) = (() for LET.
Our hypothesis class is the family of cubic B-splines as defined in (Friedman et al. 2001 Cubic B-splines are piecewise cubic functions, where the endpoints of each cubic function are called the knots. In our example, we fix the knots to be J - 1, [+e], which places a knot every point in T. This ensures that the function class contains an interpolating function on all f E T, i.e. for some 0*,
6
(t)==)((==(])
17

---

Under review conference paper at ICLR 2020
Bias criterion (Aug Sid]
On Perturbations
Standard Augmented
Standard
2
Augmented
1
7
Augmentaaion point
(a)
(b) Augment with (3.5) (c) Augment with (4.5)
Figure 5:
Visualization of the effect of single augmentation points in the noiseless spline problem The standard estimator defined by X linear.
given an initial dataset ( (0,11,2,33 (a) Plot of the difference term in Corollary (a), is positive when augmenting single point causes higher test error. Augmenting with points on Vime does not affect the bias, but augmenting with any element of (t) (2.5,3.5.4.5) hurts the bias of the augmented estimator dramatically. (b), (c) Augmenting with (3.5) or (4.5) hurts the bias by changing the direction of extrapolation.
Global (qa)
(5)
(1.5)
Local (g2s)
Old
(a) Nullspace projections onto local vs. global
Figure 6: Nullspace projections onto global direction and local direction 92. in Null(E) via llg. representing global and local eigenvectors respectively. The local perturbation Il ((15)) has both local and global components, creating a high-error component in the global direction.
We solve the minimum norm problem
A argmin M0 Xyu0 - Youd
(19)
for the standard estimator and the corresponding augmented problem obtain the augmented estimator.
D.3 EVALUATING COROLLARY I (A) FOR SPLINES
We now illustrate the characterization for the effect of augmentation with different single points in Theorem on the splines problem. We assume the domain to T defined in equation [8 s 10 and our training data to be Xad = (X()):4E / (0,1,2,3.4)) 3. Let local perturbations be spline features for & & Time where t+ is away from some E {0,1,2,3,4] from the training set. We examine all possible single augmentation points in Figure 5 (a) and plot the calculated predictive test error difference as defined in equation (16). Figure shows that augmenting with an additional point from {X()):t Time) does not affect the bias, but adding any perturbation point in {X (x) : (2.5,3.5,445)) where i Time increases the error significantly by changing the direction in which the estimator extrapolates. Particularly, local augmentations near the boundary of the original dataset hurt the most while other augmentations do not significantly affect the bias of the augmented estimator.
18

---

Under review as conference paper at ICLR 2020
D.3.1 LOCAL AND GLOBAL STRUCTURE IN THE SPLINE STAIRCASE
In the spline staircase, the local perturbations can be thought of as fitting high frequency noise in the function space, where fitting them causes a global change in the function.
To see this, we transform the problem minimum l norm linear interpolation using features (x<(t== (t)
that the results from Section 4.1.2 apply directly. Let Σ be the population covariance of Xa for a uniform distribution over the discrete domain consisting of 8 stairs and their perturbations (Figure [}. Let Q = 2 be the eigenvectors of > in decreasing order of their corresponding eigenvalues. The visualization in Figure 3 shows that 9i are wave functions in the original input space; the "frequency" of the wave increases as increases.
Suppose the original training set consists of two points, X = MM (0),XM) (1) We study the effect of augmenting point Text terms of q, above. First, we find that the first two eigenvectors corresponding to linear functions satisfy 91 = Is 92 = O. Intuitively, this is because the standard estimator is linear. For ease of visualization, we consider the 2D space in Null(2)) spanned by II 4s (global direction, low frequency) and H2 (local direction, high frequency). The matrix Iig = [ I2 projects onto this space. Note that the same results hold when projecting onto all 11 in Null(>)).
In terms of the simple 3-D example in Section the global direction corresponds the costly direc- tion with large eigenvalue, as changes in global structure heavily affect the predictive test error. Figure plots the projections II and Iex for different X When 9 has high frequency variations and is complex, 11g - = (0* - aa)) is aligned with the local dimension. For Zext immediately local to training points, the projection Ilg (orange vector F has both local and global components. Augmenting these local perturbations introduces error in the global component. For other Text farther from training points, Teg (blue vector in Figure O6) is almost entirely global and perpendicular to
O - Oed leaving bias unchanged. Thus, augmenting data close to original data cause estimators to fit local components at the cost of the costly global component which changes overall structure of the predictor like in [ The choice of inductive bias in the M-norm being minimized results in eigenvectors of Σ that correspond local and global components, dictating this tradeoff.
D.4 DATA AUGMENTATION CAN BE QUITE PAINFUL FOR SPLINES
We construct family of spline problems such that as the number the augmented estimator has much higher error than the standard estimator. We assume that our predictors are from the full family of cubic splines.
Sampling distribution
We define modified domain with continuous intervals T = [t, Considering only s which a multiple of 2, we sample the original data set as described in Section D.I with the following probability mass w:
t<s/2,tt
Time
wtt)
(20)
128/2,1E Time-
372
for 7 E 10. We define a probability distribution Py on T for a random variable T by setting T= Z SZZ where Z Categorical (w) and the Z-dependent perturbation S(2) is defined as
S(z) ~ Uniform(2,2tee)
w.p. 5
(21)
w.p. 1-
We obtain the training dataset Xsu = (X(tt)...,,(tI))) by sampling t Py. Augmenting with an interval
Consider a modified augmented estimator for the splines problem, where for each point t; we augment with the entire interval [[ta], | +c] with CE (0.1/2) and the estimator is enforced to output fa(=)= = y== [ for all z in the interval [[
Additionally, suppose that the ratio s/ 0(1= between the number of stairs and the number of samples is constant.
In this simplified setting, we can show that the test error of the augmented estimator grows while the test error of the standard estimator decays to 0.
19

---

Under review as conference paper at ICLR 2020
Theorem 5. Let the setting defined as above. Then with the choice of - y= c/8 for constant CE (0,1), the ratio between test errors is lower bounded as
and
R(Oans) =52(s²)
(22)
R(0su))
which goes to infinity as s-y00. Furthermore, R(Osu) -
0 as 00000
Proof. We first lower bound the test error of the augmented estimator. Define Ej as the event that only the lower half of the stairs is sampled, i.c. {t:t s/2]. which occurs with probability (1 (1-7)" Let t" = max; [t]] be the largest "stair" value seen in the training set. Note that the min-norm augmented estimator will extrapolate with zero derivative for t z max; This is because
the interval [t",t"++ +c], the augmented estimator is forced to have zero derivative, and the solution minimizing the second derivative of the prediction continues with zero derivative for all /. 2 L*. In the event Ei, 1" S 8/2-1. 1, where 1* =/2 1 achieves the lowest error in this event. As a result, on the points in the second half of the staircase, i.c. t T 2 1}. the augmented estimator incurs large error.
R(O
E1)
Σ
(t- (t-22/2-1)) 7
3/2
t=#/2
8/2
Σ
7 = 6 +22++++1)
8/2
t=1
Therefore the expected risk of the augmented estimator is bounded by
R( (00m))) 2 R(0aug E1) (E)) 2 2s +
6
Σ 6
(s==2))s²++2++1))
=Ω0
(s2+2s+ 1)))=
8
where in the first line, we note that the error on each interval is the same and the probability of each
interval is (1-6)__ ./2 t x/2 #/2"
Next we upper bound the error the standard estimator. Define Eg to be the event where all points are sampled from Time. which occurs with probability (1-6)". In this case, the standard estimator linear and fits the points on Time with zero error, while incurring error for all points not in Time- Note that the probability density of sampling point not in Time is either á 1-2 é
which upper c s/2 s/2
bound as é 5/2"
8 1 S/ u S/2.1 E s/2Ju
8.
R(Oua E2)
Σ
Ossc))
s/2
= =0(
Therefore for event Eg, the expected error is bounded as R( ((F2) = (())(1-)))
=0(fe
87 =1
0(6-
ST
- log(s") -log(s" -log(s"-1)))=000 )
since (og(s?)-log(() -1) for > For the complementary event L35, note that cubic spline predic- tors can grow only as O(t2), ), with error (t Therefore the expected error for case Eş is bounded as
R( ES) s 0(t))
1
(011)0(-)--00
20

---

Under review as conference paper at ICLR 2020
Putting the parts together yields
R(Osa) = R(Osal
=011/)+001//)0011}}}
Thus overall, R(0sus) -(1/s)) and combining the bounds yields the result.
E EFFECT OF SAMPLE SIZE ON ERROR INCREASE VIA AUGMENTATION
In this section, we discuss what our analysis of the effect of augmentation on the error of mininum inter- polants says about the trends with respect to varying sample sizes of the standard training set (eainngeettattataaaa (Xa)))aa))
Trends in variance. We refer the reader to the precise expression for the difference in variance provided in Theorem Let us consider case where data augmentation causes increase in variance. For simplicity, Xext std across all sample sizes the small sample regime. For a fixed Xext we that the magnitude of variance increase is governed by - which decreases get more standard training points.
Trends in bias. Recall the expressions for B(dua) and B(Qaug) from Equation Using the same notation that of 3heorem we have the following expression for the amount of bias increase. Let w= I1 Ougg and v
aug We have,
B(0agg) (B((()))= = Ev Σv-2w 2w Ev.
(23)
where w Ev a negative quantity when data augmentation causes an increase in bias. Recall that we are in the small sample regime where Das is not invertible for a range of sample sizes. Suppose we augment with eex such that Xex E Null(Eau) in this regime of interest. In this case, we can write بل lr = u 0". For fixed problem setting 6*, see that is fixed. Let now look at S+ Recall that ang the projection matrix onto En + X For fixed Xexts as the null space of Eus shrinks with more training points, w decreases. Note that the magnitude of increase in bias decreases as decreases (for fixed v). This suggests that the effect of augmentation on bias should decrease
w= II aup
get more samples, in the small data regime.
Our heuristic calculations in some settings of Xex in minimum norm interpolation linear regression suggest that the overall increase in test error should decrease as we increase the sample size of the original training set. Empirically, we find similar trends when performing adversarial data augmentations with varying training set sizes.
F X-REGULARIZATION
F.1 X-REGULLARIZATION FOR LINEAR REGRESSION
In this section, prove Theorem 3 which reproduce here.
Theorem 3. Assume the noiseless linear model y === T Let au be arbitrary interpolant of the standard data, i.e. X = Yad. Let Ox-aung be the X-regularized interpolant (6). Then
R( R(O S R((Omt-suu)
Proof. Let {u.} be orthonormal basis of the kernel Null(E + Xxx) and {2y} be an orthonormal basis for Null(Eua) \ span(fu:)). Let U and V be the linear operators defined by Uw= Σx W; and Vw=Xi E, 2 u. respectively, noting that VV= Defining II : (I-E (I- Ena) to be the projection onto the null space Xssa we see that there are unique vectors p.a such that
0 = 11 std ) + p+ Va.
(24a)
As (ot--td interpolates the standard data, we also have
Om snd (T TT 0 +Uw+ V2,
(24b)
21

---

Under review as conference paper at ICLR 2020
Xw V V==0, and finally,
0x-aug (I - IT 1 +U++VX
(24c)
where note the common p between Eqs. (24a) and (24c).
Using the representations
24
we may provide an alternative formulation for the augmented
estimator (6) using this to prove the theorem. Indeed, writing Oint-std - -xx-aue = Uww p) VV A),
we immediately have that the estimator has the form (24c). with the choice
À = argmin { (Uww~)) VV (== (X(((=)))+(((==>
X
The optimality conditions for this quadratic imply that
V
(25)
Now, recall that the predictive test error of a vector is R(0) (0 ((---)) T --(--0))) 10-00 using
Mahalanobis norm notation. particular, a few quadratic expansions yield
R(O (sd - (xx-ug)
= -V
EVa
Vo
[V=
(26)
where step (i) used that
TV
EV from the optimality conditions (25).
Finally, we consider the rightmost term in equality (26 Again using the optimality conditions 25 we have
|
/ VVllss
by Revisiting equality 26). we obtain
s(D - R( (((0x.m))
[
AI
(w)
> 2V
||
as desired.
F.2 X-REGULARIZATION FOR DATA AUGMENTATIONS THAT PROMOTE ROBUSTNESS
The main motivation of our work is to provide method to perform data augmentation such that the benefits such as robustness are preserved, without seeing the undesirable drop in standard accuracy. The general X-regularized estimator (Equation 7 holds for any form of augmentation. We now write out the exact loss functions when we apply X X-regularization to two forms of adversarial training: Projected Gradient Adversarial Training of Madry al. 2018) and TRADES (Zhang et al. 2019). Throughout, we assume the same notation as that used in the definition of the general estimator. Xaa-Maa denote the standard training set and we have access m unlabeled points F;, 1,,i=1,,..m.. 1...m.
F.2.1 PROJECTED GRADIENT ADVERSARIAL TRAINING
Note that the unlabeled data can be perturbed obtain more extra data, because of the special structure of the extra points added: every training point generates a perturbed extra training point. This leads to the following natural generalization, where obtain adversarial perturbations from the unlabeled data, and label them with the pseudo-labe generated from the standard trained model. As the distance measure, the same loss that is used for classification. Put together, we have
2x-aug = argmin
N
Σ
{(fo(z).v) + ((f
(
+ Am
((Fo(Ts) ( ( (2:1)
(27)
22

---

Under review as conference paper at ICLR 2020
In practice, zadv is found by performing few steps of projected gradient method on (=).o))))))).)))))))))))())))( and similarly aad by performing a few steps of projected gradient method on {ffo(2).fa, (.)).
F.2.2 TRADES
TRADES was modification of the projected gradient adversarial training algorithm of (Madry et al. 2018). Here, the loss function is modified in the following way, instead of operating on the label directly, the robustness term operates on the normalized logits, which can be thought probabilities of different labels. Using their modified loss and applying X-regularization leads to the following.
Ox 0x.a =
argmin N-1
Σ
{(fo())))) K (ppo ((po()))
(Xx.))((
Am ' Ce(fo(()) (+))) (B0))+BKKPppp((c (L(o (I.ve)))
(x:)) (i:))
(28)
where K (pa) is the KL divergence between the probability over class labels assigned to x and Tadv-
G EXPERIMENTAL DETAILS
G.1 SPLINE SIMULATIONS
and Figure we implement the optimization of the standard and For spline simulations in Figure 1 and robust objectives using the basis described (Friedman et. 200T). The penalty matrix M computes second-order finite differences of the parameters 0. We solve the min objective directly using CVXPY (Diamond & Boyd 2016). Each point Figure f a) represents the average test error over 25 trials of randomly sampled training datasets between 22 and 1000 samples. Shaded regions represent 1 standard deviation.
G.2 X-REGULARIZATION AS ROBUST SELF-TRAINING
In the adversarial training setting where augmentations are generated through transformations of existing data, natural to instantiate X-regularization as robust self-training, discussed in Section[F] We evaluate the performance of X-regularization applied to fo adversarial perturbations, adversarial rotations, and random rotations.
G.2.1 SUBSAMPLING CIFAR-10
We augment with fo adversarial perturbations of various sizes. In each epoch, we find the augmented ex- amples via Projected Gradient Ascent on the multiclass logistic loss (cross-entropy loss) of the incorrect class. Training the augmented estimator in this setup uses essentially the adversarial training procedure of (Madry et al. 2018). with equal weight on both the "clean" and adversarial examples during training.
We instantiate the general X-regularization estimator as robust self-training defined in (27 We compare the test error of the augmented estimator with an estimator trained using RST. We apply RST to adversarial training algorithms in CIFAR-10 using 500k unlabeled examples sourced from Tiny Images, as (Carmon et al. (001)).
We use Wide ResNet 40-2 models (Zagoruyko & Komodakis 2016) while varying the number of 10,20, ( in Figure a) and {1,2,5,8,10) 10} in Figure (b. For sub-sample factors to 20, report results averaged from 2 trials for each model. For sub-sample factors greater than 20, we average over trials. All models are trained for 200 epochs with respect to the size of the labeled training dataset and all achieve almost 100% standard and robust training accuracy.
samples C10.R-10. We sub-sample CIFAR- 10 by factors
We evaluate the robustness of models to the strong PGD-attack with 40 steps and restarts. In Figure (b), we used simple heuristic to set the regularization strength in Equation (27) to be = min (09. m))(). where 7 [0,1] is the fraction of the original CIFAR-10 10 dataset
23

---

Under review conference paper at ICLR 2020
Rob Enrontx--eee (rrott--ttglllo -o---ooo Erron(AT) 199)
Relative Err(Aug, Std) (%)
AT, 25
-X- X-Reg AT, 25
AT, 255
20
2 X-Reg, E 255
AT, 255
X-Reg, E 255
-20
10*
104
Number samples
Number of labeled samples
(a) Robust error, CIFAR- 10
(b) Relative standard error, CIFAR-10 10
Figure 7: (a) Difference in robust test eπrоr between our X-regularized adversarial training model and the vanilla adversarial training (AT) model for CIFAR- 10. X-regularization (instantiated as RST) keeps the robust accuracy within 2% of the AT model for small subsamples and even improves over the AT model for larger subsamples of CIFAR-10. (b) Relative difference in standard error between augmented estimators (our X-regularized model and the AT model) and the standard estimator CIFAR-10. We achieve up to 20% better standard error than the standard model for small subsamples.
Standard
AT
RST+AT
Standard Test Acc Robust Test Acc (c (c=11] 1/255)
94.63%
94.15%
95.47% %
85.59%
87.20%
Table 2: Accuracies for the standard, vanilla adversarial training (AT), and AT with X-regularization (RST) for 1/ 1/255 on the full CIFAR- 10 dataset. Accuracies are averaged over two trials. The robust test accuracy of the standard model is near 0%.
Standard
AT
X-reg
Standard Test Acc Robust Test Acc (e 2//255)
94.63%
92.69%
94.86
77.87%
80.46%
Table Accuracies for the standard, vanilla adversarial training (AT), and AT with X-regularization (X-reg) for 2/255 on the full CIFAR-10 10 dataset. Accuracies are averaged over two trials. The robust test accuracy standard model near 0%.
sampled. Intuitively, we give more weight the unlabeled data when the original dataset larger, meaning that the standard estimator produces more accurate pscudo-labels. We fix 3
shows that robust accuracy of RST model stays within 2% of the robust model (trained using PGD adversarial training) for all subsamples, and even improves upon the robust model on the full dataset (Tables22 2
Note that cannot directly compare the empirical performance of RST+adversarial training CIFAR-10 with other methods to obtain robust models that are modifications vanilla adversarial training. We use smaller model due computational constraints enforced by adversarial training. Since the model is small, we could only fit adversarially augmented examples with small c 2-22555, while existing baselines leads to an increase in error. We show that RST can fix this. While ensuring models are robust an important goal in itself, in this work, view adversarial training through the lens of covariate-shifted data augmentation and study how to use augmented data without increasing test error. We show that X-regularization based methods like RST preserve the other benefits of some kinds of data augmentation like increased robustness to adversarial examples.
8/ 8/255. Note that even for e = 2/255, adversarial data augmentation
G.2.2 loc ADVERSARIAL. PERTURBATIONS
In Table [ we evaluate X-regularization as robust self-training applied to PGD and TRADES adversarial training. The models are trained the full CIFAR- 10 dataset, and models which use
24

---

Under review as conference paper at ICLR 2020
unlabeled data (self-training and X-reg) also use 500k unlabeled examples from Tiny Images. All models except the Interpolated AT and Neural Architecture Search model use the same base model strong PGD-attac' with 40 steps and 5 restarts against foe perturbations of size 8/255. For X-regularization models, we set À =9 and / = in Equation (27) and Equation (28). following the heuristic À = min(0.9,1) ()/(1-mmm0009.))) for yor-=1. We train for 200 epochs such that 100% training standard accuracy is attained.
WideResNet 28-10. To evaluate robust accuracy,
G.2.3 ADVERSARIAL AND RANDOM ROTATION/TRANSLATIOON
In (right,, we instantiate X- X-regularization as robust self training for adversarial and random Intation/translattion using these transformations Tadv in Equation (27). The attack model is a grid of rotations of up to 30 degrees and translations of up to ~ 10% of the image size. The grid consists of 3 linearly spaced rotations and 5 linearly spaced translations in both dimensions. The Worst-of- 10 model samples 10 uniformly random transformations of each input and augment with the one where the model performs the worst (causes an incorrect prediction, if it exists). The Random model samples random transformation as the augmented input. All models (besides cited models) use the WRN-40-2 architec- ture and are trained for 200 epochs. We use the same hyperparameters X, as in G.2.2 for Equation (27)
H COMPARISON TO STANDARD SELF-TRAINING ALGORITHMS
The main objective of X- X-regularization standard accuracy. This is done by smoothing an augmented estimator to provide labels close to standard non-augmented estimator on the unlabeled data. This closely related to but different two broad kinds of semi-supervised learning.
allow perform data augmentation without sacrificing
1. Self-training (pseudo-labeling): Classical self- self-training does not deal with data augmentation robustness. We view X-regularization as a generalization of self-training the context of data augmentations, Here the pscudolabels are generated by a standard non-augne augmenteee estimator that is not trained on the labeled augmented points. In contrast, standard self-training would just use all labeled data to generate pseudo-labels. However, since some augmentations cause drop in standard accuracy, and hence this would generate worse pseudo-labels than the X-regularized version.
2. Consistency based regularization: Another popular semi-supervised learning strategy is based on enforcing consistency in a model's predictions across various perturbations of the unlabeled data (Miyato et al. 2018;; Xie et al., 2019 Sajjadi et al. [016]] Laine & Aila 2017)). X-regularization similar ar spirit, but has an additional crucial component. We generate pseudo-labes labels first by performing standard training, and rather than enforcing simply consistency across perturbations, we enforce that the unlabeled data and perturbations are matched with the pscudo-labed generated.
25


Reviews:
[{"review_id": "r1eQCCNUYH", "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": "This paper studies data augmentation in the regime where labels for the augmented datapoints are known. Special emphasis is put on the study of overparametrised linear models with minimum Euclidean norm of the regression weights (a.k.a. ridgeless regression). The results of this study are then used to motivate their “X-regularization” method, a semi-supervised learning algorithm which they test on the task of improving accuracy of adversarially trained models. The authors report improvement in accuracy of adversarially trained classifiers on CIFAR-10 when X-regularization is applied.\n\nWhile I think the paper could be potentially interesting to the ICLR community, I am currently leaning towards rejection for the following two reasons: (i) I am confused by significant chunks of the theoretical derivations;  (ii) the paper is hard  follow at several places, seems to be hastily written, and not well placed in the existing literature. Finally, I would like to state that since the paper is longer than 8 pages, I am holding it to a higher standard than an 8 page one as instructed by the guidelines.\n\n\nMajor comments:\n\n- I am very confused by the way you compute the (uncentred) sample covariance for the augmented dataset. On the penultimate line before eq.5, you state that Sigma_data = 1 / n X^T X if I interpret n as the total number of rows of X (which is IMHO correct). But then a couple of lines below you say that Sigma_aug = 1 / n (X_std^T X_std + alpha X_ext^T X_ext) which by the above logic should have been Sigma_aug = 1 / ((1 + alpha) n) (X_std^T X_std + X_ext^T X_ext) which is different from your definition. Inspecting appendix A.1, you also use Sigma_data = Sigma_std + alpha Sigma_ext whereas the above would suggest Sigma_data = 1 / ((1 + alpha)n) (n Sigma_data + alpha n Sigma_ext) = 1 / (1 + alpha) (Sigma_data + alpha Sigma_ext)?! Can you please clarify? Note that I did not go through the rest of the proof in the appendix.\n\n- On a related note, I am also rather confused by your example in sect.3.1.1. In particular, if you observe e_1, e_2, and e_3, and you are in the scenario where you can get the true labels for the X_ext data points + there is no noise on y (sigma = 0), then you will get theta_aug = (X^T X)^dagger X^T X theta* = Id^(-1) Id theta* = theta* (where Id stands for the identity matrix), i.e., theta_aug = theta* and so there will be zero generalisation error since y = x^T theta* is the correct data generating process in this scenario. However, in the first display on p.4, you claim the bias (and thus generalisation error) of theta_aug is non-zero. The rest of the section similarly seems to contradict the theta_aug = theta*. Can you please clarify?\n\n- Since the rest of sect.3 also uses the Sigma_aug = Sigma_data + alpha Sigma_ext instead of scaling this expression by Sigma_aug = 1 / (1 + alpha) (Sigma_data + alpha Sigma_ext), I will withhold my judgement until you could please clarify this confusion.\n\n- Can you please point me to where I can find more detail about fig.1? In particular, how was the right plot produced (incl. how many repetitions of the experiment were executed)? Also, is it true that the green points in the middle plot were not chosen at random? If so, this should be clarified in the caption and the text.\n\n- Since all of your non-toy experiments are focused on adversarial learning, it might benefit the paper to advertise this focus more clearly from page one. Furthermore, have you tested X-regularization with non-adversarial data augmentation (on CIFAR-10 or other standard benchmark) please?\n\n- While you briefly mention the existence of alternatives to your algorithm, you don’t include any of these in your experiments section. I would suggest including some benchmark results (even if this only means restating numbers from other papers with citation).\n\n\nMinor comments:\n\n- In the abstract, you claim about X-regularization: “We prove that our new estimator never increases test error.” while sect.4 you say that this guarantee only holds for linear models. I think this should be clarified in the abstract.\n\n- p.1 in par.1, you say “but in practice, we often work with models which can fit the augmented training data perfectly” (similar statements also appear throughout the paper, e.g., the last sentence of par.3 on p.1). I am confused by this statement because many augmentation schemes have full support in the input space, i.e., you will eventually have to be able to classify correctly any point in the input space. Are you assuming that the conditional distribution of y given x is almost surely deterministic, and using some universal approximation theorem for neural networks (even those tend to have some restrictions on the y = f(x) function!)? Please clarify.\n\n- p.1 in par.3, “... may increase increase error …” -> “may increase error”\n\n- Second to last paragraph on p.2, “Y = X theta + sigma N(0, I)” is mixing random variables and distributions. Please consider replacing “N(0, I)” with “epsilon, epsilon ~ N(0, I)“. Also, comparing with eq.1, did you mean “sigma^2” in eq.1?\n\n- Last paragraph on p.2, “compare the performance two estimators” -> “ compare the performance of two estimators”.\n\n- Top of p.2 in eq.3: the definition of the augmented estimator is somewhat confusing. If the augmentation causes the total number of points (i.e., n + \\alpha n) to be higher than d (the number of parameters), then the set on the right hand side can be empty (and will be unless there is some perfect multicollinearity). Can you please clarify how is the augmented estimator defined in that case?\n\n- Please reconsider use of contractions (e.g., “doesn’t” -> “does not” in par.2 of sect.3) throughout the paper.\n\n- In eq.5, in the expression for bias, I think you are missing star superscript for the 2nd theta.\n\n- Under eq.5, “... we say that augmentation is safe if the predictive risk or bias does not increase, and hurtful if it does.” Can you please clarify whether the use of “or” is in the strictly logical sense, i.e., arbitrarily large increase in variance is fine as long as bias does not increase (in which case the second part of the statement and thus the full statement is still true)?\n\n- Beginning of “Large Sample Regime” paragraph of sect.3, you claim  “Common intuition from a statistical standpoint would suggest that more data is always good.” I am not sure I agree: there is a plethora of literature on data poisoning, robustness, differential privacy, adversarial examples, etc., which shows that adding data can significantly worsen performance of models. Even without reading these papers, it seems quite natural that adding **arbitrary** data into the dataset may not be the best idea (even in the large sample regime).\n\n- Unresolved equation reference on p.11, 2nd line. Also, in the very next sentence, “yields zero and variance …” -> “yields zero bias and variance ...“?! Broken references also on p.14 (twice). ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Sken8X2g5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary: This paper provides some theory into the question of whether data augmentation can hurt test-set performance. To paraphrase the theory, data augmentation can hurt when it causes the model to learn a spurious local details instead of global structure, even if the augmented data comes from the same (predictive) distribution, and even if the true model lies in the hypothesis class of the learned model. Ironically these effects may be diminished in the large-sample regime, where data augmentation is less important in practice. Motivated by these issues, the authors propose \"X-regularization\" which requires that models trained on standard and augmented data produce similar predictions on unlabeled data. The paper includes a few experiments on a toy staircase regression problem as well as some ResNet experiments on CIFAR-10.\n\nReview: Overall I think this paper provides an interesting perspective on when and why augmented data can increase test error. Most of the theory deals with a simple convex problem, but some work is done to measure whether the insights carry over to more realistic settings. I think the main ways the paper could be improved are a) better explanation of connections between the theoretical assumptions and practice and b) better treatment of \"X-regularization\". For a) in particular, more discussion of which exiting data augmentation schemes fall under the theoretical framework would be useful. For b), X-regularization seems tacked on to the end of the paper, despite the potential strength of the contribution. It is not compared directly to existing semi-supervised or robust learning methods. As it currently stands I think the paper spends a bit too much time in the main text on the toy problem and theory, and could be bolstered by additional discussion of x-regularization. But, I think it's acceptable in its current form.\n\nSpecific comments:\n- In Figure 1 the green crosses use such wide lines that they look like dots at first glance. When the text referred to \"crosses\" I was confused. I'd suggest making them more obviously crosses.\n- \"the distribution of Px of the augmented dataset is potentially different than Stairs on the original dataset\" Up until this point, your setting was not specific to the \"Stairs\" problem so I'm not sure why you're mentioning it here. This sentence would make more sense to me if you removed the words \"Stairs on the\".\n- I think it would be useful if you provided some examples of data augmentation schemes (that are used in practice) that satisfy and do not satisfy the assumptions of your theoretical analysis.\n- I would also suggest that you provide some additional connections or discussion of the relation between the behavior of your setting (section 2) to the behavior of models we actually use in practice (neural nets). How much of the behavior do we expect to carry over? Why?\n- \"AT augments with imperceptible perturbations of training images with the corresponding correct target and thereby falls in our framework of covariate-shifted data augmentation.\" You should mention the assumptions implicit in this definition, namely that perturbing an image with a perturbation whose l_inf norm is less than some threshold will not change the target class. This is what connects it to your theoretical setting and so is an important detail.\n- Ma et al. (2018); Belkin et al. (2018) need \\citep\n- \"The assumption that we have Σ\" I think you are missing an \"on\" before \"Σ\".\n- IIUC General X-regularization essentially enforces that the distance between a model trained on augmented + non-augmented data produces the same predictions as a model trained on only the non-augmented data when both models are fed additional unlabeled data. If this is the case I would suggest clarifying this a bit. This bears some similarity to consistency regularization/the \"Pi-Model\" (Laine & Aila 2017, Sajjadi et al. 2016), except in those cases consistency is enforced between a model fed with augmented and non-augmented versions of the same image. In your case IIUC you train two separate models and use unlabeled data to compare them; in the consistency regularization a single model is trained on labeled and unlabeled data together.\n- \"Hence empirically, our X-regularization has lower standard error but higher robust error than RSL.\" I don't think you have empirical evidence that supports this claim.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": {}}, {"review_id": "BkeSIRjNqr", "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 describes situations whereby data augmentation (particularly drawn from a true distribution) can lead to increased generalization error even when the model being optimized is appropriately formulated.  The authors describe a somewhat intuitive example of how this can happen, and proceed to support this example and generalize with mathematical rigor.\n\nThe machinery of the analysis and the positive suggestion of X-regularization strike me as technically sophisticated and effective.\n\nThis is largely a theoretical paper.  The central example and description assume the availability of a true distribution to draw an arbitrary amount of examples from.  While CIFAR-10 is used to demonstrate the effectiveness of X-regularization, it is not compared to any other augmenatation / semi-supervised / regularization approach.  This makes contextualizing the contribution of this work more challenging.  General data augmentation techniques frequently do not draw examples form a true distribution (here the test distribution or a held-out development set) but rather manipulate real examples through some transformation function (like noise addition, rotation, scaling, warping, etc.).  This work does not address these conditions.  Rather the augmentation investigated here is more like self-training, where information from unlabeled examples are used in the training (i.e. regularization) of a model.  If i understand the technique correctly, assuming the eigenvector decomposition is relatively consistent under different samples of augmentation data, the regularization should be consistent whether regularized using the test set or some other unlabeled set.  While I think this is theoretically true, it would be useful to see this reflected on the CIFAR data, where the test data is unused during training at all.  \n\nThe contextualization of this work to related work -- particularly self-training and semi-supervised training -- is quite thin.  While acknowledged, the technical rigor that is brought to the main result is not used to contrast with other techniques.  Neither are there empirical comparisons to existing techniques in this space.\n\nOn balance, I find the theoretical investigation and explanation for \"how does this happen\" to be more compelling than the presentation of X-regularization.\n\nNote on \"Experience Assessment\": While I've done research on data augmentation and published in this space, the formulation and analytical tools employed in this paper I am less familiar with.   ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "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 paper describes situations whereby data augmentation (particularly drawn from a true distribution) can lead to increased generalization error even when the model being optimized is appropriately formulated. The authors propose "X-regularization" which requires that models trained on standard and augmented data produce similar predictions on unlabeled data. The paper includes a few experiments on a toy staircase regression problem as well as some ResNet experiments on CIFAR-10.  This paper received 2 recommendations for rejection, and one weak accept recommendation.  After the rebuttal phase, the author who recommended weak acceptance indicated their willingness to let the paper be rejected in light of the other reviews.  The reviewer highlighted: "I think the authors could still to better to relate their theory to practice, and expand on the discussion/presentation of X-regularization."  The main open issue is that the theoretical contributions of the paper are not sufficiently linked to the proposed algorithm.
Decision: Reject