Year: 2019

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 as 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 regression. As a fix, we propose 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-regularization consistently improves both robustness and standard test error across different adversarial training algorithms and perturbations on CIFAR-10.

heading: 1 INTRODUCTION
text: Adversarial training improves the robustness of neural networks to perturbations, commonly referred to as adversarial examples (Goodfellow et al., 2015; Szegedy et al., 2014; Biggio et al., 2013). 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 a form of data augmentation where we augment the training set with worst-case perturbations of each training image within a 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 as with adversarial `∞ perturbations increase error. Previous works (Tsipras et 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-preserving perturbations in a well-specified setting, causes an 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 1(a) illustrates a 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 error. 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 1(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 a possibly different norm on the parameter error vector which depends on the data distribution (Section 4.1). Further, one might expect augmentation to be most helpful in low data settings. We show that in 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
interpolant to stay close to 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 1(c) for its effect on the spline interpolation problem.
X-regularization naturally extends to 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, X-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 as a 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 regularizer that improves both standard accuracy and robustness. We evaluate the effect of RST on standard and robust accuracy with different adversarial training losses and perturbations on CIFAR-10 in Section 6.3. With `∞ perturbations, we find that RST improves standard accuracy by 4−6% while maintaining or 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-regularization, is a promising approach to mitigate the undesirable drop in standard accuracy when training robust networks.

heading: 2 RELATED WORK
text: The detrimental effect of data augmentation has been previously studied in the context of a “tradeoff” between accuracy and robustness.
Understanding the tradeoff. In an attempt to explain the tradeoff between robustness and accuracy, Tsipras et al. (2019); Zhang et al. (2019); Fawzi et al. (2018); Nakkiran (2019) provide simple constructions that showcase an inherent tension between these objectives even in the limit of infinite data. These constructions rely on either non-label-preserving perturbations or insufficient model complexity to express a 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 et al., 2017) or 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.

heading: 3 SETUP

heading: 3.1 COVARIATE-SHIFTED DATA AUGMENTATION.
text: Let Pxy denote the underlying distribution of (x,y) pairs, Px its marginal on Rd, and Py(· | x) the conditional distribution of the targets given inputs.
We refer to the training data from the underlying distribution Pxy by standard training data. Formally, we have n pairs (xi,yi)∼ Pxy forming the measurement matrix Xstd = [x1,x2,...xn]> ∈Rn×d and target vector ystd =[y1,y2,...yn]>∈Rn. Analogously , we consider augmenting the training set with “extra” training points denoted by Xext = [x̃1,x̃2,...x̃m]
> ∈Rm×d with associated targets yext = [ỹ1,ỹ2,...ỹm]> ∈Rm. We focus on covariate-shifted data augmentations which includes most forms of data augmentations used in practice . Here, the targets yext are drawn from the same underlying predictive distribution Py(· | x) as the standard data, while the extra inputsXext could be arbitrary.
Examples. Typically , the “extra” training points are constructed as follows: x̃i = T (xi), ỹi = yi, where T is some label-preserving transformation thereby enforcing that the extra targets are as if sampled from Py(· |x). Example transformations include translations, horizontal flips, small rotations, small `∞ 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 Xstd. 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-shifted data augmentation . Consider projected gradient adversarial training (PG-AT) (Madry et 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 as a form of iterative data augmentation that falls in our framework above. Formally, letB(x) be the set of perturbations of x that we would like to be robust against. We assume that the label is constant overB(x). The transformation at step t of the training for data point xi is Tt(xi) = argmax
x∈B(xi) `(θ̂t,xi,yi), where θ̂t are the model parameters at time step t.
The worst-case (max loss) perturbation is approximated via the projected gradient method.

heading: 3.2 MINIMUM NORM INTERPOLATION IN WELL-SPECIFIED LINEAR REGRESSION
text: Consider a regression task where the targets y ∈ R are drawn from the conditional distribution Py(· |x)=N (x>θ?, σ), for some vector θ?∈Rd. Our goal is to learn a linear predictor fθ(x)=x>θ . 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 et al., 2018; Hastie et al., 2019; Liang & Rakhlin, 2018; Bartlett et 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∈Rn×d and corresponding targets Y ∈Rn as training data, we define the following minimum norm interpolation estimator as
θ̂=argmin θ
{ ‖θ‖2 :Xθ=Y } . (1)
In particular , we compare the following estimators : (i) the standard estimator θ̂std which has [Xstd,ystd] as training data and (ii) the data augmented estimator θ̂aug with X = [Xstd;Xext],Y = [ystd;yext] as training data:
θ̂std =argmin θ
{ ‖θ‖2 :Xstdθ=ystd } and θ̂aug =argmin
θ
{ ‖θ‖2 :Xstdθ=ystd,Xextθ=yext } . (2)

heading: 4 BIAS AND VARIANCE OF MINIMUM NORM INTERPOLANTS
text: We evaluate the two estimators described in Equation 2 using the error on a random sample xtest drawn from Px. Let Σ be the covariance of Px. We focus on the error conditioned on Xstd,Xext , which
decomposes into a bias and variance term as follows
R(θ̂)=E[(x>test(θ̂−θ?))2]=E[(θ̂−θ?)>Σ(θ̂−θ?)] =(E[θ̂]−θ?)>Σ(E[θ̂]−θ?)︸ ︷︷ ︸
Bias B(θ̂)
+tr(Cov(θ̂)Σ)︸ ︷︷ ︸ Variance V (θ̂) , (3)
where the expectation is taken over the randomness in xtest and targets ystd, yext conditioned on Xstd,Xext. In this section, we treat Xstd,Xext as fixed quantities. However, since Xstd consists of samples from Px, the number of samples dictates some structure onXstd. 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.

heading: 4.1 BIAS OF MINIMUM NORM INTERPOLANTS
text: For minimum norm interpolant with X,Y as training data, the bias term B(θ̂) can be expressed as follows. On expectation (over targets Y ), any interpolating estimator recovers θ? in the column space of X , but is unconstrained in Null(X>X). The minimum norm interpolant sets the component in Null(X>X) to zero. Formally,
E[θ̂]=(X>X)†X>Xθ? =⇒B(θ̂)=θ?>Π⊥XΣΠ⊥Xθ?, where Π⊥X = ( I−(X>X)†(X>X) ) is the projection matrix onto Null(X>X).
We now compare the bias of the standard and data augmented estimators (defined in Equation 2). It is convenient to define Σstd =X>stdXstd and Σaug =X > stdXstd +X > extXext. Let Π ⊥ std = I−Σ†stdΣstd and Π⊥aug =I−Σ†augΣaug be the projection matrices onto Null(Σstd) and Null(Σaug) respectively. Then, B(θ̂std)=θ ?>Π⊥stdΣΠ ⊥ stdθ ? and B(θ̂aug)=θ? >Π⊥augΣΠ ⊥ augθ ?. (4)
Remark 1. Note that the bias in parameter error is ‖E[θ̂] − θ?‖22 = ‖Π⊥Xθ?‖22. Since Null(Σaug) ⊆ Null(Σstd), we have ‖Π⊥augθ?‖22 ≤ ‖Π⊥stdθ?‖22, and data augmentation always reduces the bias in parameter error. However, the bias in test error upon augmentationB(θ̂aug) could be larger or smaller thanB(θ̂std).

