Title: WHEN COVARIATE-SHIFTED DATA AUGMENTATION INCREASES TEST ERROR AND HOW TO FIX IT Anonymous

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.

1. INTRODUCTION:

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.

2. RELATED WORK:

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.

3. SETUP:

3.1 COVARIATE-SHIFTED DATA AUGMENTATION.

Let P xy denote the underlying distribution of (x,y) pairs, P x its marginal on R d , and P y (• | x) the conditional distribution of the targets given inputs.

We (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, let B(x) be the set of perturbations of x that we would like to be robust against. We assume that the label is constant over B(x). The transformation at step t of the training for data point

x i is T t (x i ) = argmax x∈B(xi) ( θt ,x i ,y i ),

where θt are the model parameters at time step t.

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 ∈ R are drawn from the conditional distribution P y (• | x) = N (x θ , σ), for some vector θ ∈ R d . 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 ∈ R n×d and corresponding targets Y ∈ R n as training data, we define the following minimum norm interpolation estimator as

EQUATION

In particular , we compare the following estimators : 

4. BIAS AND VARIANCE OF MINIMUM NORM INTERPOLANTS:

We evaluate the two estimators described in Equation 2 using the error on a random sample x test drawn from P x . Let Σ be the covariance of P x . We focus on the error conditioned on X std ,X ext , which decomposes into a bias and variance term as follows

EQUATION

where the expectation is taken over the randomness in x test and targets y std , y ext conditioned on X std ,X ext . In this section, we treat X std ,X ext as fixed quantities. However, since X std consists of samples from P x , the number of samples dictates some structure on X std . 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 OF MINIMUM NORM INTERPOLANTS:

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 std X std and Σ aug = X std X std + X ext X ext . Let Π ⊥ std = I -Σ † std Σ std and Π ⊥ aug = I -Σ †

aug Σ aug be the projection matrices onto Null(Σ std ) and Null(Σ aug ) respectively. Then,

EQUATION

Remark 1. Note that the bias in parameter error is

E[ θ] -θ 2 2 = Π ⊥ X θ 2 2 . Since Null(Σ aug ) ⊆ Null(Σ std ), we have Π ⊥ aug θ 2 2 ≤ Π ⊥ std θ 2 2

, and data augmentation always reduces the bias in parameter error. However, the bias in test error upon augmentation B( θaug ) could be larger or smaller than B( θstd ).

4.1.1. SIMPLE LINEAR PROBLEM IN R 3 WHERE ADDING DATA INCREASES BIAS:

The following example illustrates how the interaction between the column spaces of standard inputs X std , extra inputs X ext and the underlying true parameter θ could cause data augmentation to increase bias.

For simplicity, we choose Σ = diag([λ 1 , λ 2 , λ 3 ]) with λ 2 λ 1 , X std = e 3 and additional data X ext = e 1 + e 2 where e 1 ,e 2 ,e 3 denote the standard bases in R 3 . 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 Bias under different settings of θ . Plugging these terms into the bias expression in Equation (4) yields

-θ ) ∈ Null(Σ std ) = R 2 and ( θaug -θ ) ∈ Null(Σ aug ) = {ρ(e 1 -e 2 ) : ρ ∈ R}.

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 e 2 (red lines in Figure 2 ). Depending on θ , B( θaug ) could be larger or smaller than B( θstd ). In particular, (i) when θ 1 θ 2 as in Fig. 2 (a), augmenting with X ext 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 e 2 dominates the effect on the bias because λ 2 λ 1 .

(ii) when θ 2 θ 1 as in Fig. 2 (b), the same X ext causes B( θaug ) to be smaller than B( θstd ). Here the augmented estimator has smaller parameter error along e 2 and hence decreasing bias despite an increase along e 1 . 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.

4.1.2. GENERAL CHARACTERIZATIONS:

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 std X std and Σ aug = X std X std +X ext X ext . 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

EQUATION

where v = Π ⊥ std Π aug θ and w = Π ⊥ 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. When X ext 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 X ext is rank-one, data augmentation is safe for all θ if and only if Π ⊥ std X ext is an eigenvector of Σ. See Appendix B.4 for a proof.

Finally, we illustrate the safe augmentation directions X ext 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.

4.2. VARIANCE OF MINIMUM NORM INTERPOLANTS:

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 X std ,y std be the standard training data, with extra points X ext ,y ext and let Π ⊥ std denote the projection matrix onto Null(X std X std ). Theorem 2. For the minimum norm interpolants defined in Equation 2, the following hold.

