Theoretical Analysis of Consistency Regularization with Limited Augmented Data
Authors: Shuo Yang
Yijun Dong
Rachel Ward
Inderjit S Dhillon
sujay sanghavi
Qi Lei
Venue: ICLR 2022 Submitted (2022)
Keywords: data augmentation
consistency regularization
generalization bound

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

Under review as a conference paper at ICLR 2022
THEORETICAL ANALYSIS OF CONSISTENCY REGU- LARIZATION WITH LIMITED AUGMENTED DATA
Anonymous authors Paper under double-blind review
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 small step in this direction; we present simple new statistical framework to analyze data augmen- tation specifically, one that captures what means for one input sample to 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 complex- ity, 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 reg- ularization for logistic regression and two-layer neural networks. We perform experiments that make a clean and apples-to-apple comparison (i.e. with no ex- modeling or data tweaks) between ERM and consistency regularization using CIFAR-100 and WideResNet; these demonstrate the superior efficacy of consis- tency regularization.
INTRODUCTION
Modern machine learning models, especially deep learning models, require abundant training sam- ples. Since data collection and human annotation are expensive, data augmentation has been ubiquitous practice in creating artificial labeled samples and improving generalization performance. This practice is corroborated by the fact that the semanties of images remain the same through sim- ple 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 many recent state-of-the-aar supervised semi- supervised algorithms. This idea was first proposed in (Bachman et al., 2014) and popularized by Laine & Aila (2016); Sajjadi et (2016), and gained more attention recently with the success of FixMatch (Sohn et al., 2020) for semi- 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 theoretical understanding 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 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?

---

