Year: 2021

Abstract:
Data augmentation is popular in the training of large neural networks; currently, however, there is no clear theoretical comparison between different algorithmic choices on how to use augmented data. In this paper, we take a small step in this direction; we present a simple new statistical framework to analyze data augmentation specifically, one that captures what it means for one input sample to be an augmentation of another, and also the richness of the augmented set. We use this to interpret consistency regularization as a way to reduce function class complexity, and characterize its generalization performance. Specializing this analysis for linear regression shows that consistency regularization has strictly better sample efficiency as compared to empirical risk minimization (ERM) on the augmented set. In addition, we also provide generalization bounds under consistency regularization for logistic regression and two-layer neural networks. We perform experiments that make a clean and apples-to-apples comparison (i.e. with no extra modeling or data tweaks) between ERM and consistency regularization using CIFAR-100 and WideResNet; these demonstrate the superior efficacy of consistency regularization.

heading: 1 INTRODUCTION
text: Modern machine learning models, especially deep learning models, require abundant training samples. Since data collection and human annotation are expensive, data augmentation has been a ubiquitous practice in creating artificial labeled samples and improving generalization performance. This practice is corroborated by the fact that the semantics of images remain the same through simple translations like obscuring, flipping, rotation, color jitter, rescaling (Shorten & Khoshgoftaar, 2019).
Conventional algorithms use data augmentation to expand the training data set (Krizhevsky et al., 2012; Simard et al., 1998; Cubuk et al., 2018; Simonyan & Zisserman, 2014; He et al., 2016). As an alternative, consistency regularization enforces the model to output similar predictions on the original and augmented samples and contributes to many recent state-of-the-art supervised or semisupervised algorithms. This idea was first proposed in (Bachman et al., 2014) and popularized by Laine & Aila (2016); Sajjadi et al. (2016), and gained more attention recently with the success of FixMatch (Sohn et al., 2020) for semi-supervised few-shot learning, and AdaMatch (Berthelot et al., 2021) for domain adaptation.
Several recent papers (see e.g. (Chen et al., 2020a; Mei et al., 2021; Lyle et al., 2019)) attempt to provide a theoretical understanding of data augmentation (DA); they focus on establishing that augmenting data saves on the number of labeled samples needed for the same level of accuracy. However, none of these explicitly compare in an apples to apples way the efficacy (in terms of the number of augmented samples) of one algorithmic choice of how to use the augmented samples vs another algorithmic choice. Another dimension un-explored in previous work is any characterization of the quality of augmentation.
In this paper, we hope to answer the following research question:
Is it possible to develop a theoretical framework to compare the sample efficiency of different algorithms that use augmented data?
We present a new theoretical framework that casts consistency regularization as a way to reduce function class complexity, which immediately connects to the well-established theory on generalization and gives rise to a generalization bound for consistency regularization under a general bounded loss function. When specialized to linear regression, this new theoretical framework shows that the consistency regularization is strictly more sample efficient than empirical risk minimization (ERM) on the augmented dataset. In addition, using this framework, we also provide generalization bounds under consistency regularization for logistic regression, two-layer neural networks, and expansion-based data augmentations.
As summary, our main contributions are:
• A statistical framework of consistency regularization. We first present a simple new statistical framework to analyze data augmentation - with a formal theoretical definition of data augmentation and its strength. We then use this framework to give a generalization bound of consistency regularization and provide instantiations for linear regression, logistic regression, two-layer neural networks, and expansion-based data augmentations.
• Theoretically proving the efficacy of consistency regularization. When specializing our framework with consistency regularization to linear/logistic regression, it yields a strictly smaller generalization error than ERM with the same augmented data.
• Empirical comparisons between consistency regularization and ERM. We perform experiments that make a clean and apples-apples comparison (i.e., with no extra modeling or data tweaks) between consistency regularization and ERM using CIFAR-100 and WideResNet. Our empirical results demonstrate the superior efficacy of consistency regularization.

heading: 2 RELATED WORK
text: Empirical findings. Data augmentation (DA) is an essential recipe for almost every state-of-theart supervised learning algorithm since the seminal work of (Krizhevsky et al., 2012) (see reference therein (Simard et al., 1998; Cubuk et al., 2018; Simonyan & Zisserman, 2014; He et al., 2016; Kuchnik & Smith, 2018)). It started from adding augmented data to the training samples via (random) perturbations, distortions, scales, crops, rotations, and horizontal flips. More sophisticated variants were subsequently designed; a non-exhaustive list includes Mixup (Zhang et al., 2017), Cutout (DeVries & Taylor, 2017), and Cutmix (Yun et al., 2019). The choice of data augmentation and their combinations require domain knowledge and experts’ heuristics, which triggered some automated search algorithm to find the best augmentation strategies (Lim et al., 2019; Cubuk et al., 2019). The effects of different DAs have been systematically explored in (Tensmeyer & Martinez, 2016).
Recent practices not only add augmented data to the training set but also enforce the predictor output to be similar by adding consistency regularization (Bachman et al., 2014; Laine & Aila, 2016; Sohn et al., 2020). One benefit of consistency regularization is the feasibility of exploiting unlabeled data. Therefore input consistency on augmented data also formed a major component to state-of-theart algorithms for semi-supervised learning (Laine & Aila, 2016; Sajjadi et al., 2016; Sohn et al., 2020; Xie et al., 2020), self-supervised learning (Chen et al., 2020b), and unsupervised domain adaptation (French et al., 2017; Berthelot et al., 2021).
Theoretical studies. Many interpret the effect of DA as some form of regularization (He et al., 2019). Some work focuses on linear transformations and linear models (Wu et al., 2020) or kernel classifiers (Dao et al., 2019). Convolutional neural networks by design enforce translation equivariance symmetry (Benton et al., 2020; Li et al., 2019); further studies have hard-coded CNN’s invariance or equivariance to rotation (Cohen & Welling, 2016; Marcos et al., 2017; Worrall et al., 2017; Zhou et al., 2017), scaling (Sosnovik et al., 2019; Worrall & Welling, 2019) and other types of transformations.
A line of work view data augmentation as invariant learning by averaging over group actions (Chen et al., 2020a; Mei et al., 2021; Lyle et al., 2019). They consider an ideal setting that is equivalent to ERM with all possible augmented data, bringing a clean mathematical interpretation. We are interested in a more realistic setting with limited augmented data. In this setting, it is crucial to utilize the limited data with proper training methods, the difference of which cannot be revealed under the previous studied settings.
Some more recent work investigates the feature representation learning procedure with DA for selfsupervised learning tasks (Wen & Li, 2021; HaoChen et al., 2021; von Kügelgen et al., 2021; Garg & Liang, 2020). Cai et al. (2021); Wei et al. (2021) studied the effect of data augmentation with label propagation. Data augmentation is also deployed to improve robustness (Rajput et al., 2019), to facilitate domain adaptation and domain generalization (Cai et al., 2021; Sagawa et al., 2019) .

heading: 3 DATA AUGMENTATION CONSISTENCY AND HOW IT LEARNS EFFICIENTLY
text: In this section, we first formally define data augmentation and introduce the problem setup. We then define data augmentation consistency (DAC) regularization and show how it effectively reduces the function class complexity, which connects to a generalization bound for bounded loss functions via Rademacher complexity. Subsequently, we specialize our general result to linear regression, which firmly shows that the DAC regularization provably learns more efficiently than minimizing the empirical risk on the augmented dataset. The following section will present more applications (including logistic regression, neural network, etc.).

heading: 3.1 PROBLEM SETUP AND DATA AUGMENTATION
text: Consider the standard supervised learning problem setup: x ∈ X are input features, and y ∈ Y is its label (or response). Let P ∗ be the true distribution of (x, y) (i.e., the label distribution follows y ∼ P ∗(y|x)). We can then formally define data augmentation as: Definition 1 (Data augmentation). For any sample x ∈ X , we say x′ ∈ X is its augmentation, if and only if P ∗(y|x) = P ∗(y|x′).
The definition above specifies what it means for one input sample to be an augmentation of another. While the definition covers any x′ with the same label distribution as x, our results only use the augmented samples that can be achieved via certain transformations (e.g., random cropping, rotation). However, our definition does not cover augmentations that alter the labels (e.g., MixUp (Zhang et al., 2017)).
Now we introduce the learning problem on an augmented dataset: Let (X,y) ∈ XN × YN be a training set consisting of N i.i.d. samples. Besides the original (X,y), each training sample in it is provided with α augmented samples. The input features of the augmented dataset can be written as:
Ã(X) = [x1; · · · ; xN ; x1,1; · · · ; xN,1; · · · ; x1,α; · · · ; xN,α] ∈ X (1+α)N ,
where xi is in the original training set and xi,j ,∀j ∈ [α] are the augmentations of xi. The labels of the augmented samples are kept the same, which can be denoted as M̃y ∈ Y(1+α)N , where M̃ ∈ R(1+α)N×N is a vertical stack of (1 + α) identity mappings. Specifically, when the input xis are d-dimensional real vectors, we have the following notion of augmentation strength daug:
Definition 2 (Strength of augmentations). For any δ ∈ (0, 1), let
daug(δ) , argmax daug
PÃ,X [ rank ( Ã(X)− M̃X ) < daug ] ≤ δ, daug , daug (1/N) .
Intuitively, strength of augmentations daug(δ) means that with probability at least 1 − δ, the augmentations perturb at least daug(δ) dimensions; whereas daug can be intuitively understood as the minimum number of dimensions that the augmentations in Ã(X) perturbed with high probability. A lager daug corresponds to a stronger data augmentations. For instance, when Ã(X) = M̃X almost surely (e.g., when the augmentations are identical copies of the original samples, corresponding to the weakest augmentation – no augmentations at all), we have daug(δ) = daug = 0 for all δ ∈ (0, 1). On the other hand, if the augmentations are randomly generated, then it is more likely to see larger daug (i.e., more dimensions being perturbed) with larger α (i.e., more augmentations).
In the next subsection, we formally introduce “data augmentation consistency regularization” and present a generalization bound under bounded loss functions. We subsequently specialize the bound to linear regression and show that consistency regularization is strictly more sample efficient than empirical risk minimization (ERM) on the augmented dataset.