1.. When Π ⊥:

std X ext = 0 such that the extra points lie in the column space of original standard training data, V ( θaug ) ≤ V ( θstd ).

2. When X ext ⊥ X std , such that the extra points lie entirely in Null(X std X std ), we have

V ( θaug ) ≥ V ( θstd ).

In general, when X ext ∈ Null(X std X std ), 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.

5. EFFECT OF SIZE OF THE ORIGINAL TRAINING SET:

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.

5.1. MINIMUM NORM INTERPOLATION-SMALL AND LARGE DATA REGIMES.:

Without loss of generality, we assume that Σ, the population covariance of P x 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 std X std ≈ 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 Figure 4 : 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 ∞ perturbations via adversarial training (AT) on CIFAR-10, we find that as we increase the number of samples, the increase in test error 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 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 Π ⊥ std X ext decreases (See Appendix E) for details). This suggests that as the size of X std 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).

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, 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.

6. MITIGATING THE INCREASE IN BIAS UPON AUGMENTATION:

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.

6.1. X-REGULARIZATION FOR LINEAR REGRESSION:

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 X std θ int-std = y std . We use θ int-std to construct a new data augmented estimator θx-aug that interpolates both the standard data and augmented extra data while satisfying R( θx-aug ) ≤ R(θ int-std ).

Given Σ and an initial interpolant θ int-std , we propose the X-regularized data augmentation estimator

EQUATION

)

The X-regularized estimator θx-aug optimizes for small error on the labeled data (X std , y std ) and (X ext ,y ext ) while keeping the predictions of θx-aug close to those of θ int-std over unlabeled inputs drawn from P x . 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 X ext , 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 fit X ext 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. X std θ int-std = y std . 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 where X ext 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 via X ext .

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.

6.2. ROBUST SELF-TRAINING AS X-REGULARIZATION FOR 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 a more general form:

(θ-θ int-std ) Σ(θ-θ int-std ) = E Px [(x θ-x θ int-std ) 2 ] = E Px [ 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 constitute X ext . Generalizing the linear regression estimator of Equation 6 to use arbitrary losses and transformation (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 ( ∞ and rotation/translations).

based augmentations, we get,

EQUATION

)

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.

6.3. EMPIRICAL EVALUATION OF X-REGULARIZATION AS RST:

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-28-10 model with the entire labeled CIFAR-10 training set and 500K unlabeled images. 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.

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 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:

EQUATION

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/2 x and rotated parameters θ ← M 1/2 θ maintain Y = Xθ+σN (0,I) and the M -norm of parameters simplifies to θ 2 .

B BIAS OF MINIMUM NORM INTERPOLANTS:

B.1 PROOF OF THEOREM 1 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 θ and w = Π ⊥ std Π ⊥ aug θ . We also want to note that the bias difference does scale with θ 2 .

B.2 BIAS INCREASE REQUIRES COMPLEX TRUE ESTIMATORS:

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 given X std ,X ext ,Σ, a bias increase of B( θaug )-B( θstd ) = c > 0 via augmentation with X ext is possible only if θ is sufficiently more complex than θstd in the 2 norm, i.e.

θ 2 2 -θstd 2 2 > γc (10)

for some scalar γ > 0 that depends on X std ,X ext ,Σ.

B.2.1 PROOF OF INEQUALITY (10):

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 vectors w,v for which the following holds

w v = 0 and w Σv = 0 (11)

Hence, there exists a combination of original and augmentation dataset X std , X ext such that condition (11

) holds for two directions v ∈ Col(Π ⊥ std Π aug ) and w ∈ 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 Σ, X std , X ext are fixed. Then condition (11) holds for two directions v ∈ Col(Π ⊥ std Π aug ) and w ∈ Col(Π ⊥ std Π ⊥ aug ) iff there exists a θ such that B( θaug )-B( θstd ) ≥ c for some c > 0. Furthermore, the 2 norm of θ needs to satisfy the following lower bounds with c

EQUATION

)

where β i are constants that depend on X std ,X ext ,Σ.