Under review as a conference paper at ICLR 2022
We present new theoretical framework that casts consisteney regularization way reduce function class complexity, which immediately connects to the well-established theory on gener- alization and gives rise to 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 generaliza- tion bounds under consistency regularization for logistic regression, two-layer neural networks, and expansion-bate 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 formal theoretical definition of data augmentation and its strength. We then use this framework to give 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 strictly smaller generalization error than ERM with the same augmented data.
Empirical comparisons between consistency regularization and ERM. We perform ex- periments 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 WideRes- Net. Our empirical results demonstrate the superior efficacy of consistency regularization.
RELATED WORK
Empirical findings. Data augmentation (DA) is essential recipe for almost every state-of-the- art supervised learning algorithm since the seminal work of (Krizhevsky et al., 2012) 2) (see reference therein (Simard et al., 1998; Cubuk et al., 2018; Simonyan & Zisserman, 2014; He al., 2016; Kuchnik & Smith, 2018)). It started from adding augmented data to the training samples via (ran- dom) perturbations, distortions, scales, crops, rotations, and horizontal flips. More sophisticated variants were subsequently designed; non-exhaustive list includes Mixup (Zhang et al., 2017), Cutout (De Vries & Taylor, 2017), and Cutmix (Yun 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 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-the- algorithms for semi-supervised learning (Laine & Aila, 2016; Sajjadi et al., 2016; Sohn al., 2020: Xie et al., 2020), self-supervised learning (Chen et al., 2020b), and unsupervised domain adaptation (French al., 2017; Berthelot 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 al., 2020) or kernel classifiers (Dao et al., 2019). Convolutional neural networks by design enforce translation equiv- ariance 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 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.
2

---

Under review as a conference paper at ICLR 2022
Some more recent work investigates the feature representation learning procedure with DA for self- supervised learning tasks (Wen & Li, 2021; HaoChen et al., 2021; von Kü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 also deployed to improve robustness (Rajput et al., 2019), to facilitate domain adaptation and domain generalization (Cai et al., 2021; Sagawa al., 2019).
DATA AUGMENTATION CONSISTENCY AND HOW IT LEARNS EFFICIENTLY
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 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.).
3.1 PROBLEM SETUP AND DATA AUGMENTATION
Consider the standard supervised learning problem setup: x E X are imput features, and y E y is its label (or response). Let Pa be the true distribution of (x,y) v) (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 E X. we say x' E X is its augmentation, if and only if Pa (ylx) = P" (v)x'.
The definition above specifies what means for one input sample to be an augmentation of another. While the definition covers any x' with the same label distribution x, results only use the aug- mented samples that can be achieved via certain transformations (e.g., random cropping, rotation). However, definition does not cover augmentations that alter the labels (e.g.. MixUp (Zhang al., 2017)).
Now introduce the learning problem augmented dataset: Let (X, E X YN be training set consisting of N Li.d. samples. Besides the original yX, each training sample in it is provided with a augmented samples. The input features of the augmented dataset can be written as:
Á(X)= = [x1 1 :NN13 ;1,aii ................................ ;NN o E (1++a)N
where X; is in the original training set and Xt,j Vj E [a] are the augmentations of x,. The labels of the augmented samples are kept the same, which can be denoted My E ((++)) where M E No)+ is vertical stack of (1 + a) identity mappings. Specifically, when the input x,s are d-dimensional real vectors, we have the following notion of augmentation strength dang:
Definition 2 (Strength of augmentations). For any ò E (0, 1), let
dang (8) A argmax IP Tx rank (Ā(X) (8xX)-Mxxxx < dang SS dang dang (1/N).
dagg
Intuitively, strength of augmentations (5) means that with probability at least 1 - 5, the aug- mentations perturb at least daug dimensions; whereas dang be intuitively understood as the minimum number of dimensions that the augmentations in A(X) perturbed with high probability. A
lager dang corresponds to stronger data augmentations. For instance, when Á(X) MX almost surely (e.g. when the augmentations are identical copies of the original samples, corresponding to the weakest augmentation On the other hand, the augmentations are randomly generated, then it is more likely to see larger dang (i.e., more dimensions being perturbed) with larger a (i.e., more augmentations).
augmentations at all), have dang (8) d 0 for all 8 (0, 1).
In the next subsection, we formally introduce "data augmentation consistency regularization" and present generalization bound under bounded loss functions. We subsequently specialize the bound to linear regression and show that consistency regularization strictly more sample efficient than empirical risk minimization (ERM) the augmented dataset.
3

---

Under review as a conference paper at ICLR 2022
3.2 DATA AUGMENTATION CONSISTENCY REGULARIZATION
Let H -= (h: X + } be a well-specified function class (e.g. for regression problems, 34 E H. s.t. h*(x) Elylx) that we hope to learn from. Without loss of generality, we assume that each function h E H can be expressed as h = Jn o @h, where Φ) E $ = {Ø- : + W] is a proper representation mapping and fn E representation. We tend to decompose h such that 4% is a powerful feature extraction function whereas fn can be as simple as linear combiner. For instance, in a deep neural network, all the layers before the final prediction layer can be viewed as feature extraction di, and the predictor fr. corresponds to the final linear combination of the features.
{f W->) is predictor on top of the learned
For loss function 1 : Y' x y + R and a metric e properly defined on the representation space W, learning with data augmentation consisteney (DAC) regularization can expressed as:
argmin NEW
((h(xs), v1)
e (0
j=1
DAC regulirizaation
Note that the DAC regularization in Equation (1) can be easily implemented empirically as regu- larizer. Intuitively, DAC regularization penalizes the representation difference between the original sample Φb (x.) and the augmented sample Φs (x.,),, with the belief that similar samples (i.e., origi- nal 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., X + oc) given that the conditional distribution of y does not change. The function de learned with data augmentation consistency regularization can then be written as the solution of a constrained optimization problem:
N
ddae A argmin NEH
Σ [(((x)), vi) s.t. (x,) = (n(x)))) Vi E [N],j E [a].
(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 Á(X). we have: Definition 3 (Data Augmentation Consistency Operator).
T Thee (H) & {hl h H. (x,) (x..), Vi E [N], e [a]}
Particularly, we assume that a proper representa- tion class d is chosen with respect to the augmen- tations such that h* E Á.x (H). The DAC opera- tor maps the original function class H to (poten- tially much smaller) subset Taac (H), where every function E Tdac (H) gives consistent represen- A.
Original Function Class: H. BE on (x;). On (x.)) can different.
Reduced Function Class: A.X
(H)
tation for all samples and their augmentations (i.e., ou (x,) = Φn (xx,)). ) It is now clear that with DAC regularization, Equation (2) is effectively learning in the function class T (H), which is a subset of H.
s.t. (x(x)) (x(x))) W E [o). [o).
dy is the feature mapping of h E H.
As we will show in the next subsection, the function class size reduction is the key for efficient learning with data augmentations.
Figure I: The DAC regularization reduces function class H. to du (H). A.
One of the contributions of our paper is to view consistency regularization as function class complex- ity reduction. Our next proposition connects the generalization bound to the Rademacher complexity Tiac (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 E H, i.e L(h) A B(x.v) [(b(x),))) w))l Proposition 1 (formally in Proposition 8). With Equation (2), if is B-bounded and Cy-Lipschirz. then for a fixed 1 dae (H.) and any å E (0, 1). with probability at least 6-6 8, we have A.X
I(hdac)- I(h")= < 4C, AN (Tdex((1) +
2B" 1og(2/8)
N
4

---

Under review as a conference paper at ICLR 2022
Remark 1. Our results can be immediately extended 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 the labeled dataset in the main text and defer discussions on unlabeled data to the appendix.
3.3 EFFICACY OF DAC REGULARIZATION. A GENTLE START WITH LINEAR REGRESSION
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:
N
T Rda-erm A argmin
Σ (h(())))))) +
(((()))...).
(3)
hEH
Now we show that the DAC regularization learns more efficiently than ERM. Consider the following setting: given N observations X E IR Nxx, the responses E R are generated from a linear model
y XØ + where RRN is zero-mean noise with E | [] LNIN. Recall that A(X) is the entire augmented dataset, and My corresponds to the labels. Our next result characterizes the
fixed design excess risk of f A(X), which is defined [(0) (I+o)N [(X] A(x))
1
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 Á(X), notice that by Definition 2, daug rank ((x)= MX) 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 [(ōdac)= - L(07) (d-dwu)o² while learning with ERM directly on
the augmented dataset, we have EE [ -((0)] (d' where d' E [0, danel
Formally, d' is defined as d' L(((Axx))PP) -Ps PPS)MM where A(X) orthogonal projector onto S
2 A(X) A(X)) and Ps the
Ita
A MXA 4O Rdd, s.t.
(Ā(X) MX 8 0=0].
Here present explanation for d'.
Note that x² MM is the noise co- variance matrix of the augmented dataset. We have tr (P&MMTT being the variance being the
0.5
Excess Rik
DAC with d
DA-ERM with d
of @duc, and tr variance of pda-erm. Therefore, d' o tr (() Ps) MMT) is used to mea- sure the difference. When H xx(x) * Ps (a common scenario as instantiated in Example 1), we have DAC being strictly better than ERM augmented data.
DAC with dap
0.2
DA-ERM with 2
0.1
5
10
20
Different d's induced by Example 1
Figure 2: Comparison of DAC regularization and DA-ERM (Example 1). The results precisely match Theorem DA-ERM depends on the d' in- duced by different augmentations, while the DAC regularization works equally well and better than the DA-ERM. Further, both DAC and DA-ERM are affected by the "strength of augmentation" dawg.
Example Consider a 30-dimensional lin- ear regression. The original training set con- tains 50 samples. The inputs x;5 are gener- ated independently from (0, Is0) and we set 8- = 10;; 0) with 8: ~ (O, [s) and 0 E 25
The noise variance is set to 1. We break into 3 parts [I.1, Te, Fe2l and take the following augmentations: A(xxa Fa x22)) = [ 2x - Lo2l, Iel E IR Re Zel E R& Zez E R92,, where
del del + de2 30.
5

---

Under review as a conference paper at ICLR 2022
Notice that the augmentattin perturbs Zel and Ze2 and leaving dei unchanged, we therefore have daug 30 de1- By changing de1 and del. we can have different augmentations with different dang: d'. The results for daug E {20, 25} and various d's induced by different d, 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.
VARIOUS APPLICATIONS
Now ground our general result the DAC regularization with set of common applications, in- cluding 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 Á(X). Then, we discuss the corresponding excess risk L( 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 the- orems 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.
4.1 LOGISTIC REGRESSION
Here we consider logistic regressions with X f Rd ||x|| S D). y {0, For some unkown l" E Rd with ||0'|| I Co. we have P (y= 1|x) = a (0 x) where a(.) is the sigmoid function (2) & 1/(1 exp(-2)). The function class H. is H. {h(x) = x 0 Rd |10||2 S Co). such that predictions are given by 7 (0 x). For binary classification,
the logistic loss 1(0
x, 1(0Tx,
y ( x)) (1 y) log(1 a x)).
Recall the strength of augmentations daug from Definition Under proper regularity conditions (i.c., is sub- Gaussian and N is not too small, Appendix B), we have the following generalization bound for learning logistic regression under DAC regularization.
Theorem (Informal result on logistic regression with DAC (formally in Theorem 9)). Learning logistic regression with the DAC regularization h(x,) = h(x;,), with high probability:
L(hdac) - L(h')(())))))))())) S d dang log N
N
where the strength of augmentation daug E [0.d-1] 1].
Intuitively, with high probability, minimizing empirical loss on augmented samples gives gener-
alization bound of L L(dda-ermy - L(h") S max (V VaafiNN
d- at best, where the first
term corresponds to the generalization bound for a d-dimensional logistic regression with (a+ + 1)N samples, and the second term follows as the augmentations fail to perturb (d - daug) -diimessooa sub-space (and in which ERM can only rely on the original samples for learning). The first term will dominate the max when there is limited augmented data (i.e., a is small).
Comparing the two, we see that DAC more efficient than ERM. In particular, consider the scenario that the limited data augmentations well perturb the data (c.g.,
1 and dang d - 1). The ERM gives generalization error that scales as /d/N, while DAC yields dimension free /1/N error. Please see Appendix E for supporting numerical example, which demonstrates the benefits of DAC over DA-ERM for logistic regression, and empirically verifies the impact of dang and a that matches with our theoretical analysis.
4.2 TWO-LAYER NEURAL NETWORK
In this section, we discuss special case where the result for bounded losses in Proposition 8 can be extended to the unbounded square loss. With X' Rdd and Y' = IR, consider ground truth

---

Under review as a conference paper at ICLR 2022
distribution P (v(x) induced by two-layer ReLU network: y (x"B).. w" +
B'
dxq
[bj... ... bg.... bāl, for some unknown h* (x) - (x B²), w" where (.) _ max element-
wisely denotes the ReLU function, by E g for all k E [q], and 2 ~ N o²) is the Gaussian
noise. In terms of the function class H. for some constant C 2 [| we have:
H = {1(x) = (x ()) B [b) (b....bu by] E Rdxg, ||bıll2 = V j E [a]. [w]l S )
such that h" E H. We use the standard square loss 1(h(x),
(h(x) y)²
Let Pvv be the projector onto the null space of Â(x) MX. 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 two-layer neural network with DAC (formally in Theorem 10)).
Assuming E Ei= || PN] I C2 for some ON > 0, learning the two-layer ReLU network with the DAC regularization
(x. B)+ B) gives, with high probability:
L (pduc) (hh) S Cw
VN
Recall the strength of augmentations daug from Definition 2. Under proper regularity condi- tions (i.e., x is sub-Gaussian and N is reasonably large, see Appendix B.2), we have Cx S vd daug with high probability. Analogous to the logistic regression example, applying the ERM directly the augmented samples achieves no better than L(fcaa-rm) L(h") x
oC Ia+1IN
dane
with high probability. The comparison again illustrates the advan-
tage of DAC regularization over ERM. The advantage is large when the limited data augmentations strong (i.e., large daug and small a)).
4.3 EXPANSION-BASER DATA AUGMENTATIONS
In this section, we demonstrate that for the classification problems, enforcing consistency on a dif- ferent notion of data augmentations based on expansion also brings a considerable reduction in complexity of the feasible function class.
Concretely, we consider multi-class classification problem: for arbitrary set X, let ) [K] and h* X + [K] be the ground truth classifier that partitions X: for each k E [K], let X₁ 2 {x E X' h- (x) = k... with X, n n2 O. Vi # j. Here we focus on the expansion- based data augmentations defined as following:
Definition 4 (Expansion-based data augmentations), Let A: X - 2 be a function generating sel of augmentations A(x) from a given x E X that satisfies the following;
(a) Nontrivial augmentation and class invariant: (x} S AA()) S (x E = hx()x)) for all x E X; and
(b) Non-trivial expansion: for all k [K], given any @ C S S Xx, there exists some x' & S such that A(x) n A(x') + 0.
We consider general class of classifiers H. C {h: X [K]} where the ground truth classifier is alizable, A* E H.. With the zero-one loss 4oz (h(x), y) = (h(x)) * y). and the corresponding pop- ulation loss Loi (h) A Ex (l / 11* (x)HI, we learn a classifier from H with the DAC regular- ization, h(x) h((x), where x's are expansion-based data augmentations generated by an A (Defi nition 4). As a warm-up, we begin with 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 reg- ularization yields a classifier di E Téis (H) - (h E H lx(x) = l1(x') Vx x E X, x' E A(x)) Theorem 5 (DAC with expansion-bart bbsed data augmentations over population). Learning the classi- fier with DAC regularization over population, with high probability.
Loi (Rdaee - Loi (h²) 5
log K + log N
N

---

Under review as a conference paper at ICLR 2022
Particularly, with the DAC regularization, the generalization bound of the K-class classification problem is dimension-inndpendennt 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 enforced over 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.
5 EXPERIMENTS
In this section, we empirically verify that training with DAC learns more efficiently than empirical risk minimization randomly select 10,000 labeled data as the training set (i.c., 100 labeled samples per class). During the training time, given training batch, we generate augmentations by RandAugment (Cubuk et al., 2020). We set the number of augmentations per sample to unless otherwise mentioned.
augmented dataset. The dataset is derived from CIFAR- 100, where
The experiments focus on comparisons of 1) training with consistency regularization, and 2) empir- ical risk minimization on the augmented dataset (DA-ERM). In particular, we use the same network architecture (a -edeResNet-28-22 (Zagoruyko & Komodakis, 2016)) and the same training settings (e.g., optimizer, learning rate schedule, etc) for both methods. We defer the detailed experiment settings 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 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
DA-ERM
== 0
==1
=
=
X x 20
69.40 + 0.05
62.82
0.21
68.63
0.11
70.56 + 0.07 +
68.65 + 0.27
Table 1: Testing accuracy of ERM and DAC regularization with different X's (regularization coeff.).
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 sam- ples, ranging from 1,000 (i.e., 10 images per class) to 20,000 samples (i.e., 200 images per class). We generate augmentations for each of the samples during the training time, and the results are presented in Table 2. Notice that the DAC regularization gives bigger improvement over DA-ERM when the labeled samples are scarce. This matches the intuition that when there are sufficient train- ing samples, data augmentation is less necessary. Therefore, the difference between different ways of utilizing the augmented samples becomes diminishing
Number of Labeled Data
1000
10000
20000
DA-ERM
31.11 + 0.30
68.89 + 0.07
76.79 + 0.13
DAC (A 10)
33.59
= 0.41
70.71 + 0.10
76.86 + 0.16
Table 2: Testing accuracy of ERM and DAC regularization with different numbers of labeled data.
(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 The DAC regularization offers more significant improvement when the number of augmentations is small. This clearly demonstrates that the DAC regularization learns more efficiently from the limited number augmentations.
8

---

Under review as a conference paper at ICLR 2022
Number of Augmentations
15
DA-ERM
67.92 0.08
69.04 + 0.05
69.25 = 0.16
69.30 0.11
DAC (A = 10)
70.06 = 0.08
70.77 + 0.20
70.74 + 0.11
70.31 0.12
Table Testing accuracy of ERM and DAC regularizzati with different numbers of augmentations.
Proper augmentation brings good performance. To achieve good performance, it is important to have proper data augmentation needs be strong such that 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 crop- ping. flipping, etc.) applied to the training samples se- quentially. More transformations imply stronger aug- mentations. The number of transformations ranges from to 10, and the results are listed Table 4. We see that both DA-ERM and the DAC regularization benefits from proper augmentation. When the augmentation is strong (e.g., Augmentation Strength 10, as shown in Figure 3), the DAC regularization gives worse perfor- mance. It might be explained by falsely enforcing DAC regularization where the labels of the augmented samples have changed.
Original
Aug Strength
Aug Strength
Aug Strength 10
Figure 3: Examples of different aug- mentation strengths.
Augmentation Strength
DA-ERM
68.56 0.12
69.32 + 0.11
69.97 0.14
69. + 0.16
DAC (A = 10)
70.66 - 0.14
70.65 + 0.07 70.01 + 0.10
68.95 = 0.27
Table 4: Testing accuracy of EMR and DAC regularization with various augmentation strengths.
Combining with a semi-supervised learning algorithm. Here show that the DAC regularization be easily extended the semi- supervised learning setting. We take the previously established semi- supervised learning method Fix- Match (Sohn al., 2020) as the bascline 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, 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 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.
Number of Unlabeled Data
5000
10000
20000
FixMatch
67.74
69.23
70.76
FixMatch + DAC
(A DAC
71.24
72.7
74.04
Table 5: DAC regularization helps FixMatch when the un- labeled data is scarce.
CONCLUSION
present a simple new theoretical framework for understanding the statistical efficiency of consis- tency regularization with limited data augmentations. In particular, our proposed framework gives a generalization bound for consistency regularization in general cases. We also provide instantia- tions for linear regression, logistic regression, two-layer neural networks, and expansion- -baedd data augmentations. When specialized to linear regression/logistic regression, it shows that consistency regularization yields strictly smaller generalization error than ERM with augmented data. We also provide apples-to-appee -pplesss empirical comparisons between augmented ERM and consistency regular- ization. These together demonstrate the superior efficacy of consistency regularization.

---

Under review as a conference paper at ICLR 2022
Reproducibility Statement Our main theoretical results, including problem setup and (simplified) theorem statements are in Sections 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.
REFERENCES
Philip Bachman, Ouais Alsharif, and Doina Precup. Learning with pseudo-ensembles. Advances in neural information processing systems, 27:3365-3373, 2014.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3(mull):463-488 March 2003. ISSN 1532-4435.
Gregory Benton, Mare Finzi, Pavel Izmailov, and Andrew Gordon Wilson. Learning invariances in neural networks. arXiv preprint veXiv:2010.11882 2020.
David Berthelot, Rebecca Roelofs, Kihyuk Sohn, Nicholas Carlini, and Alex Kurakin. Adamatch: A unified approach to semi-supervised learning and domain adaptation. arXiv preprint
1.X::2206.04732. 2021.
Tianle Cai, Ruiqi Gao, Jason D. Lee, and Qi Lei. A theory of label propagation for subpopulation shift, 2021.
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. A group-theoretic framework for data augmenta- tion. Journal of Machine Learming Research, 21(245):1-71, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020b.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International confer- ence on machine learning, pp. 2990-2999. PMLR, 2016.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation policies from data. arXiv preprint arXiv:1805.09500) 2018.
Ekin D Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation strategies from data. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 113-123, 2019.
Ekin Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 702-703, 2020.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In International Conference on Machine Learning, pp- 1528-1537. PMLR, 2019.
Terrance Dres and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:1708.044 140500455, 2017.
Simon S. Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably, 2020.
Geoffrey French, Michal Mackiewiez, and Mark Fisher. Self-ensembling for visual domain adapta- tion. arXiv preprint urXiv:1706.080 05208, 2017.
Siddhant Garg and Yingyu Liang. Functional regularization for representation learning: A unified theoretical perspective. arXiv preprint arXiv:2008. 024447 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. arXiv preprint arXiv: 1eee:2006.44445 2021.
10

---

Under review as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Zhuoxun He, Lingxi Xie, Xin Chen, Ya Zhang, Yanfeng Wang, and Qi Tian. Data augmentation revisited: Rethinking the distribution gap between clean and augmented data. arXiv preprini 1909,099 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems. 25:1097-1105, 2012.
Michael Kuchnik and Virginia Smith. Efficient augmentation via data subsampling. arXiv preprint arXiv:/810.05222, 2018.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint
arXiv:1610.02222, 2016.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science Business Media, 2013.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon $ Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint vrXiv:1911.00809 2019.
Sungbin Lim, Ildoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. Fast autoaugment.
Advances in Neural Information Processing Systems, 32:6665-6675, 2019.
Clare Lyle, Marta Kwiatkowksa, and Yarin Gal. analysis of the effect of invariance on gen- eralization in neural networks. In International conference machine learning Workshop on Understanding and Improving Generalization Deep Learning, 2019.
Diego Marcos, Michele Volpi, Nikos Komodakis, and Devis Tuia. Rotation equivariant vector field networks. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5048- 5057, 2017.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. arXiv preprint wxXiv:2102.132/1 2021.
Shashank Rajput, Zhili Feng, Zachary Charles, Po-Ling Loh, and Dimitris Papailiopoolos. Does data augmentation lead to positive margin? In International Conference on Machine Learning. pp. 5321-5330. PMLR, 2019.
Shiori Sagawa, Pang Wei Koh, Tatsunori Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generaliza- tion. arXiv preprint arXiv: /. 1.08711, 2019.
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep semi-supervised learning. Advances in neural information processing systems, 29: 163-1171, 2016.
Connor Shorten and Taghi M Khoshgoftaar. A survey image data augmentation for deep learning. Journal of Big Data, 6(1):1-48, 2019.
Patrice Y Simard, Yann A LeCun, John S Denker, and Bernard Victorii. Transformation invariance in pattern recognition- taanget distance and tangent propagation. In Neural networks: tricks of the trade, pp. 239-274. Springer, 1998.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409, 1556, 2014.
Kihyuk Sohn, David Berthelot, Chun-Liang Li. Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. arXiv preprint arXiv:2001.07685, 2020.

---

Under review as a conference paper at ICLR 2022
Ivan Sosnovik, Michal Szmaja, and Amold Smeulders. Scale-equivariant steerable networks. arXiv preprint arXiv:1910.110990 2019.
Christopher Tensmeyer and Tony Martinez. Improving invariance and equivariance properties of convolutional neural networks. 2016.
Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. arXiv preprint vrXiv:2/06.04611 2021.
Martin J. Wainwright. High- High--Diensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/ 9781 108627771.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classifica- tion via an all-layer margin, 2021.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data, 2021.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. arXiv preprint arXiv:2/0S.15134, 2021.
Daniel E Worrall and Max Welling. Deep scale-spaces: Equivariance over scale. arXiv preprint arXiv: 11697, 2019.
Daniel E Worrall, Stephan Garbin, Daniyar Turmukhambetov, and Gabriel J Brostow. Harmonic networks: Deep translation and rotation equivariance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5028-5037, 2017.
Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations in data augmentation. In International Conference Machine Learning, pp. 10410-10420. PMLR, 2020.
Qizhe Xie, Minh- Thang Luong, Eduard Hovy, and Quoe V Le. Self-training with noisy student improves imagenet classification. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10687-10698, 2020.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. Proceed- ings of the IEEE/CVF International Conference Computer Vision, pp. 6023-6032, 2019.
Sergey Zagoruyko and Nikos Komodakis. 1rXiv:1605.071466 2016.
Wide residual networks.
arXiv preprint
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09411 2017.
Yanzhao Zhou, Qixiang Ye, Qiang Qiu, and Jianbin Jiao. Oriented response networks. Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 519-528, 2017.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS FOR BOUNDED Loss AND LINEAR REGRESSION
A.1 PROOF FOR DAC ON LINEAR REGRESSION
For fixed A(X), we recall that daug - rank (Ā(x) - -M) since there is no randomness in A, X
in fix design setting. Assuming that A(X) admits full column rank, 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 regu- larization, have E [(@dac)) [(0*)] (d-dwy)o² whiie learning with ERM directly the augmented dataset, we have E. T.(0do- T,(0*)
(d-dmctd''o" d' is defined as
d' tr M
H (ixx) - -Ps)
M
1
where d' E [0, dawg) with H z(x) B(+ the projection matrix to S. and S is defined to be S P MX8 V0 stt. (Ā(x)- - MX) 0 0= 0=0].
A(X) ((())T A(x)) A(X)T and Ps
Proof. With L(0)
1 (1+a)N
[(x] A(x))r the excess risk of ERM on the augmented
training set satisfies that:
E L((da-erm)
-
E
(1+a)N
X(X)(XXX)XXXX A(X)) ((XX) T (A(X)0" + +M)) Ā(x))- 1
R
(1+a)N
M(X)0OXX00 + TXX Me Ā(X)0' 1:3
E
(1+a)N
| Mc !
E
(1+a)N
(ur(eTi M H Me]]
(1+a)N
(1+a)N tr M H XXXX
Let Că(x) and Ci denote the column space of Ā(X) and M, respectively. Notice that S is subspace both Ci(X) and Crr. Observing that dang = rank (Ā(x) - MX) rank (Ps). we have
E
L(Oda -erm)
E (r(M H
MaxxMM
(1 a)N
E cr PsM)
E tr(M (H x(xx) MPs)
(1 a)N
(1 (1+a)N*
+ G2 N
tr(M (H A(X)
- -Ps)
E a)N
tr (
EE
1+a
By the data augmentation consistency constraint, we are essentially solving the linear regression on the (d ) dimennsionl space (0 (Ā(x) - Mx)0 = 03. The rest of proof is identical to standard regression analysis, with features first projected S:
13

---

Under review as a conference paper at ICLR 2022
L(Odec)
E
{(x)ōdac -(x))0 [
(1+a)1
[(XX(A(X T(X)) (((X) T(X)) PP + +Mc) Ā(x))-)
E
(1+a)N
Ps + H PsMe Ā(X)O'
(1 a) E
21
(: Ā(X)0*
E ES, and H Ps Ps since S _ (a(X)
PS 2
E
(1 + o.N
tr(M C0(MPssM P))
(1 + aaN
(d do
N
B APPLICATIONS OF LEARNING WITH DAC
To instantiate our general result on the DAC regularization, start with concrete application of Proposition 8 on the logistic regression problem with bounded loss (Section 4.1, Appendix B.I), 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 addi- tional 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, X² x ) from the unlabeled samples X" E X (possibly with different sizes N 2 n), while both sample sets are drawn i.i.d. from Pa. Particularly, in the supervised learning setting, the DAC regularization is based on the observables from the labeled training set such that X = X (N = n). While in the semi-supervised learning setting. X 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 X in contrast to the augmented sample A(X) in the main text) as
Ā(x") [x : x
" ............ x XaN,
1 Jelai is a set of a augmentations generated from x and let M NoNxNN be the vertical stack of N N identity matrices. Then analogously, with the unlabeled training set X", we can quantify the strength of the data augmentations .A with
where for each [N). { (xX]
doue A rank (Ā(x") MX" rank (Ā(x*) (A(X))-Xx)
such that 0 S damg S min (d, aN) can be intuitively interpreted as the number of dimensions in the span of the unlabeled samples, Row Row(X"), perturbed by A. Moreover, we denote N as the (d dang) dimensionaa null space of A(Xx)) MX", and Pv the projection onto N such that
PN - I. (Ā(X*) - -MX*) (A(x*)) (A(X")-MX') -MX)).
14

---

Under review as a conference paper at ICLR 2022
Correspondingly, let ! be the orthogonal complement of N, and P.y be the projection onto N/ such that Px = Ia - Pa. Then by recalling Definition 2, we have the following: Proposition 7. For any E (0, 1), with probability at least ò. 6.
rank (Px) = dim (N- Jann 2 (o),
rank (Px²) dim (N) d Jams
daug( (5).
Furthermore, for dang dang (L/n), with high probability, Jaug danc and d Jang S d daug In terms of (X,y) y) and X", the regularization formulation in Equation (1) can be restated as,
N e
argmin Σ 1(h(x)) +
DAC regularizer
and with the notation of A, the corresponding DAC operator is given by
Axx= Tyde (H) A [h E H on (x") = (x(x))) V [M
where Tdae and T A.
equivalent by construction.
A.x
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 and Assumption 2, where we assume X' C Rd.
Assumption (Regularity of marginal distribution). Let x P*(x) be zero-mean E[x with the covairance [[[x]]] Σx > O. We assume that (Ex 1/2 x) is -a-sbaaaussinn 1 and there exist constants C 2 c (11) such that cld & Ex $ CTa.
Assumption 2 (Sufficient labeled data). For (X,y) E X" x )m, with respect to X and À (
that characterize doug. we assume n > p² (d dama))
For R-bounded loss function 1 y x y R (i.e., 0 S < B) such that for all y V, I(+;)): + R is Ci-Lipschitz, we have the following:
Proposition 8 (Formal restatement of Proposition 1 on DAC with bounded loss), Learning with DAC regularization (Equation (2)), for fixed Tduc. (H) and any 8 E (0, 1), with probability at least 1 8, we have
2B log (2/8)
L(hdae) L(h²) S 40 RR, Rr, (ee dac
Ax (H))
where R, (Idde (H)) represents the Rademacher complexity of T (H). xxx
A.x"
Proof of Proposition 8. We first decompose the expected excess risk as
L(hdoc) L(h") (Lhhda - [(hdaa)) (I(rdae) - I(h')) + (I(h")
where [(hdar)- [(he)) < by the basic inequality, and as a consequence, for fixed Ho =
dac (H). xxx"
L(hdac) L(h)) < 2
L(h) - Iim) = 2 sup nEH
L(h) - I(n)|-
sup dee A,x" (H)
We denote g+(ggt (X, = SuPREи.
L(h) L(h) and g- -(X,y) = supnEm, -(h) + I(h). Then,
P [Thdaa) L(h") ) > { < P
X y) イ/ +F (X, 2 2
'A random vector E Rdd is p² psssugaaussian if for any unit vector E gd-1 11 v is p² susuuaaussn,nn, E. [exp(s- -u" T v)] exp (s² (2))
15

---

Under review as a conference paper at ICLR 2022
We will derive tail bound for g* y) with the standard inequalities and symmetrization argu- ment Wainwright (2019); Bartlett & Mendelson (2003), while the analogous statement holds for g y).
Let (X ((()) be sample set generated by replacing arbitrary observation in (X, with any (x, E X V. Since is B-bounded. we have 1 (X.
9 (x("), ,y('| - B/n. Leveraging
the McDiarmid's inequality Bartlett Mendelson (2003),
2nt²
P l (X, 2 Big (Xg (X, y) + < exp
B
For an arbitrary sample set yX, let (x, (1) = (((x)))) yi) be the empirical risk of with respect to y) Then, by a classical symmetrization argument (e.g., proof of Wainwright (2019) Theorem 4.),), can bound the expectation: for an independent sample set (X), y') X" x )r drawn i.idd from P",
9 yX,
E (x
sup L(h) L (1)
LEHo
B( [<(x),>((()]] - (1))
(x.)
sup NEHO
(x.))
sup AEHo
Exx's [Txx) (1)))()))
(x,
(x,))
x(x''")
sup (k)) -2000--xxxxh (h)
(x,y)
LieH.
(Law of iterated conditional expectation)
E [xxx''''
(x)) - I (1) sup LEEH
Since y) and y', independent and identically distributed, can introduce i.id. Rademacher random variables (-1,++1 | [n]] (independent of both (X, and (X', such that
Σ ri (x()) , vi - 1(h (xx) mil))
(X. Sixx
sup hEH. n
<2 F(x.y.))
sup NEH. n
rs 1 (x,), vi)
f=1
2 Rm (lo Ho)
where o H. (((h(-)..) .) X x - Ho} the loss function class. Analogously, Elg (X,y) < 29, (1 Ho). Therefore, with probability at least 1 - 8.
2Ba log(2/5)
L [(hdac) L(h*)= s 49 Ho) +
Finally, since 1(-. y) Ci Lipschcii for all y y. by Ledoux & Talagrand (2013) Theorem 4.12, we have Rr (1o Ho) & C Rr (Ho).
B. FORMAL RESULT ON LOGISTIC REGRESSION
For the logistic regression problem in Section 4.1, with X' (x Rd ||x|/ S D). y (0,1), training with the DAC regularization can be formulated explicitly as
ddac
argmin OER"
Σ 1 (0 Vi)
T 1=1
1101/ S Co. -(x")0-MX MX'0
s.t.
and yields 7.dae(x) 2 xT Odac
16

---

Under review as a conference paper at ICLR 2022
Theorem 9 (Formal restatement of Theorem 3 logistic regression with DAC). Let E H. - PP PN I CN for some CN > O. Then, learning logistic regression with the DAC regularization h(x²)) = h(xx))) yields that, for any E (0, 1), with probability at least 1 6:
L(hdar L(h') CoCN + CoDy (1/0)
Vn
where under Assumption I and Assumption 2, CN S vd daus (6/2).
Proof of Theorem 9. Notice that the logistic loss 1(:, v) is 2-L.ischitz for all V, @l(2.))
(z) - y. whose absolute value is bounded by 2. Meanwhile, with ||01]2 I Co and ||*||| 2 for all and x, the logistic loss also bounded: I (0* x, 3) S log 2 C.D. Then, applying Proposition 8, we have that for any 8 E (0, 1), with probability at least - 8/2,
L(hdng) L(h") Ri
(Thee
i.." (H)) VoDA
log(1/8)
left to bound the Rademacher complexity T (H). First notice that the sigmoid function (-) is a bijective function, the data augmentation consistency constraints are equivalent to
A.
(A(X*)-M) -M)" 0 0
Thus, we have
Tdae (H) = (l(x) 0 1 EN,, 1101|2 S Co).
with which we are ready to bound the Rademacher complexity of Tracs (H). For the emprical Rademacher complexity, we have
xx (Tuae (H1) (Trcc.
E Rad(()
sup
Σ 0 Xi
AET (7) A,x
1=1
E eed
sup
0 PNX:
OEN i=1
Co E Rad()) (
Σ PNPx 1=1
Co
E Rad
JepPxxxl)
Co
P 1
Co Val tr
(PPNXTXPN)
Converting this to the population Rademacher complexity, we take expectation over X, while con- ditioned on P.v. and recall Jensen's 's inequality,
Rr (Tdac (H1)
<
Co
E
(PPXTXPPN)
PN
Co
(PNXXTXPN)
E
ir
Px
CoCN
Vn
17

---

Under review as a conference paper at ICLR 2022
Leveraging Lemma 5, have that under Assumption 1 and Assumption conditioned on Pv,, with high probability over X ~ .
P
XP
$.10
n
2
Then can find some CN > 0 with E
S C2
such that,
Oy (d-dJan)) Jrme)
1
PNX
S Jamg-
By Proposition 7, we have ON SS /d dave (0/2) with probability at least 1 8/2.
To obtain Theorem 3, we leverage the union bound and suppress the constants such that, with prob- ability at least 1 8,
I(Tdac) - L(h²)= - d daug (6/2)
(1/(1/6)
n Finally, taking 2/n and applying the Jensen's inequality to the two terms in Equation (4) complete the proof.
n
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
B dac dac
argmin GEReXo,WER*
2n ||y (XB)_ 1
s.t. = [bi... bg... by), by E - vk [q]. |w]] S C
(A(X")) = =(MX"B)+
and yields Tedae(x) & (x Bdac) + Wadae
Theorem 10 (Formal restatement of Theorem 4 on two-layer neural network with DAC). Sampling from P that follows Assumption I, let the augmented training set À (X") satisfy (a) o. 4daug. (b) AX*) MX admits an absolutely continuous distribution over N and P fulfills (c) -or for some CN > Then, learning the two-layer ReLU network 1 S SCy
with the DAC regularization on ((x+) B) = (xx,)) TB)_ gives that, with high probability, (Todac) - (hh)) OC..N
B),
Vni
where under Assumption I and Assumption 2, CN S /d- daug (6) with probability least 1 - 8.
Lemma 1. Under the assumptions in Theorem 10, every size-d subset of rows A(X") MX is linearly independent almost surely.
Proof of Lemma 1. Since aN > Jang. is sufficient to show that random matrix with an absolutely continuous distribution is totally invertible almost surely.
is known that for any dimension m E N. an m X m square matrix S is singular 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 Æm has Lebesgue measure zero, ((S xm det(S) 0}}) = 0. Then, for an absolutely continuous probability measure μ with respect to X, we also have
P [S Rm singular] = μ (fS E R
det((S) = 0}) =
Since general matrix R contains only finite number of submatrices, when R is drawn from
absolutely continuous distribution, by the union bound, P R cotains singular submatrix] = 0. That is, R totally invertible almost surely.
A matrix is totally invertible if all its square submatrices invertible.
18

---

Under review as a conference paper at ICLR 2022
Lemma 2.
Under the assumptions in Theorem 10, the hidden layer in the two-layer ReLU network learns N, the invariant subspace under data augmentttiioss : with high probability
x Bdac)
PN (x
VXEX.
Proof of Lemma 2. We will show that for all by PAbs + + h [g]. Pyb; with high probability, which then implies that given any x E X, (x bx)+ (x PNpbb for all & E [g].
For any l: E [g] associated with an arbitrary fixed by: E gdd1 let X P A be the inclusion-wisely maximum row subset of X" such that X 0 eiement-wisely, Meanwhile, we denote A(X;) M A(X)))
XaN, as the augmentation of X where M2
RaN.xN, xNN, the vertical stack of a identity matrices with size N₂ x Ng. Then the DAC constraint implies that (A(())) M, by =0
With Assumption 1, for fixed by E Ed P[x T by
0]
Then, with the Chernoff bound,
N
Se Se %
No
2
which implies that, N₂ 2 N with high probability.
Leveraging the assumptions in Theorem 10, aN 2 4dang implies that aN2 dang. Therefore by Lemma 1, Row (Ā(x:) M,X;) = with probability 1. Thus, (A(X)) Px 0 enforces that bbbb O.
Proof of Theorem 10. Lemma 2 implies that (X = (XP and therefore. Tdac (H) (h(x) (x B)+
[b ......u byl. by Sa-1 (XB) x),xB)+;llWlll Cw)
In other words, the DAC regularization reduces the feasible set for B such that
B B - B = [b .b. byl | = 1 [gl. (XB)+ = (XPxB))) || S Cw. Meanwhile, for the square loss, the corresponding excess risk given by
L (Adde) L (h*) = Ex
(X
wadac (XB") "
2n
Leveraging Equation (21) and (22) in Du et al. (2020), since (B", w*) is feasible under the straint, by the basic inequality.
yy (XBdao) ddoe 2 S Ily (0--(XBB) (XB*) +
(5)
where ddcc B E B and | S C..
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 - RJ,
6 x (+)
E (0.1) Ltd.
sup ΦE
1
(x)
(.)()
E x (6)
i=1 k=1
In terms of the Gaussian complexity, for a fixed Tidcc (H),
Ex
(X
dade (XB*), w 1 x
2n
<
T
1
(XBBdac), widar (XB))+'')
X"
m
Za
Ex
(Tape (70) x"
19

---

Under review as a conference paper at ICLR 2022
where the empirical Gaussian complexity can be upper bounded by
Gx
Axx
E
sup BEB,
(XB) w
(0.T.)
w/l SR
C E
sup LBES
(XB)
gl1
C
I
sup Lbega-1
g' (XPwb)+
(Lemma 6, (-)+ is 1-Lipschitz)
C
E
sup
g XPxb
8 bb
C E
P
[112]
n
g
C
|| g $1{)]
1/2
Cw
(tr(PxX XP
n
C
P 1
Taking expectation over X ~ P we have that for a fixed Tdacc (H) (i.e., conditioned on PA), dxx=
G₂ (Tx (76)
CN
Vn
Leveraging Lemma 5, we have that under Assumption 1 and Assumption 2, conditioned on Pv, with high probability over X P
PNX XP
1110 1
Then we can find some CN > 0 with Ei= PAxX, S SR such that,
CN S (d- dams)
| P
S d dawg-
By Proposition 7, we have CN S /d dayg (0) with probability least 1 5.
B.3 FORML RESULTS ON EXPANSION-BASEN DATA AUGMENTATION
For the formal analysis of the expansion-bacte based data augmentations, we first introduce some helpful notations.
With respect to an augmentation function A X - 2 fulfilling the conditions in Definition 4, we define the neighborhood for an arbitrary x E X. well as for any C X, such that,
(B(x) {x' X A(x) n A(x)) 0) NB(S) & NB
Then Definition 4(b) implies that the corresponding neighborhood function NB X' + 2 of Aas non-trivial expansion:
0 C S X = ( # V A [K], S X.
Intuitively, the non- trivial expansion guarantees that the neighborhood of any proper subset of class always enlarges the subset within the class.
Remark 2. The ground truth classifier is invariant throughout the neighborhood: for any aug- mentation function A X + 2 satisfying the conditions in Definition 4, the corresponding neigh- borhood function satisfies that, given any X, 1e (x) h² (x') for all x' E (x)()).
20

---

Under review as a conference paper at ICLR 2022
Notice that the previous data augmentation strength dang (Definition 2) is not well defined for Defini- tion 4 (since X' needs not be subset of IR Therefore need new notion of data augmentation strength.
Remark 3. The strength of expansion-bur bassdd data augmentations (Definition 4) is characterized by the size of A(x). Intuitively, for any x E X. the augmentations can be stronger (i.e., there exists x' E A(x) that is more different from x) if A(x) is inclusion-wid inclusion-wisely larger.
In addition, for an arbitrary classifier h E H. we denote the majority label with respect to h for each class,
ie arginax Px [M(x) y X Xi] AkE [K],
sE[K]
along with the respective class-wise local and global minority sets,
K M - (xE Me M(x) + Dr ç X [KE[K], M
UM-
Infinite unlabeled data. As up, we simplify the setting by enforcing consistency over the population such that learning with the DAC constraints can be expressed as,
Idoe (dre(h) 1
Tode
argmin NEW
L01
1 (h (x+) + ht (xi))
s.t. h(x) = hx V VXEX, x' A(x).
We can also formulate algorithm in terms of the DAC operator,
h
dac A argmin
(h)) TAeS & (h E H h(x) = (xxx)xXEA x A(x)}.
beT A (P)
Lemma Given any h (H), for each E [K], there exists some The E [K] such that h(x) = for all x E Xx.
Proof Lemma 3. It is sufficient to show that M₁ 0 for all k E [K]. By contradiction, suppose
Mj * 0. Then by the non-trivial expansion assumption in Definition 4, (NB n * O.
That is, there exists some E (NB(M&) MR) Xr. But on one hand, E (M,) implies
that we can find some x' E M& and x" E A (x) n (x'). Therefore by the consistency constraint
h T h(x") h(x) h(x'). On the other hand, x E X \M, implies that h(x) 0k f
l(xx), and leads to a contradiction.
Restating Theorem 5 with the formal notations in the appendix: with high probability,
Lo1 (Tdac) Loi (1²)
K log K + logn
Proof of Theorem 5. By Lemma 3, since
TX (Ht S (h E H Mxx) = 0h Vx E X.) where (Tx E
[K] [<]]:
the consistency constraint yields finite feasible classifier class with T (H)) K! - K
Meanwhile, since A(x) S. fx' E X' (x) h (xx)),, by construction, we know that Tidar (H) is realizable (i.e., h TTilac (7() such that [dda(h") 0). Therefore,
[Lo1 (R
3h = T (H) Loi (h) > e A idac (h) = 0/
< IPPP
where for every classifier E (HA)(HH))
P [Loo (h) A Ida = 0] <1 c)" Se
21

---

Under review as a conference paper at ICLR 2022
Then by the union bound, have
P
Loi
c
P
Loi (h) > E A Ldr 0]
AET (H)
T (H) -
The proof is completed by upper bounding the above, IP (Lor (Titee)
S 1/n, when taking
log
A,
(H) + log n
K log K log
n
n
and observing that Loi (h*) O.
Finite unlabeled data. For the finite unlabeled data case, we start by introducing some addi- tional concepts and notations. We concretize the classifier class H with proper function class l(x) argmax
such that H adapt the existing setring 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 regulariza- tion with finite unlabeled observations X" [x" ........ x5 we leverage, from Wei & Ma (2021), the notion of all-layer-margin, m F X' y R20. that measures the maximum possible perturbation in all layers of f while maintaining the prediction y. Precisely, given any f E J such that (x) W Wpip (... (Wx).... ...) for some activation function R + R and parameters (W, E R. xd, 1 1= we write f f2p-1 o...o fi where fx) W.x for all [p] and (z) (z)) for (p- 1]. For an arbitrary set of perturbation vectors ō (ō1,..., 82p-1) such that 62.-1, 62, E Rd. for all let f(x, 8) be the perturbed neural network defined recursively
JF (
f(x)x fEF]. Specifically,
1==1
such that
1 f1 (x) |x|| 8,
2. ft (2.-1) + 2 5. = 2,...,2. 2p 1,
f(x, 8) 2-p-1-
The all- laaer--mrggi m x, measures the minimum norm of the perturbation 8 such that f(x, 8) fails to provide the classification y.
2p
m(f, x,
18.12 s.t. argmax f(x, 8) + y. kE(K]
With the notion of all-layer-margin established, for any A X 2 that satisfies conditions in Definition 4, the robust margin is defined as
m)(fx) & sup m m(ix' f,,,' argxax kE(N]
argmax fxx)
x'EA(x)
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 (xx.s)))xpssiin-baasee data augmentation). With respect the given function class F and some proper constant - > 0, Let A : X' + 2 be function that satisfies conditions in Definition 4, and additionally,
sup inf (f, fer XE
Then for any sample x E X, x' E X' a (F, T) expansionn based data augmentation of x induced by A xf E A(x).
22

---

Under review as a conference paper at ICLR 2022
Remark 4. The existence of the (F.r)-expansion-basee data augmentations relies the suitable choice of with respect to the given F. For a fixed F, as T increases, Equation (8) imposes stronger assumption 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 g,
== ( R S2p-1 .... S1, (x) = W,x, (2) ( 1,....=
where with W, Rd. Rd.xd.11 for all [p], 9 max,=o....pp d,- The goal is to learn a classifier Ado [ Plly (x)) where fddn E FF is fully connected neural network. With respect to F. we choose a suitably large r > O such that there exists a A X' - 2 fulfilling the conditions in Definition 5. To enforce sufficiently strong consistency of with finite unlabeled samples, incorporate the DAC regularization with a positive robust margin such that,
x
* ht (xx)) A argmin D (h) = Σ (x.)
(9)
NEH
π
s.t.
MA AA VielN..
In terms of the DAC operator, the algorithm can be restated as h & argmin ker (H6) Ld with
Tuke - (H) - {h H ma(fx()) [ie
Definition (Expansion assumptions, Wei al. (2021); Cal (2021)). The marginal distribution Pa (x) satisfies
(a) (q, conosttntt expansion if given any S C X with pa (S) 2 q and P* (S for all l E [K], P (NB (S)) 2 min (Pr {S)) + P (S); (b) (a, c) --mulipplicative expansion for all [K], given any S S X with P (S Xx) S a. pa (NB (S) n (x)) ) 2 min {c. P (k) 1).
Proposition 11 (Wei et al. (2021) Theorem 3.7, Cai et al. (2021) Proposition 2.2). For any å E (0, 1), with probability least - 6/2, there exists some μ such that
Pp- Ba-'x' E A(x) s.t. h(x)) # ((x') S Ei Liaiva W.Wlle + TVN
log (1/8) plog N
N
for all h E T (H), where Ō (.) hides polylogarithmic
N and d.
Theorem 12 (DAC with expansion-based data augmentations over finite samples). With proper choices of O, for any A X > 2 inducing (F, expansssiin based data augmentations, learning the classifier with DAC regularization, Equation (9), provides that, for any E (0. 1), with
probability at least 8,
/
2 log 4/0)
Loi
(idae Lon (h*) S 49
(10)
n
In specific, for some 9 }, with sufficiently large unlabeled sample size N such that μ < 1/2 min (c - 1,1
(a) when pa (x) satisfies (q, 2n) -constaatntt expansion,
2K log K + 2K max {g. 2u),
R <
n
(b) while when Pa (x) satisfies (g. c) multiplicaatiee expansion.
2K log K
4K μ
99 <
min (c 1, 1,
23

---

Under review as a conference paper at ICLR 2022
where we recall from Proposition 11 that,
E Vq (. .ll
log (1/8) + plog N
p S
TVN
N
Lemma 4 (Cai et al. (2021), Lemma A.1). For any h E TAx (H), when P satisfies
(a) (g, 2p)-constant expansion with q < 1. Pa (M) S max {q, 2μ};
(b) (2 c) multiplicative expansion with > 1 1+ Au, P (M) S max { c-1 2
2p
Proof of Lemma 4. We start with the proof for Lemma 4 (a). By definition of Mr. and Øk. know
that M2- = M n A S 2. Therefore, for any 0 < q < 2. one of the following two cases holds:
(i) Pa (M) qi
(ii) P (M) 2 q. Since Pa (M < 1 for all k E [K] holds by construction, with the (g. 2p) connttnt expansion, P (NB (M)) 2 min {P" (M) 2n} + P* (M).
Meanwhile, since the ground truth classifier ht is invariant throughout the neighborhoods,
NB (M&)NNB (Mxy) = @ for k * k', and therefore NB (M) \M = U NB (M₂) M with each NB (M&) \M disjoint. Then, we observe that for each x E NB (M) \M, here exists some & h" (x) such that x NB (M&) \M--
E M&M implies that h (x) = Dk. while x E NB (M&) suggests that there exists some x' E A (x) n A (xx) where x" E Mr such that either h (x') = yn and h (x') A (x") for x' E A (x"), or & (x') + The and h (x') of h (x) for x' E A (x). Therefore, we have
P" (NB (M) \M) S p- 3 E A(x) s.t. 1(x) * h(x')l < 2p. Moreover, since P (NB (M)) - P* (M) < pr (NB (M) \M) - 2/,, know that min [P* (M), 2n}- P (M) < P* (NB (M) - P* (M) 24,.
That is, Pa (M) S 2p.
Overall, we have Pa (M) < max {g, 2n}.
To show Lemma 4 (b), recall from Wei et al. (2021) Lemma B.6 that for any >> 1 + 4p, (+, c) multipliccatie expansion implies
2u c-I 2p -constant expansion. Then leveraging the proof
2p for Lemma (a), with q c- have P (M) max
2g T- 2p
Proof of Theorem 12. To show Equation (10), we leverage the proof of Proposition 8, and observe that B with the zero-one loss. Therefore, when conditioned on T (H), for any E (0, 1), with probability at least 5/2,
Loi (h*) < 49, (lor o TA (H)) + log(4/8)
Loi
For the upper bounds of the Rademacher complexity, let ğ suPherdee (H) P* (M) where M denotes the global minority set with respect to h E T (H). Lemma 4 suggests that
(a) when Pa satisfies (q. 24) consttant expansion for some q < 1,2 Ā S max {g. 24}; while
(b) when Pa satisfies (2. c) multiplicaaiiee expansion for some > 1 + 4p, j S min(c-1.1)
Then, it is sufficient to show that, conditioned on Tiaes (H))
2K log K + 2K
Ru (lor o Thee (H)) <
(11)
To show this, we first consider a fixed set of n observations in X. X [xi,..., E X Let the number of distinct behaviors over X in Tyge.. (H) be
(T (H), X) A [h (x1), .... h h E Tdac. (H))
24

---

Under review as a conference paper at ICLR 2022
Then, by the Massart's finite lemma, the empirical rademacher complexity with respect to X is upper bounded by
2 logg a (Toxx- (?1), x
Rx (l01 Txx (H)) s
By the concavity of Vlog (.), we know that,
2 2ogg s
(Tdex (H), X
Rn (l01 Tole (H)) =Exx ii (lo1 T (H0) Ex
log Ex
(Tdex (H):
(12)
Since P (M) S for all h E TAX (H), we have that, conditioned on T (H),
Ex (s (TAM (H), x) -
1 (1 p0) K K
SK k
(MR)" (1 - (1-1
==0
= K k (1 T + KT
<K* Knp
Plugging this into Equation (12) yields Equation (11). Finally, the randomness in T (H) is
quantified by i., μ., and upper bounded by Proposition 11.
B.4 SUPPLEMENTARY EXAMPLE: DOMAIN ADAPTATION
As supplementary example, we demonstrate the possible fallure of the ERM on augmented training set, and how the DAC regularization can serve remedy, with illustrative linear regression problem the domain adaptation setting: where the training samples are drawn from some source distribution Ps while the excess risk is tested over related but different distribution Pt, known as the target distribution. Specifically, assuming that Ep- [y|x] and Ep [y|x] are distinct, but there exists some invariant feature subspace X, C X' such that Ps [y/x X,] p [y|x Xr), aim to demonstrate the advantage of the DAC regularization over the ERM on augmented training set, with provable separation in the respective excess risks.
S.
Figure 4: Causal graph shared by ps and pt.
Source and target distributions. Formally, the source and target distributions concretized with the causal graph in Figure 4. For both ps and pt, the observable feature x is described via a linear generative model in terms of two latent features, the 'invariant" feature Çiv Rdo and the "environmental" feature S. E TRde;
-Si Se) A S (Swi Ce] SioCio + S.Ce:
25

---

Under review as a conference paper at ICLR 2022
where S [St., S.] E (d)((d (diy + de S d) consists of orthonormal columns. Let the label y depends only on the invariant feature Çiv for both domains,
y (0") == =00) Siu - + 22, 2 2~~(
1 Siv
for some 0 Range (Si.) such that pa [y]] ps [y/ Giol, while the environmental feature S. is conditioned on y. Siv, (along with the Gaussian noise 2), and varies across different domains with Ep. [y/x] * Ep. [g/x]. In other words, with the square loss 1(h(x), y) } (h(xx y)² 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 ps can overfit the source distribution, in which scenario identifying the invariant feature subspace Range (Stv) becomes in- dispensable for achieving good generalization in the target domain.
Moreover, assume the following regularity conditions the source and target distributions:
Assumption 3 (Regularity conditions for Pa and Pt). Let pa satisfy Assumption I, and pt satisfy the following: let Ep. xx > O, and
(a) for the invariant feature, Cr. o Ep (Siv & CiivoIer for some C1, 2 Ct,iv (1); (b) for the environmental featture p ISe i cr,edd, for some Ct.e > O, and Ep [z Ge = 0.
Training samples and data augmentations. For a fair comparison between learning with the DAC regularization and the ERM augmented training set, restrict to the supervised learning setting: X X E X². Recall that we denote the augmented training sets, including and excluding the original samples, respectively with
A = [11] .. :X, X1,1 " ( X1,ai ... an,a) x(1+aan
A(x) [x1,1 : (X1,a [n,aa x
In particular, we consider set of augmentations that only perturb the environmental feature Çe, while keep the invariant feature Çiv intact,
S X = ST
S. + ST. xix Vie [n], j E [a].
(13)
We recall the notion dang rank (Ā(X) MX) rank (Ā - MX) (notice that 0 < Jnus S de), and assume that and A(X) are representative enough:
Assumption 4 (Diversity X and A(X)). (X,y) x x y is sufficiently large with >> p'd 0r E Espan {x; E [m]], and damng = da.
Excess risks in target domain. Learning from the linear hypothesis class H [M(x) = T x
E ] with the DAC regularization on h (xx) = h (x we have
@dac
argmin (eT
I1y
x0l 2
Thee (H) = {n (x) = oTx Á(x) = MX8].
2n
while with the ERM on augmented training set,
dda-erm
argmin
1
My - A(x)
OER
2(1 a:nn
where M and M denote the vertical stacks of and 1+ identity matrices of size n n,, respectively as denoted earlier.
We (x)().)) [ 0
interested in the excess risk on pt: Le (0) L. (0r) where L1 (0)
Theorem 13 (Domain adaptation with DAC), Under Assumption 3(a) and Assumption 4, @ sal- isfies that, with constant probability,
2d
Ep- (gddaa - L((0')
<
(14)
n
26

---

Under review as a conference paper at ICLR 2022
Theorem 14 (Domain adaptation with ERM augmented samples). Under Assumption and Assumption 4, @dac and @da-erm satisfies that,
Ep-
- - Ep [ - -L( Ct,e" EERe,
(15)
for some EER, > O.
In contrast to ddoc where the DAC constraints enforce S.. Ōduc = 0 with a sufficiently diverse À (X) (Assumption 4), the ERM on augmented training set fails filter out the environmental feature in @da-erm: S @da-erm j O. As a consequence, the expected excess risk of @da-erm in the target domain can be catastrophic when Ct.c - 0o, as instantiated by Example 2.
Proofs and instantiation.
We first recall from the beginning of Appendix B that
L (Ā(x) ( -M) (a(x)- -MX)
is the orthogonal projector onto the dimension-(d- - dame) null space of Á(x) MX. Furthermore, let Pi. S. and P. _ S.S.T be the orthogonal projectors onto the invariant and environmental =(Pse
feature subspaces, respectively, such that x S S.Co- = se + P.) x for all x.
Proof of Theorem 13. By construction Equation (13), (A(X) - MX) P.v = 0, and follows that
P & Pv. Meanwhile from Assumption 4, doug de implies that dim (Px) dan. Therefore,
P.v Pu. and the data augmentation consistency constraints can restated as
T (7)) & {h (x) = AT x P = } (x) = 0 x Pi = 0}
Then with 0 span {x; E [n]] from Assumption
1 - x,,
1
daac 0"
P (XP 0" +2) - 0 = - -Ex xx
P z.
x,0
where
Σx..
LP Po TXP, ic. Since @dac
0r E (S,)),
we have
Ep
x Pe Pe(Odac - 0*) = 0. Therefore, let Ex, A Ep [xx J. with high probability,
1
Eps
[,(@dac) - (0') = Ep
@dec 0. Ex.e_
2
Pi (2P.,XXXX
)( Ex.t
tr
Epp
12z 1 Epa
2n
tr
Ep
Exx11
2n
0²
< Ci
tr [Bpo (5x..
(Lemma 5, w.h.p.)
2n
tr (Epo XPixxx P(nl)
2n
S d'
< ir(Piv)
2nc
2n
Proof of Theorem 14. Let Σ A(x)
A A(x) (X). Then with 0- span fx l E [n]]
T
[I+ajm Σ
from Assumption 4, we have 0*
S 0¹ Since 0' E Col (S.,,, MxØ
A(X)
A(x)
MXP;.. =(X)0 Then, the ERM on the augmented training yields
St gde-erm 0" = (I+a)m
I(x) M(X0' +z) St A:::
E Aax) 0-
A(x)
Et (1+a)
1
A(X) MMz.
1(X)
27

---

Under review as a conference paper at ICLR 2022
Meanwhile with Epc [2 Sel 0 from Assumption 3, we have Ep [a P.x] 0. Therefore, by
recalling that Ex,t _ Ep [xx] J.
(, - (.(0)) = (x)
1 (x)
+ + Pe(0- 04)
2 |00 0
2
such that the expected excess risk can be expressed as
Ep-
(odaa-erm -L((0))
2(1 + a) tr EEp
Σ1 A(x)
(A(x)
Mzz M MMA(X)) A(x)) Et. ((x)) Ex.1)
where let ((X.)
2 PP, T(x) P..
Ep.
S1 ((X)
(A(X) Maz M A(X)) Et ((X)
Ep-
(Prc
St
P ic
P
Et
P.
A(X) Mzz M A(X) (Pio i(x) Pir + P.
A(x) (.)x.P))
A(x)
A(X)
b ² + a Epp
Ep
Σt
((x,) A(X.) Mzz M A(X.) A(X.)
A(x.)
We denote
xxxx) A(X.) Mzz M A(X.) ES x ))
EERg
tr Epp
Σt 2(1 + an?
A(x.)
and observe that
EER. = Ep-
- (1 (1-a)m A(x.)
A(X.) Mz
> 0.
2
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-
Ta(@da-erm) - [0()
tr
0
Ep
SSt Xiv
Exxtt)
St + tr Ep 2(1 + a) A(X.) A(X.)
Mzz M A(X.) St St A(X.)
Ex,
2n
expected exoess risk from environmental feature subspace Ct, EER,
> Ep-
+ Cr,e" EER.- (o(dna - -((0))
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 augmented training set (i.e., @da-erm) erm).
Example 2. We consider Pa and pt that follow the same set of relations in Figure 4, except for the distributions over e where ps (e) # pt (e). Precisely, let the environmental feature Çe depend (Sie,9,0 e):
Ce f-sigg (T sign(2)e, ~~, 2ie.
where e ~ N (0, Ia,) for (e) and e ~ N o,,, for P'))), 0, 2 cte (recall Ct.e from
Assumption 3). Assume that the training set X is sufficiently large, n > d. + log (1/8) for some
given ā E (0, 1). Augmenting X with simple by common type of data augmentations the linear
transforms, we let
Á(X) = X: (XAA)...((AA.... A, P + HuyyJ uy. E CS.
Eje
and define
A.
)
V1 A max (1) (I)Uuf (Az) E [(o} and U2 - o
1
I + Σ Ar
I+a
28

---

Under review as a conference paper at ICLR 2022
where mmin()) and (-) refer the minimum and maximum singular values, respectively. Then under Assumption and Assumption 4, with constant probability.
de
Ep T - Ix((0) Ep- (T(@dlac) - T,((0))
+ +,,e""
2n
Proof of Example 2. With the specified distribution, for E
jeli... enl E RRnxd.
S & 1/2 S.E ES
Σ T(x)) =
Se
E E Σ A
E
E
a)m
Ā(x,) Mz + (1+a)n
1
I
+
Σ J=1
A
S.E |z].
1+a
By Lemma 5, under Assumption 3 and Assumption 4, we have that with high probability, 0.91a, < E E < 1.IIa, Therefore with E and being independent,
2
EER. = Ep.
1 a:) (1+a))
S A(X.) A(X.) Mz
2
(1+
1/2
(
S. ES!
TES '7)
Eps
2n V
n2
2 V
tr (S:S!)
2n
V1
0² de
2n
and the rest follows from Theorem 14.
C TECHNICAL LEMMAS
Lemma 5. We consider random vector x E IRd with E[x] O, E[xx ] E, and x --1/2x
3 being p² p--suggaussian Given an i.i.d. sample of x, X = [x....., x. for any ö E (0, if
> pdd, then 0.90 & 1 X 1.1E with probability high probability.
Proof. We first denote Pxx A ΣΣ as the orthogonal projector onto the subspace X' C Rd supported by the distribution of x. With the assumptions E[x] and E xxx] E, observe that E [x] and E
Px. Given the sample set X of size n > p² (d + log(1/8)) for some E (0, 1). we let = 1 Σ X xx] Px- Then the problem can be reduced to showing that, with probability at least 1 8, |U|| 0.1. For this, we leverage the e-net argument as following.
xx = = [x [xXxxxx
'x
For an arbitrary Xn 8d-1 we have
v
TUv
(v x; xJ
(vTx))²=- -1)
i=1
where, given x; being -ussbaaausiinn, v T x; is p²ssubgaussian Since
E
(v x
2
v=
we know that xx,) 1 16p2 subexponnnnl. Then, we recall the Bernstein's 's inequality,
n min (16p2)² 16p² ))
P Uv
E < 2exp -
IIn the case where E is rank-deficiem slightly abuse the notation such that 1-1/2 and E-1 refer to the respective pscudo-inverses.
29

---

Under review as a conference paper at ICLR 2022
Let N n gd-1 be nnt such that [N] c(d)) Then for some < C2 union bound,
16p², by the
IP
max VEN
| Uv > </) s 22|N]
-
n
min
2
(16p2)
)a
16p²
E
S exp (
n
5
2
(16p?)²
whenever n 2 (0 (d) + log t). By taking ô = exp
-
c2
n we have that
T6p²
max v Uv VEN
I 62 with high probability when n > 4 16p"
2
θ (d), and taking n > p d is
sufficient.
Now for any X n gd-1, there exists some v' N such that ||v v'll2 S 61. Therefore,
v Uv
Uv
Uv + +2 v') v') U (v--v -vo
| |v +2 U122 | 1|v -ivvvvl v + | -
VEN
U112 (26) st |vTuv|)
max
Taking the supremum over 8d-1 with probability least 1 8,
max ver' 84-1
Uv Uv] = 11] S + ||U|l (2e1 + +f)),
[ S
62
2 (1 + +1)
With E - and 62 we have 2-(1+e,)
T0
Overall, if >> p²d, then with high probability, we have | < 0.1.
Lemma 6. Let U C Id be an arbitrary non-trivial subspace in Rd, and g ~ N (0, Ia) be Gaussian random vector. Then for any continuous and Ci-Lipschitz function yp + R fi.e. (ę(u) - p(u')) < C ju u' for all u, ul E RR),
Eg sup g' p(u) S Eg LueU
sup g u LuEU
where ip acts on u witrl, (p(u)), = p(u;). In other words, the Gaussian width of the image (oU & {s(()) Rd E U} upper bounded by that U scaled by the Lipschitz constant.
30

---

Under review as a conference paper at ICLR 2022
Proof.
1 8
Fg
sup g ueU
(0()
sup g
(p() + sup g pp())
2
LuEU
n'EU
ER
sup
g'
(+(u)) - =(('())
2
Lu
1 Eg
sup
1 (1)) - s((un1)
1. 3 is Ci-Lipschitz
2
u.w'EU
j=1
Ct
d Σ
Eg
sup
|/و Uy -/il
2
u,u' EU
j=1
Ct
Eg
sup
g (u - u')
2
Lu,u'EU
Ct
+ sup g T (-u') w'EU
Egg
sup g
2
LuEU
-C1- Eg
sup g
LuEU
D EXPERIMENT DETAILS
In this section, we provide the details of our experiments. Our code adapted from the publicly released repo: https: /gtthub.b.... cow htt.to/dde//iiaaahh-eppepe
Our training dataset 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 different training samples, also trained our model with dataset that contains 1,000 and 20,000 samples. Evaluations are done on standard test set of CIFAR- 1000 which contains 10,000 testing samples.
Dataset:
Data Augmentation:
During the training time, given a training batch, 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 RandAug- ment provides each transformation with single scalar (1 to 10) 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 ran- dom transformations to generate an augmented sample). To see the impact of different augmentation strength, we choose E {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 2 steps. During the training, we adopt the SGD optimizer with momentum set to 0.9, with learning rate for step é being 0.03 x cos 212x16
ix
Additional Settings for the semi-supervised learning results: For the results on semi-supervise 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/ wttp//eencclle/ee/ FixMat captttt-ttttt.........
E ILLUSTRATIVE EXAMPLE
31

---

Under review as a conference paper at ICLR 2022
Here present an illustrative example for lo- gistic regression, which numerically shows the benefits of DAC over ERM, and also clearly demonstrates the impact of different daug and
DAC with 0
DA-ERM with 25
with d
0.9
Test Error
DA-ERM with 20
Example 3. Consider 30-dimensional logis- tic regression. The original training set con- tains 50 samples. The inputs X;8 gener- ated independently from N(O, Iso) and we set 0" [0;; with ~ (0, Ia) and IR27.
0.7
2
10
12
Number nuttionatiions per sample (i.c.
To generate the augmentations, we first specify parameler daug and leave the first 30- daug elements of each X4 unchanged, and replace the later dang elements of each X4 with new vector randomly generated from (0, Adwr). Further, we generate augmentations for each of the x,. For any 2 1, the augmentation will perturb dang coordinates with probability 1.
Figure 5: Comparison of DAC regularization and DA-ERM for logistic regression (Example 3). The results precisely match Theorem and the discussion afterward. As suggested by the the- oretical analysis, the performance of DAC only depends on the daug, not a. Further, given the same augmented dataset, DA-ERM is always worse than DAC. The gap is particularly signifi- cant when the number of augmentations is small (i.e., a small a:).
The results for dang {20, 25} and various os are presented Figure 5. The test error clearly matches Theorem 3 and the discussion after- ward: 1) The generalization performance of DAC only relies on dame but not a, and larger dane gives smaller testing error. 2) The performance of DA-ERM crucially depends
a, when is small (i.e., limited augmentations), the performance between DAC and DA-ER ERM is very significant. And when we further increases o, DA-ERM can only approach DAC but not ner-perform DAC.
32


Reviews:
[{"review_id": "tT7wwZ9-Hqz", "reviewer": "Reviewer_fxf3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Data augmentation (DA) 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.\n- While data augmentation is used for better generalization with less data, it is also used to suppress spurious features and generalize to unseen distributions. A discussion around that is warranted. Also, the theory unfortunately is not applicable to this other major usecase of DA.\n- While this paper introduces a regularizer $\\rho$ in Eq. (1), the exact functional form of the regularizer is of no use as long as it is a proper divergence between the original samples and the augmented samples. However, this is practically not true as the functional form of the regularizer can be make or break in obtaining results. This is a shortcoming of the analysis in this paper, which needs to be clearly reflected.\n- Eq. (2) can be obtained as a limit of Eq. (1) when $\\lambda \\to \\infty$ only if $\\rho$ satisfies certain regularity conditions (e.g., being a divergence). No such conditions are stated in the paper, so the deduction is wrong as stated.\n- The mathematical model for DA that is described in Definition 1 is limited in scope. For example, it cannot capture some of the motivating works that the paper cites, such as mixup. This needs to be clearly stated.\n- The operational meaning of the DA strength in Definition 2 is unclear beyond the linear examples that are provided, as this does not capture any nonlinear relationship between features.\n- As far as I followed, from a theoretical perspective, the data augmentation in this paper $\\widetilde{\\mathcal{A}}(X)$ is always linear for deriving the main Theorems (2-4). \n- It is not clear how Definition 2 does or can capture randomness in training examples or the augmentation function as $d_\\text{aug}$ itself becomes a random variable.\n- Another important relationship that is missing is the relationship between $d_\\text{aug}$ and $\\alpha$ (which is the number of times data is augmented). Can you at least say what happens when $\\alpha \\to \\infty$?\n- One major issue that has been ignored is that $\\widehat{h}^{\\text{dac}}$ as defined in Eq. (2) is not directly solvable through the empirical risk minimization framework. Even worse, it is unclear whether there is any way to devise a stochastic solver for it. Hence, the theoretical study of the paper is only applicable to a solver that is not practically existing.\n- In Theorem 1, it is unclear how one would be able to relate the Rademacher complexity of $T^{\\text{dac}}_{\\widetilde{\\mathcal{A}}, X}$ to $\\alpha$ and $d_{\\text{aug}}$. Henceforth, it is not clear how to interpret the improvement beyond **there is some improvement associated with dac compared to vanilla DA,** which we already knew.\n- In Theorem 1, what is $C_l$?\n- In Theorem 1 and its proof, the data augmentation seem to have been assumed to be a fixed linear transformation. That should be clearly communicated. In particular, in the second line of the proof on Page 13 in Appendix A.1, there is no expectation with respect to the randomness associated with DA. Even if the DA function is deterministic, the set $T^{\\text{dac}}_{\\widetilde{\\mathcal{A}}, X}$ is random so I don’t know how to interpret the inequality.\n\n\nThe 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. \n- Please change the notation of $\\widehat{h}^{erm}$ in Eq. (3). I suggest calling this DA-ERM rather than ERM not to confuse with ERM w/o/ augmentation.\n- The benefit of the consistency regularizer in LR is characterized in Theorem 2 through a quantity called d’. It is not clear to me how to interpret that even after reading Remark 2 and Example 1. Can you please provide a more intuitive explanation?\n\n- Can you please better explain Figure 2? Is the x-axis d’? How is it calculated?\n\n- Why is the bound in Theorem 3 presented in this obscure form rather than the more commonly used high probability bound?\n- Wouldn’t data augmentation without consistency regularization also admit the same form as Theorem 3? If so, then how does Theorem 3 characterize benefits of consistency regularization? In particular, I am not sure if I can follow the argument about the generalization properties of $\\widehat{h}^{erm}$ stated without proof after Theorem 3, and I suspect it to be incorrect.\n- The proof of Theorem 4 is inscrutable. I could not make my way through it although I consider myself to be on the more theoretical side of the spectrum. So, I would say the mathematical exposition of the paper is not accessible to the ICLR general audience.\n- I could not follow what the goal of Section 4.3 is.\n- Theorem 5 is stated for realizable model classes. It is known that in this case, the generalization bounds admit “fast” $O(1/n)$ rates rather than the usual $O(1/\\sqrt{n})$ rates; see Tsybakov (2004); Steinke and Zakynthinou (2020). Hence, the upper bound in Theorem 5 is order-wise loose, and I am not sure how to interpret it.\n\n\nThe 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. While I like the results, there are several major concerns here.\n- First, it is unclear what form of regularizer function $\\rho$ has been used to produce the results in the experiments section. Can you please clearly explain the regularizer for all experiments.\n- As is well known and can also be seen in the experiments, when dealing with overparameterized non-convex neural models, choosing $\\lambda \\to \\infty$ practically results in convergence to poor local minima that do not generalize. For example, this can be seen in Table 1 for $\\lambda = 20$ and if $\\lambda$ is even further increased, the resulting model would achieve the performance of a random classifier. This is a big discrepancy between the theoretical setup of this paper and the empirical setup, and a discussion around this shortcoming is warranted.\n- In Table 1, can you please explain the drop of the performance seen for $\\lambda =1$? One would intuitively expect that increasing $\\lambda$ from 0, the performance would increase, and then it will plateau and then start to deteriorate. Hence, $lambda =1$ performance is counter-intuitive.\n- It is claimed that “the DAC regularization gives a worse performance as it falsely enforces DAC regularization where the label of the augmented sample may have changed.” However, this is not substantiated through sufficient evidence. Either change the language to “might be explained” or provide more evidence.\n\n\nTypos:\n- pg 4, after (1): as an regularizer -> as a regularizer\n- pg 17, Statement of Thm 8: satisfies -> satisfy\n\nReferences\n- Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135–166, 2004. \n- Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Proceedings of Thirty Third Conference on Learning Theory, volume 125, pages 3437–3452, 09–12 Jul 2020. \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This paper develops a mathematical framework for consistency regularization. Several theoretical results and empirical results are provided. Overall, I like the general idea of the paper, however, there are several major concerns with the way it is executed. In particular, the major issue is that the theory and experiments are disjoint and do not support each other. (1) The theory is too tied to linear models and it is unclear how it could be extended beyond linear models. (2) The theory is only applicable to linear models with $\\lambda \\to \\infty$. This regime is not even viable in the empirical world when we deal with neural models (as also evidenced in the experiments of the paper). (3) While the experiments are interesting, they are not conclusive on their own and lack important details. For example the regularizer function $\\rho$ is not specified. Also, baselines for these benchmarks are not compared against. While there are many things that I like about the paper, it does not tell a coherent story, and especially one that would benefit the ICLR audience, and hence I recommend the paper to be rejected in its current form. I hope the authors can clarify some of the explicit comments/questions that I have raised in my review during the rebuttal.\n\n\n====== update after author response ======\n\nI would like to thank the authors for their extensive responses to my original comments as well as the follow-up comments, and also for their revisions to the paper which has improved the paper significantly. Thus, I am raising my score from 3 to 5. While some of my previous concerns are addressed, there are many remaining concerns that would require another careful/extensive revision and would require another round of review, which is why I still don't think the paper is ready to be accepted. I would like to emphasize that I like the general formulation of the problem, and the general positioning of the paper and I think the paper would be a nice contribution to the literature once the problems (especially with mathematical exposition) are fixed. Here are some explicit pointers for the authors:\n\n- **Imprecise and inscrutable mathematical exposition:** There are lots of imprecise statements (which also **Reviewer s3Ue** complained about) still in the revised paper. For example, what does $\\gg$ mean in Assumption 2 (page 15)? At the same time, the math is not followable. I still could not follow some of the proofs.\n\n\n- **Hard to gain intuition/takeaways from theoretical results:** While the authors present several results, it is hard to understand takeaways from the developed theory. While they have addressed many concerns, several still remain. For example, RHS of (the revised) Thm 5 does not depend on any of the data augmentation parameters, such as $d_{\\text{aug}}$ and $\\alpha$. What is the takeaway from this theorem given that the same bound also applies to ERM and DA-ERM?\n\n- **gap between theory and practice not discussed:** Although I explicitly gave feedback to address the gap between the theory and practice, it is not well discussed yet. For example, the theory is developed for $\\lambda \\to \\infty,$ while there is a practical sweet spot for $\\lambda$ in the experiments based on the optimization challenges. While I think that this gap should not be the reason to not accept the paper, it warrants a discussion around the results and their practical applicability, which is currently missing from the paper.\n\nI hope the authors would find these comments useful in revising their paper for a future submission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rKC933plpYy", "reviewer": "Reviewer_QuHm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nThis work presents several clear strengths. \n\n  - This paper is one of the several works pioneering the discussions of data augmentation when used together with consistency loss, although several preceding works have been ignored [1, 2]. \n\n  - After the general form is introduced, several applications can be directly extended, which shows the potential of this work. \n\n  - An interesting definition of the strength of the augmentation\n\n**Weakness**\n\nHowever, I also have several major concerns about this work, for example\n\n - If I understand correctly, Theorem 1 is essentially a re-use of the standard generalization error bound with a replacement of the original hypothesis space to the regularized hypothesis space, and then, the main argument is that since regularized hypothesis space is believed to be smaller, then the new bound is tighter. Overall, I don't think this result is significant enough, especially considering it takes a major position in this paper. \n   \n      - I think is too trivial to be considered as an important theorem of a publication at this level. It might be more appropriate to call it a lemma or a proposition of the theorem of the error bound with standard hypothesis space. \n      - A smaller upper bound does not really say much of the performances, both of the bounds could be not tight, and even they are tight, some discussions of how smaller the regularized one is will be helpful. \n\n  - While it is very interesting to see the definition of the strength of the augmentation, it does not say much in practice. Without a deeper or broader discussion, the definition seems to be a math brick for the theorem, discussions on how it is linked to the practice could be helpful, especially since the definition plays a central role as the major assumption in following theoretical results. \n    - The intuitive explanation offered by the authors are not intuitive enough, in particular, for the examples of using rotation as augmentation (the authors state they use rotation in this paper), what are the intuitions of the definition, how different degrees of rotation corresponds to different strengths, and any numerical evidence can be reported? \n    - Also, what's the intuitive explanation of Assumption 1? \n\n  - With Theorem 1 being trivial, as discussed above, Theorem 2 is probably one of the most important result in this paper, yet there seems  also some issues. \n      -. The proof of Theorem 2 critically depends on Assumption 1, this is not made clear in the main text. \n      -. It might be better to put the full statement, at least the full definition of d' back to the main manuscript. \n\n\n - The empirical results do not offer any validation to the new theoretical discussion, but used to show that training with DAC can benefit in comparison to ERM, a fact that the community has known for a while. \n\n\n[1] Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness\n\n[2] Squared ℓ2 Norm as Consistency Loss for Leveraging Augmented Data to Learn Robust and Invariant Representations", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall, I feel like the theoretical discussion is not significant enough, and the associated experiments are also weak (in the context of theoretical papers)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "kxRcgTIl-fa", "reviewer": "Reviewer_TPuR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- What would be the difference between data augmentation and consistency regularization? This is unclear from the introduction and it serves as a motivation for this work. Previous work has demonstrated that regularized risk minimization problems with augmented training samples (the setting known as vicinal risk minimization) can have identical effect as \"consistency regularization\", i.e., low variance between predictions over original and augmented samples. Please check out the work on vicinal risk minimization and references further developing that line of work.\n[1] O Chapelle, J Weston, L Bottou, V Vapnik (NIPS). Vicinal risk minimization.\n\n- Definition 1: This definition is overly restrictive. For some instances it is natural to have the conditional distribution with larger entropy and yet the instance is a proper augmentation. There are definitely transformations of images that are more confusing relative to labels of interest, when compared to the notion of original instance. This assumption is, thus, not motivated by practical considerations and might be an artefact required for theoretical analysis.\nHere, it is also important to properly introduce \"original\", because in different worlds pairs (x, y) sampled from a data generating distribution are different. This would then imply that the notion of original is not unique.\n\n- Definition 2: It is common actually that the data lies on a low-dimensional manifold and augmentation is in a number of cases just a walk over that manifold. Thus, I see no reason why this metric would be of any use in assessing the informativeness of data augmentation. Also, the difference is the perturbation over the input space which might have nothing to do with the manifold that we would like to learn and over which the data generating distribution actually operates.\n\n- Consistency regularization: What is so special about Eq. (1) in the context of prior work (not discussed nor covered in details)? Is this not equivalent to learning with empirical risk minimization and augmented samples (known as vicinal risk minimization for 20+ years)? For the latter, it can be demonstrated theoretically that it minimizes the variance over the neighborhood in the instance space defined by augmented samples. I can see that Eq. (1) might provide more flexibility when it comes to the enforcement of label alignment over such neighborhoods but that needs to be demonstrated. The vicinal setting is also quite flexible.\n\n- The theoretical results are under restrictive assumptions and in my understanding apply only to linear models. Theorem 4 is an attempt to obtain a theoretical result on the effectiveness for two layer neural network, but the assumption $(x_i^{\\top}B)_{+} = (x_{i,j}^{\\top}B)_{+}$ actually restricts this to linear models as well.\n\n- Experiments: The performance improvements are rather modest, 1% relative on CIFAR-100. In the training setting, were the batches ordered in the same way? The problem is non-convex and that might impact the generalization performance.\n- Table 2: The experiment with different number of samples 1,000 - 20,000: Why only 3 augmented samples per training instance? In such cases, augmentation typically adds many more samples and it would be nice to see the results with 10+ additional samples per training instance, as in the case for the experiment in Table 1.\n- Table 3: How can the performance be consistently the same with 3, 7, and 15 augmented samples? This might be an indication that the augmentation scheme does not do enough to describe the local neighborhoods around training samples. This, in turn, might then not be an objective assessment of the effectiveness.\nTable 4: The same argument as for Table 3, one would expect much more differentiation between numbers for \"strength\" 2, 5, and 10. In fact, this experiment increases my scepticism in the utility of the $d_{aug}$ as a measure of augmentation informativeness.", "summary_of_the_paper": "The paper proposes a regularization approach based on data augmentation and develops learning bounds for that setting. The main motivation is to provide means to characterize reduction in sample complexity as a result of employing data augmentation techniques during training.", "summary_of_the_review": "The assumptions under which the paper operates are quite restrictive and do not see that they hold in practice, and thus apply to widely used data augmentation schemes along with deep learning models. The crux of the theoretical contributions is restricted to linear models, which further limits their scope. The paper does not also cover well the prior work on empirical risk minimization problems, especially the line of work on vicinal risk minimization. Experiments show rather incremental improvement (1% relative) and it is quite strange that there is no substantially larger effect of augmentation when the replication factor goes from 3 to 15.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hCDgB867Otj", "reviewer": "Reviewer_s3Ue", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n### Strengths\n\n1. The paper introduces a formal framework to study data augmentations and consistency regularization. The ideas are simple but novel, with several meaningful results and implications.\n2. The paper is quite well-written, with the main ideas outlined clearly. The approach is well-motivated and seems to be built upon established literature. The review of related works is informative.\n\n### Weakness\n\n1. My main concern with the paper is about the results of Theorem 3 and Theorem 5, which appear (very much) weaker than they should be.\n     - Theorem 5: \"*For some* δ ∈ (0, 1)*, with probability at least* 1 − δ...\" From a mathematical point of view, this is an extremely weak result (delta could be 0.999999). A regular generalization bound would have stated \"For all delta>0, when n is large enough...\".\n     - Theorem 3: \"*With constant probability, learning..\"* The face value of the statement would be that the probability of the event stated in the theorem remains constant as n changes, which is obviously not true. I suppose that the author means \"with probability bounded from below by a constant\". Even in that case, this is a very weak result: wouldn't we want the probability to be at least close to one, or say, greater than 1/2?\n     - The appendix, which is supposed to contain formal statements and proofs, also runs into that problem. Statements about \"constant probability\" appear in several places. The main assumption of the analysis, Assumptions 3: \n\n          n ≫ ρ^4 (d − d_{*aug}* + log(1/δ)  \n         is also stated for **some** delta>0.\n     - Theorem 4, in technicality, doesn't share the same problem. However, its result is only meaningful under Assumption 3, which is subject to the same constraint.\n\n   If I understand correctly, the proofs of the paper might be adapted to support typical generalization bounds, but the manuscript in its current state didn't do that, and the results of the theorems do not make much sense.\n2. The technical contributions of the other main results of the paper, Theorem 1 and Theorem 2, are limited. The proof (and result) of Theorem 1 is straightforward. The result of Theorem 2 for linear regression is interesting, but the proof involves standard computations.\n\n### Other comments\n\n- Throughout the manuscript and also in the appendix (which is supposed to contain rigorous proof), the author used several asymptotic notations such as <<, <~, and big-O notation, which may not be appropriate since (1) the analyses of the paper is non-asymptotic and involves many parameters (2) in rigorous non-asymptotic analyses, statements such as n ≥ N(\\delta) is important but will be obscured using big-O notations\n- A significant part of the proof in the appendix (10 pages) was to prove several results that correspond to a three-sentence remark in the main texts with no result statements. If the authors believe that this is a central point, a subsection in the main text should be created to provide the details. Otherwise, I suggest removing those parts out of the text (just the remarks) and the appendix, since those materials are not central to the content, totally not peer-reviewed, and shouldn't be associated with the paper if it is accepted.\n- Example 1: \"It can be verified that...\". It would be helpful if a short verification is included in the appendix.\n- Proof of Theorem 2: \"The rest of proof is identical to standard regression analysis\". This part is central to the result, so more details should be spelled out, or a reference should be given.\n- Notations: rho is used both as a metric and as the sub-Gaussian constant. This is further confusing since they appear close to each other at times.\n- Proof of Lemma 5:\n    - The last statement on page 28 is incorrect. O(d) do not dominate d.\n    - There is a typo in the equation \"ρ2 ≥ ε2/16\"\n\n### Questions\n\n- How are the regularizing constant (lambda =10) chosen in the last 4 experiments, while it is not the optimal value in the first one?\n", "summary_of_the_paper": "### Summary\n\nThe paper introduces a statistical framework to analyze data augmentation to interpret consistency regularization as a way to reduce function class complexity. Building upon this framework: the paper\n\n- shows that for linear regression, consistency regularization is more efficient than empirical risk minimization\n- provides generalization bounds under consistency regularization for logistic regression, two-layer neural networks,\n- provides a generalization bound for expansion-based data augmentations for multiclass classification\n\n", "summary_of_the_review": "Overall, my vote for the paper is a (weak) reject. I think the framework of the paper is original and the ideas are intuitive with several interesting results and implications. On the other hand, the statements of some of the results are very weak (to an extent that they are not meaningful). The writing of the main text, as well as the proofs, are non-rigorous (which was partially an intention of the authors, at least for the main text, but might have affected the paper's mathematical quality).\n\n==== Update after response and revisions\n\nThe revision addresses my main concern about the weakness of the results of Theorem 3 and 5. On the other hand, I'm still of the opinions that the heavy uses of asymptotic representations and the choices of present thee results of the main text in non-rigorous manner have affected the paper's mathematical quality. A few other concerns are left unaddressed. I thus raise my score from 5 to 6", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows how constraining the representation to be invariant to augmentation shrinks the hypothesis space to improve generalization more than just introducing additional samples through augmentation. I agree with the reviewers that this is a novel, intuitive, and interesting finding. However, there were many technical and clarity issues with the original submission. These were partially addressed by the authors in the rebuttal. The reviewers appreciated the authors' efforts and commitment in the rebuttal, but my conclusion from our discussion that this paper requires another round of revisions. I hope the authors would follow the reviewer's comments, improve the paper, and re-submit.
Decision: Reject