heading: 3.2 DATA AUGMENTATION CONSISTENCY REGULARIZATION
text: Let H = {h : X → Y} be a well-specified function class (e.g. for regression problems, ∃h∗ ∈ H, s.t. h∗(x) = E[y|x]) that we hope to learn from. Without loss of generality, we assume that each function h ∈ H can be expressed as h = fh ◦ φh, where φh ∈ Φ = {φ : X → W} is a proper representation mapping and fh ∈ F = {f :W → Y} is a predictor on top of the learned representation. We tend to decompose h such that φh is a powerful feature extraction function whereas fh can be as simple as a linear combiner. For instance, in a deep neural network, all the layers before the final prediction layer can be viewed as feature extraction φh, and the predictor fh corresponds to the final linear combination of the features.
For a loss function l : Y × Y → R and a metric % properly defined on the representation spaceW , learning with data augmentation consistency (DAC) regularization can be expressed as:
argmin h∈H N∑ i=1 l(h(xi), yi) + λ α∑ j=1 N∑ i=1
% (φh(xi), φh(xi,j))︸ ︷︷ ︸ DAC regularization . (1)
Note that the DAC regularization in Equation (1) can be easily implemented empirically as a regularizer. Intuitively, DAC regularization penalizes the representation difference between the original sample φh(xi) and the augmented sample φh(xi,j), with the belief that similar samples (i.e., original and augmented samples) should have similar representations. When the data augmentations do not alter the labels, it is reasonable to enforce a strong regularization (i.e., λ → ∞) - given that the conditional distribution of y does not change. The function ĥdac learned with data augmentation consistency regularization can then be written as the solution of a constrained optimization problem:
ĥdac , argmin h∈H N∑ i=1 l(h(xi), yi) s.t. φh(xi) = φh(xi,j), ∀i ∈ [N ], j ∈ [α]. (2)
The constraint in Equation (2) effectively reduces the size of the function class H. To rigorously capture such reduction, we define the following data augmentation consistency (DAC) operator over H. Given the original training samples X and the augmented dataset Ã(X), we have: Definition 3 (Data Augmentation Consistency Operator).
T dacÃ,X(H) , {h | h ∈ H, φh(xi) = φh(xi,j), ∀i ∈ [N ], j ∈ [α]} .
Ã,X
(H).
Particularly, we assume that a proper representation class Φ is chosen with respect to the augmentations such that h∗ ∈ T dac
Ã,X (H). The DAC opera-
tor maps the original function class H to a (potentially much smaller) subset T dac
Ã,X (H), where every
function h ∈ T dac Ã,X (H) gives consistent representation for all samples and their augmentations (i.e., φh(xi) = φh(xi,j)). It is now clear that with DAC regularization, Equation (2) is effectively learning in the function class T dac
Ã,X (H), which is a subset ofH.
As we will show in the next subsection, the function class size reduction is the key for efficient learning with data augmentations.
One of the contributions of our paper is to view consistency regularization as function class complexity reduction. Our next proposition connects the generalization bound to the Rademacher complexity T dac Ã,X
(H) via standard analysis. We further provide various instantiations in the rest of our paper. Let L(h) denote the population loss induced by h ∈ H, i.e., L(h) , E(x,y)∼P∗ [l(h(x), y)]. Proposition 1 (formally in Proposition 8). With Equation (2), if l is B-bounded and Cl-Lipschitz, then for a fixed T dac
Ã,X (H) and any δ ∈ (0, 1), with probability at least 1− δ, we have
L(ĥdac)− L(h∗) ≤ 4Cl ·RN ( T dacÃ,X(H) ) + √ 2B2 log(2/δ)
N .
Remark 1. Our results can be immediately extended to use unlabeled data. Notice that the DAC regularization only enforces the same predictions for the original and augmented samples, where no ground truth label is needed. For clarity of exposition, we focus on the labeled dataset in the main text and defer discussions on unlabeled data to the appendix.

heading: 3.3 EFFICACY OF DAC REGULARIZATION: A GENTLE START WITH LINEAR REGRESSION
text: To see the efficacy of DAC regularization (i.e., Equation (2)), we revisit a more commonly adopted training method here - empirical risk minimization (ERM) on augmented data:
ĥda−erm , argmin h∈H N∑ i=1 l(h(xi), yi) + N∑ i=1 α∑ j=1 l(h(xi,j), yi). (3)
Now we show that the DAC regularization learns more efficiently than ERM. Consider the following setting: given N observations X ∈ RN×d, the responses y ∈ RN are generated from a linear model y = Xθ∗ + , where ∈ RN is zero-mean noise with E [ > ]
= σ2IN . Recall that Ã(X) is the entire augmented dataset, and M̃y corresponds to the labels. Our next result characterizes the
fixed design excess risk of θ on Ã(X), which is defined as L(θ) , 1(1+α)N ∥∥∥Ã(X)θ − Ã(X)θ∗∥∥∥2
2 .
Under regularity conditions (e.g., x is sub-Gaussian and N is not too small), it is not hard to extend to random design, i.e., the more commonly acknowledged generalization bound with the same order.
Given Ã(X), notice that by Definition 2, daug = rank ( Ã(X)− M̃X ) since there is no randomness
in Ã,X in fixed design setting. For a linear regression model to be identifiable (i.e., having an unique solution), we assume that Ã(X) has full column rank. We then have the following theorem on the excess risks of learning by DAC regularization and by ERM on the augmented dataset. Theorem 2 (Informal result on linear regression (formally in Theorem 6)). Learning with DAC regularization, we have E [ L(θ̂dac)− L(θ∗) ] =
(d−daug)σ2 N , while learning with ERM directly on the augmented dataset, we have E [ L(θ̂da−erm)− L(θ∗) ] =
(d−daug+d′)σ2 N , where d ′ ∈ [0, daug].
Formally, d′ is defined as d′ , tr((HÃ(X)−PS)M̃M̃ >) 1+α , where HÃ(X) , Ã(X)Ã(X) †, and PS is the orthogonal projector onto S , { M̃Xθ | ∀θ ∈ Rd, s.t. ( Ã(X)− M̃X ) θ = 0 } .
Here we present an explanation for d′. Note that σ2 · M̃M̃> is the noise covariance matrix of the augmented dataset. We have tr ( PSM̃M̃ > ) being the variance
of θ̂dac, and tr ( HÃ(X)M̃M̃ > ) being the variance of θ̂da−erm. Therefore, d′ ∝ tr (( HÃ(X) −PS ) M̃M̃> ) is used to measure the difference. When HÃ(X) 6= PS (a common scenario as instantiated in Example 1), we have DAC being strictly better than ERM on augmented data. Example 1. Consider a 30-dimensional linear regression. The original training set contains 50 samples. The inputs xis are generated independently from N (0, I30) and we set θ∗ = [θ∗c ; 0] with θ ∗ c ∼ N (0, I5) and 0 ∈ R25.
The noise variance σ is set to 1. We break x into 3 parts [xc1, xe1 , xe2] and take the following augmentations: A([xc1;xe1;xe2]) = [xc1; 2xe1;−xe2], xc1 ∈ Rdc1 , xe1 ∈ Rde1 , xe2 ∈ Rde2 , where dc1 + de1 + de2 = 30.
Notice that the augmentation perturbs xe1 and xe2 and leaving xc1 unchanged, we therefore have daug = 30 − dc1. By changing dc1 and de1, we can have different augmentations with different daug, d
′. The results for daug ∈ {20, 25} and various d′s induced by different de1s are presented in Figure 2. The excess risks precisely match Theorem 2. It confirms that the DAC regularization is strictly better than ERM on an augmented dataset for a wide variety of augmentations.

heading: 4 VARIOUS APPLICATIONS
text: Now we ground our general result on the DAC regularization with a set of common applications, including the logistic regression, two-layer neural networks, and expansion-based data augmentations. For each of the applications, we first specify the ground truth distribution P ∗, the function class H, the loss function l, as well as the augmented dataset Ã(X). Then, we discuss the corresponding excess risk L(ĥdac)−L(h∗) for the DAC regularization (Equation (2)). We abridge the analysis in a set of concrete examples with concise arguments while deferring the complete assumptions and theorems to Appendix B. As a supplementary remark, in addition to the popular in-distribution setting where we consider a unique distribution P ∗ for both training and testing, DAC regularization is also known to improve out-of-distribution generalization for settings like domain adaptation. We defer detailed discussion on such advantage of DAC regularization for linear regression in the domain adaptation setting to Appendix B.4.

heading: 4.1 LOGISTIC REGRESSION
text: Here we consider logistic regressions with X = { x ∈ Rd ∣∣ ‖x‖2 ≤ D}, Y = {0, 1}. For some unkown θ∗ ∈ Rd with ‖θ∗‖ ≤ C0, we have P ∗ (y = 1|x) = σ ( θ∗>x ) , where σ(·) is the sigmoid function σ(z) , 1/(1 + exp(−z)). The function class H is H ={ h(x) = θ>x
∣∣ θ ∈ Rd, ‖θ‖2 ≤ C0}, such that predictions are given by ŷ = σ (θ>x). For binary classification, we use the logistic loss l(θ>x, y) = −y log(σ(θ>x))− (1− y) log(1− σ(θ>x)). Recall the strength of augmentations daug from Definition 2. Under proper regularity conditions (i.e., x is sub-Gaussian and N is not too small, see Appendix B), we have the following generalization bound for learning logistic regression under DAC regularization. Theorem 3 (Informal result on logistic regression with DAC (formally in Theorem 9)). Learning logistic regression with the DAC regularization h(xi) = h(xi,j), with high probability:
L(ĥdac)− L(h∗) . √ d− daug + logN
N ,
where the strength of augmentation daug ∈ [0, d− 1].
Intuitively, with high probability, minimizing empirical loss on augmented samples gives a generalization bound of L(ĥda−erm) − L(h∗) . max (√
d (α+1)N , √ d−daug N ) at best, where the first
term corresponds to the generalization bound for a d-dimensional logistic regression with (α+ 1)N samples, and the second term follows as the augmentations fail to perturb a (d− daug)-dimensional sub-space (and in which ERM can only rely on the N original samples for learning). The first term will dominate the max when there is limited augmented data (i.e., α is small).
Comparing the two, we see that DAC is more efficient than ERM. In particular, consider the scenario that the limited data augmentations well perturb the data (e.g., α = 1 and daug = d− 1). The ERM gives a generalization error that scales as √ d/N , while DAC yields a dimension-free √ 1/N error. Please see Appendix E for a supporting numerical example, which demonstrates the benefits of DAC over DA-ERM for logistic regression, and empirically verifies the impact of daug and α that matches with our theoretical analysis.

heading: 4.2 TWO-LAYER NEURAL NETWORK
text: In this section, we discuss a special case where the result for bounded losses in Proposition 8 can be extended to the unbounded square loss. With X = Rd and Y = R, we consider a ground truth
distribution P ∗ (y|x) induced by a two-layer ReLU network: y = ( x>B∗ ) + w∗ + z, B∗ d×q = [b∗1 . . .b ∗ k . . .b ∗ d] , for some unknown h ∗ (x) , ( x>B∗ ) +
w∗ where (·)+ , max(0, ·) elementwisely denotes the ReLU function, b∗k ∈ Sd−1 for all k ∈ [q], and z ∼ N ( 0, σ2 ) is the Gaussian noise. In terms of the function classH, for some constant Cw ≥ ‖w∗‖1, we have:
H = { h(x) = (x>B)+w ∣∣ B = [b1 . . .bq] ∈ Rd×q, ‖bk‖2 = 1 ∀ j ∈ [q], ‖w‖1 ≤ Cw} , such that h∗ ∈ H. We use the standard square loss l(h(x), y) = 12 (h(x)− y) 2.
Let PN be the projector onto the null space of Ã(X) − M̃X. When the augmented sample set Ã(X) is reasonably diverse (see Appendix B.2), regression over two-layer ReLU networks with the DAC regularization generalizes as following: Theorem 4 (Informal result on two-layer neural network with DAC (formally in Theorem 10)). Assuming E [ 1 n ∑n i=1 ‖PNxi‖ 2 2
∣∣∣PN ] ≤ C2N for some CN > 0, learning the two-layer ReLU network with the DAC regularization on ( x>i B ) + = ( x>i,jB ) + gives, with high probability:
L ( ĥdac ) − L (h∗) . σCwCN√
N .
Recall the strength of augmentations daug from Definition 2. Under proper regularity conditions (i.e., x is sub-Gaussian and N is reasonably large, see Appendix B.2), we have CN .√ d− daug with high probability. Analogous to the logistic regression example, applying the ERM directly on the augmented samples achieves no better than L(ĥda−erm) − L(h∗) .
σCwmax
(√ d (α+1)N , √ d−daug N ) with high probability. The comparison again illustrates the advan-
tage of DAC regularization over ERM. The advantage is large when the limited data augmentations are strong (i.e., large daug and small α).