Inequality (10) follows directly from the second statement of Lemma 2 by minimizing the bound (12) with respect to c 1 which is a free parameter to be chosen during construction of θ (see proof of Lemma (2). The minimum is attained for c 1 = 2 (β 1 +1)(β 2 c 2 ). We hence conclude that θ needs to be sufficiently more complex than a good standard solution, i.e. θ 2 2 -θstd 2 2 > γc where γ > 0 is a constant that depends on the X std ,X ext .

B.3 PROOF OF TECHNICAL LEMMAS:

In this section we prove the technical lemmas that are used to prove Theorem 1.

B.3.1 PROOF OF LEMMA 2:

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 ζ i v i θ = θaug + wj ∈rest ξ j w j ,

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 ζ i v i ) Σ( vi∈ext ζ i v i )+c = -2( wj ∈rest ξ j w j )Σ( vi∈ext ζ i v i ) ⇐⇒ ( vi∈ext ζ i v i ) Σ( vi∈ext ζ i v i )+c = -2 wj ∈rest,vi∈ext ξ j ζ i w j Σv i (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 Σv i = 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 the w Σ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 ζ i w j Σv i > 0 for at least some i,j. We can then set ζ i > 0 such that θaugθstd 2 = ζ 2 = c 1 > 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 := [w 1 , ... , w |rest| ] and

EQUATION

which is well-defined since x = 0, yields a θ such that augmentation hurts. It is thus necessary for

B( θaug )-B( θstd ) = c that j ξ 2 j = (c 0 +c) 2 4 W ΣV ζ 2 = (ζ V ΣV ζ +c) 2 4ζ V ΣW W ΣV ζ ≥ (ζ V ΣV ζ) 2 4ζ V ΣW W ΣV ζ + c 2 4ζ V ΣW W ΣV ζ ≥ c 1 4 λ 2 min (V ΣV ) λ 2 max (W ΣV ) + c 2 4c 1 λ 2 max (W ΣV )

.

By assuming existence of i,j such that ξ j ζ i w j Σv i = 0, we are guaranteed that λ 2 max (W ΣV ) > 0.

Note due to construction we have θ 2 2 = θstd 2 2 + i ζ 2 i + j ξ 2 j and plugging in the choice of ξ j in equation ( 14) we have

θ 2 2 -θstd 2 2 ≥ c 1 1+ λ 2 min (V ΣV ) 4λ 2 max (W ΣV ) + c 2 4λ 2 max (W ΣV ) 1 c 1 .

Setting

β 1 = 1+ λ 2 min (V ΣV ) 4λ 2 max (W ΣV ) , β 2 = 1 4λ 2 max (W ΣV ) yields the result.

B.3.2 PROOF OF LEMMA 1:

Let λ 1 ,...,λ m be the m non-zero eigenvalues of Σ and u i be the corresponding eigenvectors. Then choose v to be any combination of the eigenvectors v = U β where U = [u 1 ,...,u m ] where at least β i ,β j = 0 for λ i = λ j . We next construct w = U α by choosing α as follows such that the inequality in (11) holds:

α i = β j β 2 i +β 2 j α j = -β i β 2 i +β 2 j

and α k = 0 for k = i,j. Then we have that α β = 0 and hence w v = 0. Simultaneously

w Σv = λ i β i α i +λ j β j α j = (λ i -λ j ) β i β j β 2 i +β 2 j = 0

which concludes the proof of the first statement.

We now prove the second statement by constructing Σ std = X std X std , Σ ext = X ext X ext using w, v.

We can then obtain X std , X ext using any standard decomposition method to obtain X std , X ext . 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.

B.4 CHARACTERIZATION COROLLARY 1:

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

EQUATION

)

(b) (in terms of eigenvectors) Data augmentation does not increase bias for any θ if Π ⊥ std x ext 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 x ext increase bias.

The form in Equation ( 15) compares ratios of inner products of Π ⊥ std x ext 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 x ext may hurt bias. Here again, if Σ = γI for γ > 0, then the condition must hold.

B.4.1 PROOF OF COROLLARY 1 (A):

Note that for a single augmentation point

X ext = x ext , the orthogonal decomposition of Π ⊥ std θ into Col(Π ⊥ aug ) and Col(Π ⊥ std Π aug ) is defined by v = Π ⊥ std xext θ Π ⊥ std xext 2 Π ⊥ std x ext 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 ⇐⇒ Π ⊥ std x ext ΣΠ ⊥ std x ext ≤ 2(Π ⊥ std θ ) ΣΠ ⊥ std x ext • Π ⊥ std x ext 2 Π ⊥ std x ext θ