heading: 4.1.1 SIMPLE LINEAR PROBLEM IN R3 WHERE ADDING DATA INCREASES BIAS
text: The following example illustrates how the interaction between the column spaces of standard inputsXstd, extra inputsXext and the underlying true parameter θ? could cause data augmentation to increase bias.
For simplicity, we choose Σ = diag([λ1, λ2, λ3]) with λ2 λ1, Xstd = e3 and additional data Xext = e1 +e2 where e1,e2,e3 denote the standard bases in R3. For brevity in notation, we denote E[θ̂std] by θ̂std and E[θ̂aug] by θ̂aug.
Recall that by virtue of being minimum norm interpolants, (θ̂std − θ?) ∈ Null(Σstd) = R2 and (θ̂aug−θ?)∈Null(Σaug)={ρ(e1−e2) : ρ∈R}. Figure 2 depicts these parameter errors for different choices of θ?.
Bias under different settings of θ?. Plugging these terms into the bias expression in Equation (4) yields
B(θ̂std)=θ ? 1 2λ1+θ ? 2 2λ2 and B(θ̂aug)=(1/4)(θ?1−θ?2)2λ1+(1/4)(θ?1−θ?2)2λ2. Since in our construction of Σ we have λ2 λ1, the bias expression is dominated by the coefficient on λ2, which is the projection of the parameter error on e2 (red lines in Figure 2). Depending on θ?, B(θ̂aug) could be larger or smaller thanB(θ̂std). In particular,
(i) when θ?1 θ?2 as in Fig. 2 (a), augmenting with Xext can increase bias B(θ̂aug) B(θ̂std). Even though the augmented estimator has lower parameter error overall (‖θ̂aug−θ?‖2≤‖θ̂std−θ?‖2), the increase in parameter error along e2 dominates the effect on the bias because λ2 λ1. (ii) when θ?2 θ?1 as in Fig. 2 (b), the same Xext causes B(θ̂aug) to be smaller than B(θ̂std). Here the augmented estimator has smaller parameter error along e2 and hence decreasing bias despite an increase along e1.
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 eigenvectors 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 a general characterization below.