heading: 4.3 EXPANSION-BASED DATA AUGMENTATIONS
text: In this section, we demonstrate that for the classification problems, enforcing consistency on a different notion of data augmentations based on expansion also brings a considerable reduction in complexity of the feasible function class.
Concretely, we consider a multi-class classification problem: for an arbitrary set X , let Y = [K], and h∗ : X → [K] be the ground truth classifier that partitions X : for each k ∈ [K], let Xk , {x ∈ X | h∗(x) = k}, with Xi ∩ Xj = ∅,∀i 6= j. Here we focus on the expansion-based data augmentations defined as following: Definition 4 (Expansion-based data augmentations). Let A : X → 2X be a function generating a set of augmentations A(x) from a given x ∈ X that satisfies the following: (a) Nontrivial augmentation and class invariant: {x} ( A(x) ⊆ {x′ ∈ X | h∗(x) = h∗(x′)} for
all x ∈ X ; and (b) Non-trivial expansion: for all k ∈ [K], given any ∅ ( S ( Xk, there exists some x′ /∈ S such
that A(x) ∩ A(x′) 6= ∅.
We consider a general class of classifiersH ⊆ {h : X → [K]}where the ground truth classifier is realizable, h∗ ∈ H. With the zero-one loss l01 (h(x), y) = 1 {h(x) 6= y}, and the corresponding population loss L01 (h) , Ex [1 {h (x) 6= h∗ (x)}], we learn a classifier fromH with the DAC regularization, h(x) = h(x′), where x′s are expansion-based data augmentations generated by an A (Definition 4). As a warm-up, we begin with a simplified setting where we enforce consistency over the population in lieu of a finite set of training samples as in practice. Then, learning with the DAC regularization yields a classifier ĥdac ∈ T dacA,X (H) , {h ∈ H | h(x) = h(x′) ∀ x ∈ X , x′ ∈ A(x)}. Theorem 5 (DAC with expansion-based data augmentations over population). Learning the classifier with DAC regularization over population, with high probability,
L01
( ĥdac ) − L01 (h∗) ≤ K logK + logN
N .
Particularly, with the DAC regularization, the generalization bound of the K-class classification problem is dimension-independent but only scales with the number of classes, Õ(K).
Furthermore, in Appendix B.3, we extend the result to a more practical setting where the consistency is enforced over a finite training set. Notably, Theorem 5, along with the finite train set case in Appendix B.3, is a reminiscence of Theorem 3.6 and 3.7 by Wei et al. (2021), as well as Theorem 2.1, 2.2, and 2.3 by Cai et al. (2021). We adapt these existing theories and provide a unified analysis under our setting, which demonstrates the generality of our framework.

heading: 5 EXPERIMENTS
text: In this section, we empirically verify that training with DAC learns more efficiently than empirical risk minimization on an augmented dataset. The dataset is derived from CIFAR-100, where we randomly select 10,000 labeled data as the training set (i.e., 100 labeled samples per class). During the training time, given a training batch, we generate augmentations by RandAugment (Cubuk et al., 2020). We set the number of augmentations per sample to 7 unless otherwise mentioned.
The experiments focus on comparisons of 1) training with consistency regularization, and 2) empirical risk minimization on the augmented dataset (DA-ERM). In particular, we use the same network architecture (a WideResNet-28-2 (Zagoruyko & Komodakis, 2016)) and the same training settings (e.g., optimizer, learning rate schedule, etc) for both methods. We defer the detailed experiment settings to Appendix D. Our test set is the standard CIFAR-100 test set, and we report the average and standard deviation of the testing accuracy of 5 independent runs. The consistency regularizer is implemented as the l2 distance of the model’s predictions on the original and augmented samples.
Efficacy of DAC regularization. We first show that the DAC regularization learns more efficiently than ERM on the augmented dataset. The results are listed in Table 1. Notice that with proper choice of λ (i.e., the multiplicative coefficient before the DAC regularization, see Equation (1)), training with DAC regularization significantly improves over DA-ERM.
DAC regularization helps more when data is scarce. Our theoretical results suggest that the DAC regularization brings more benefits when the training data is scarce. The data scarcity can be interpreted in two ways:
(1) Labeled samples are scarce. We conduct experiments with different numbers of labeled samples, ranging from 1,000 (i.e., 10 images per class) to 20,000 samples (i.e., 200 images per class). We generate 3 augmentations for each of the samples during the training time, and the results are presented in Table 2. Notice that the DAC regularization gives a bigger improvement over DA-ERM when the labeled samples are scarce. This matches the intuition that when there are sufficient training samples, data augmentation is less necessary. Therefore, the difference between different ways of utilizing the augmented samples becomes diminishing.
(2) Augmented samples are scarce. While keeping the number of labeled samples to be 10,000, we evaluate the performance of the DAC regularization and DA-ERM with different numbers of augmentations. The number of augmentations for each training sample ranges from 1 to 15, and the results are listed in Table 3. The DAC regularization offers a more significant improvement when the number of augmentations is small. This clearly demonstrates that the DAC regularization learns more efficiently from the limited number of augmentations.
Proper augmentation brings good performance. To achieve good performance, it is important to have proper data augmentation - it needs to be strong such that it well perturbs the input features, but it should also leave the label distribution unchanged. Here we experiment with different augmentation strengths, which is the number of different random transformations (e.g., random cropping, flipping, etc.) applied to the training samples sequentially. More transformations imply stronger augmentations. The number of transformations ranges from 1 to 10, and the results are listed in Table 4. We see that both DA-ERM and the DAC regularization benefits from a proper augmentation. When the augmentation is too strong (e.g., Augmentation Strength 10, as shown in Figure 3), the DAC regularization gives a worse performance. It might be explained by falsely enforcing DAC regularization where the labels of the augmented samples have changed.
Combining with a semi-supervised learning algorithm. Here we show that the DAC regularization can be easily extended to the semisupervised learning setting. We take the previously established semisupervised learning method Fix-
Match (Sohn et al., 2020) as the baseline and adapt the FixMatch by combining it with the DAC regularization. Namely, besides using FixMatch to learn from the unlabeled data, we additionally generate augmentations for the labeled samples and apply the DAC regularization. In particular, we focus on the data-scarce regime by only keeping 10,000 labeled samples and at most 20,000 unlabeled samples. Results are listed in Table 5. We see that the DAC regularization also improves the performance of FixMatch when the unlabeled samples are scarce. This again demonstrates the efficiency of learning with DAC regularization.

heading: 6 CONCLUSION
text: We present a simple new theoretical framework for understanding the statistical efficiency of consistency regularization with limited data augmentations. In particular, our proposed framework gives a generalization bound for consistency regularization in general cases. We also provide instantiations for linear regression, logistic regression, two-layer neural networks, and expansion-based data augmentations. When specialized to linear regression/logistic regression, it shows that consistency regularization yields a strictly smaller generalization error than ERM with augmented data. We also provide apples-to-apples empirical comparisons between augmented ERM and consistency regularization. These together demonstrate the superior efficacy of consistency regularization.
Reproducibility Statement Our main theoretical results, including problem setup and (simplified) theorem statements are in Sections 3 and 4. The formal theorem statements along with the proofs can be found in Appendices A and B. We present empirical results in Section 5, and the detailed experiment setup is in Appendix D. We also submit our experiment code in the supplementary material.

heading: A PROOFS FOR BOUNDED LOSS AND LINEAR REGRESSION
text: A.1 PROOF FOR DAC ON LINEAR REGRESSION For fixed Ã(X), we recall that daug = rank ( Ã(X)− M̃X ) since there is no randomness in Ã,X
in fix design setting. Assuming that Ã(X) admits full column rank, we have the following theorem on the excess risk of DAC and ERM: Theorem 6 (Formal restatement of Theorem 2 on linear regression.). Learning with DAC regularization, we have E [ L(θ̂dac)− L(θ∗) ] =
(d−daug)σ2 N , while learning with ERM directly on the augmented dataset, we have E [ L(θ̂da−erm)− L(θ∗) ] =
(d−daug+d′)σ2 N . d ′ is defined as
d′ , tr ( M̃> ( HÃ(X) −PS ) M̃ )
1 + α , where d′ ∈ [0, daug] with HÃ(X) = Ã(X) ( Ã(X)>Ã(X) )−1 Ã(X)> and PS ∈ R(α+1)N×(α+1)N is the projection matrix to S, and S is defined to be S ,{ M̃Xθ | ∀θ ∈ Rd, s.t. ( Ã(X)− M̃X ) θ = 0 } . Proof. With L(θ) , 1(1+α)N ∥∥∥Ã(X)θ − Ã(X)θ∗∥∥∥2
2 , the excess risk of ERM on the augmented
training set satisfies that: E [ L(θ̂da−erm) ] = 1 (1 + α)N E [∥∥∥Ã(X)θ̂da−erm − Ã(X)θ∗∥∥∥2 2 ] = 1 (1 + α)N E [∥∥∥Ã(X)(Ã(X)>Ã(X))−1Ã(X)>(Ã(X)θ∗ + M̃ )− Ã(X)θ∗∥∥∥2 2
] = 1 (1 + α)N E [∥∥∥HÃ(X)Ã(X)θ∗ +HÃ(X)M̃ − Ã(X)θ∗∥∥∥2 2
] = 1 (1 + α)N E [∥∥∥HÃ(X)M̃ ∥∥∥2 2
] = 1 (1 + α)N E [ tr( >M̃>HÃ(X)M̃ )
] = σ2 (1 + α)N tr ( M̃>HÃ(X)M̃ ) .
Let CÃ(X) and CM̃ denote the column space of Ã(X) and M̃, respectively. Notice that S is a subspace of both CÃ(X) and CM̃. Observing that daug = rank ( Ã(X)− M̃X ) = rank (PS), we have
E [ L(θ̂da−erm) ] =
σ2 (1 + α)N E [ tr(M̃>HÃ(X)M̃) ] = σ2 (1 + α)N E [ tr(M̃>PSM̃) ] + σ2 (1 + α)N E [ tr(M̃>(HÃ(X) −PS)M̃)
] = σ2 (1 + α)N E [ tr(M̃>PSM̃) ] + σ2 N · E [ tr(M̃>(HÃ(X) −PS)M̃) 1 + α ]
By the data augmentation consistency constraint, we are essentially solving the linear regression on the (d − daug)-dimensional space { θ | (Ã(X)− M̃X)θ = 0 } . The rest of proof is identical to
standard regression analysis, with features first projected to S:
E [ L(θ̂dac) ] =
1 (1 + α)N E [∥∥∥Ã(X)θ̂dac − Ã(X)θ∗∥∥∥2 2 ] = 1 (1 + α)N E [∥∥∥Ã(X)(Ã(X)>Ã(X))−1Ã(X)>PS(Ã(X)θ∗ + M̃ )− Ã(X)θ∗∥∥∥2 2
] = 1 (1 + α)N E [∥∥∥HÃ(X)PSÃ(X)θ∗ +HÃ(X)PSM̃ − Ã(X)θ∗∥∥∥2 2
] ( ∵ Ã(X)θ∗ ∈ S, and HÃ(X)PS = PS since S ⊆ CÃ(X)
) = 1 (1 + α)N E [∥∥∥PSM̃ ∥∥∥2 2
] = σ2 (1 + α)N E [ tr(M̃>PSM̃)
] = (d− daug)σ2
N .

heading: B APPLICATIONS OF LEARNING WITH DAC
text: To instantiate our general result on the DAC regularization, we start with a concrete application of Proposition 8 on the logistic regression problem with bounded loss (Section 4.1, Appendix B.1), followed by an extension to the unbounded square loss (Section 4.2, Appendix B.2). Subsequently, we discuss an alternative notion of data augmentations based on expansion for the classification problems (Section 4.3, Appendix B.3). Finally, we present a supplementary example for the domain adaptation in linear regression (Appendix B.4).
Before diving into the concrete applications, we recall the general setting, and introduce some additional notations used throughout the formal analysis.
DAC regularization with unlabeled data. Since the DAC regularization leverages only on the unlabeled observable features but not their labels, the unlabeled training set in the DAC regularizer and the labeled training set in the first term of Equation (1) for label learning can be considered separately. For clarification, in the formal analysis, we distinguish the labeled training set (X,y) ∈ Xn × Yn from the unlabeled samples Xu ∈ XN (possibly with different sizes N ≥ n), while both sample sets are drawn i.i.d. from P ∗. Particularly, in the supervised learning setting, the DAC regularization is based on the observables from the labeled training set such that Xu = X (N = n). While in the semi-supervised learning setting, Xu can be N unlabeled observations drawn i.i.d. from the marginal distribution P ∗ (x).
For the DAC regularization, we denote the augmentation of the unlabeled samples (excluding the original samples Xu, in contrast to the augmented sample Ã(X) in the main text) as
Â(Xu) = [ xu1,1; · · · ; xuN,1; · · · ; xu1,α; · · · ; xuN,α ] ∈ XαN ,
where for each i ∈ [N ], { xui,j } j∈[α] is a set of α augmentations generated from x u i , and let M ∈ RαN×N be the vertical stack of α N × N identity matrices. Then analogously, with the unlabeled training set Xu, we can quantify the strength of the data augmentations Â with
d̂aug , rank ( Â(Xu)−MXu ) = rank ( Ã(Xu)− M̃Xu ) ,
such that 0 ≤ d̂aug ≤ min (d, αN) can be intuitively interpreted as the number of dimensions in the span of the unlabeled samples, Row(Xu), perturbed by Â. Moreover, we denote N as the (d− d̂aug)-dimensional null space of Â(Xu)−MXu, and PN as the projection onto N such that
PN , Id − ( Â(Xu)−MXu )† ( Â(Xu)−MXu ) .
Correspondingly, let N⊥ be the orthogonal complement of N , and P⊥N be the projection onto N⊥ such that P⊥N = Id −PN . Then by recalling Definition 2, we have the following: Proposition 7. For any δ ∈ (0, 1), with probability at least 1− δ,
rank ( P⊥N ) = dim ( N⊥ ) = d̂aug ≥ daug(δ),
rank (PN ) = dim (N ) = d− d̂aug ≤ d− daug(δ).
Furthermore, for daug , daug (1/n), with high probability, d̂aug ≥ daug and d− d̂aug ≤ d− daug.
In terms of (X,y) and Xu, the regularization formulation in Equation (1) can be restated as,
argmin h∈H n∑ i=1 l(h(xi), yi) + λ α∑ j=1 N∑ i=1 % ( φh(x u i ), φh(x u i,j) )
︸ ︷︷ ︸ DAC regularizer
,
and with the notation of Â, the corresponding DAC operator is given by T dacÂ,Xu(H) , { h ∈ H | φh(xui ) = φh(xui,j), ∀i ∈ [N ], j ∈ [α] } ,
where T dac Â,Xu and T dac Ã,Xu are equivalent by construction.
Marginal distribution and training set. Here we formally state the common regularity conditions for the logistic regression (Section 4.1) and the two-layer neural network (Section 4.2) examples in Assumption 1 and Assumption 2, where we assume X ⊆ Rd. Assumption 1 (Regularity of marginal distribution). Let x ∼ P ∗(x) be zero-mean E[x] = 0, with the covairance E[xx>] = Σx 0. We assume that (Σ−1/2x x) is ρ2-subgaussian 1, and there exist constants C ≥ c = Θ(1) such that cId 4 Σx 4 CId. Assumption 2 (Sufficient labeled data). For (X,y) ∈ Xn × Yn, with respect to Xu and Â (Xu) that characterize d̂aug, we assume n ρ4 ( d− d̂aug ) .
For a B-bounded loss function l : Y × Y → R (i.e., 0 ≤ l ≤ B) such that for all y ∈ Y , l(·, y) : Y → R is Cl-Lipschitz, we have the following: Proposition 8 (Formal restatement of Proposition 1 on DAC with bounded loss). Learning with DAC regularization (Equation (2)), for a fixed T dac
Â,Xu (H) and any δ ∈ (0, 1), with probability at
least 1− δ, we have L(ĥdac)− L(h∗) ≤ 4Cl ·Rn(T dacÂ,Xu(H)) + √ 2B2 log(2/δ)
n ,
where Rn(T dacÂ,Xu(H)) represents the Rademacher complexity of T dac Â,Xu (H).
Proof of Proposition 8. We first decompose the expected excess risk as L(ĥdac)− L(h∗) = ( L(ĥdac)− L̂(ĥdac) ) + ( L̂(ĥdac)− L̂(h∗) ) + ( L̂(h∗)− L(h∗) ) ,
where L̂(ĥdac) − L̂(h∗) ≤ 0 by the basic inequality, and as a consequence, for a fixed Ho = T dac Â,Xu (H),
L(ĥdac)− L(h∗) ≤ 2 sup h∈Tdac
Â,Xu (H)
∣∣∣L(h)− L̂(h)∣∣∣ = 2 sup h∈Ho ∣∣∣L(h)− L̂(h)∣∣∣ . We denote g+(X,y) = suph∈Ho : L(h)− L̂(h) and g −(X,y) = suph∈Ho : −L(h) + L̂(h). Then,
P [ L(ĥdac)− L(h∗) ≥ ] ≤ P [ g+(X,y) ≥
2
] + P [ g−(X,y) ≥
2
] .
1A random vector v ∈ Rd is ρ2-subgaussian if for any unit vector u ∈ Sd−1, u>v is ρ2-subgaussian, E [ exp(s · u>v) ] ≤ exp ( s2ρ2/2 ) .
We will derive a tail bound for g+(X,y) with the standard inequalities and symmetrization argument Wainwright (2019); Bartlett & Mendelson (2003), while the analogous statement holds for g−(X,y).
Let (X(1),y(1)) be a sample set generated by replacing an arbitrary observation in (X,y) with any (x, y) ∈ X × Y . Since l is B-bounded, we have ∣∣g+(X,y)− g+(X(1),y(1))∣∣ ≤ B/n. Leveraging the McDiarmid’s inequality Bartlett & Mendelson (2003),
P [ g+(X,y) ≥ E[g+(X,y)] + t ] ≤ exp ( −2nt 2
B2
) .
For an arbitrary sample set (X,y), let L̂(X,y) (h) = 1n ∑n i=1 l (h(xi), yi) be the empirical risk of h with respect to (X,y). Then, by a classical symmetrization argument (e.g., proof of Wainwright (2019) Theorem 4.10), we can bound the expectation: for an independent sample set (X′,y′) ∈ Xn × Yn drawn i.i.d. from P ∗,
E [ g+(X,y) ] =E(X,y) [ sup h∈Ho L(h)− L̂(X,y)(h) ]
=E(X,y) [
sup h∈Ho
E(X′,y′) [ L̂(X′,y′)(h) ] − L̂(X,y)(h) ] =E(X,y) [ sup h∈Ho E(X′,y′) [ L̂(X′,y′)(h)− L̂(X,y)(h)
∣∣∣ (X,y)]] ≤E(X,y) [ E(X′,y′) [ sup h∈Ho L̂(X′,y′)(h)− L̂(X,y)(h) ∣∣∣∣ (X,y)]]
(Law of iterated conditional expectation) =E(X,y,X′,y′) [
sup h∈Ho
L̂(X′,y′)(h)− L̂(X,y)(h) ]
Since (X,y) and (X′,y′) are independent and identically distributed, we can introduce i.i.d. Rademacher random variables r = {ri ∈ {−1,+1} | i ∈ [n]} (independent of both (X,y) and (X′,y′)) such that
E [ g+(X,y) ] ≤E(X,y,X′,y′,r) [ sup h∈Ho 1 n n∑ i=1 ri · (l (h (x′i) , y′i)− l (h (xi) , yi)) ]
≤2 E(X,y,r) [ sup h∈Ho 1 n n∑ i=1 ri · l (h (xi) , yi) ] ≤2 Rn (l ◦ Ho)
where l ◦ Ho = {l(h(·), ·) : X × Y → R : h ∈ Ho} is the loss function class. Analogously, E[g−(X,y)] ≤ 2Rn (l ◦ Ho). Therefore, with probability at least 1− δ,
L(ĥdac)− L(h∗) ≤ 4Rn(l ◦ Ho) + √ 2B2 log(2/δ)
n
Finally, since l(·, y) is Cl-Lipschitz for all y ∈ Y , by Ledoux & Talagrand (2013) Theorem 4.12, we have Rn (l ◦ Ho) ≤ Cl ·Rn (Ho).
B.1 FORMAL RESULT ON LOGISTIC REGRESSION For the logistic regression problem in Section 4.1, with X = { x ∈ Rd ∣∣ ‖x‖2 ≤ D}, Y = {0, 1}, training with the DAC regularization can be formulated explicitly as
θ̂dac = argmin θ∈Rd
1
n n∑ i=1 l ( θ>xi, yi ) s.t. ‖θ‖2 ≤ C0, Â (X u)θ = MXuθ,
and yields ĥdac(x) , x>θ̂dac.
Theorem 9 (Formal restatement of Theorem 3 on logistic regression with DAC). Let E [
1 n ∑n i=1 ‖PNxi‖ 2 2 ∣∣∣PN ] ≤ C2N for some CN > 0. Then, learning logistic regression with the DAC regularization h(xui ) = h(x u i,j) yields that, for any δ ∈ (0, 1), with probability at least 1− δ:
L(ĥdac)− L(h∗) . C0CN + C0D √ log (1/δ)√
n , where under Assumption 1 and Assumption 2, CN . √ d− daug (δ/2).
Proof of Theorem 9. Notice that the logistic loss l(·, y) is 2-Lipschitz for all y ∈ Y , as ∂l(z,y)∂z = σ(z)−y, whose absolute value is bounded by 2. Meanwhile, with ‖θ‖2 ≤ C0 and ‖x‖2 ≤ D for all θ and x, the logistic loss is also bounded: l ( θ>x, y ) ≤ log 2+C0D. Then, applying Proposition 8, we have that for any δ ∈ (0, 1), with probability at least 1− δ/2,
L(ĥdac)− L(h∗) . Rn ( T dacÂ,Xu(H) ) + C0D √ log(1/δ)
n .
It left to bound the Rademacher complexity of T dac Â,Xu (H). First notice that the sigmoid function σ(·) is a bijective function, the data augmentation consistency constraints are equivalent to(
Â(Xu)−MXu ) θ = 0.
Thus, we have T dacÂ,Xu(H) = { h(x) = θ>x ∣∣ θ ∈ N , ‖θ‖2 ≤ C0} , with which we are ready to bound the Rademacher complexity of T dac
Â,Xu (H).
For the emprical Rademacher complexity, we have
R̂X ( T dacÂ,Xu(H) ) = 1 n E i∼Rad( 12 )  sup θ∈Tdac
Â,Xu (H) n∑ i=1 iθ >xi  = 1
n E i∼Rad( 12 ) [ sup θ∈H n∑ i=1 iθ >PNxi ]
= C0 n E i∼Rad( 12 ) [∥∥∥∥∥ n∑ i=1 iPNxi ∥∥∥∥∥ 2 ]
≤C0 n √√√√E i∼Rad( 12 ) n∑ i=1 ‖ iPNxi‖22
= C0 n √√√√ n∑ i=1 ‖PNxi‖22
= C0√ n
√ tr ( 1
n PNX>XPN
) .
Converting this to the population Rademacher complexity, we take expectation over X, while conditioned on PN , and recall Jensen’s inequality,
Rn ( T dacÂ,Xu(H) ) ≤ C0√ n E [√ tr ( 1 n PNX>XPN ) ∣∣∣∣∣ PN ]
≤ C0√ n
√ E [ tr ( 1
n PNX>XPN ) ∣∣∣∣ PN] = C0CN√
n .
Leveraging Lemma 5, we have that under Assumption 1 and Assumption 2, conditioned on PN , with high probability over X ∼ P ∗,∥∥∥∥ 1nPNX>XPN ∥∥∥∥ 2 ≤ 1.1C . 1
Then we can find some CN > 0 with 1n ∑n i=1 ‖PNxi‖ 2 2 ≤ C2N such that,
C2N ≤ ( d− d̂aug ) · ∥∥∥∥ 1nPNX>XPN ∥∥∥∥ 2 . d− d̂aug.
By Proposition 7, we have CN ≤ √ d− daug (δ/2) with probability at least 1− δ/2.
To obtain Theorem 3, we leverage the union bound and suppress the constants such that, with probability at least 1− δ,
L(ĥdac)− L(h∗) . √ d− daug (δ/2)
n +
√ log(1/δ)
n . (4)
Finally, taking δ = 2/n and applying the Jensen’s inequality to the two terms in Equation (4) complete the proof.
B.2 FORMAL RESULT ON TWO-LAYER NEURAL NETWORK
In the two-layer neural network regression setting described in Section 4.2, training with the DAC regularization can be formulated explicitly as
B̂dac, ŵdac = argmin B∈Rd×q,w∈Rq
1
2n ∥∥y − (XB)+ w∥∥22 s.t. B = [b1 . . .bk . . .bq] , bk ∈ Sd−1 ∀ k ∈ [q], ‖w‖1 ≤ Cw(
Â (Xu) B )
+ = (MXuB)+ ,
and yields ĥdac(x) , (x>B̂dac)+ŵdac. Theorem 10 (Formal restatement of Theorem 4 on two-layer neural network with DAC). Sampling from P ∗ that follows Assumption 1, let the augmented training set Â (Xu) satisfy (a) αN ≥ 4d̂aug, (b) Â(Xu) − MXu admits an absolutely continuous distribution over N⊥, and P ∗ fulfills (c) E [
1 n ∑n i=1 ‖PNxi‖ 2 2 ∣∣∣PN ] ≤ C2N for some CN > 0. Then, learning the two-layer ReLU network with the DAC regularization on ( (xui ) > B ) + = (( xui,j )> B ) + gives that, with high probability,
L ( ĥdac ) − L (h∗) . σCwCN√
n , where under Assumption 1 and Assumption 2, CN . √ d− daug (δ) with probability at least 1− δ.
Lemma 1. Under the assumptions in Theorem 10, every size-d̂aug subset of rows in Â(Xu)−MXu is linearly independent almost surely.
Proof of Lemma 1. Since αN > d̂aug, it is sufficient to show that a random matrix with an absolutely continuous distribution is totally invertible 2 almost surely.
It is known that for any dimension m ∈ N, an m × m square matrix S is singular if det(S) = 0 where entries of S lie within the roots of the polynomial equation specified by the determinant. Therefore, the set of all singular matrices in Rm×m has Lebesgue measure zero, λ ({S ∈ Rm×m | det(S) = 0}) = 0. Then, for an absolutely continuous probability measure µ with respect to λ, we also have
Pµ [ S ∈ Rm×m is singular ] = µ ({ S ∈ Rm×m ∣∣ det(S) = 0}) = 0. Since a general matrix R contains only finite number of submatrices, when R is drawn from an absolutely continuous distribution, by the union bound, P [R cotains a singular submatrix] = 0. That is, R is totally invertible almost surely.
2A matrix is totally invertible if all its square submatrices are invertible.
Lemma 2. Under the assumptions in Theorem 10, the hidden layer in the two-layer ReLU network learns N , the invariant subspace under data augmentations : with high probability,(
x>B̂dac ) + = ( x>PN B̂ dac ) + ∀ x ∈ X .
Proof of Lemma 2. We will show that for all bk = PNbk + P⊥Nbk, k ∈ [q], P⊥Nbk = 0 with high probability, which then implies that given any x ∈ X , (x>bk)+ = (x>PNbk)+ for all k ∈ [q].
For any k ∈ [q] associated with an arbitrary fixed bk ∈ Sd−1, let Xuk , XukPN +XukP⊥N ∈ XNk be the inclusion-wisely maximum row subset of Xu such that Xukbk > 0 element-wisely. Meanwhile, we denote Â(Xuk) = MkXukPN + Â(Xuk)P⊥N ∈ XαNk as the augmentation of Xuk where Mk ∈ RαNk×Nk is the vertical stack of α identity matrices with size Nk ×Nk. Then the DAC constraint implies that (Â(Xuk)−MkXuk)P⊥Nbk = 0.
With Assumption 1, for a fixed bk ∈ Sd−1, P[x>bk > 0] = 12 . Then, with the Chernoff bound, P [ Nk < N 2 − t ] ≤ e− 2t 2 N ,
which implies that, Nk ≥ N4 with high probability.
Leveraging the assumptions in Theorem 10, αN ≥ 4d̂aug implies that αNk ≥ d̂aug. Therefore by Lemma 1, Row ( Â(Xuk)−MkXuk ) = N⊥ with probability 1. Thus, (Â(Xuk)−MkXuk)P⊥Nbk = 0 enforces that P⊥Nbk = 0.
Proof of Theorem 10. Lemma 2 implies that (XB̂dac)+ = (XPN B̂dac)+, and therefore, T dacÂ,Xu(H) = { h(x) = (x>B)+w | B = [b1 . . .bq],bk ∈ Sd−1, (XB)+ = (XPNB)+, ‖w‖1 ≤ Cw } .
In other words, the DAC regularization reduces the feasible set for B such that
B ∈ B , {B = [b1 . . .bq] | ‖bk‖ = 1 ∀ k ∈ [q], (XB)+ = (XPNB)+} , ‖w‖1 ≤ Cw. Meanwhile, for the square loss, the corresponding excess risk is given by
L ( ĥdac ) − L (h∗) = EX [ 1
2n ∥∥∥(XB̂dac)+ŵdac − (XB∗)+w∗∥∥∥2 2 ] .
Leveraging Equation (21) and (22) in Du et al. (2020), since (B∗,w∗) is feasible under the constraint, by the basic inequality,∥∥∥y − (XB̂dac)+ŵdac∥∥∥2
2 ≤ ‖y − (XB∗)+w∗‖22 , (5)
where B̂dac,B∗ ∈ B and ∥∥ŵdac∥∥
1 ≤ Cw.
Analogously to the Rademacher complexities for the bounded losses, for the square loss, we recall the definitions of the Gaussian complexities of a vector-valued function class Φ = {φ : X → Rq},
ĜX(Φ) , E gik∼N (0,1) i.i.d. [ sup φ∈Φ 1 n n∑ i=1 q∑ k=1 gikφk(xi) ] , Gn(Φ) , E [ ĜX(Φ) ] . (6)
In terms of the Gaussian complexity, for a fixed T dac Â,Xu (H), EX [ 1
2n ∥∥∥(XB̂dac)+ŵdac − (XB∗)+w∗∥∥∥2 2 ∣∣∣∣Xu] ≤EX [ z> ( 1
n
( (XB̂dac)+ŵ dac − (XB∗)+w∗ )) ∣∣∣∣Xu]
.σ · EX [ ĜX ( T dacÂ,Xu(H) ) ∣∣∣Xu]
where the empirical Gaussian complexity can be upper bounded by
ĜX ( T dacÂ,Xu(H) ) = E
g∼N (0,In)
[ sup
B∈B,‖w‖1≤R
1 n g>(XB)+w
]
≤Cw n E g [ sup B∈B ∥∥(XB)>+g∥∥∞] = Cw n E g [ sup b∈Sd−1 g> (XPNb)+ ] (Lemma 6, (·)+ is 1-Lipschitz)
≤Cw n E g
[ sup
b∈Sd−1 g>XPNb ] = Cw n E g
[∥∥PNX>g∥∥2] ≤Cw n ( E g
[∥∥PNX>g∥∥22])1/2 = Cw n √ tr(PNX>XPN )
= Cw√ n √√√√ 1 n n∑ i=1 ‖PNxi‖22.
Taking expectation over X ∼ P ∗, we have that for a fixed T dac Â,Xu (H) (i.e., conditioned on PN ),
Gn ( T dacÂ,Xu(H) ) ≤ CwCN√
n .
Leveraging Lemma 5, we have that under Assumption 1 and Assumption 2, conditioned on PN , with high probability over X ∼ P ∗,∥∥∥∥ 1nPNX>XPN ∥∥∥∥ 2 ≤ 1.1C . 1
Then we can find some CN > 0 with 1n ∑n i=1 ‖PNxi‖ 2 2 ≤ C2N such that,
C2N ≤ ( d− d̂aug ) · ∥∥∥∥ 1nPNX>XPN ∥∥∥∥ 2 . d− d̂aug.
By Proposition 7, we have CN ≤ √ d− daug (δ) with probability at least 1− δ.
B.3 FORML RESULTS ON EXPANSION-BASED DATA AUGMENTATION
For the formal analysis of the expansion-based data augmentations, we first introduce some helpful notations.
With respect to an augmentation function A : X → 2X fulfilling the conditions in Definition 4, we define the neighborhood for an arbitrary x ∈ X , as well as for any S ⊆ X , such that,
NB(x) , { x′ ∈ X ∣∣ A(x) ∩ A(x′) 6= ∅} , NB(S) , ∪x∈SNB(x). Then Definition 4(b) implies that the corresponding neighborhood function NB : X → 2X ofA has non-trivial expansion:
∅ ( S ∩ Xk ( Xk ⇒ (NB(S)\S) ∩ Xk 6= ∅ ∀ k ∈ [K], S ⊆ X .
Intuitively, the non-trivial expansion guarantees that the neighborhood of any proper subset of a class always enlarges the subset within the class. Remark 2. The ground truth classifier is invariant throughout the neighborhood: for any augmentation function A : X → 2X satisfying the conditions in Definition 4, the corresponding neighborhood function satisfies that, given any x ∈ X , h∗ (x) = h∗ (x′) for all x′ ∈ NB(x).
Notice that the previous data augmentation strength d̂aug (Definition 2) is not well defined for Definition 4 (since X needs not be a subset of Rd). Therefore we need a new notion of data augmentation strength. Remark 3. The strength of expansion-based data augmentations (Definition 4) is characterized by the size of A(x). Intuitively, for any x ∈ X , the augmentations can be stronger (i.e., there exists x′ ∈ A(x) that is more different from x) if A(x) is inclusion-wisely larger.
In addition, for an arbitrary classifier h ∈ H, we denote the majority label with respect to h for each class,
ŷk , argmax y∈[K]
Px [ h(x) = y ∣∣ x ∈ Xk] ∀ k ∈ [K], along with the respective class-wise local and global minority sets,
Mk , { x ∈ Xk ∣∣ h(x) 6= ŷk} ( Xk ∀ k ∈ [K], M , K⋃ k=1 Mk.
Infinite unlabeled data. As a warm-up, we simplify the setting by enforcing consistency over the population such that learning with the DAC constraints can be expressed as,
ĥdacX , argmin h∈H
L̂dac01 (h) = 1
n n∑ i=1 1 {h (xi) 6= h∗ (xi)}
s.t. h(x) = h (x′) ∀ x ∈ X , x′ ∈ A(x).
We can also formulate algorithm in terms of the DAC operator,
ĥdacX , argmin h∈TdacA,X (H) L̂dac01 (h), T dac A,X , {h ∈ H | h(x) = h(x′) ∀ x ∈ X , x′ ∈ A(x)} .
Lemma 3. Given any h ∈ T dacA,X (H), for each k ∈ [K], there exists some ŷk ∈ [K] such that h(x) = ŷk for all x ∈ Xk.
Proof of Lemma 3. It is sufficient to show that Mk = ∅ for all k ∈ [K]. By contradiction, suppose Mk 6= ∅. Then by the non-trivial expansion assumption in Definition 4, (NB(Mk)\Mk) ∩ Xk 6= ∅. That is, there exists some x ∈ (NB(Mk)\Mk) ∩ Xk. But on one hand, x ∈ NB(Mk) implies that we can find some x′ ∈ Mk and x′′ ∈ A (x) ∩ A (x′). Therefore by the consistency constraint h ∈ T dacA,X (H), h(x′′) = h(x) = h(x′). On the other hand, x ∈ Xk\Mk implies that h(x) = ŷk 6= h(x′), and leads to a contradiction.
Restating Theorem 5 with the formal notations in the appendix: with high probability,
L01 ( ĥdacX ) − L01 (h∗) ≤ K logK + log n
n .
Proof of Theorem 5. By Lemma 3, since
T dacA,X (H) ⊆ {h ∈ H | h(x) = ŷk ∀ x ∈ Xk} where {ŷk ∈ [K]}k∈[K] , the consistency constraint yields a finite feasible classifier class with ∣∣T dacA,X (H)∣∣ = K! ≤ KK .
Meanwhile, since A(x) ⊆ {x′ ∈ X | h∗(x) = h∗(x′)}, by construction, we know that T dacA,X (H) is realizable (i.e., h∗ ∈ T dacA,X (H) such that L̂dac01 (h∗) = 0). Therefore,
P [ L01 ( ĥdacX ) > ] ≤ P [ ∃ h ∈ T dacA,X (H) ∣∣∣ L01 (h) > ∧ L̂dac01 (h) = 0] , where for every classifier h ∈ T dacA,X (H),
P [ L01 (h) > ∧ L̂dac01 (h) = 0 ] ≤ (1− )n ≤ e− n.
Then by the union bound, we have P [ L01 ( ĥdacX ) > ] ≤ ∑ h∈TdacA,X (H) P [ L01 (h) > ∧ L̂dac01 (h) = 0 ] ≤ ∣∣T dacA,X (H)∣∣ · e− n.
The proof is completed by upper bounding the above, P [ L01 ( ĥdacX ) > ] ≤ 1/n, when taking
= log ∣∣T dacA,X (H)∣∣+ log n
n ≤ K logK + log n n ,
and observing that L01 (h∗) = 0.
Finite unlabeled data. For the finite unlabeled data case, we start by introducing some additional concepts and notations. We concretize the classifier class H with a proper function class F ⊆ { f : X → RK } such that H = { h(x) , argmaxk∈[K] f(x)k ∣∣∣ f ∈ F}. Specifically, we adapt the existing setting in Wei et al. (2021); Cai et al. (2021), and consider F as a class of fully connected neural networks. To constrain the feasible hypothesis class through the DAC regularization with finite unlabeled observations Xu = [xu1 , . . . ,x u N ] >, we leverage, from Wei & Ma (2021), the notion of all-layer-margin, m : F × X × Y → R≥0, that measures the maximum possible perturbation in all layers of f while maintaining the prediction y. Precisely, given any f ∈ F such that f (x) = Wpϕ (. . . ϕ (W1x) . . . ) for some activation function ϕ : R → R and parameters{ Wι ∈ Rdι×dι−1 }p ι=1
, we can write f = f2p−1 ◦ · · · ◦ f1 where f2ι−1(x) = Wιx for all ι ∈ [p] and f2ι(z) = ϕ(z) for ι ∈ [p− 1]. For an arbitrary set of perturbation vectors δ = (δ1, . . . , δ2p−1) such that δ2ι−1, δ2ι ∈ Rdι for all ι, let f(x, δ) be the perturbed neural network defined recursively such that
z̃1 = f1 (x) + ‖x‖2 δ1, z̃ι = fι (z̃ι−1) + ‖z̃ι−1‖2 δι ∀ ι = 2, . . . , 2p− 1, f(x, δ) = z̃2p−1.
The all-layer-marginm(f,x, y) measures the minimum norm of the perturbation δ such that f(x, δ) fails to provide the classification y,
m(f,x, y) , min δ=(δ1,...,δ2p−1) √√√√2p−1∑ ι=1 ‖δι‖22 s.t. argmax k∈[K] f(x, δ)k 6= y. (7)
With the notion of all-layer-margin established, for any A : X → 2X that satisfies conditions in Definition 4, the robust margin is defined as
mA(f,x) , sup x′∈A(x) m
( f,x′, argmax
k∈[k] f(x)k
) .
With merely finite unlabeled data, comparing to enforcing consistency over population, we need stronger assumptions on data augmentations in addition to the ones in Definition 4, as specified in Definition 5 below. Definition 5 ((F , τ)-expansion-based data augmentation). With respect to the given function class F and some proper constant τ > 0, Let A : X → 2X be a function that satisfies conditions in Definition 4, and additionally,
sup f∈F inf x∈X mA(f,x) > τ. (8)
Then for any sample x ∈ X , x′ ∈ X is a (F , τ)-expansion-based data augmentation of x induced by A if x′ ∈ A(x).
Remark 4. The existence of the (F , τ)-expansion-based data augmentations relies on the suitable choice of τ with respect to the given F . For a fixed F , as τ increases, Equation (8) imposes stronger assumption on A (i.e., A(x) is forced to be inclusion-wisely smaller, where A becomes weaker), while better theoretical guarantee (Theorem 12) can be achieved.
We consider a class of p-layer fully connected neural networks with maximum width q, F = { f : X → RK ∣∣ f = f2p−1 ◦ · · · ◦ f1, f2ι−1(x) = Wιx, f2ι(z) = ϕ(z) ∀ ι = 1, . . . , p} , where with Wι ∈ Rdι×dι−1 for all ι ∈ [p], q , maxι=0,...,p dι. The goal is to learn a classifier ĥdacXu = argmaxk∈[K] f̂ dac n,N (x)k where f̂ dac n,N ∈ F is a fully connected neural network. With respect to F , we choose a suitably large τ > 0 such that there exists aA : X → 2X fulfilling the conditions in Definition 5. To enforce sufficiently strong consistency of f with finite unlabeled samples, we incorporate the DAC regularization with a positive robust margin such that,
ĥdacXu , argmin h∈H
L̂dac01 (h) = 1
n n∑ i=1 1 {h (xi) 6= h∗ (xi)} (9)
s.t. mA(f,xui ) > τ ∀ i ∈ [N ].
In terms of the DAC operator, the algorithm can be restated as ĥdacXu , argminh∈TdacA,Xu (H) L̂ dac 01 (h) with
T dacA,Xu(H) , {h ∈ H |mA(f,xui ) > τ ∀ i ∈ [N ]} .
Definition 6 (Expansion assumptions, Wei et al. (2021); Cai et al. (2021)). The marginal distribution P ∗ (x) satisfies
(a) (q, ξ)-constant expansion if given any S ⊆ X with P ∗ (S) ≥ q and P ∗ (S ∩ Xk) ≤ 12 for all k ∈ [K], P ∗ (NB (S)) ≥ min {P ∗ (S) , ξ}+ P ∗ (S); (b) (a, c)-multiplicative expansion if for all k ∈ [K], given any S ⊆ X with P ∗ (S ∩ Xk) ≤ a, P ∗ (NB (S) ∩ Xk) ≥ min {c · P ∗ (S ∩ Xk) , 1}.
Proposition 11 (Wei et al. (2021) Theorem 3.7, Cai et al. (2021) Proposition 2.2). For any δ ∈ (0, 1), with probability at least 1− δ/2, there exists some µ such that
PP∗ [∃ x′ ∈ A(x) s.t. h(x) 6= h(x′)] ≤ µ ≤ Õ
(∑p ι=1 √ q ‖Wι‖F
τ √ N
+
√ log (1/δ) + p logN
N
)
for all h ∈ T dacA,Xu(H), where Õ (·) hides polylogarithmic factors in N and d. Theorem 12 (DAC with expansion-based data augmentations over finite samples). With proper choices of τ > 0, for any A : X → 2X inducing (F , τ)-expansion-based data augmentations, learning the classifier with DAC regularization, Equation (9), provides that, for any δ ∈ (0, 1), with probability at least 1− δ,
L01 ( ĥdacXu ) − L01 (h∗) ≤ 4R + √ 2 log(4/δ)
n , (10)
In specific, for some q < 12 , c > 1, with a sufficiently large unlabeled sample size N such that µ ≤ 14 min {c− 1, 1},
(a) when P ∗ (x) satisfies (q, 2µ)-constant expansion,
R ≤ √ 2K logK
n + 2K max {q, 2µ},
(b) while when P ∗ (x) satisfies ( 12 , c)-multiplicative expansion,
R ≤
√ 2K logK
n +
4Kµ
min {c− 1, 1} ,
where we recall from Proposition 11 that,
µ ≤ Õ
(∑p ι=1 √ q ‖Wι‖F
τ √ N
+
√ log (1/δ) + p logN
N
) .
Lemma 4 (Cai et al. (2021), Lemma A.1). For any h ∈ T dacA,Xu(H), when P ∗ satisfies
(a) (q, 2µ)-constant expansion with q < 12 , P ∗ (M) ≤ max {q, 2µ}; (b) ( 1 2 , c ) -multiplicative expansion with c > 1 + 4µ, P ∗ (M) ≤ max { 2µ c−1 , 2µ } .
Proof of Lemma 4. We start with the proof for Lemma 4 (a). By definition of Mk and ŷk, we know that Mk = M ∩ Xk ≤ 12 . Therefore, for any 0 < q < 1 2 , one of the following two cases holds:
(i) P ∗ (M) < q; (ii) P ∗ (M) ≥ q. Since P ∗ (M ∩ Xk) < 12 for all k ∈ [K] holds by construction, with the
(q, 2µ)-constant expansion, P ∗ (NB (M)) ≥ min {P ∗ (M) , 2µ}+ P ∗ (M). Meanwhile, since the ground truth classifier h∗ is invariant throughout the neighborhoods, NB (Mk)∩NB (Mk′) = ∅ for k 6= k′, and therefore NB (M) \M = ⋃K k=1 NB (Mk) \Mk with each NB (Mk) \Mk disjoint. Then, we observe that for each x ∈ NB (M) \M , here exists some k = h∗ (x) such that x ∈ NB (Mk) \Mk. x ∈ Xk\Mk implies that h (x) = ŷk, while x ∈ NB (Mk) suggests that there exists some x′ ∈ A (x) ∩ A (x′′) where x′′ ∈ Mk such that either h (x′) = ŷk and h (x′) 6= h (x′′) for x′ ∈ A (x′′), or h (x′) 6= ŷk and h (x′) 6= h (x) for x′ ∈ A (x). Therefore, we have
P ∗ (NB (M) \M) ≤ 2PP∗ [∃ x′ ∈ A(x) s.t. h(x) 6= h(x′)] ≤ 2µ. Moreover, since P ∗ (NB (M))− P ∗ (M) ≤ P ∗ (NB (M) \M) ≤ 2µ, we know that
min {P ∗ (M) , 2µ}+ P ∗ (M) ≤ P ∗ (NB (M)) ≤ P ∗ (M) + 2µ. That is, P ∗ (M) ≤ 2µ.
Overall, we have P ∗ (M) ≤ max {q, 2µ}. To show Lemma 4 (b), we recall from Wei et al. (2021) Lemma B.6 that for any c > 1 + 4µ,(
1 2 , c ) -multiplicative expansion implies ( 2µ c−1 , 2µ ) -constant expansion. Then leveraging the proof
for Lemma 4 (a), with q = 2µc−1 , we have P ∗ (M) ≤ max { 2µ c−1 , 2µ } .
Proof of Theorem 12. To show Equation (10), we leverage the proof of Proposition 8, and observe that B = 1 with the zero-one loss. Therefore, when conditioned on T dacA,Xu(H), for any δ ∈ (0, 1), with probability at least 1− δ/2,
L01 ( ĥdacXu ) − L01 (h∗) ≤ 4Rn ( l01 ◦ T dacA,Xu(H) ) + √ 2 log(4/δ)
n .
For the upper bounds of the Rademacher complexity, let µ̃ , suph∈TdacA,Xu (H) P ∗ (M) where M denotes the global minority set with respect to h ∈ T dacA,Xu(H). Lemma 4 suggests that
(a) when P ∗ satisfies (q, 2µ)-constant expansion for some q < 12 , µ̃ ≤ max {q, 2µ}; while (b) when P ∗ satisfies ( 12 , c)-multiplicative expansion for some c > 1 + 4µ, µ̃ ≤ 2µ min{c−1,1} .
Then, it is sufficient to show that, conditioned on T dacA,Xu(H),
Rn ( l01 ◦ T dacA,Xu(H) ) ≤ √ 2K logK
n + 2Kµ̃. (11)
To show this, we first consider a fixed set of n observations in X , X = [x1, . . . ,xn]> ∈ Xn. Let the number of distinct behaviors over X in T dacA,Xu(H) be
s ( T dacA,Xu(H),X ) , ∣∣{[h (x1) , . . . , h (xn)] ∣∣ h ∈ T dacA,Xu(H)}∣∣ .
Then, by the Massart’s finite lemma, the empirical rademacher complexity with respect to X is upper bounded by
R̂X ( l01 ◦ T dacA,Xu(H) ) ≤ √√√√2 log s(T dacA,Xu(H),X) n .
By the concavity of √ log (·), we know that,
Rn ( l01 ◦ T dacA,Xu(H) ) =EX [ R̂X ( l01 ◦ T dacA,Xu(H) )] ≤ EX  √√√√2 log s(T dacA,Xu(H),X)
n

≤ √√√√2 logEX [s(T dacA,Xu(H),X)] n . (12)
Since P ∗ (M) ≤ µ̃ ≤ 12 for all h ∈ T dac A,Xu(H), we have that, conditioned on T dacA,Xu(H),
EX [ s ( T dacA,Xu(H),X )] ≤ n∑ r=0 ( n r ) µ̃r (1− µ̃)n−r ·KK ·Kr
≤KK n∑ r=0 ( n r ) (µ̃K) r (1− µ̃)n−r =KK (1− µ̃+Kµ̃)n
≤KK · eKnµ̃.
Plugging this into Equation (12) yields Equation (11). Finally, the randomness in T dacA,Xu(H) is quantified by µ̃, µ, and upper bounded by Proposition 11.
B.4 SUPPLEMENTARY EXAMPLE: DOMAIN ADAPTATION
As a supplementary example, we demonstrate the possible failure of the ERM on augmented training set, and how the DAC regularization can serve as a remedy, with an illustrative linear regression problem in the domain adaptation setting: where the training samples are drawn from some source distribution P s, while the excess risk is tested over a related but different distribution P t, known as the target distribution. Specifically, assuming that EP s [y|x] and EP t [y|x] are distinct, but there exists some invariant feature subspace Xr ⊂ X such that P s [y|x ∈ Xr] = P t [y|x ∈ Xr], we aim to demonstrate the advantage of the DAC regularization over the ERM on augmented training set, with a provable separation in the respective excess risks.
Source and target distributions. Formally, the source and target distributions are concretized with the causal graph in Figure 4. For both P s and P t, the observable feature x is described via a linear generative model in terms of two latent features, the ‘invariant’ feature ζiv ∈ Rdiv and the ‘environmental’ feature ζe ∈ Rde :
x = g(ζiv, ζe) , S [ζiv; ζe] = Sivζiv + Seζe,
where S = [Siv,Se] ∈ Rd×(div+de) (div + de ≤ d) consists of orthonormal columns. Let the label y depends only on the invariant feature ζiv for both domains,
y = (θ∗) > x + z = (θ∗) > Sivζiv + z, z ∼ N ( 0, σ2 ) , z ⊥ ζiv,
for some θ∗ ∈ Range (Siv) such that P s [y|ζiv] = P t [y|ζiv], while the environmental feature ζe is conditioned on y, ζiv , (along with the Gaussian noise z), and varies across different domains e with EP s [y|x] 6= EP t [y|x]. In other words, with the square loss l(h(x), y) = 12 (h(x) − y)
2, the optimal hypotheses that minimize the expected excess risk over the source and target distributions are distinct. Therefore, learning via the ERM with training samples from P s can overfit the source distribution, in which scenario identifying the invariant feature subspace Range (Siv) becomes indispensable for achieving good generalization in the target domain.
Moreover, we assume the following regularity conditions on the source and target distributions: Assumption 3 (Regularity conditions for P s and P t). Let P s satisfy Assumption 1, and P t satisfy the following: let EP t [xx>] 0, and (a) for the invariant feature, ct,ivIdiv 4 EP t [ζivζ>iv] 4 Ct,ivIdiv for some Ct,iv ≥ ct,iv = Θ(1); (b) for the environmental feature, EP t [ζeζ>e ] < ct,eIde for some ct,e > 0, and EP t [z · ζe] = 0.
Training samples and data augmentations. For a fair comparison between learning with the DAC regularization and the ERM on augmented training set, we restrict to the supervised learning setting: Xu = X ∈ Xn. Recall that we denote the augmented training sets, including and excluding the original samples, respectively with
Ã(X) = [x1; · · · ; xn; x1,1; · · · ; xn,1; · · · ; x1,α; · · · ; xn,α] ∈ X (1+α)n, Â(X) = [x1,1; · · · ; xn,1; · · · ; x1,α; · · · ; xn,α] ∈ Xαn.
In particular, we consider a set of augmentations that only perturb the environmental feature ζe, while keep the invariant feature ζiv intact,
S>ivxi = S > ivxi,j , S > e xi 6= S>e xi,j ∀ i ∈ [n], j ∈ [α]. (13) We recall the notion d̂aug = rank ( Â (X)−MX ) = rank ( Ã (X)− M̃X ) (notice that 0 ≤
d̂aug ≤ de), and assume that X and Â(X) are representative enough:
Assumption 4 (Diversity of X and Â(X)). (X,y) ∈ Xn×Yn is sufficiently large with n ρ4div , θ∗ ∈ span {xi | i ∈ [n]}, and d̂aug = de.
Excess risks in target domain. Learning from the linear hypothesis class H ={ h(x) = θ>x ∣∣ θ ∈ Rd}, with the DAC regularization on h (xi) = h (xi,j), we have θ̂dac = argmin
θ∈Tdac Â,X (H)
1
2n ‖y −Xθ‖22 , T dac Â,X (H) =
{ h (x) = θ>x ∣∣∣ Â(X)θ = MXθ} , while with the ERM on augmented training set,
θ̂da−erm = argmin θ∈Rd
1
2(1 + α)n ∥∥∥M̃y − Ã(X)θ∥∥∥2 2 ,
where M and M̃ denote the vertical stacks of α and 1+α identity matrices of size n×n, respectively as denoted earlier.
We are interested in the excess risk on P t: Lt (θ) − Lt (θ∗) where Lt (θ) , EP t(x,y) [ 1 2 (y − x >θ)2 ] .
Theorem 13 (Domain adaptation with DAC). Under Assumption 3(a) and Assumption 4, θ̂dac satisfies that, with constant probability,
EP s [ Lt(θ̂ dac)− Lt(θ∗) ] .
σ2div n . (14)
Theorem 14 (Domain adaptation with ERM on augmented samples). Under Assumption 3 and Assumption 4, θ̂dac and θ̂da−erm satisfies that,
EP s [ Lt(θ̂ da−erm)− Lt(θ∗) ] ≥ EP s [ Lt(θ̂ dac)− Lt(θ∗) ] + ct,e · EERe, (15)
for some EERe > 0.
In contrast to θ̂dac where the DAC constraints enforce S>e θ̂ dac = 0 with a sufficiently diverse Â (X) (Assumption 4), the ERM on augmented training set fails to filter out the environmental feature in θ̂da−erm: S>e θ̂
da−erm 6= 0. As a consequence, the expected excess risk of θ̂da−erm in the target domain can be catastrophic when ct,e →∞, as instantiated by Example 2.
Proofs and instantiation. We first recall from the beginning of Appendix B that PN , Id − ( Â(X)−MX )† ( Â(X)−MX ) is the orthogonal projector onto the dimension-(d− d̂aug) null space of Â(X)−MX. Furthermore, let Piv , SivS>iv and Pe , SeS > e be the orthogonal projectors onto the invariant and environmental feature subspaces, respectively, such that x = Sivζiv + Seζe = (Piv + Pe) x for all x. Proof of Theorem 13. By construction Equation (13), ( Â(X)−MX ) Piv = 0, and it follows that
Piv 4 PN . Meanwhile from Assumption 4, d̂aug = de implies that dim (PN ) = div . Therefore, Piv = PN , and the data augmentation consistency constraints can be restated as
T dacÂ,X(H) , { h (x) = θ>x ∣∣ PNθ = θ} = {h (x) = θ>x ∣∣ Pivθ = θ} Then with θ∗ ∈ span {xi | i ∈ [n]} from Assumption 4,
θ̂dac − θ∗ = 1 n Σ̂†XivPivX >(XPivθ ∗ + z)− θ∗ = 1 n Σ̂†XivPivX >z,
where Σ̂Xiv , 1 nPivX >XPiv . Since θ̂dac − θ∗ ∈ Col (Siv), we have EP t [ z · x>Pe(θ̂dac − θ∗) ] = 0. Therefore, let Σx,t , EP t [xx>], with high probability,
EP s [ Lt(θ̂ dac)− Lt(θ∗) ] = EP s [ 1
2 ∥∥∥θ̂dac − θ∗∥∥∥2 Σx,t ] = tr ( 1
2n EP s
[ zz> ] EP s
[( 1
n PivX
>XPiv )†] Σx,t )
= tr
( σ2
2n EP s
[ Σ̂†Xiv ] Σx,t ) ≤ Ct,iv σ2 2n tr ( EP s [ Σ̂†Xiv ]) (Lemma 5, w.h.p.) . σ2 2n tr (( EP s [ Pivxx >Piv ])†) ≤ σ 2
2nc tr(Piv) . σ2div 2n .
Proof of Theorem 14. Let Σ̂Ã(X) , 1 (1+α)n Ã (X) > Ã (X). Then with θ∗ ∈ span {xi | i ∈ [n]} from Assumption 4, we have θ∗ = Σ̂† Ã(X) Σ̂Ã(X)θ ∗. Since θ∗ ∈ Col (Siv), M̃Xθ∗ = M̃XPivθ ∗ = Ã(X)θ∗. Then, the ERM on the augmented training set yields
θ̂da−erm − θ∗ = 1 (1 + α)n Σ̂† Ã(X) Ã(X)>M̃(Xθ∗ + z)− Σ̂† Ã(X) Σ̂Ã(X)θ ∗
= 1 (1 + α)n Σ̂† Ã(X) Ã(X)>M̃z.
Meanwhile with EP t [z · ζe] = 0 from Assumption 3, we have EP t [z ·Pex] = 0. Therefore, by recalling that Σx,t , EP t [xx>],
Lt(θ)− Lt(θ∗) = EP t(x) [ 1
2
( x>(θ − θ∗) )2 + z · x>Pe(θ − θ∗) ] = 1
2 ‖θ∗ − θ‖2Σx,t ,
such that the expected excess risk can be expressed as EP s [ Lt(θ̂ da−erm)− Lt(θ∗) ] = 1 2(1 + α)2n2 tr ( EP s [ Σ̂† Ã(X) ( Ã(X)>M̃zz>M̃>Ã(X) ) Σ̂† Ã(X) ] Σx,t ) ,
where let Σ̂Ã(Xe) , PeΣ̂Ã(X)Pe, EP s [ Σ̂† Ã(X) ( Ã(X)>M̃zz>M̃>Ã(X) ) Σ̂† Ã(X) ] < EP s [( PivΣ̂
† Ã(X) Piv + PeΣ̂ † Ã(X) Pe
) Ã(X)>M̃zz>M̃>Ã(X) ( PivΣ̂
† Ã(X) Piv + PeΣ̂ † Ã(X) Pe )] < σ2(1 + α)2n · EP s [ Σ̂†Xiv ] + EP s [ Σ̂† Ã(Xe) Ã(Xe)>M̃zz>M̃>Ã(Xe)Σ̂†Ã(Xe) ] .
We denote EERe , tr ( EP s [ 1
2(1 + α)2n2 Σ̂† Ã(Xe) Ã(Xe)>M̃zz>M̃>Ã(Xe)Σ̂†Ã(Xe)
]) ,
and observe that
EERe = EP s [ 1
2 ∥∥∥∥ 1(1 + α)nΣ̂†Ã(Xe)Ã(Xe)>M̃z ∥∥∥∥2
2
] > 0.
Finally, we complete the proof by partitioning the lower bound for the target expected excess risk of θ̂da−erm into the invariantand environmental parts such that
EP s [ Lt(θ̂ da−erm)− Lt(θ∗) ]
≥ tr ( σ2
2n EP s
[ Σ̂†Xiv ] Σx,t ) ︸ ︷︷ ︸
=E[Lt(θ̂dac)−Lt(θ∗)]
+ tr ( EP s [ 1
2(1 + α)2n2 Σ̂† Ã(Xe) Ã(Xe)>M̃zz>M̃>Ã(Xe)Σ̂†Ã(Xe)
] Σx,t ) ︸ ︷︷ ︸
expected excess risk from environmental feature subspace≥ct,e·EERe ≥ EP s [ Lt(θ̂ dac)− Lt(θ∗) ] + ct,e · EERe.
Now we construct a specific domain adaptation example with a large separation (i.e., proportional to de) in the target excess risk between learning with the DAC regularization (i.e., θ̂dac) and with the ERM on augmented training set (i.e., θ̂da−erm). Example 2. We consider P s and P t that follow the same set of relations in Figure 4, except for the distributions over e where P s (e) 6= P t (e). Precisely, let the environmental feature ζe depend on (ζiv, y, e):
ζe = sign ( y − (θ∗)> Sivζiv ) e = sign(z)e, z ∼ N (0, σ2), z ⊥ e,
where e ∼ N (0, Ide) for P s(e) and e ∼ N (0, σtIde) for P t(e), σt ≥ ct,e (recall ct,e from Assumption 3). Assume that the training set X is sufficiently large, n de + log (1/δ) for some given δ ∈ (0, 1). Augmenting X with a simple by common type of data augmentations – the linear transforms, we let
Ã(X) = [X; (XA1) ; . . . ; (XAα)] , Aj = Piv + ujv>j , uj ,vj ∈ Col (Se) ∀ j ∈ [α], and define
ν1 , max {1} ∪ {σmax(Aj) | j ∈ [α]} and ν2 , σmin  1 1 + α Id + α∑ j=1 Ak  ,
where σmin(·) and σmax(·) refer to the minimum and maximum singular values, respectively. Then under Assumption 3 and Assumption 4, with constant probability,
EP s [ Lt(θ̂ da−erm)− Lt(θ∗) ] & EP s [ Lt(θ̂ dac)− Lt(θ∗) ]
+ ct,e · σ2de 2n .
Proof of Example 2. With the specified distribution, for E = [e1; . . . ; en] ∈ Rn×de ,
Σ̂Ã(Xe) = 1
(1 + α)n Se E>E + α∑ j=1 A>j E >EAj S>e 4 ν21n SeE>ES>e , 1
(1 + α)n Ã(Xe)>M̃z =  1 1 + α Id + α∑ j=1 Aj > 1 n SeE > |z| .
By Lemma 5, under Assumption 3 and Assumption 4, we have that with high probability, 0.9Ide 4 1 nE >E 4 1.1Ide . Therefore with E and z being independent,
EERe = EP s [ 1
2 ∥∥∥∥ 1(1 + α)nΣ̂†Ã(Xe)Ã(Xe)>M̃z ∥∥∥∥2
2
]
≥ σ 2
2n ν22 ν41 tr
( EP s [( 1
n SeE
>ES>e
)†])
& σ2
2n ν22 ν41
tr ( SeS > e ) & σ2de 2n ,
and the rest follows from Theorem 14.

heading: C TECHNICAL LEMMAS
text: Lemma 5. We consider a random vector x ∈ Rd with E[x] = 0, E[xx>] = Σ, and x = Σ−1/2x 3 being ρ2-subgaussian. Given an i.i.d. sample of x, X = [x1, . . . ,xn]>, for any δ ∈ (0, 1), if n ρ4d, then 0.9Σ 4 1nX >X 4 1.1Σ with probability high probability.
Proof. We first denote PX , ΣΣ† as the orthogonal projector onto the subspaceX ⊆ Rd supported by the distribution of x. With the assumptions E[x] = 0 and E[xx>] = Σ, we observe that E [x] = 0 and E [ xx> ] = E [ xΣ−1x> ] = PX . Given the sample set X of size n ρ4 (d+ log(1/δ)) for
some δ ∈ (0, 1), we let U = 1n ∑n i=1 xiΣ
−1x>i − PX . Then the problem can be reduced to showing that, with probability at least 1− δ, ‖U‖2 ≤ 0.1. For this, we leverage the -net argument as following.
For an arbitrary v ∈ X ∩ Sd−1, we have
v>Uv = 1
n n∑ i=1 ( v>xiΣ −1x>i v − 1 ) = 1 n n∑ i=1 (( v>xi )2 − 1) , where, given xi being ρ2-subgaussian, v>xi is ρ2-subgaussian. Since
E [( v>xi )2] = v>E [ xix > i ] v = 1,
we know that ( v>xi )2 − 1 is 16ρ2-subexponential. Then, we recall the Bernstein’s inequality, P [∣∣v>Uv∣∣ > ] ≤ 2 exp(−n
2 min
( 2
(16ρ2) 2 , 16ρ2
)) .
3In the case where Σ is rank-deficient, we slightly abuse the notation such that Σ−1/2 and Σ−1 refer to the respective pseudo-inverses.
Let N ⊂ X ∩ Sd−1 be an 1-net such that |N | = eO(d). Then for some 0 < 2 ≤ 16ρ2, by the union bound,
P [ max v∈N : ∣∣v>Uv∣∣ > 2] ≤ 2 |N | exp(−n 2 min ( 22 (16ρ2) 2 , 2 16ρ2 ))
≤ exp ( O (d)− n
2 ·
2 2
(16ρ2) 2
) ≤ δ
whenever n > 2(16ρ2)
2
22
( Θ (d) + log 1δ ) . By taking δ = exp ( − 14 ( 2 16ρ2 )2 n ) , we have that
max v∈N ∣∣v>Uv∣∣ ≤ 2 with high probability when n > 4( 16ρ2 2 )2 Θ (d), and taking n ρ4d is sufficient.
Now for any v ∈ X ∩ Sd−1, there exists some v′ ∈ N such that ‖v − v′‖2 ≤ 1. Therefore,
∣∣v>Uv∣∣ = ∣∣∣v′>Uv′ + 2v′>U (v − v′) + (v − v′)>U (v − v′)∣∣∣ ≤ (
max v∈N
: ∣∣v>Uv∣∣)+ 2 ‖U‖2 ‖v′‖2 ‖v − v′‖2 + ‖U‖2 ‖v − v′‖22
≤ (
max v∈N
: ∣∣v>Uv∣∣)+ ‖U‖2 (2 1 + 21) .
Taking the supremum over v ∈ Sd−1, with probability at least 1− δ,
max v∈X∩ Sd−1
: ∣∣v>Uv∣∣ = ‖U‖2 ≤ 2 + ‖U‖2 (2 1 + 21) , ‖U‖2 ≤ 2
2− (1 + 1)2 .
With 1 = 13 and 2 = 1 45 , we have 2 2−(1+ 1)2 = 110 .
Overall, if n ρ4d, then with high probability, we have ‖U‖2 ≤ 0.1.
Lemma 6. Let U ⊆ Rd be an arbitrary non-trivial subspace in Rd, and g ∼ N (0, Id) be a Gaussian random vector. Then for any continuous and Cl-Lipschitz function ϕ : R → R (i.e., |ϕ(u)− ϕ(u′)| ≤ Cl · |u− u′| for all u, u′ ∈ R),
Eg [
sup u∈U
g>ϕ(u) ] ≤ Cl · Eg [ sup u∈U g>u ] ,
where ϕ acts on u entry-wisely, (ϕ(u))j = ϕ(uj). In other words, the Gaussian width of the image set ϕ(U) , { ϕ(u) ∈ Rd | u ∈ U } is upper bounded by that of U scaled by the Lipschitz constant.
Proof. Eg [
sup u∈U
g>ϕ(u) ] = 1 2 Eg [ sup u∈U g>ϕ(u) + sup u′∈U g>ϕ(u) ] = 1 2 Eg [ sup u,u′∈U g> (ϕ(u)− ϕ(u′)) ]
≤1 2 Eg  sup u,u′∈U d∑ j=1 |gj | ∣∣ϕ(uj)− ϕ(u′j)∣∣  ∵ ϕ is Cl-Lipschitz ≤Cl
2 Eg  sup u,u′∈U d∑ j=1 |gj | ∣∣uj − u′j∣∣  = Cl 2 Eg [ sup u,u′∈U g> (u− u′) ]
= Cl 2 Eg [ sup u∈U g>u + sup u′∈U g> (−u′) ]
=Cl · Eg [
sup u∈U
g>u
]

heading: D EXPERIMENT DETAILS
text: In this section, we provide the details of our experiments. Our code is adapted from the publicly released repo: https://github.com/kekmodel/FixMatch-pytorch.
Dataset: Our training dataset is derived from CIFAR-100, where the original dataset contains 50,000 training samples of 100 different classes. Out of the original 50,000 samples, we randomly select 10,000 labeled data as training set (i.e., 100 labeled samples per class). To see the impact of different training samples, we also trained our model with dataset that contains 1,000 and 20,000 samples. Evaluations are done on standard test set of CIFAR-100, which contains 10,000 testing samples.
Data Augmentation: During the training time, given a training batch, we generate corresponding augmented samples by RandAugment (Cubuk et al., 2020). We set the number of augmentations per sample to 7, unless otherwise mentioned.
To generate an augmented image, the RandAugment draws n transformations uniformaly at random from 14 different augmentations, namely {identity, autoContrast, equalize, rotate, solarize, color, posterize, contrast, brightness, sharpness, shear-x, shear-y, translate-x, translate-y}. The RandAugment provides each transformation with a single scalar (1 to 10) to control the strength of each of them, which we always set to 10 for all transformations. By default, we set n = 2 (i.e., using 2 random transformations to generate an augmented sample). To see the impact of different augmentation strength, we choose n ∈ {1, 2, 5, 10}. Examples of augmented samples are shown in Figure 3. Parameter Setting: The batch size is set to 64 and the entire training process takes 215 steps. During the training, we adopt the SGD optimizer with momentum set to 0.9, with learning rate for step i being 0.03× cos ( i×7π
215×16
) .
Additional Settings for the semi-supervised learning results: For the results on semi-supervised learning, besides the 10,000 labeled samples, we also draw additionally samples (ranging from 5,000 to 20,000) from the training set of the original CIFAR-100. We remove the labels of those additionally sampled images, as they serve as “unlabeled” samples in the semi-supervised learning setting. The FixMatch implementation follows the publicly available on in https://github. com/kekmodel/FixMatch-pytorch.
E ILLUSTRATIVE EXAMPLE
Here we present an illustrative example for logistic regression, which numerically shows the benefits of DAC over ERM, and also clearly demonstrates the impact of different daug and α. Example 3. Consider a 30-dimensional logistic regression. The original training set contains 50 samples. The inputs xis are generated independently from N (0, I30) and we set θ∗ = [θ∗c ; 0] with θ ∗ c ∼ N (0, I3) and 0 ∈ R27.
To generate the augmentations, we first specify a parameter daug and leave the first 30 − daug elements of each xi unchanged, and replace the later daug elements of each xi with a new vector randomly generated from N (0, Idaug). Further, we generateα augmentations for each of the xi. For any α ≥ 1, the augmentation will perturb daug coordinates with probability 1.
The results for daug ∈ {20, 25} and various αs are presented in Figure 5. The test error clearly matches Theorem 3 and the discussion after-
ward: 1) The generalization performance of DAC only relies on daug but not α, and larger daug gives smaller testing error. 2) The performance of DA-ERM crucially depends on α, when α is small (i.e., limited augmentations), the performance between DAC and DA-ERM is very significant. And when we further increases α, DA-ERM can only approach to DAC but not out-perform DAC.

Review summaries:
Data augmentation is a common technique to improve generalization, especially when data is scarce. This paper introduces a theoretical framework for analyzing the effectiveness of consistency regularization when data augmentation is employed. In the limit, consistency regularization is akin to solving a constrained optimization problem with consistency constraints. The paper theoretically studies this limit for linear regression, logistic regression, and a two-layer perceptron with ReLU activation, and tries to characterize the benefits of consistency regularization beyond that of vanilla data augmentation. The paper then continues to experiments where it is shown that consistency regularization outperforms data augmentation on three benchmarks, and the benefits are significant especially when labeled data is scarce. 

This paper aims to offer a theoretical analysis of the training with data augmentation and associated consistency loss. While it is intuitive that training with data augmentation and consistency loss will help, this paper offers a theoretical justification of the intuitions. The simple framework (to view DAC as a hypothesis space complexity reduction technique) is neat and intuitive.