Rearranging the terms yields inequality (15).

Safe augmentation directions for specific choices of θ and Σ are illustrated in Figure 2 .

B.4.2 PROOF OF COROLLARY 1 (B):

Assume that Π ⊥ std x ext is an eigevector of Σ with eigenvalue λ > 0. We have

x ext Π ⊥ std ΣΠ ⊥ std x ext x ext Π ⊥ std x ext -2 (Π ⊥ std x ext ) ΣΠ ⊥ 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 find w such that w Σv = 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.

B.4.3 PROOF OF COROLLARY 1 (C):

Suppose ΣΠ ⊥ std θ = λΠ ⊥ std θ for some λ min (Σ) ≤ λ ≤ λ max (Σ). Then starting with the expression (15),

x ext Π ⊥ std ΣΠ ⊥ std x ext x ext Π ⊥ std x ext -2 (Π ⊥ std x ext ) ΣΠ ⊥ std θ x ext Π ⊥ std θ = x ext Π ⊥ std ΣΠ ⊥ std x ext x ext Π ⊥ std x ext -2λ ≤ λ max (Σ)-2λ < 0

by applying λmax(Σ) λmin(Σ) ≤ 2. Thus when Π ⊥ std θ is an eigenvector of Σ, there are no augmentations x ext 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:

EQUATION

where

X ext def = Π ⊥ std X ext , is the component of X ext in the null space of Σ std . Proof. Recall from (3) that the V ( θ) = tr(Cov( θ | X std X ext )Σ).

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 ) = σ 2 tr Σ † std Σ , V ( θaug ) = σ 2 tr Σ † aug Σ ,

where Σ std = X std X std and Σ aug = X std X std +X ext X ext . Note that since Σ std ,Σ aug are unnormalized, the quantities Σ † std and Σ † aug decay with n with 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 ext X ext ) † = Σ † std -Σ † std X ext (I +X ext Σ † std X ext ) -1 X ext Σ † std +X † ext (X † ext )

, where recall that X ext is the component of X ext 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 T 1 and T 2 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) if X ext is entirely in the span of Σ std making X ext = 0, T 1 = 0 making V ( θaug ) ≤ V ( θstd ) (ii) On the other extreme, if X ext is entirely in the null space with Σ † std X ext = 0, T 2 = 0 and hence V ( θaug ) ≥ V ( θstd ).

D DETAILS FOR SPLINE STAIRCASE:

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.

D.1 TRUE MODEL:

We consider a finite input domain

EQUATION

for some integer s corresponding to the total number of "stairs" in the staircase problem. Let T line ⊂ T = {0,1,...,s-1}. We define the underlying function f : R → R as f (t) = t . This function takes a staircase shape, and is linear when restricted to T line .

Sampling training data X std 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 . Let w ∈ ∆ s define a distribution over T line 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 T line according to the categorical distribution described by w, such that i ∼ Categorical(w). Second, sample t by perturbing i with probability δ such that

t = i w.p. 1-δ i+ w.p. δ.

The sampled t is in T line with probability 1-δ and T c line with probability δ, where we choose δ to be small. Sampling augmented points X ext For each element t i in the training set, we augment with Ti = [u u.a.r ∼ B(t i )], an input chosen uniformly at random from B(t i ) = { t i , t i + }. 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 ( ti ) = f (t i ) for all t ∈ B(t i ), and thus we can set the augmented targets to be ỹi = y i . 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.

D.2 SPLINE MODEL:

We parameterize the spline predictors as f θ (t) = θ X(t) where X : R → R d 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 R d 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 R d . There is a one-to-one correspondence between t and X(t), such that X -1 is well-defined. We define the features that correspond to inputs in T line as X line = {x : X -1 (x) ∈ T line }. 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 θ , Figure 5 : Visualization of the effect of single augmentation points in the noiseless spline problem given an initial dataset X std = {Φ(t) : t ∈ {0,1,2,3,4}}. The standard estimator defined by X std is linear.

f θ (t) = θ X(t) = f (t) = t .

(a) Plot of the difference term in Corollary 1 (a), is positive when augmenting a single point causes higher test error. Augmenting with points on X line does not affect the bias, but augmenting with any element of {X(t) : t ∈ {2.5,3.5,4.5}} hurts the bias of the augmented estimator dramatically. (b), (c) Augmenting with X(3.5) or X(4.5) hurts the bias by changing the direction of extrapolation. We solve the minimum norm problem