heading: 4.1.2 GENERAL CHARACTERIZATIONS
text: We now study the biases of the standard and augmented estimators in general. Recall that Π⊥std and Π ⊥ aug are the projection matrices onto Null(Σstd) and Null(Σaug) respectively, where Σstd =X>stdXstd and Σaug =X > stdXstd+X > extXext. Since Null(Σaug)⊆Null(Σstd), we can decompose Π⊥stdθ? into orthogonal components v = Π⊥augθ ? and w= Π⊥stdΠaugθ
?. Substituting this decomposition into Equation 4, we get the following exact characterization for when data augmentation increases bias.
Theorem 1. The augmented estimator θ̂aug has larger bias i.e.,B(θ̂aug)>B(θ̂std) if and only if
v>Σv<−2w>Σv, (5)
where v=Π⊥stdΠaugθ ? andw=Π⊥augθ ?.
The proof of Theorem 1 is in Appendix B.1. We see that condition (5) depends on θ? which is typically unknown. Hence, we cannot determine apriori if 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). However, we can make the following statements about when data augmentation is safe (for any θ?) in some restricted settings.
1. When Σ = I , the condition (5) is always met (since w ⊥ v) and hence data augmentation is always safe and never increases bias for any θ?. This suggests that data augmentation increases bias when there is a mismatch between the norm being minimized during interpolation and the norm of the parameter error that determines test error.
2. WhenXext spans the entire nullspace of Σstd such that Σaug is invertible,w=0 for all θ? and data augmentation never increases bias.
3. In the simple case where Xext is rank-one, data augmentation is safe for all θ? if and only if Π⊥stdXext is an eigenvector of Σ. See Appendix B.4 for a proof.
Finally, we illustrate the safe augmentation directionsXext in the nullspace of Σstd for the simple 3-D problem discussed above for two different choices of Σ and a fixed θ? (Figure 2 (c), (d)). The safe augmentations lie in cones around the eigenvectors of Σ while the width and alignment of the cones depends on the alignment between θ? and the eigenvectors of Σ. As the eigenvalues of Σ become more skewed,
the space of safe augmentations shrinks. We present a dual perspective on Theorem 1 in Appendix B which characterizes the effect of augmentation on the bias in terms of properties of the true parameter θ?.
Local vs. global structure. Finally, we tie our analysis back to the spline staircase problem from Figure 1. 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(Σstd) 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 in Null(Σstd) could lead to a worse fit of the global structure, leading to increased test error (See Figure 3). This is suggestive of a similar trade-off phenomenon in practice where adversarial training (with say `∞ perturbations) encourages neural networks to fit the high-frequency components of the signal while compromising on the overall global structure causing an increase in test error.

heading: 4.2 VARIANCE OF MINIMUM NORM INTERPOLANTS
text: The main focus of this work is on the effect of data augmentation on the bias of minimum norm interpolants. For completeness, we present some conditions under which the data augmentation increases or decreases variance. For a more complete treatment, please refer to Appendix C. Let Xstd,ystd be the standard training data, with extra points Xext,yext and let Π⊥std denote the projection matrix onto Null(X>stdXstd).
Theorem 2. For the minimum norm interpolants defined in Equation 2, the following hold.
1. When Π⊥stdXext = 0 such that the extra points lie in the column space of original standard training data, V (θ̂aug)≤V (θ̂std).
2. When Xext ⊥ Xstd, such that the extra points lie entirely in Null(X>stdXstd), we have V (θ̂aug)≥V (θ̂std).
In general, when Xext ∈ Null(X>stdXstd), we see that both the bias and variance of minimum norm interpolants could increase upon data augmentation, shedding some light on why data augmentation sometimes increases standard error in practice.

heading: 5 EFFECT OF SIZE OF THE ORIGINAL TRAINING SET
text: In this section, we study how the effect of data augmentation varies as we vary the size of the original standard training set. We first briefly study this in the setting of minimum norm interpolation in linear regression. We then empirically evaluate the effect of adversarial training as we vary the number of original training samples in CIFAR-10 and observe that the empirical trends mirror the trends dictated by our analysis in linear regression.

heading: 5.1 MINIMUM NORM INTERPOLATION—SMALL AND LARGE DATA REGIMES.
text: Without loss of generality, we assume that Σ, the population covariance of Px is invertible since the test error only depends on columnspace of Σ.
Large data regime. In the large data regime where the number of standard training points n→∞, the empirical covariance of the original training points Σstd =X>stdXstd≈nΣ is invertible with Π⊥std = 0. Both θ̂std and θ̂aug are unbiased (from Equation 4). From Theorem 2, variance of θ̂aug is never larger than
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 n is much smaller than d, the empirical covariance Σstd could be far from invertible. As we increase the number of samples, the null space Null(Σstd) shrinks. Our analysis in Section 4 shows that for a fixed θ?, the magnitude of possible increase in both bias and variance decreases as Π⊥stdXext decreases (See Appendix E) for details). This suggests that as the size ofXstd increases, the increase in test error due to augmentation decreases. We run simulations of the spline staircase example from Figure 1 and find that this trend holds (Figure 4(a); see Appendix D).

heading: 5.2 EMPIRICAL OBSERVATIONS ON THE EFFECT OF SAMPLE SIZE.
text: Do the trends in linear regression also hold for classification with more complex models and real world datasets? For our empirical study, we focus on adversarial training (Madry et al., 2018), iterative data augmentations with adversarial `∞ perturbations of different magnitudes . We train a WideResNet-40-2 (Zagoruyko & Komodakis, 2016) on CIFAR-10 training set subsampled by varying amounts. We plot the difference in the test errors of the augmented and standard estimators as a function of training set size in Figure 4. We find that augmentation is 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—contradicting the toy examples studied in (Tsipras et al., 2019; Zhang et al., 2019; Nakkiran, 2019) which we discussed in Section 2.

heading: 6 MITIGATING THE INCREASE IN BIAS UPON AUGMENTATION
text: To this point, the paper focuses on understanding why data augmentation could increase test error by analysing the setting of minimum norm interpolation in linear regression. However, data augmentation (e.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-regularization, and prove that X-regularization eliminates the increase in bias upon augmentation for noiseless linear regression (Section 6.1. In Section 6.2, we show that this estimator naturally generalizes to arbitrary losses and complex models and is closely connected to the classical semi-supervised self-training algorithm (Scudder, 1965). We empirically evaluate the performance of this general X-regularization on adversarial training in Section 6.3. In a nutshell, X-regularization causes a smaller increase in standard error while maintaining or simultaneously improving the robustness of neural networks trained on CIFAR-10.

heading: 6.1 X-REGULARIZATION FOR LINEAR REGRESSION
text: Our development considers a stylized setting of interpolation in linear regression with noiseless observations from a linear model, y=x>θ?, where the dimension is (much) larger than the number of observations. Let θint-std interpolate the initial data, satisfying Xstdθint-std = ystd. We use θint-std to construct a new data augmented estimator θ̂x-aug that interpolates both the standard data and augmented extra data while satisfyingR(θ̂x-aug)≤R(θint-std). Given Σ and an initial interpolant θint-std, we propose the X-regularized data augmentation estimator
θ̂x-aug∈argmin θ
{ (θ−θint-std)>Σ(θ−θint-std) :Xstdθ=ystd, Xextθ=yext } . (6)
The X-regularized estimator θ̂x-aug optimizes for small error on the labeled data (Xstd, ystd) and (Xext,yext) while keeping the predictions of θ̂x-aug close to those of θint-std over unlabeled inputs drawn from Px. 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 Xext, the data augmented estimator could have a larger parameter error than θint-std in important directions of Σ, and consequently higher test error (Figure 2). A natural strategy to mitigate this increase, then, is to fitXext while staying close to θint-std weighted by Σ, which leads to the estimator defined in Equation 6. This intuition can be formalized to prove that the X-regularized interpolant θ̂x-aug never has higher test error than θint-std.
Theorem 3. Assume the noiseless linear model y=x>θ?. Let θint-std be an arbitrary interpolant of the standard data, i.e.Xstdθint-std =ystd. Let θ̂x-aug be the X-regularized interpolant (6). Then
R ( θ̂x-aug)≤R(θint-std).
See Appendix ?? for proof. To provide some graphical intuition for the result, consider the spline interpolant θ̂std Fig. 1 illustrates whereXext consists of local perturbations. The X-regularized estimator matches the standard interpolant θ̂std on points outside the training set, thereby capturing global structure while simultaneously fitting local structure on the training set viaXext.
Note that our discussion on the effect of sample sizes in Section 5 suggests that a larger labeled standard training set would mitigate the drop in standard error due to augmentation. However, our development of X-regularization suggests that we only need unlabeled data, which is much cheaper to 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.

heading: 6.2 ROBUST SELF-TRAINING AS X-REGULARIZATION FOR ROBUSTNESS
text: 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 a more general form:
(θ−θint-std)>Σ(θ−θint-std)=EPx [(x>θ−x>θint-std)2]=EPx [`sq(fθ(x),fθint-std(x))],
where `sq is the squared loss between the predictions of the model fθ(x) with the predictions (pseudo-labels) of a given interpolant fθint-std(x). A generalized version of X-regularization replaces `sq 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 label-preserving transformations of existing inputs. With augmentations take the form of some label-preserving transformations T , it is natural to consider transformations of both the labeled and unlabeled data as the set of “extra” points, that constituteXext. Generalizing the linear regression estimator of Equation 6 to use arbitrary losses and transformation
based augmentations, we get,
θ̂x-aug :=argmin θ
{ N−1 ∑ (x,y)∈[Xstd,ystd] `(fθ(x),y)+β ˜̀(fθ(T (x)),y)
+λm−1 m∑ i=1 `(fθ(x̃i),fθ̂std(x̃i))+β ˜̀(fθ(T (x̃i)),fθ̂std(x̃i)) } . (7)
We note that the general X-regularized estimator above is the Robust Self-Training (RST) algorithm proposed and studied recently by Carmon et al. (2019), when applied to arbitrary transformations. Variants of RST were also studied in (Najafi et al., 2019; Uesato et al., 2019). By deriving RST via Xregularization, we provide some theoretical justification for why RST would improve standard accuracy.

heading: 6.3 EMPIRICAL EVALUATION OF X-REGULARIZATION AS RST
text: For our empirical investigation, we evaluate the effect of 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 to 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 F.2. All of our experiments are on CIFAR-10, and RST estimators use 500K unlabeled images sourced from Tiny Images in (Carmon et al., 2019) in 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-10 in Section 5. We compare the error of RST+PG-AT and standard training in Figure 4. 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.1). 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 a larger WRN-2810 model with the entire labeled CIFAR-10 training set and 500K unlabeled images. Table 1(left) summarizes the results. While there is a still a drop in 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
robustness and accuracy such as 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, we test the effect of RST on a different family of perturbations. We consider adversarial (worst of 10) and random augmentations using simultaneous rotations and translations of the input image. Table 1(right) 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.

heading: 7 DISCUSSION
text: 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 on 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 to 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 et al., 2019; Najafi et al., 2019; Uesato et al., 2019) has studied the benefits of semi-supervised learning in improving robustness. In our work, we bolster this line of work by demonstrating that semi-supervised learning can simultaneously improve the accuracy, while maintaining robustness.
Self-training. In this work, we study X-regularization which is closely related to self-training, perhaps the oldest semi-supervised learning algorithm (Scudder, 1965). In the traditional setting of improving standard accuracy, self-training has shown some success, but other approaches perform significantly better; see survey (Oliver et al., 2018). However, in the regime where we care about both robustness and accuracy, we see that self-training based approaches such as X-regularization offer significant benefits. We provide a detailed comparison of X-regularization to other semi-supervised learning algorithms in Appendix H. Variants of self-training are also gaining prominence in the related but different setting of unsupervised 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 prominence with the observation that neural networks obtain zero training error. Previous works (Hastie et al., 2019; Bartlett et 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 networks 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 augmentation sometimes helps and sometimes harms test performance. In contrast, in the classical underparameterized regime, data augmentation never harms test performance as common statistical intuition would suggest. Studying interpolation in the overparameterized 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 a stylized setting and proved that unlabeled data can eliminate possible increase in test error. This motivated a 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 to 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 a large amount of unlabeled data, or do we need further innovations in neural network architectures and training?

heading: A TRANSFORMATIONS TO HANDLE ARBITRARY MATRIX NORMS
text: Consider a more general minimum norm estimator of the following form. Given inputs X and corresponding targets Y as training data, we study the interpolation estimator,
θ̂=argmin θ
{ θ>Mθ :Xθ=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 `2 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←M−1/2x and rotated parameters θ←M1/2θ maintain Y =Xθ+σN (0,I) and theM -norm of parameters simplifies to ‖θ‖2.

heading: B BIAS OF MINIMUM NORM INTERPOLANTS

heading: B.1 PROOF OF THEOREM 1
text: Inequality (5) follows from
B(θ̂aug)−B(θ̂std)=(θ?−θ̂aug)>Σ(θ?−θ̂aug)−(θ?−θ̂std)>Σ(θ?−θ̂std) =(Π⊥augθ ?)>ΣΠ⊥augθ ?−(Π⊥stdθ?)>ΣΠ⊥stdθ?
=w>Σw−(w+v)>Σ(w+v) =−2w>Σv−v>Σv (9)
by decomposition of Π⊥stdθ ?=v+w where v=Π⊥stdΠaugθ ? andw=Π⊥stdΠ ⊥ augθ ?. We also want to note that the bias difference does scale with ‖θ?‖2.

heading: B.2 BIAS INCREASE REQUIRES COMPLEX TRUE ESTIMATORS
text: A dual perspective on Theorem 1 leads the following proposition that characterizes the properties of the true function θ? that leads to harmful augmentations.
Proposition 1. For a givenXstd,Xext,Σ, a bias increase ofB(θ̂aug)−B(θ̂std)=c>0 via augmentation withXext is possible only if θ? is sufficiently more complex than θ̂std in the `2 norm, i.e.
‖θ?‖22−‖θ̂std‖22>γc (10) for some scalar γ>0 that depends onXstd,Xext,Σ.

heading: B.2.1 PROOF OF INEQUALITY (10)
text: The proof of inequality (10) is based on the following two lemmas that are also useful for characterization purposes in Corollary 1. Lemma 1. If a PSD matrix Σ has non-equal eigenvalues, one can find two unit vectorsw,v for which the following holds
w>v=0 and w>Σv 6=0 (11) Hence, there exists a combination of original and augmentation dataset Xstd, Xext such that condition (11) holds for two directions v∈Col(Π⊥stdΠaug) andw∈Col(Π⊥stdΠ⊥aug)=Col(Π⊥aug).
Note that neither w nor v can be eigenvectors of Σ in order for both conditions in equation (11) to hold. Given a population covariance, fixed original and augmentation data for which condition (11) holds, we can now explicitly construct θ? for which augmentation hurts bias. Lemma 2. Assume Σ, Xstd, Xext are fixed. Then condition (11) holds for two directions v ∈ Col(Π⊥stdΠaug) andw∈Col(Π⊥stdΠ⊥aug) iff there exists a θ? such thatB(θ̂aug)−B(θ̂std)≥c for some c>0. Furthermore, the `2 norm of θ? needs to satisfy the following lower bounds with c1 :=‖θ̂aug‖2−‖θ̂std‖2
‖θ?‖2−‖θ̂aug‖2≥β1c1+β2 c2
c1
‖θ?‖2−‖θ̂std‖2≥(β1+1)c1+β2 c2
c1 (12)
where βi are constants that depend onXstd,Xext,Σ.
Inequality (10) follows directly from the second statement of Lemma 2 by minimizing the bound (12) with respect to c1 which is a free parameter to be chosen during construction of θ? (see proof of Lemma (2). The minimum is attained for c1 =2 √ (β1+1)(β2c2). We hence conclude that θ? needs to be sufficiently more complex than a good standard solution, i.e. ‖θ?‖22−‖θ̂std‖22>γcwhere γ>0 is a constant that depends on theXstd,Xext.

heading: B.3 PROOF OF TECHNICAL LEMMAS
text: In this section we prove the technical lemmas that are used to prove Theorem 1.

heading: B.3.1 PROOF OF LEMMA 2
text: Any vector Π⊥stdθ ∈ Null(Σstd) can be decomposed into orthogonal components Π⊥stdθ = Π⊥stdΠ ⊥ augθ + Π ⊥ stdΠaugθ. Using the minimum-norm property, we can then always decompose the (rotated) augmented estimator θ̂aug∈Col(Π⊥aug)=Col(Π⊥stdΠ⊥aug) and true parameter θ? by
θ̂aug = θ̂std+ ∑ vi∈ext ζivi
θ?= θ̂aug+ ∑ wj∈rest ξjwj ,
where we define “ext” as the set of basis vectors which span Col(Π⊥stdΠaug) and respectively “rest” for Null(Σaug). Requiring the bias increase to be some constant c>0 can be rewritten using identity (9) as follows
B(θ̂aug)−B(θ̂std)=c ⇐⇒ ( ∑ vi∈ext ζivi) >Σ( ∑ vi∈ext ζivi)+c=−2( ∑ wj∈rest ξjwj)Σ( ∑ vi∈ext ζivi)
⇐⇒ ( ∑ vi∈ext ζivi) >Σ( ∑ vi∈ext ζivi)+c=−2 ∑ wj∈rest,vi∈ext ξjζiw > j Σvi (13)
The left hand side of equation (13) is always positive, hence it is necessary for this equality to hold with any c>0, that there exists at least one pair i,j such that w>j Σvi 6= 0 and one direction of the iff statement is proved.
For the other direction, we show that if there exist v ∈ Col(Π⊥stdΠaug) and w ∈ Col(Π⊥stdΠ⊥aug) for which condition (11) holds (wlog we assume that thew>Σv<0) we can construct a θ? for which the inequality (5) in Theorem 1 holds as follows:
It is then necessary by our assumption that ξjζiw>j Σvi>0 for at least some i,j. We can then set ζi>0 such that ‖θ̂aug−θ̂std‖2 =‖ζ‖2 =c1>0, i.e. 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 c>0).
The choice of ξ minimizing ‖θ? − θ̂aug‖2 = ∑ j ξ 2 j that also satisfies equation (13) is an appropriately scaled vector in the direction of x = W>ΣV ζ where we define W := [w1, ... ,w|rest|] and V :=[v1,...,v|ext|]. Defining c0 =ζ>V >ΣV ζ for convenience and then setting
ξ=− c0+c 2‖x‖22 x (14)
which is well-defined since x 6= 0, yields a θ? such that augmentation hurts. It is thus necessary for B(θ̂aug)−B(θ̂std)=c that∑
j
ξ2j = (c0+c)
2 4‖W>ΣV ζ‖2 = (ζ>V >ΣV ζ+c)2 4ζ>V >ΣWW>ΣV ζ
≥ (ζ >V >ΣV ζ)2
4ζ>V >ΣWW>ΣV ζ +
c2
4ζ>V >ΣWW>ΣV ζ
≥ c1 4
λ2min(V >ΣV )
λ2max(W >ΣV )
+ c2
4c1λ2max(W >ΣV )
.
By assuming existence of i,j such that ξjζiw>j Σvi 6=0, we are guaranteed that λ2max(W>ΣV )>0.
Note due to construction we have ‖θ?‖22 = ‖θ̂std‖22 + ∑ iζ 2 i + ∑ jξ 2 j and plugging in the choice of ξj in equation (14) we have
‖θ?‖22−‖θ̂std‖22≥c1 [ 1+ λ2min(V >ΣV )
4λ2max(W >ΣV )
] +
c2
4λ2max(W >ΣV )
1 c1 .
Setting β1 = [ 1+ λ2min(V >ΣV )
4λ2max(W >ΣV ) ] , β2 = 14λ2max(W>ΣV ) yields the result.

heading: B.3.2 PROOF OF LEMMA 1
text: Let λ1,...,λm be the m non-zero eigenvalues of Σ and ui be the corresponding eigenvectors. Then choose v to be any combination of the eigenvectors v=UβwhereU=[u1,...,um] where at leastβi,βj 6=
0 for λi 6=λj . We next constructw=Uα by choosingα as follows such that the inequality in (11) holds:
αi= βj
β2i +β 2 j
αj= −βi
β2i +β 2 j
and αk=0 for k 6= i,j. Then we have that α>β=0 and hencew>v=0. Simultaneously w>Σv=λiβiαi+λjβjαj
=(λi−λj) βiβj β2i +β 2 j 6=0
which concludes the proof of the first statement.
We now prove the second statement by constructing Σstd = X>stdXstd,Σext = X > extXext using w,v. We can then obtain Xstd,Xext using any standard decomposition method to obtain Xstd,Xext. We construct Σstd,Σext using w, v. 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,v. Then if we set the corresponding eigenvalues λw(Σext) = 0,λv(Σext)> 0 and λw(Σstd) = 0,λv(Σstd) = 0, then λw(Σaug) = 0 such that w∈Col(Π⊥stdΠ⊥aug) and v∈Col(Π⊥stdΠaug). This shows the second statement. With this, we can design a θ? for which augmentation hurts as in Lemma 2.

heading: B.4 CHARACTERIZATION COROLLARY 1
text: A 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. Corollary 1. The following characterizations hold for augmentation directions that do not cause the bias of the augmented estimator to be higher than the original estimator.
(a) (in terms of ratios of inner products) For a given θ?, data augmentation does not increase the bias of the augmented estimator for a single augmentation direction xext if
x>extΠ ⊥ stdΣΠ ⊥ stdxext
x>extΠ ⊥ stdxext
−2(Π ⊥ stdxext) >ΣΠ⊥stdθ ?
x>extΠ ⊥ stdθ
? ≤0 (15)
(b) (in terms of eigenvectors) Data augmentation does not increase bias for any θ? if Π⊥stdxext is an eigenvector of Σ. However if one augments in the direction of a mixture of eigenvectors of Σ with different eigenvalues, there exists θ? such that augmentation hurts.
(c) (depending on well-conditioning of Σ) If λmax(Σ)λmin(Σ) ≤2 and Π ⊥ stdθ ? is an eigenvector of Σ, then no augmentations xext increase bias.
The form in Equation (15) compares ratios of inner products of Π⊥stdxext and Π ⊥ stdθ ? in two spaces: the one in the numerator is weighted by Σ whereas the denominator is the standard inner product. Thus, if Σ scales and rotates rather inhomogeneously, then augmenting with xext may hurt bias. Here again, if Σ=γI for γ>0, then the condition must hold.

heading: B.4.1 PROOF OF COROLLARY 1 (A)
text: Note that for a single augmentation point Xext = x>ext, the orthogonal decomposition of Π ⊥ stdθ ? into Col(Π⊥aug) and Col(Π ⊥ stdΠaug) is defined by v = Π⊥stdxext > θ?
‖Π⊥stdxext‖2 Π⊥stdxext and w = Π ⊥ stdθ ?− v respectively. Plugging back into into identity (9) then yields the following condition for safe augmentations:
2(v−Π⊥stdθ?)>Σv−v>Σv≤0 (16) v>Σv−2(Π⊥stdθ?)>Σv≤0
⇐⇒Π⊥stdxext > ΣΠ⊥stdxext≤2(Π⊥stdθ?)>ΣΠ⊥stdxext · ‖Π⊥stdxext‖2
Π⊥stdxext > θ?
Rearranging the terms yields inequality (15).
Safe augmentation directions for specific choices of θ? and Σ are illustrated in Figure 2.

heading: B.4.2 PROOF OF COROLLARY 1 (B)
text: Assume that Π⊥stdxext is an eigevector of Σ with eigenvalue λ>0. We have
x>extΠ ⊥ stdΣΠ ⊥ stdxext
x>extΠ ⊥ stdxext
−2(Π ⊥ stdxext) >ΣΠ⊥stdθ ?
x>extΠ ⊥ stdθ
? =−λ<0
for any θ?. Hence by Corollary 1 (a), the bias doesn’t increase by augmenting with eigenvectors of Σ for any θ?.
When the single augmentation direction v is not an eigenvector of Σ, by Lemma 1 one can findw such that w>Σv 6= 0. The proof in Lemma 1 gives an explicit construction for w such that condition (11) holds and the result then follows directly by Lemma 2.

heading: B.4.3 PROOF OF COROLLARY 1 (C)
text: Suppose ΣΠ⊥stdθ ?=λΠ⊥stdθ ? for some λmin(Σ)≤λ≤λmax(Σ). Then starting with the expression (15), x>extΠ ⊥ stdΣΠ ⊥ stdxext
x>extΠ ⊥ stdxext
−2(Π ⊥ stdxext) >ΣΠ⊥stdθ ?
x>extΠ ⊥ stdθ
? = x>extΠ ⊥ stdΣΠ ⊥ stdxext
x>extΠ ⊥ stdxext
−2λ
≤λmax(Σ)−2λ<0 by applying λmax(Σ)λmin(Σ) ≤2. Thus when Π ⊥ stdθ
? is an eigenvector of Σ, there are no augmentations xext 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 θ̂std and data augmented estimator θ̂aug. The following theorem provides a general characterization of the relation between variance of the standard estimator and variance of the augmented estimator. Theorem 2 is a corollary of this general result that we present first. Theorem 4 (Variance). The difference in the variances of a standard and augmented estimator can be expressed as follows:
1
σ2 (V (θ̂aug)−V (θ̂std))=tr
( ΣX†ext(X † ext) >)︸ ︷︷ ︸
T1: Variance increase
−tr ( ΣΣ†stdX > ext(I+XextΣ † stdX > ext) −1XextΣ † std )︸ ︷︷ ︸ T2: Variance reduction , (17)
whereXext def = Π⊥stdXext, is the component ofXext in the null space of Σstd.
Proof. Recall from (3) that the V (θ̂)=tr(Cov(θ̂ |XstdXext)Σ). For the minimum norm interpolation estimators θ̂std and θ̂aug in Equation 2, we have the following expressions for the variances of the estimators.
V (θ̂std)=σ 2tr ( Σ†stdΣ ) ,
V (θ̂aug)=σ 2tr ( Σ†augΣ ) ,
where Σstd =X>stdXstd and Σaug =X > stdXstd+X > extXext. Note that since Σstd,Σaug are unnormalized, the quantities Σ†std and Σ † aug decay with nwith the variances V (θ̂std),V (θ̂aug) also decay with n as expected. In order to compare V (θ̂std) and V (θ̂aug), we need to compare Σ † std and Σ † aug. Iorder to do this, we leverage the result from Kovanic (1979) on the pseudo-inverse of the sum of two symmetric matrices:
(Σstd+X > extXext) †=Σ†std−Σ†stdX>ext(I+XextΣ†stdX>ext)−1XextΣ†std+X†ext(X†ext)>, where recall that Xext is the component of Xext in the null space of Σstd. Multiplying each term by Σ and using linearity of trace, we get the required expression.
Proof of Theorem 2. Theorem 2 follows directly from the general result above (Theorem 4). Note that the terms T1 and T2 are traces of PSD matrices and hence non-negative, and capture the magnitude of variance increase and variance reduction respectively. From Theorem 4, we see that (i) ifXext is entirely in the span of Σstd makingXext =0, T1 =0 making V (θ̂aug)≤V (θ̂std) (ii) On the other extreme, ifXext is entirely in the null space with Σ † stdXext =0, T2 =0 and hence V (θ̂aug)≥V (θ̂std).

heading: D DETAILS FOR SPLINE STAIRCASE
text: We describe the data distribution, augmentations, and model details for the spline experiment in Figure 4 and toy scenario in Figure 1. Finally, we show that we can construct a simplified family of spline problems where the ratio between test errors of the augmented and standard estimators increases unboundedly as the number of stairs.

heading: D.1 TRUE MODEL
text: We consider a finite input domain
T ={0, ,1,1+ ,...,s−1,s−1+ } (18) for some integer s corresponding to the total number of “stairs” in the staircase problem. Let Tline⊂T ={0,1,...,s−1}. We define the underlying function f? :R 7→R as f?(t)=btc. This function takes a staircase shape, and is linear when restricted to Tline. Sampling training dataXstd We describe the data distribution in terms of the one-dimensional input t, and by the one-to-one correspondence with spline basis features x=X(t), this also defines the distribution of spline features x∈X . Letw∈∆s define a distribution over Tline where ∆s is the probability simplex of dimension s. We define the data distribution with the following generative process for one sample t. First, sample a point i from Tline according to the categorical distribution described by w, such that i∼Categorical(w). Second, sample t by perturbing iwith probability δ such that
t= { i w.p. 1−δ i+ w.p. δ.
The sampled t is inTline with probability 1−δ andT cline with probability δ, where we choose δ to be small. Sampling augmented points Xext For each element ti in the training set, we augment with T̃i=[u
u.a.r∼ B(ti)], an input chosen uniformly at random fromB(ti)={btic,btic+ }. Recall that in our work, we consider data augmentation where the targets associated with the augmented points are from the ground truth oracle. Notice that by definition, f?(t̃i) = f?(ti) for all t̃∈B(ti), and thus we can set the augmented targets to be ỹi=yi. This is similar to random data augmentation in images (Yaeger et al., 1996; Krizhevsky et al., 2012), where inputs are perturbed in a way that preserves the label.

heading: D.2 SPLINE MODEL
text: We parameterize the spline predictors as fθ(t) = θ>X(t) where X : R→Rd is the cubic B-spline feature mapping (Friedman et al., 2001) and the norm of fθ(t) can be expressed as θ>Mθ for a matrix M that penalizes a large second derivative norm where [M ]ij = ∫ X ′′ i (u)X ′′
j (u)u. . Notice that the splines problem is a linear regression problem from Rd to R in the feature domain X(t), allowing direct application of Theorem 1. As a linear regression problem, we define the finite domain as X ={X(t) : t∈T } containing 2s elements in Rd. There is a one-to-one correspondence between t and X(t), such thatX−1 is well-defined. We define the features that correspond to inputs in Tline asXline = {x :X−1(x)∈Tline}. Using this feature mapping, there exists a θ? such that fθ?(t)=f?(t) for t∈T . 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 [0, ,1,...,s−1,s−1+ ], which places a knot on every point in T . This ensures that the function class contains an interpolating function on all t∈T , i.e. for some θ?,
fθ?(t)=θ ?>X(t)=f?(t)=btc.
We solve the minimum norm problem
θ̂std =argmin θ {θ>Mθ :Xstdθ=ystd} (19)
for the standard estimator and the corresponding augmented problem to obtain the augmented estimator.

heading: D.3 EVALUATING COROLLARY 1 (A) FOR SPLINES
text: We now illustrate the characterization for the effect of augmentation with different single points in Theorem 1 (a) on the splines problem. We assume the domain to T as defined in equation 18 with s=10 and our training data to beXstd ={X(t) : t∈{0,1,2,3,4}}. Let local perturbations be spline features for t̃ /∈Tline where t̃= t+ is away from some t∈ {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 5 shows that augmenting with an additional point from {X(t) : t∈Tline} does not affect the bias, but adding any perturbation point in {X(t̃) : t̃∈{2.5,3.5,4.5}} where t̃ /∈ Tline 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.

heading: D.3.1 LOCAL AND GLOBAL STRUCTURE IN THE SPLINE STAIRCASE
text: 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 to minimum `2 norm linear interpolation using features XM (t) =X(t)M
−1/2 so that the results from Section 4.1.2 apply directly. Let Σ be the population covariance of XM for a uniform distribution over the discrete domain consisting of s stairs and their perturbations (Figure 1). Let Q= [qi]2si=1 be the eigenvectors of Σ in decreasing order of their corresponding eigenvalues. The visualization in Figure 3 shows that qi are wave functions in the original input space; the “frequency” of the wave increases as i increases.
Suppose the original training set consists of two points,Xstd =[XM (0),XM (1)]>. We study the effect of augmenting pointxext in terms of qi above. First, we find that the first two eigenvectors corresponding to linear functions satisfy Π⊥stdq1 =Π ⊥ stdq2 =0. Intuitively, this is because the standard estimator is linear. For ease of visualization, we consider the 2D space in Null(Σ) spanned by Π⊥stdq3 (global direction, low frequency) and Π⊥stdq2s (local direction, high frequency). The matrix Πlg = [Π ⊥ stdq3, Π ⊥ stdq2s] > projects onto this space. Note that the same results hold when projecting onto all Π⊥stdqi in Null(Σ).
In terms of the simple 3-D example in Section 4.1.1, the global direction corresponds to the costly direction with large eigenvalue, as changes in global structure heavily affect the predictive test error. Figure 6 plots the projections Πlgθ? and ΠlgXext for different Xext. When θ? has high frequency variations and is complex, Πlgθ?=(θ?−θ̂std) is aligned with the local dimension. For xext immediately local to training points, the projection Πlgxext (orange vector in Figure 6) has both local and global components. Augmenting these local perturbations introduces error in the global component. For other xext farther from training points, Πlgxext (blue vector in Figure 6) is almost entirely global and perpendicular to θ?− θ̂std, 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 Figure 1(middle). The choice of inductive bias in theM–norm being minimized results in eigenvectors of Σ that correspond to local and global components, dictating this tradeoff.

heading: D.4 DATA AUGMENTATION CAN BE QUITE PAINFUL FOR SPLINES
text: We construct a 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.

heading: Sampling distribution
text: We define a modified domain with continuous intervals T =∪s−1t=0 [t,t+ ]. Considering only swhich is a multiple of 2, we sample the original data set as described in Section D.1 with the following probability massw:
w(t)= { 1−γ s/2 t<s/2,t∈Tline γ s/2 t≥s/2,t∈Tline.
(20)
for γ ∈ [0,1). We define a probability distribution PT on T for a random variable T by setting T =Z+S(Z) whereZ∼Categorical(w) and theZ-dependent perturbation S(z) is defined as
S(z)∼ {
Uniform([z,z+ ]) w.p. δ z, w.p. 1−δ. (21)
We obtain the training datasetXstd ={X(t1),...,X(tn)} by sampling ti∼PT .

heading: Augmenting with an interval
text: Consider a modified augmented estimator for the splines problem, where for each point ti we augment with the entire interval [btic,btic+ ] with ∈ [0,1/2) and the estimator is enforced to output fθ̂(x)=yi=btic for all x in the interval [btic,btic+ ]. Additionally, suppose that the ratio s/n=O(1) between the number of stairs s and the number of samples n 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.
Theorem 5. Let the setting be defined as above. Then with the choice of δ= log(s 7)−log(s7−1)
s and γ=c/s for a constant c∈ [0,1), the ratio between test errors is lower bounded as
R(θ̂aug) R(θ̂std) =Ω(s2) (22)
which goes to infinity as s→∞. Furthermore,R(θ̂std)→0 as s→∞.
Proof. We first lower bound the test error of the augmented estimator. DefineE1 as the event that only the lower half of the stairs is sampled, i.e. {t : t<s/2}, which occurs with probability (1−γ)n. Let t?=maxibtic be the largest “stair” value seen in the training set. Note that the min-norm augmented estimator will extrapolate with zero derivative for t ≥ maxibtic. This is because on the interval [t?,t?+ ], 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 t≥ t?. In the event E1, t?≤ s/2−1, where t∗= s/2−1 achieves the lowest error in this event. As a result, on the points in the second half of the staircase, i.e. t={t∈T : t> s2−1}, the augmented estimator incurs large error:
R(θ̂aug |E1)≥ s∑
t=s/2
(t−(s/2−1))2 · γ s/2
= s/2∑ t=1 t2 · γ s/2 = γ 6 (s2+2s+1).
Therefore the expected risk of the augmented estimator is bounded by
R(θ̂aug)≥R(θ̂aug |E1)P (E1)= γ
6 (s2+2s+1)(1−γ)n
≥ 1 6 γ(1−γn)(s2+2s+1) =Ω( c−c2 s (s2+2s+1))=Ω(s)
where in the first line, we note that the error on each interval is the same and the probability of each interval is (1−δ) γs/2 + δ · γ s/2 = γ s/2 .
Next we upper bound the test error of the standard estimator. DefineE2 to be the event where all points are sampled from Tline, which occurs with probability (1−δ)n. In this case, the standard estimator is linear and fits the points on Tline with zero error, while incurring error for all points not in Tline. Note that the probability density of sampling a point not in Tline is either δ · 1−γ s/2 or δ · γ s/2 , which we upper bound as δ · 1s/2 .
R(θ̂std |E2)= s−1∑ t=1 δ · 1 s/2 ∫ 0 u2du= δ · 1 s/2 O(s 3)
=O(δ)
Therefore for eventE2, the expected error is bounded as
R(θ̂std |E2)P (E2)=O(δ)(1−δ)n
=O(δ)e−δn
=O(δ · s 7−1 s7 ) =O(δ)=O( log(s7)−log(s7−1)
s )=O(1/s)
since log(s7)−log(s7−1)≤1 for s≥2. For the complementary eventEc2, note that cubic spline predictors can grow only asO(t3), with errorO(t6). Therefore the expected error for caseEc2 is bounded as
R(θ̂std |Ec2)P (Ec2)≤O(t6)(1−e−δn)
=O(t6)O( 1
s7 )=O(1/s)
Putting the parts together yields
R(θ̂std)=R(θ̂std |E2)P (E2)+R(θ̂std |Ec2)P (Ec2) ≤O(1/s)+O(1/s)=O(1/s).
Thus overall,R(θ̂std)=O(1/s) and combining the bounds yields the result.

heading: E EFFECT OF SAMPLE SIZE ON ERROR INCREASE VIA AUGMENTATION
text: In this section, we discuss what our analysis of the effect of augmentation on the error of mininum interpolants says about the trends with respect to varying sample sizes of the standard training set (Xstd,ystd).
Trends in variance. We refer the reader to the precise expression for the difference in variance provided in Theorem 4. Let us consider a case where data augmentation causes an increase in variance. For simplicity,Xext⊥Xstd, across all sample sizes in the small sample regime. For a fixedXext, we see that the magnitude of variance increase is governed by Π⊥stdXext which decreases as we get more standard training points.
Trends in bias. Recall the expressions for B(θ̂std) and B(θ̂aug) from Equation 4. Using the same notation as that of Theorem 5, we have the following expression for the amount of bias increase. Let v=Π⊥stdΠaugθ ? and v=Π⊥augθ ?. We have,
B(θ̂aug)−B(θ̂std)=−v>Σv−2w>Σv, (23)
where w>Σv is a negative quantity when data augmentation causes an increase in bias. Recall that we are in the small sample regime where Σstd is not invertible for a range of sample sizes. Suppose we augment withXext such thatXext∈Null(Σstd) in this regime of interest. In this case, we can write v = Π⊥stdΠ ⊥ augθ
? = u>θ?. For a fixed problem setting θ?, we see that v is fixed. Let us now look at w=Π⊥augθ ?. Recall that Π⊥aug is the projection matrix onto Σstd+X > extXext. For a fixedXext, as the null space of Σstd shrinks with more training points,w decreases. Note that the magnitude of increase in bias decreases as w decreases (for a fixed v). This suggests that the effect of augmentation on bias should decrease as we get more samples, in the small data regime.
Our heuristic calculations in some settings ofXext in minimum norm interpolation in 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-REGULARIZATION FOR LINEAR REGRESSION
In this section, we prove Theorem 3, which we reproduce here.
Theorem 3. Assume the noiseless linear model y=x>θ?. Let θint-std be an arbitrary interpolant of the standard data, i.e.Xstdθint-std =ystd. Let θ̂x-aug be the X-regularized interpolant (6). Then
R ( θ̂x-aug)≤R(θint-std).
Proof. Let {ui} be an orthonormal basis of the kernel Null(Σstd + X>extXext) and {vi} be an orthonormal basis for Null(Σstd) \ span({ui}). Let U and V be the linear operators defined by Uw= ∑ iuiwi and V w= ∑ iviwi, respectively, noting thatU
>V =0. Defining Π⊥std :=(I−Σ†stdΣstd) to be the projection onto the null space ofXstd, we see that there are unique vectors ρ,α such that
θ?=(I−Π⊥std)θ?+Uρ+V α. (24a) As θint-std interpolates the standard data, we also have
θint-std =(I−Π⊥std)θ?+Uw+V z, (24b)
asXstdUw=XstdV z=0, and finally, θ̂x-aug =(I−Π⊥std)θ?+Uρ+V λ (24c) where we note the common ρ 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 θint-std−θ̂x-aug =U(w−ρ)+V (z−λ), we immediately have that the estimator has the form (24c), with the choice
λ=argmin λ
{ (U(w−ρ)+V (z−λ))>Σ(U(w−ρ)+V (z−λ)) } .
The optimality conditions for this quadratic imply that V >ΣV (λ−z)=V >ΣU(w−ρ). (25)
Now, recall that the predictive test error of a vector θ isR(θ)=(θ−θ?)>Σ(θ−θ?)=‖θ−θ?‖2Σ, using Mahalanobis norm notation. In particular, a few quadratic expansions yield
R(θint-std)−R(θ̂x-aug) =‖U(w−ρ)+V (z−α)‖2Σ−‖V (λ−α)‖ 2 Σ =‖U(w−ρ)+V z‖2Σ+‖V α‖ 2 Σ−2(U(w−ρ)+V z)>ΣV α−‖V λ‖ 2 Σ−‖V α‖ 2 Σ+2(V λ) >ΣV α
(i) = ‖U(w−ρ)+V z‖2Σ−2(V λ)>ΣV α−‖V λ‖ 2 Σ+2(V λ) >V α =‖U(w−ρ)+V z‖2Σ−‖V λ‖ 2 Σ, (26) where step (i) used that (U(w−ρ))>ΣV =(V (λ−z))>ΣV from the optimality conditions (25). Finally, we consider the rightmost term in equality (26). Again using the optimality conditions (25), we have ‖V λ‖2Σ =λ>V >Σ1/2Σ1/2(U(w−ρ)+V z)≤‖V λ‖Σ‖U(w−ρ)+V z‖Σ by Cauchy-Schwarz. Revisiting equality (26), we obtain
R(θint-std)−R(θ̂x-aug)=‖U(w−ρ)+V z‖2Σ− ‖V λ‖4Σ ‖V λ‖2Σ
≥‖U(w−ρ)+V z‖2Σ− ‖V λ‖2Σ‖U(w−ρ)+V z‖ 2 Σ
‖V λ‖2Σ =0,
as desired.
F.2 X-REGULARIZATION FOR DATA AUGMENTATIONS THAT PROMOTE ROBUSTNESS
The main motivation of our work is to provide a 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-regularization to two forms of adversarial training: Projected Gradient Adversarial Training of (Madry et al., 2018) and TRADES (Zhang et al., 2019). Throughout, we assume the same notation as that used in the definition of the general estimator. Xstd,ystd denote the standard training set and we have access tom unlabeled points x̃i,i=1,...m.

heading: F.2.1 PROJECTED GRADIENT ADVERSARIAL TRAINING
text: Note that the unlabeled data can be perturbed to 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 we obtain adversarial perturbations from the unlabeled data, and label them with the pseudo-label generated from the standard trained model. As the distance measure, we use the same loss that is used for classification. Put together, we have
θ̂x-aug :=argmin θ
{ N−1 ∑ (x,y)∈[Xstd,ystd] `(fθ(x),y)+β `(fθ(xadv),y)
+λm−1 m∑ i=1 `(fθ(x̃i),fθ̂std(x̃i))+β `(fθ(x̃advi),fθ̂std(x̃i)) } , (27)
In practice, xadv is found by performing a few steps of projected gradient method on `(fθ(x),y), and similarly x̃adv by performing a few steps of projected gradient method on `(fθ(x̃),fθ̂std(x̃)).

heading: F.2.2 TRADES
text: TRADES was a 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 of as probabilities of different labels. Using their modified loss and applying X-regularization leads to the following.
θ̂x-aug :=argmin θ
{ N−1 ∑ (x,y)∈[Xstd,ystd] `(fθ(x),y)+β KL(pθ(xadv)||pθ(x))
+λm−1 m∑ i=1 `(fθ(x̃i),fθ̂std(x̃i))+β KL(pθ(x̃advi)||pθ̂std(x̃i)) } , (28)
where KL(pθ(x),pθ(xadv) is the KL divergence between the probability over class labels assigned to x and xadv.

heading: G EXPERIMENTAL DETAILS

heading: G.1 SPLINE SIMULATIONS
text: For spline simulations in Figure 1 and Figure 4, we implement the optimization of the standard and robust objectives using the basis described in (Friedman et al., 2001). The penalty matrixM computes second-order finite differences of the parameters θ. We solve the min-norm objective directly using CVXPY (Diamond & Boyd, 2016). Each point in Figure 4(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, it is natural to instantiate X-regularization as robust self-training, as discussed in Section F. We evaluate the performance of X-regularization applied to `∞ adversarial perturbations, adversarial rotations, and random rotations.

heading: G.2.1 SUBSAMPLING CIFAR-10
text: We augment with `∞ adversarial perturbations of various sizes. In each epoch, we find the augmented examples 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 in (Carmon et al., 2019).
We use Wide ResNet 40-2 models (Zagoruyko & Komodakis, 2016) while varying the number of samples in CIFAR-10. We sub-sample CIFAR-10 by factors of {1,2,5,8,10,20,40} in Figure 4(a) and {1,2,5,8,10} in Figure 4(b). For sub-sample factors 1 to 20, we report results averaged from 2 trials for each model. For sub-sample factors greater than 20, we average over 5 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.
We evaluate the robustness of models to the strong PGD-attack with 40 steps and 5 restarts. In Figure 4(b), we used a simple heuristic to set the regularization strength λ in Equation (27) to be λ= min(0.9,γ)/(1−min(0.9,γ)) where γ ∈ [0,1] is the fraction of the original CIFAR-10 dataset
sampled. Intuitively, we give more weight to the unlabeled data when the original dataset is larger, meaning that the standard estimator produces more accurate pseudo-labels. We fix β=5.
Figure 7 shows that the robust accuracy of the 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 (Tables 2,3).
Note that we cannot directly compare the empirical performance of RST+adversarial training on CIFAR-10 with other methods to obtain robust models that are modifications of vanilla adversarial training. We use a smaller model due to computational constraints enforced by adversarial training. Since the model is small, we could only fit adversarially augmented examples with small =2/255, while existing baselines use =8/255. Note that even for =2/255, adversarial data augmentation leads to an increase in error. We show that RST can fix this. While ensuring models are robust is an important goal in itself, in this work, we 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.

heading: G.2.2 `∞ ADVERSARIAL PERTURBATIONS
text: In Table 1, we evaluate X-regularization as robust self-training applied to PGD and TRADES adversarial training. The models are trained on the full CIFAR-10 dataset, and models which use
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 WideResNet 28-10. To evaluate robust accuracy, we use a strong PGD-attack with 40 steps and 5 restarts against `∞ perturbations of size 8/255. For X-regularization models, we set λ=9 and β=5 in Equation (27) and Equation (28), following the heuristic λ=min(0.9,γ)/(1−min(0.9,γ)) for γ=1. We train for 200 epochs such that 100% training standard accuracy is attained.

heading: G.2.3 ADVERSARIAL AND RANDOM ROTATION/TRANSLATIONS
text: In Table 1 (right), we instantiate X-regularization as robust self-training for adversarial and random rotation/translations, using these transformations as xadv 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 31 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 1 random transformation as the augmented input. All models (besides cited models) use the WRN-40-2 architecture and are trained for 200 epochs. We use the same hyperparametersλ,β as in G.2.2 for Equation (27).

heading: H COMPARISON TO STANDARD SELF-TRAINING ALGORITHMS
text: The main objective of X-regularization is to allow to perform data augmentation without sacrificing standard accuracy. This is done by smoothing an augmented estimator to provide labels close to a standard non-augmented estimator on the unlabeled data. This is closely related to but different two broad kinds of semi-supervised learning.
1. Self-training (pseudo-labeling): Classical self-training does not deal with data augmentation or robustness. We view X-regularization as a a generalization of self-training in the context of data augmentations. Here the pseudolabels are generated by a standard non-augmented 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 a 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., 2016; Laine & Aila, 2017)). X-regularization is similar in spirit, but has an additional crucial component. We generate pseudo-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 pseudo-labels generated.

Review summaries:
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.

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.