EQUATION

EQUATION

for the standard estimator and the corresponding augmented problem to obtain the augmented estimator.

D.3 EVALUATING COROLLARY 1 (A) FOR SPLINES:

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 be X std = {X(t) : t ∈ {0,1,2,3,4}}. Let local perturbations be spline features for t / ∈ T line 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 ∈ T line } does not affect the bias, but adding any perturbation point in {X( t) : t ∈ {2.5,3.5,4.5}} where t / ∈ T line 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.

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 to minimum 2 norm linear interpolation using features X M (t) = X(t)M -1/2 so that the results from Section 4.1.2 apply directly. Let Σ be the population covariance of X M for a uniform distribution over the discrete domain consisting of s stairs and their perturbations (Figure 1 ). Let Q = [q i ] 2s i=1 be the eigenvectors of Σ in decreasing order of their corresponding eigenvalues. The visualization in Figure 3 shows that q i 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, X std = [X M (0),X M (1)] . We study the effect of augmenting point x ext in terms of q i above. First, we find that the first two eigenvectors corresponding to linear functions satisfy Π ⊥ std q 1 = Π ⊥ std q 2 = 0. Intuitively, this is because the standard estimator is linear. For ease of visualization, we consider the 2D space in Null(Σ) spanned by Π ⊥ std q 3 (global direction, low frequency) and Π ⊥ std q 2s (local direction, high frequency). The matrix Π lg = [Π ⊥ std q 3 , Π ⊥ std q 2s ] projects onto this space. Note that the same results hold when projecting onto all Π ⊥ std q i 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 Π lg X ext for different X ext . When θ has high frequency variations and is complex, Π lg θ = (θ -θstd ) is aligned with the local dimension. For x ext immediately local to training points, the projection Π lg x ext (orange vector in Figure 6 ) has both local and global components. Augmenting these local perturbations introduces error in the global component. For other x ext farther from training points, Π lg x ext (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 the M -norm being minimized results in eigenvectors of Σ that correspond to local and global components, dictating this tradeoff.

D.4 DATA AUGMENTATION CAN BE QUITE PAINFUL FOR SPLINES:

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.

Sampling distribution:

We define a modified domain with continuous intervals T = ∪ s-1 t=0 [t,t+ ]. Considering only s which is a multiple of 2, we sample the original data set as described in Section D.1 with the following probability mass w:

EQUATION

)

for γ ∈ [0, 1). We define a probability distribution P T on T for a random variable T by setting T = Z +S(Z) where Z ∼ Categorical(w) and the Z-dependent perturbation S(z) is defined as

EQUATION

We obtain the training dataset X std = {X(t 1 ),...,X(t n )} by sampling t i ∼ P T .

Augmenting with an interval:

Consider a modified augmented estimator for the splines problem, where for each point t i we augment with the entire interval [ t i , t i + ] with ∈ [0,1/2) and the estimator is enforced to output f θ (x) = y i = t i for all x in the interval [ t i , t i + ]. 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(s 7 -1) s and γ = c/s for a constant c ∈ [0,1), the ratio between test errors is lower bounded as

R( θaug ) R( θstd ) = Ω(s 2 ) (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. Define E 1 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 = max i t i be the largest "stair" value seen in the training set. Note that the min-norm augmented estimator will extrapolate with zero derivative for t ≥ max i t i . 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 E 1 , 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 > s 2 -1}, the augmented estimator incurs large error:

R( θaug | E 1 ) ≥ s t=s/2 (t-(s/2-1)) 2 • γ s/2 = s/2 t=1 t 2 • γ s/2 = γ 6 (s 2 +2s+1).

Therefore the expected risk of the augmented estimator is bounded by

R( θaug ) ≥ R( θaug | E 1 )P (E 1 ) = γ 6 (s 2 +2s+1)(1-γ) n ≥ 1 6 γ(1-γn)(s 2 +2s+1) = Ω( c-c 2 s (s 2 +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. Define E 2 to be the event where all points are sampled from T line , which occurs with probability (1δ) n . In this case, the standard estimator is linear and fits the points on T line with zero error, while incurring error for all points not in T line . Note that the probability density of sampling a point not in T line is either δ • 1-γ s/2 or δ • γ s/2 , which we upper bound as

δ • 1 s/2 . R( θstd | E 2 ) = s-1 t=1 δ • 1 s/2 0 u 2 du = δ • 1 s/2 O(s 3 ) = O(δ)

Therefore for event E 2 , the expected error is bounded as

R( θstd | E 2 )P (E 2 ) = O(δ)(1-δ) n = O(δ)e -δn = O(δ• s 7 -1 s 7 ) = O(δ) = O( log(s 7 )-log(s 7 -1) s ) = O(1/s)

since log(s 7 )-log(s 7 -1) ≤ 1 for s ≥ 2. For the complementary event E c 2 , note that cubic spline predictors can grow only as O(t 3 ), with error O(t 6 ). Therefore the expected error for case E c 2 is bounded as

R( θstd | E c 2 )P (E c 2 ) ≤ O(t 6 )(1-e -δn ) = O(t 6 )O( 1 s 7 ) = O(1/s)

Putting the parts together yields

R( θstd ) = R( θstd | E 2 )P (E 2 )+R( θstd | E c 2 )P (E c 2 ) ≤ O(1/s)+O(1/s) = O(1/s).

Thus overall, R( θstd ) = O(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 interpolants says about the trends with respect to varying sample sizes of the standard training set (X std ,y std ).

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, X ext ⊥ X std , across all sample sizes in the small sample regime. For a fixed X ext , we see that the magnitude of variance increase is governed by Π ⊥ std X ext 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,

EQUATION

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 with X ext such that X ext ∈ 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 ext X ext . For a fixed X ext , 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 of X ext 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. X std θ int-std = y std . Let θx-aug be the X-regularized interpolant (6). Then R θx-aug ) ≤ R(θ int-std ).

Proof. Let {u i } be an orthonormal basis of the kernel Null(Σ std + X ext X ext ) and {v i } be an orthonormal basis for Null(Σ std ) \ span({u i }). Let U and V be the linear operators defined by U w = i u i w i and V w = i v i w i , respectively, noting that U V = 0. Defining Π ⊥ std := (I -Σ † std Σ std ) to be the projection onto the null space of X std , we see that there are unique vectors ρ,α such that

EQUATION

As θ int-std interpolates the standard data, we also have

EQUATION

as X std U w = X std V 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

EQUATION

Now, recall that the predictive test error of a vector θ is R(θ) = (θ-θ ) Σ(θ-θ ) = θ-θ 2 Σ , using Mahalanobis norm notation. In particular, a few quadratic expansions yield

EQUATION

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. X std ,y std denote the standard training set and we have access to m unlabeled points xi ,i = 1,...m.

F.2.1 PROJECTED GRADIENT ADVERSARIAL TRAINING:

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

EQUATION

In practice, x adv is found by performing a few steps of projected gradient method on (f θ (x),y), and similarly xadv by performing a few steps of projected gradient method on (f θ (x),f θstd (x)).

F.2.2 TRADES:

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 

where KL(p θ (x),p θ (x adv ) is the KL divergence between the probability over class labels assigned to x and x adv .

G EXPERIMENTAL DETAILS G.1 SPLINE SIMULATIONS 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 matrix M 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.

G.2.1 SUBSAMPLING CIFAR-10:

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 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,γ)/(1min(0.9,γ)) where γ ∈ [0,1] is the fraction of the original CIFAR-10 dataset 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.

G.2.3 ADVERSARIAL AND RANDOM ROTATION/TRANSLATIONS:

In Table 1 (right), we instantiate X-regularization as robust self-training for adversarial and random rotation/translations, using these transformations as x adv 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).

H COMPARISON TO STANDARD SELF-TRAINING ALGORITHMS:

The main objective of X-regularization 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.

:



Figures and Tables:

Figure 1: We consider perfectly fitting training points using cubic splines while minimizing smoothness of the function. (Left) depicts the true function f and the mass P xy 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 error 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 a standard model (trained without perturbations) on unlabeled data, allowing for fitting both the local and global structure.

(i) the standard estimator θstd which has [X std ,y std ] as training data and (ii) the data augmented estimator θaug with X = [X std ;X ext ],Y = [y std ;y ext ] as training data: θstd = argmin θ θ 2 : X std θ = y std and θaug = argmin θ θ 2 : X std θ = y std ,X ext θ = y ext . (2)

Figure 2 depicts these parameter errors for different choices of θ .

Figure 2: Illustration of the 3-D example described in Sec. 4.1.1. In (a), (b) we depict the errors θaugθ (green solid) and θstdθ (blue solid) projected onto Null(Σ std ) that is spanned by eigenvectors e 1 and e 2 of Σ with λ 2 λ 1 . Red lines depict the projection of parameter errors on e 2 which determines the bias. In (a) θ 1 θ 2 and bias increases upon augmentation. In (b) θ 1 θ 2 and bias decreases upon augmentation. (c), (d)The space of safe augmentation directions (orange) that don't increase bias for a given θ are cone-shaped, where the cone width depends on the alignment of θ with eigenvectors of Σ and the skew in eigenvalues of Σ.

Figure 6: Nullspace projections onto global direction q 3 and local direction q 2s in Null(Σ) via Π lg , representing global and local eigenvectors respectively. The local perturbation Π lg Φ(1.5) has both local and global components, creating a high-error component in the global direction.

y)∈[Xstd,ystd] (f θ (x),y)+β KL(p θ (x adv )||p θ (x(x i ),f θstd (x i ))+β KL(p θ (x advi )||p θstd (x i )) ,

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.

refer to the training data from the underlying distribution P xy by standard training data. Formally, we have n pairs (x i ,y i ) ∼ P xy forming the measurement matrixX std = [x 1 ,x 2 ,...x n ] ∈ R n×d and target vector y std = [y 1 ,y 2 ,...y n ] ∈ R n .Analogously , we consider augmenting the training set with "extra" training points denoted byX ext = [x 1 , x2 ,... xm ] ∈ R m×d with associated targets y ext = [ỹ 1 , ỹ2 ,... ỹm ] ∈ R m .We focus on covariate-shifted data augmentations which includes most forms of data augmentations used in practice . Here, the targets y ext are drawn from the same underlying predictive distribution P y (• | x) as the standard data, while the extra inputs X ext could be arbitrary.

Table content: <table/>

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 ∞ perturbations of size = 8/255. All methods use = 8/255 while training. Robust accuracies are against a PG based attack with 20 steps. (Right) CIFAR-10 standard test accuracy and robust test accuracy against a grid attack of rotations up to 30 degrees and translations up to ∼ 10% of the image size, following

Table content: <table><tr><td>Method</td><td>Robust</td><td>Standard</td><td/><td/><td/></tr><tr><td/><td>Test Acc.</td><td>Test Acc.</td><td/><td/><td/></tr><tr><td>Standard Training Standard Self-Training</td><td>0.8% 0.3%</td><td>95.2% 96.4%</td><td>Method</td><td>Robust Test Acc.</td><td>Standard Test Acc.</td></tr><tr><td>PG-AT (Madry et al., 2018)</td><td>45.8%</td><td>87.3%</td><td>Standard Training</td><td>0.2%</td><td>94.6%</td></tr><tr><td>RST + PG-AT</td><td>58.5%</td><td>91.8%</td><td>Worst-of-10</td><td>73.9%</td><td>95.0%</td></tr><tr><td>TRADES (Zhang</td><td>55.4%</td><td>84.0%</td><td>RST + Worst-of-10</td><td>75.1%</td><td>95.8%</td></tr><tr><td>et al., 2019)</td><td/><td/><td>Random</td><td>67.7%</td><td>95.1%</td></tr><tr><td>RST + TRADES</td><td>63.1%</td><td>89.7%</td><td>RST + Random</td><td>70.9%</td><td>95.8%</td></tr><tr><td>(Carmon et al., 2019)</td><td/><td/><td>Worst-of-10</td><td>69.2%</td><td>91.3%</td></tr><tr><td>Interpolated AT</td><td>45.1%</td><td>93.6%</td><td>(Engstrom et al., 2019) 2</td><td/><td/></tr><tr><td>(Lamb et al., 2019) 1</td><td/><td/><td colspan="2">Random (Yang et al., 2019) 3 58.3%</td><td>91.8%</td></tr><tr><td>Neural Arch. Search</td><td>50.1%</td><td>93.2%</td><td/><td/><td/></tr><tr><td>(Cubuk et al., 2017)</td><td/><td/><td/><td/><td/></tr></table>

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.

Table content: <table/>

. 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?

Table content: <table/>

Peer review (iclr2020):
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. The machinery of the analysis and the positive suggestion of X-regularization strike me as technically sophisticated and effective. This 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. The 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. On balance, I find the theoretical investigation and explanation for *how does this happen* to be more compelling than the presentation of X-regularization. Note 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.