A Theory of PAC Learnability under Transformation Invariances
Authors: Han Shao
Omar Montasser
Avrim Blum
Venue: NeurIPS 2022 Accept (2022)
Keywords: transformation invariance
data augmentation
PAC learning
sample complexity

Abstract: Transformation invariances are present in many real-world problems. For example, image classification is usually invariant to rotation and color transformation: a rotated car in a different color is still identified as a car. Data augmentation, which adds the transformed data into the training set and trains a model on the augmented data, is one commonly used technique to build these invariances into the learning process. However, it is unclear how data augmentation performs theoretically and what the optimal algorithm is in presence of transformation invariances. In this paper, we study PAC learnability under transformation invariances in three settings according to different levels of realizability: (i) A hypothesis fits the augmented data; (ii) A hypothesis fits only the original data and the transformed data lying in the support of the data distribution; (iii) Agnostic case. One interesting observation is that distinguishing between the original data and the transformed data is necessary to achieve optimal accuracy in setting (ii) and (iii), which implies that any algorithm not differentiating between the original and transformed data (including data augmentation) is not optimal. Furthermore, this type of algorithms can even ``harm'' the accuracy. In setting (i), although it is unnecessary to distinguish between the two data sets, data augmentation still does not perform optimally. Due to such a difference, we propose two combinatorial measures characterizing the optimal sample complexity in setting (i) and (ii)(iii) and provide the optimal algorithms.

A Theory of PAC Learnability under Transformation Invariances
Han Shao
Omar Montasser
Toyota Technological Institute Chicago Chicago, 60637
Toyota Technological Institute Chicago Chicago, 60637 omar@ttic. edu
han@ttic.eda
Avrim Blum
Toyota Technological Institute Chicago Chicago, 60637 avrim8ttic. edu
Abstract
Transformation invariances are present in many real-world problems. For example, image classification is usually invariant rotation and color transformation: a rotated car in different color is still identified as car. Data augmentation, which adds the transformed data into the training set and trains model on the augmented data, is one commonly used technique to build these invariances into the learning process. However, is unclear how data augmentation performs theoretically and what the optimal algorithm is in presence of transformation invariances. In this paper, we study PAC learnability under transformation invariances in three settings according to different levels of realizability: (i) A hypothesis fits the augmented data; (ii) A hypothesis fits only the original data and the transformed data lying the support of the data distribution; (iii) Agnostic case. One interesting observation is that distinguishing between the original data and the transformed data is nec- essary to achieve optimal accuracy in setting (ii) and (iii), which implies that any algorithm not differentiating between the original and transformed data (including data augmentation) is not optimal. Furthermore, this type of algorithms "harm" the accuracy. In setting (i), although it is unnecessary to distinguish between the two data sets, data augmentation still does not perform optimally. Due to such a difference, we propose two combinatorial measures characterizing the optimal sample complexity in setting (i) and (ii)iii) and provide the optimal algorithms.
Introduction
Transformation invariances are present in many real-world learning problems. That is, given a certain set of transformations, the label of an instance is preserved under any transformation from the set. Image classification is often invariant to rotation/fli/ccoor translation. Syntax parsing is invariant to exchange of noun phrases in sentence. Such invariances often built into the learning process by two ways. One is designing new architectures in neural networks to learn a transformation invariant feature, which is usually task-speciff and challenging. A more universally applicable and easier way data augmentation (DA that is, adding the transformed data into the training set and training a model with the augmented data. Although DA performs well empirically, is unclear whether and when DA "helps". In this paper, we focus on answering two questions:
Throughout the paper, we refer to ERM over the augmented data by DA.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

How does data augmentation perform theoretically?
What is the optimal algorithm in terms of sample complexity under transformation invariances?
We formalize the problem of binary classification under transformation invariances in the PAC model. Given instance space X, label space y = {0, 1). and hypothesis class H. we consider the following three settings according to different levels of realizability.
Invariantly realizable setting: There exists a hypothesis ht E H such that h can correctly classify not only the natural data (drawn from the data distribution) but also the transformed data. For example, considering the transformation of rotating images where all natural images are upright, the hypothesis h" can correctly classify every upright image (natural data) and their rotations (transformed data).
(ii) Relaxed realizable setting: There exists a hypothesis h² E H such lt" has zero error over the support of the data distribution (and therefore will correctly classify the transformed data that lies in the support of the data distribution), but he may not correctly classify transformed data that lies outside the support of the natural data distribution. For example, there exists an h² classifying all small rotations that lie in the support of the distribution correctly, but misclassifying upside-down cars.
(iii) Agnostic setting: Every hypothesis in H. might not fit the natural data.
In most of this work, we consider the case where the set of transformations forms a group (e.g.. all rotations and all color translations). which is a classic setting studied in literature (c.g., Cohen and Welling 2016; Bloem-Reddy and Teh 2020 Chen et al. 2020). Some algorithms and analyses in this work also apply to non-group transformations (e.g., croppings).
Main contributions First, show that DA outperforms vanilla ERM but is sub-optimal in setting (i) above. We then introduce a complexity measure (see Definition P that characterizes the optimal sample complexity of learning in setting (i), and we give an optimal (up log-factors) algorithm in this setting based on I I-inclusion-gret
predictors. Second, we characterize the complexity of learning in setting (ii) when the learner only receives the augmented data (without specifying which are natural). Such a characterization provides us with a sufficient condition under which DA "hurts". Third, we introduce a complexity measure (see Definition 5)) that characterizes the optimal sample complexity of learning in settings (ii) and (iii) above. and we give optimal algorithms for these settings. Finally, we also provide adaptive learning algorithms that interpolate between settings (i) and (ii), i.e., when h² is partially invariant. We want to emphasize that our complexity measures take into account the complexity of both the hypothesis class H and the set of transformations being considered. The results are formally summarized in Section S
Related work Theoretical guarantees of DA has received a lot of attention recently. Chen al. 20200: Lyle et al. (2020) study theoretical guarantees of DA under the assumption of "equality" in distribution, i.e., for any transformation in the transformation group, the data distribution of the transformed data is approximately the same as that of the natural data (c.g., the upside-down variations of images happen at the same probability as the original upright images). Under this assumption, they show that DA reduces variance and induces better generalization error upper bounds. Our work does not make such an assumption. Dao et al. 2019) models augmentation as a Markov process and shows that for kernel linear classifiers DA can be approximated by first-order feature averaging and second-order variance regularization components. The concurrent work by Shhn et al.. (2022) studies the benefit of DA when training a two layer convolutional neural network in specific multi-view model, showing that DA can alter the relative importance of various features. There is a line of theoretical study on the invariance gain in different models. For example, Elesedy and Zaidi 202T) study the linear model and Elesedy (202T); Mci et al. (02T);; D) Bictti et al. (202)) study the non-parametric regression. The concurrent work by Elesedy (2022) also studies PAC learning under transformation invariances but only provides an upper bound on the sample complexity, while our work provides a complete characterization of learning under this model with optimal algorithms. There is a parallel line of theoretical study on architecture design (e.g., Wood and Shawe- Shawe-Taylor
1996: Ravanbakhsh al. 2017 Kondor and Trivedi 2018 Hloem-Redde and Teh 2020).
Learning under transformation invariances has also been studied a lot empirically. Here we briefly mention a few results. DA has been applied as standard method in modern deep learning, e.g.. in Alexnet (Krizhevsky et al. 2012). Gontijo-Lopes et al. (2020) proposes two measures, affinity and diversity, to quantify the performance of the existing DA methods. Fawzi et al. (2016); Cubuk

---

et al. 2018) Chaziiannazis et al. (02T)) study how to automatically search for improved data augmentation policies. For architecture design, one celebrated example is convolutions (Fukushimal and Miyake 1982 LeCun et al.
1989). which are translation equivariant. See Cohen and Welling
(2016); Dieleman et al. (2016); Worrall et al. (2017) for more different architectures invariant or equivariant to different symmetries.
Another line of related work is adversarial training, which adds the perturbed data into the training set and can be considered as a special type of data augmentation. Raghunathan et al.] (2019); Schmidt et al. 20188; Nakkiran (219)) study the standard accuracy of adversarial training and provide examples showing that adversarial training can sometimes "harm" standard accuracy.
Notation For any n N, let e1, ...... denote the standard basis vectors in R". For any set V and any v E y", let v-; (r1,.... 11-,, Uit1,...., Un) E y denote the remaining part of after removing the i-th entry and (v', V-1) (01.-.., U1-1, v', 0e+1y...., P.)) V denote the vector after replacing i-th entry of v with of E V. Let @ denote the bitwise XOR operator. For any h E yx and X = {II, Fn C X, denote hix (h(z1),... ....................... h((x)) the restriction of on X. A data set or sample is multiset of X' x V For any sample S. let Sx {21(2, y) S} (with multiplicity) and for any distribution D over X' x y, for (z, y) ~ D. let Dx denote the marginal distribution of x. For any data distribution DD and any hypothesis h. the expected error (h) == (((a.)))D( (h(()) F y). Denote err(h) errp (h) when D is clear from the context. For any sample S of finite size, crrs(h) == [s| E(yy)s [1((z) o yl. For any sample S of possibly of infinite size, we say errg(h) = 0 if f(x) = y for all (z. y) S.
2 Problem setup
We study binary classification under transformation invariances. We denote by X' the instance space, ) = } the label space and H the hypothesis class.
Group transformations We consider a group 9 of transformations acting on the instance space through a mapping a: G x X' + X, which is compatible with the group operation. For convenience, we write a(g, = gz for g E G and x E X. For example, consider g = {e, 91, 92, ga} where e is the identify function and 9i is rotation by 90i degrees. Given an image x, ex = is the original image and g1 is the image rotated by 90 degrees. The orbit of any x E X is the subset of X' that can be obtained by acting an element in 9 on Z, Gz == {ørlg E g}. Note that since G is a group, for any r' E Gr. we have Gx' = Gz. Thus we can divide the instance space into a collection of separated orbits, which does not depend on the data distribution. Given a (natural) data set S C X x Y, we call GS == ((ga, (xr, y) E S. g E 9) the augmented data set.
Transformation invariant hypotheses and distributions To model transformation invariance, we assume that the true labels are invariant over the orbits of natural data. Formally, for any transformation group G and X C. we say a hypothesis h is (g. -invariia if
Mggr) = h(x), Vg E G, E X.
That is to say, for every E X, h predicts every instance in the orbit of x the same as x. For any marginal distribution Dx over X. we say a hypothesis is (G. Dx -invariian if h(gx) = h(x) for all nupp(Dxx, i.e., Præ-Da, (3z' E Gr: h(x') # h(z)) = 0. We say distribution g E G, for all G-invariant if there exists a (G, Dxx -iiiiiiiiiann hypothesis f (possibly not in H) D over X x y is with (f*) = 0. We assume that the data distribution is G-invariant throughout the paper.
Realizability of hypothesis class We consider three settings according to the different levels of realizability of H: (i) invariantly realizable setting, where there exists (G. DDx)-invarian hypothesis h² E H with (h") = O; (ii) relaxed realizable setting, where there exists a (not necessarily (G. Dx) )ii-aaaaina hypothesis h² E H with err (h*) = O; and (iii) agnostic setting, where there might not exist a hypothesis in H with zero error. To understand the difference among the three settings, here is example.
Example 1. Consider X = +2), 9 = fe--e) being the group generated by flipping the sign
(i.e., Gr = {x. - xt), and the data distribution 'D being the uniform distribution over {(1, 0), (). H = (h(-) = 0} contuins only the all-zero function, then it is in setting (i) as l((.) = 0 is
(x.DD))-ivarrai -invariant and errp(h) = 0; If H = [1 [/ < 0}} contains only the hypothesis predicting (2) as 1 and {1, 2) as O, then is in setting (ii) as 1 [x < 0] is not (9, Diivarrria but errp [1 < 0)) 0: If H {1(x 0]}. it is in setting (iii) as no hypothesis in H has zero error.
3

---

The following definitions formalize the notion of PAC learning in the three settings.
Definition 1 (Invariantly realizable PAC learnability), For any c. 8 E (0. 1). the sample complexity of invariantly realizable (e, P learning of H with respect transformation group G, denoted MINv(e, 5; H,9) 9) is defined as the smallest yn E N for which there exists a learning rule A such that, for every G-invariant data distribution 'D over X' x Y where there exists a (g. Dx) -invarinan predictor h' E H with zero error, errp(h") = O, with probability at least 1 - 8 over S ~ D"
errp (A(()) S.
such in exists, define MINV (e, o; H. cc. We say that H is PAC learnable in the invariantly realizable setting with respect to transformation group G if, 5 E (0, 1), MINy(e, ,; 6;H, 9) is finite. For any algorithm A, denote by MINv(e, 8; 5; A, the sample complexity of A.
Definition 2 (Relaxed realizable PAC learnability). For any e, E (0, 1), the sample complexity of relaxed realizable (e, 6PC learning of H. with respect to transformation group G. denoted MRE(E, 6; H. G). is defined the smallest m E IN for which there exists learning rule A such that, for every G-invariant data distribution D over X x y where there exists a predictor ht E H with zero error, crrp(h") 0, with probability at least 8 over S ~ Dm,
eTTD(A(S)) S.
If no such m exists, define MRE(E, o; 9) = xc. We say that H. is PAC learnable in the relaxed realizable setting with respect to transformation group G if, E 10, MRE(E, 8; G) is finite. For any algorithm A, denote by MRE(E, 6; H, the sample complexity of A.
Definition 3 (Agnostic PAC learnability). For any e, 1), the sample complexity of agnostic (c, 6)C learning of H with respect to transformation group G, denoted MaG(C, 5; H. 9), is defined as the smallest m. E N for which there exists a learning rule such that, for every G-invariant data distribution D over X x y, with probability at least 1 - 8 over S ~ Dm,
eIr (AA()) & inf (r) + E. NEH
no such exists, define MAG (c, 6; 91 Do. We say that H is PAC learnable in the agnostic setting with respect to transformation group G if, E 1), MaG 6; H, G) is finite.
Data augmentation One main goal of this work is analyze the sample complexity of data augmentation. When we talk of data augmentation (DA) as an algorithm, it actually means ERM over the augmented data. Specifically, given fixed loss function L mapping data set and a hypothesis to [0, I]. and a training set Sum. DA outputs an h E H such that h(x) = y for all (z,, y) E GSSm if there exists one; outputs hypothesis E H with the minimal loss L(SS h) otherwise. When we say DA without specifying the loss function, it means DA w.r.t. an arbitrary loss function, which can be defined based on any probability measure on the transformation group.
To characterize sample complexities, we define two measures as follows.
Definition 4 (VC dimension of orbits). The VC dimension of orbits, denoted VC. 9), is defined as the largest integer k for which there exists set X = [II,...,,II] C X such that their orbits are pairwise disjoint, i.e., Gx, n Gz, = 0, Vi,j E [k] and every labeling of X is realized by a (9, X))invariant hypothesis in H. i.e. Vy E (0, 1) there exists a (9, X--invariant hypothesis h E H.s.I h(x.) = Vi, Vi E [k].
Definition 5 (VC dimension across orbits). The VC dimension across orbits, denoted &C (H, 9), defined as the largest integer k for which there exists a set X = (x1...., C. X such that their orbits are pairwise disjoint, i.e., GI, n nzz = 0, Vi,j E [k] and every labeling of X is realized by hypothesis in H, i.e., Vy E {0, 1,,, there exists hypothesis h E H. s.t. h(x;)) = yr Vi E [k].
Let VCdim (H) denote the VC dimension of H. By definition, it is direct check that VC. < VC.. g) < VCdim(H) For any H. g with (H, = d, we can supplement 7 to new hypothesis class H' such that VC. (H', g) is still d while VC (7L'. 9) is as large as the total number of orbits with at least two instances, i.e., VC.o g) = Hgzz | 2 2, E X}I. This can be done by supplementing H with all hypotheses predicting Gar with two different labels for all x with [Ga] > 2. Besides, for any H with VCdim(H) = d, we can construct transformation group & to make all instances lie in one single orbit, which makes VC,. 9) S 1. Hence the gap among the three measures can be arbitrarily large. Here are few examples for better understanding of the gaps.

---

Example 2. Consider X' = 22.. 22d} for some d > 0 H {1(x E A C
[2d] and [A] =d being the set of all hypotheses labeling exact d elements from [2d] as and g = {e. -e} being the group generated by flipping the sign. Then we have VCo () = 0 since for any i E [2d], there is no (G. {i])- -invariant hypothesis that can label as (which due to the fact that
d. Example 3. Consider X {ar E R2| || = 1} being a circle, the hypothesis class H {0, being all labeling functions and G being all rotations (thus Va, Nx = x Then we have VC (H. VC (H, 9) =
-i is labeled as O by any hypothesis in H). It is direct to check that aC 9) = VCdim(H)
there is only one orbit and VCdim(H) =
Example 4. Consider the natural data being upright images and the transformation set G is rotation by 0, 11,600/1 //0 2 360/n..... ,,....,,, (n 1) 360 / degrees for some integer n. For expressive hypothesis class H (e.g., neural networks) that can shatter all rotated versions of these images, we have VCdim(H) (H) nk and (H. G) VC,o(H, 9) = k. For a hypothesis class H' composed of all hypotheses labeling all upright images and their upside-down variations differently, we have VCdim(H') (n 1)k, vC (H', g) k and (H,' ,)) 0.
3
Main results
We next present and discuss our main results.
Invariantly realizable setting (Definition D
-DA "helps" but is not optimal. The sample complexity of DA is characterized by VCao 9). For any H. G. DA can learn H with sample complexity O (VCC...H..) + log } where ignores log-factors of (H. (Theorem D. For all d > 0, there exists H. 9 with VC.o 9) d and (C, 9) = 0 such that DA needs ( samples (Theorem 2b.
- The optimal sample complexity is characterized by (H, For any H. g, we have Q2 (C.(H.)) log )) < (en((e, o; 9) < O O (C. log 2) (Theorem 4p. We propose an algorithm achieving this upper bound based on 1-inclusion graphs, which does not distinguish between the original and transformed data. It worth noting that the algorithm takes the invariance over the test point into account, which provides some theoretical justification for test-time adaptation such as Wang et al. (20TT)
Relaxed realizable setting (Definition
DA can "hurt". DA belongs to the family of algorithms not distinguishing the original data from the transformed data. We show that the optimal sample complexity of this family is characterized by ((H, 9) (see Definition 6) (Theorem 5). which can be arbitrarily larger than VCdim (H). This implies that for any H. G with ((H, > VCdim(H), the sample complexity of DA is higher than that of ERM.
-he optimal sample complexity is characterized by VC (H, 9). For any H. G, we have 2( (H.0) + lng(1/8) & MRE((,, 6: HH 9) < Õ (H.)) + log }) (Theorem 7 We propose two algorithms achieving similar upper bounds, with one based ERM and one based on l-inclusion graphs. Both algorithms have to distinguish between the original and the transformed data.
An adaptive algorithm interpolates between two settings. We present an algorithm that adapts to different levels of invariance of the target function h", which achieves Ō( (C,o(H))))
e
sample complexity in the relaxed realizable setting and Ö (H.(H. sample complexity in the sampll
invariantly realizable setting without knowing it (Theorem in Appendix).
Agnostic setting (Definition 3)
- -The optimal sample complexity is characterized by VC.o (H, For any H, G. 2 MAG H, 2 MRE(C, 8; H.9), 9), (H, characterizes the optimal sample complex- ity.
MAG 6; H) = o
0 (VCmm.(H.)) log² (CC..(H.0) + + log (Theorem 8). Since
4 Invariantly Realizable setting
In this section, we discuss the results in the invariantly realizable setting (see Definition !|
5

---

4.1 DA "helps" but is not optimal
We show that in the invariantly realizable setting, DA indeed "helps" to improve the sample complexity
from Ō )) (the sample complexity of ERM in standard PAC learning) to Ō (Can(H.9))
First, we have the following upper bound on the sample complexity of DA.
Theorem For any H. G with aC.. < co, DA satisfies that MINv 6: H,, =
0 (H..S) log (H. + 1 log 4)-
Intuitively, for a set of instances in one orbit that can be labeled by H in multiple ways, we only need to observe one instance from this orbit to learn the labels of all the instances by applying DA. Thus, DA helps to improve the accuracy. The detailed proof is deferred to Appendix [A] However, DA does not fully exploit the transformation invariances it only utilizes the invariances of the training set. Hence, DA does not perform optimally in presence of the transformation invariances. In fact, besides DA, all proper learners (i.e., learners outputting a hypothesis in H) have the same problem.
Theorem 2. For any d > there exists a hypothesis class Hi and a group Ga with VC (Ha, Ga) d and (C,, Ga) O such that Misv(e, 5; Ha, Ga, A) ( for any proper learner A. including DA and standard ERM.
The theorem shows that DA is sub-optimal as we will show that the optimal sample complexity is characterized by VC. G) in Theorem We provide an idea of the construction here and defer the detailed proof to Appendix B Consider the X, H and G in Example 2 Pick the target function [[x A] uniformly at random from H. and let the data distribution only put probability mass points in [2d] \ A, the orbits of which are labeled as 0 by the target function. Then any proper learner must predict d unobserved examples of [2d] as 1, which leads to high error if the learner observes fewer than d/2 examples. Theorem 2 also implies that for any hypothesis class including H as a
subset, there exists a DA learner (i.e., a proper learner fitting the augmented data) whose sample complexity is (2
Theorem shows that the sample complexity of DA is Ō (C...HH.S)) better than that of ERM in standard PAC learning, Ō( VCdim(()). This is insufficient show that DA outperforms ERM it might be possible that ERM can also achieve better sample complexity in presence of transformation invariances. To illustrate that DA indeed "helps", we show that any algorithm without exploiting the transformation invariances still requires sample complexity of 22 VCdim(H). ).
c
Theorem 3. For any H. there exists a group G with (H. S 5 s.t. MINv(e, 8; (. = 2 VCdim(H) (H) + 1 log 1) 5 for any algorithm A not given any information about G (e.g., ERM).
The basic idea is that, given a set of k instances that can be shattered by H. for some k > 0, G is uniformly at random picked from a set of 2* groups, each of which partitions the into two orbits in a different way. If given G. the algorithm only need to observe one instance in each orbit to learn the labels of all & instances. If not, the algorithm can only randomly guess the label of every unobserved instance. The detailed construction is included in Appendix C
4.2 The optimal algorithm
We show that the optimal sample complexity is characterized by (C,(H,
Theorem 4. For any H.G with VC. < cc, we have Q VC.(H.)) MINV(E, H, < O (C.(H. log z))
+ 1 log !) <
Our algorithm is based on the l-inclusion-graphh predictor by Haussler et al. (1944.. Given hypothesis class H and instance space X = (a1...., } the classical I l-inclusion graph consists of vertices {hix/h lh E H), which are labelings of X realized by H, and two vertices are connected by an edge and only if they differ at the labeling of exactly single x; E X. Haussler et al. (1994) shows that the edges can be oriented such that each vertex has in-degree at most VCdim H). This orientation can be translated to prediction rule. Specifically, for any i E [4], given the labels of all instances in X except J. if there are two hypotheses h, h E such that their labelings are consistent with the labels of X \ {æx) } and different at I,, then h X Aix are two vertices in the graph and we predict

---

the label of 24 as the edge between x M/x is oriented against. The average leave-one-out-eroor is upper bounded by VCdim(H)
Lemma 1 (Theorem 2.3 of Haussler et al. (1994). For any hypothesis class H and instance space X with VCdim H) < oo, there is a function Q (X x y))* x X y such that, for any & N and sample [(11, y.),..., .... (...,.... (x)) that is realizable w.r.t. H,
1
1[Q((za(0) Vota) bj Fo(t) # ya(e)) VCdim(H)
Σ
0ESym(t)
where Sym(() denotes the symmetric group on [t). The function Q can be constructed by 1- inclusion-grant graph predictor.
Denote by QH.x the function guaranteed by Eq for hypothesis class H and instance space X. For (Iz, v.)}. let X denote the set of different elements in Sx. Define H((s) == x h is (G, Xs)-invariant] being the of all possible (g,Xs (s,xXs iinvariaan label- ings of Xs- We then define our algorithm A(S) by letting (1)) =
any & E N and S = {(11,31)
Xs)
(x))), (5) if H(Xs U {x}) * and predicting arbitrarily if H(Xs U {=}) = 0. That is to say, A(S) needs to construct a function Q for every test example. Given any test example, this -inclusion-grapee based algorithm takes into account whether the prediction can be invariant over the whole orbit of the test example and thus benefits from the invariance of test examples. This can provide some theoretical justification for test-time adaptation such Wang al. (202T). By definition, we have VCdim (X U (x+)) < (H, for all S and æ. Then the expected error of A can be bounded by VC, (H, 9) through Lemma I We defer the details and the proof of Theorem 4 to Appendix D
Note that the results of Theorem also apply to non-group transformation 2
5 Relaxed realizable setting
In this section, we discuss the results in the relaxed realizable setting (see Definition 2p As we can see, DA belongs to the family of algorithms not distinguishing between the original and transformed data. In Section 5.1 we provide a tight characterization ((H, 9) (Definition 6) on the sample complexity of this family algorithms. This implies that when (*, 9) >> VCdim(H), there exists distribution s.t. DA performs worse than ERM. We then show that there exists H. G such that (uH, 9) > VCdim(H) and the gap can be arbitrarily large. In Section 5.2 we provide two optimal algorithms, both of which have to distinguish between the original and transformed data.
5.1 DA can even "hurt"
In the invariantly realizable setting, the optimal algorithm based on l-inclusion graphs does not need to distinguish between the original and transformed data since H(Xs U {x}) in the algorithm is fully determined by the augmented data. However, the relaxed realizable setting, distinguishing between the original and transformed data is crucial. In the following, we will provide characterization of the sample complexity of algorithms not distinguishing between the original and transformed data, including DA. Such characterization induces sufficient condition when DA "hurts".
Let MDA 5; H. 9) be the smallest integer for which there exists a learning rule A such that for every G-invariant data distribution D. with probability at least 1 - 5 over Sur ~ Dmm (A)) < e. The quantity MDA (e, 6; H. )) is the optimal sample complexity achievable algorithms can only access the augmented data without knowing the original training set. In standard PAC learning, the optimal sample complexity can be characterized by the maximum density of any subgraph of the 1-inclusion graphs, which is actually equal to the VC dimension (Haussler et al.) 1994 Daniely and Shalev-Shwart> 2014). Analogously, we characterize MpA(c, (c, 8; H,, 9) based on
a vaninnt of 1-inclusion graphs, which is constructed as follows.
In the 1-inclusion graph for standard PAC learning (Haussler et al. 1994), given any sequence of
instances = (I1,- .., ..e., ..).)). ). the vertices are labelings of and two vertices connected iff. they different at only one instance in x and this instance appears once. our setting, the input is a multiset of labeled orbits and an unlabeled test instance, hence the vertices are pairs of labelings of orbits
In this case, we only assume that contains the identity element.
7

---

and unlabeled instances. Specifically, for any E N, given multi-set of orbits Φ (ei....,0 oi of some unknown original data, a labeling yd is possible iff. there exists a sequence of instances x = .2) E I o and hypothesis h E H. such that lix = and that instances in the same orbit are labeled the same, i.e., (Gx; x {1 - fi)) (())) - 0 for all E [4]. We denote the set of all possible labelings of Φ by
(x( = (f E y" E H, 3x E II oi, h|x f and Dee (Ga; x (1- fa)) ((2) e [0] = 0}.
(2)
Denote the set of all such sequences
Ih= Oi of instances that can be labeled f by
Ur(Φ)= = (x II
o. E H. h1x = f and Useg (Gx, x (1- fiDi ((2g, e [t] 0}.
i=1
Denote the set of all pairs of labeling and its corresponding instance sequence by
B(H, Φ) == (d) (f) x (+(o))
For any xf, E B(H, o), x is a candidate of original data and f is candidate of labeling of x. Now we define a graph Gh.g (T)) where the vertices are all pairs of labeling f E (T) and an element in instance sequence corresponding f. Formally, the vertex set is
V {(f, (f x) E B(H, G) E [t]]-
For every two vertices (f,x) and (g, 2), they connected if and only if (i) exists j E [t] such that x E Φj. f; = 9:, vi + j and f; * gji and (iii) Ø3 only appear once gf.g..) and we denote E the edge set. If edge = {f, x) exists, the edge could be recovered given only f,x or g, I. and thus, we also denote by <ff, .:) (g .) = {f, g, x). Any algorithm accessing only the augmented data corresponds an orientation of edges in the graph we constructed, which leads to the following definition.
2; (ii) there
in Each edge can be represented by
[0, 1] be mapping such that for every e {f, g, x), w(e, f) + w(e,g) = 1 and w(e, h) O if h & e and let W be the set of all such mappings. Note that w actually defines randomized orientation of each edge graph GH,g((); the edge
Definition 6. Let
E (Ø))
gf.g.z)) is oriented towards vertex (f,z) z)) with probability w(e,f). For any (f,x) E B(H,,, Φ). it corre- sponds cluster of vertices {(f, aa) E [1] in GH.g (+)) and Eiet E. (C. w(e(f, the expected degree of the cluster. Let (BB(H, g, Φ)) denote the set of all distributions over B(H, 9, Φ). For any P AAB(H, d)), we define
(HH,9,6, P) = min E [(x))~
Σ
w(e(f,
(4)
wEW
:e(1):eeE
By taking the supremum over P. we define U G, Φ) = SUPPEA(B(H.GGO)) (H,, P). By taking supremum over Φb we define ((H, 9,t) == sup (L,, 9, Φ)) and
M(H 9) sup ((, 9,
(5)
tEN
Theorem 5. For any H. MDA (,,0 6: H, satisfies the following bounds:
For all 2 2 with H(H, G,t) < xc, MDA
16(t-1) 1J M(H.G.)), H. = 92 ((H.9..)) This implies that if
u(H, 9) < cc, there exists a constant dependent H. s.t. MDA H. G) 22( (((((H.))
For all with 1 < ((H.0.)) I 3. MD,M(,,, O (H.G..) log" ((H.0.)) log ))-
If ((H, < MDAlE, 8: (;H, 0 ((H0.9110g(1//)
Theorem 5 implies that when (HH,9) 9) > VCdim there exists distribution such that any algorithm not differentiating between the original and transformed data performs worse than simply applying ERM over the original data. We defer the proof of Theorem to Appendix E As we can see, the definition of μoHH, 9) is not intuitive and it might be difficult to calculate ju( (.. G) as well as
to further determine when (H, g) > VCdim(H).. We introduce a new dimension follows, which lower bounds ((H, G) and is casier to calculate.
8

---

Definition 7 (VC Dimension of orbits generated by H). The VC dimension of orbits generated by H. denoted dim 9). defined as the largest integer l for which there exists a set X
{x1...., .Kk C X such that (i) their orbits Φ = - 0%) are pairwise disjoint, (ii) ( =
yk (defined in Eq 22) and (iii) there exists a set B =
C CBH,,, 9) (defined in Eq (3 such that f + g e₁ implies 24,1 - Ig.. for all i E [g),
Theorem 6. For any H. 9. g) 2 dim 92
The proof is included in Appendix F Through this dimension, we claim that the gap between u(H, 9) and VCdim(H) can be arbitrarily large. In the following, we give example of H. 9 with dim(H, 9) > VCdimmX)) (H), which cannot be learned by DA but can be easily learned by ERM.
Example 5. For any d > 0, ler X = } x {aylt E [24] C R2d+1, , H = {xr > 0, S 0} and 9 {I2d41, I2d+1 (c)) (i.e. the cyclic group generated by flipping the sign of x (.). It is easy to check that VCdim(H) = Ler X = {[1, e1), (1, c2)...., (1. 026)} and then the orbits generated from X are Φ =
E [2d]]] For every labeling f E )22d, if Eieza J is odd, let X ((2f: 1; if Eieed fs is even, let lerx, ((1 2f,, )) It is direct
to check that (f) E g. for all E y2d. Then for all i E [2d], f @ g = c; implies Te, Fg Hence, tlmmH. 9) = 2d, where d can be an arbitrary positive integer. According to Theorem 0 we have p H. 9) 2 d.
The above example can be interpreted in a vision scenario. Let's consider an example of classifying land birds versus water birds. The natural data is 2d images of land birds with land background and water birds with water background. The transformation set is composed of keeping the current background and changing the background from land (water) to water (land). Consider simple hypotheses depending on backgrounds only. Specifically, H {hi, h22 with hn predicting all images with water background as water birds and h2 predicting all images with water background as land birds. Let the data distribution be the uniform distribution over all the original images. Then given any training data, hı and h2 have the same empirical loss on the augmented training data. Thus, for any unobserved image, DA will make a mistake with constant probability. Hence DA requires at least (dd) sample complexity. It is direct to check that standard ERM only needs one labeled instance to achieve zero error.
Open question: It is unclear whether ((H, g) is upper bounded by dim(Hl,)) g). If true, then we can tightly characterize MDA 6; H. g) by ().
5.2 The optimal algorithms
Different from the invariantly realizable setting, the optimal sample complexity in the relaxed realizable setting is characterized by VC. 9). The optimal (up to log-facorss sample complexity can be achieved by another variant of l-inelusion-graph predictor. Besides, we propose an ERM- algorithm, called ERM-INV (see Appendix G for details), achieving the similar guarantee.
Theorem 7. For any H.G with VC (H. G) < 00, we have Ω VC
log(1/5)) S
MRr 6; H. 9) < O (min (VC,.(H..) log (Cnn(H.9) + 1 log 3: (C,.(HL.) log 8)
We defer the details of algorithms and the proof of Theorem 7 to Appendix Usually, ERM-INV is more efficient than the 1-inclusion-grant -rraph predictor. But the 1-inclusion graph predictor as well as the lower bound can apply to non-group transformations. Another advantage of 1 1-inclusion-gran predictor is allowing us design an adaptive framework which automatically adjusts to different levels of invariance of h². Specifically, for any hypothesis h E H. we say h is (1 - -7)-invariant over the distribution Dx for some 7 E [0. 1] Pa-Dx (3rr' E Gv, h((') + h(x)) = 17. When ry(h") = 0, it degenerates into the invariantly realizable setting, which implies that we can achieve better bounds when ry(h") is smaller. We propose an adaptive algorithm with sample complexity dependent on m(h") and the details are included in Appendix [.]
6 Agnostic setting
In the agnostic setting (Definition 3 infseh err(h) is possibly non-zero. Different from the ag- nostic setting in the standard PAC learning allowing probabilistic labels, our problem is limited to

---

deterministic labels because we assume that the data distribution is G-invariant, i.e., there exists a (G, -ii-arraria hypothesis f (possibly not H) with eII = 0.
Theorem 8. The sample complexity in the agnostic setting satisfies:
For all d > O, there exists H. G with aC
d, MAG 1/64: H. (0
For any H, 9 with VC (H,9) < oc, Maa(e, 6; H. = Ō (VC..(2..)) + log ())
For upper bound, we show that ERM-INV achieves sample complexity Ō (VCmm(H. There is another way of achieving similar upper bound based on applying the reduction reduction-to-realizeee to-realizable technique David et al. (2 Note that a direct combination of any reduction-to doduction-t-rraaizzall rerallizaaeee technique and any optimal algorithm in relaxed realizable setting does not work in our agnostic setting, This is because the relaxed realizable setting requires not only realizability, but also invariance in the support of the data distribution. For example, the reduction method Hopkins et al. (202T) needs to run a realizable algorithm over set labeled by each h E H. which might label two instances in the same orbit differently and make the realizable algorithm not well-defined. When combining the reduction method of David et al. (2016) and the 1-inclusion-graa perssiinnnggahtypper algorithm, the similar problem also exists but can be fixed by predicting arbitrarily when the invariance property is not satisfied. For lower bound, According to Ben- David and Umnr (2014), the sample complexity of agnostic PAC learning under deterministic labels is not fully determined by the VC dimension. Following the construction by Ben-David and Urner (2014), details and the proofs are deferred to Appendix H Analogous to the realizable setting, we provide one algorithm adapting to different levels of invariance of the optimal hypothesis in H in Appendix [.2 Similar to the results in the realizable settings, the lower bound and the 1-inclusion-gres -grssihnngrphhh predictor in the agnostic setting also apply to non-group transformations.
provide an analogous lower bound in our setting. The algorithm
7 Discussion
Definition of invariance under probabilistic labels In this work, we model invariance by assuming that the data distribution is G-invariant, which restricts the labels to be deterministic. It is unclear what "invariance under probabilistic labels" means. One option is assuming that the distribution of the labels is invariant over the orbits, Pr(vlgæ) Pr(y]ær for all g G, E X. However, such condition may not characterize invariance in real-world scenarios due to classes having different underlying distributions. For example, given fuzzy image with probability 0.5 being car and 0.5 being a tree, it is uncertain the chance of this image being a car is still 0.5 after rotation.
The performance of DA under non-group transformations Most results of DA and ERM-type algorithms only hold when the transformation set is group. If we regard adversarial training as a special type of data augmentation through ball around the natural data, then the transformation set is not a group. The appropriate way to formulate theoretical guarantees for DA under arbitrary transformations is still open question.
Acknowledgements
This work was supported in part by the National Science Foundation under grant CCF-188501 and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. The views expressed in this work do not necessarily reflect the position or the policy of the Govermment and no official endorsement should be inferred. Approved for public release; distribution is unlimited.
We thank anonymous reviewers for their valuable suggestions. HS thanks Freda Shi for discussion on the application of DA and suggestions from an applied viewpoint.
References
Ben-David, S. and Urner, R. (2014). The sample complexity of agnostic learning under deterministic labels. In Conference on Learning Theory, pages 527-542. PMLR.
Bietti, A., Venturi, I.,, and Bruna, J. (2021). On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 34.
10

---

Bloem-Reddy, B. and Teh. Y. W. (2020). Probabilistic symmetries and invariant neural networks. J. Mach. Learn. Res., 21:90-1.
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. (1989), Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-963.
Chatzipantazis, E., Pertigkiozoglou. S., Dobriban, E., and Danilidiss K. (2021). Learning augmenta- tion distributions using transformed risk minimization. arXiv preprint S.Kv:2111.081999
Chen, S., Dobriban, E., and Lee, J. H. (2020). A group-theoretic framework for data augmentation. Journal of Machine Learning Research, 21:1-71.
Cohen, T. and Welling, M. (2016). Group equivariant convolutional networks. In International conference on machine learning, pages 2990-2999. PMLR.
Cubuk, E. D., Zoph, B., Mane, D., Vasudevan, V., and Le, Q. V. (2018). Autoaugment: Learning augmentation policies from data, arXiv preprint Xiv: S.Kiv.888.009500 805.09501.
Daniely, A. and Shalev-Shwartz, S. (2014). Optimal learners for multiclass problems. In Conference on Learning Theory, pages 287-316. PMLR.
Dao, T., Gu, A., Ratner, A., Smith, V., De Sa, C., and Ré, C. (2019). A kemel theory of modern data augmentation. International Conference on Machine Learning, pages 1538-1537. PMLR.
David, O., Moran, S., and Yehudayoff, A. (2016). Supervised learning through the lens of compression. Advances in Neural Information Processing Systems, 29.
Dieleman, S., De Fauw, J., and Kavukcuoglu, K. (2016). Exploiting cyclic symmetry in convolutional neural networks. In International conference on machine learning, pages 1889-1898, PMLR.
Ehrenfeucht, A., Haussler, D., Kearns, M., and Valiant, L. (1989). A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261.
Elesedy, B. (2021). Provably strict generalisation benefit for invariance kernel methods. Advances in Neural Information Processing Systems, 34.
Elesedy. B. (2022). Group symmetry in pac learning. In ICLR 2022 Workshop Geometrical and Topological Representation Learning.
Elesedy, B. and Zaidi, S. (2021). Provably strict generalisation benefit for equivariant models. In International Conference on Machine Learning, pages 2959-2969, PMLR.
Fawzi, A., Samulowitz, H., Turaga, D., and Frossard, (2016). Adaptive data augmentation for image classification. In 2016 IEEE international conference on image processing (ICIP), pages 3688-3692 Ieee.
Fukushima, K. and Miyake, S. (1982). Neocognitron: self-organizing neural network model for mechanism of visual pattern recognition. In Competition and cooperation in neural nets, pages 267-285. Springer.
Gontijo-Lopes R., Smullin, S. J., Cubuk, E. D., and Dyer, E. (2020). Affinity and diversity: Quantifying mechanisms of data augmentation. arXiv preprint DeXXi::0002.08733..
Graepel, T., Herbrich, R., and Shawe-Taylue Taylor, J. (2005). Pac-bayesian compression bounds the prediction error of learning algorithms for classification. Machine Learning, 59(1-2):55-76.
Haussler, D., Littlestone, N., and Warmuth, M. K. (1994). Predicting (0, 1 Iffunctionss on randomly drawn points. Information and Computation, 115(2):248-292.
Hopkins, M., Kane, D., Lovett, S., and Mahajan, G. (2021). Realizable learning all you need. 11.0446...
arXiv preprint
Kondor, R. and Trivedi, S. (2018). On the generalization of equivariance and convolution in neural networks to the action of compact groups. In International Conference on Machine Learning, pages 2747-2755, PMLR.

---

Krizhevsky, A., Sutskever, I., and Hinton, G. E. (2012). Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25.
LeCun, Y. Boser, B., Denker, J. S., Henderson, D., Howard, R. E., Hubbard, W., and Jackel, L. D. (1989). Backpropagation applied to handwritten zip code recognition. Neural computation. 144):541-551.
Littlestone, N. and Warmuth, M. (1986). Relating data compression and learnability.
Lyle, C., van der Wilk, M., Kwiatkowska, M., Gal, Y., and Bloem-Reddy, B. (2020). On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.0017:
Mei, S., Misiakiewicz, T., and Montanari, A. (2021). Learning with invariances in random features and kernel models. In Conference on Learning Theory, pages 3351-3418. PMLR.
Nakkiran, P. (2019). arXiw:1901.00532.
Adversarial robustness may be at odds with simplicity. arXiv preprint
Raghunathan, A., Xie, M., Yang. F., Duchi, J. C., and Liang, (2019). Adversarial training can hurt generalization. arXiv preprint arXiv: arXiv:1906.0660 1906.0602.
Ravanbakhsh, S., Schneider, J., and Poczos, B. (2017). Equivariance through parameter-sharing. In International Conference on Machine Learning, pages 2892-2901. PMLR.
Schapire, R. and Freund, Y. (2012). Boosting:
Foundations and Algorithms. MIT Press.
Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A. (2018). Adversarially robust generalization requires more data, arXiv preprint arXiv: 1804 1285.
Shen, R., Bubeck, S., and Gunasekar, (2022). Data augmentation as feature manipulation: story of desert cows and grass cows. arXiv preprint arXiv:2203.01572
Vapnik, V. and Chervonenkis, A. (1974). Theory of Pattern Recognition. Nauka, Moscow.
Wang, D., Shelhamer, E., Liu, S., Olshausen, B. A., and Darrell, T. (2021). Tent: Fully test-time adaptation by entropy minimization. In International Conference on Learning Representations.
Wood, and ShawerTaylor, (1996). Representation theory and invariant neural networks. Discrete applied mathematics, 69(12)3333-6 60.
Worrall, D. E., Garbin, $. J., Turruuhammbttv,, D., and Brostow, G. J. (2017). Harmonic networks: Deep translation and rotation equivariance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5028-5037.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This is technical theory work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
12

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' re using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "j1NRNMgqX9n", "reviewer": "Reviewer_vznS", "summary": "This paper studies the PAC learnability of hypothesis classes with different levels of invariance realizability, assuming that the data distribution is group-transformation-invariant. For each realizability case, the authors derive sample complexity bounds for data-augmented ERM and a 1-inclusion-graph-based learning algorithm, using two “invariant versions” of VC-dimension that limit the choices of samples and hypotheses. They show that the sample complexity of the former algorithm is sub-optimal or even worse than ERM while the latter one achieves the optimal sample complexity.\n", "questions": "1. I suggest that the authors give an intuitive explanation for the term “distinguish between the original and transformed data” in the main text.\n2. Readers could also benefit from an intuitive description about the 1-inclusion-graph-based learning algorithm in the main text.", "limitations": "Yes, the authors address the limitation of assuming invariant data distributions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n1. This paper addresses two important problems: PAC learnability under transformation invariance and theoretical understanding of data augmentation.\n\n2. The theoretical analyses are sound and interesting — the two “invariant versions” of VC-dimension are novel and the lower and upper sample complexity bounds in each realizatiliby case are comprehensive.\n\n3. The conclusions, suggesting that the DA can be sub-optimal in practice and using the 1-inclusion-graph-based algorithm could help achieve the optimal sample complexity, are inspiring.\n\n### Weaknesses:\n1. My major concern is to what extent the theoretical results in this paper hold on real data and how much practical insight we could gain from this paper. Specifically,\n    1. The two proposed combinatorial complexity measures seem hard to evaluate in practice. Evaluating the VC-dimension of a neural network class while limiting data points to lie in disjoint orbits seems non-trivial to me. I wonder how many previous results on VC-dimension calculation for neural networks could be adapted here. If we cannot evaluate the proposed combinatorial complexity measures in practice, how can we gain insight from the sample complexity results based on it?\n   2. Many of the main theoretical results, including the arbitrarily large gap between different versions of VC-dimension and all the lower bounds of the sample complexity (which are used to show the sub-optimality and harm of data augmentation), are based on specific data distribution constructions. I understand that these are common proof practices for VC-dimension but am also wondering to what extent they hold on real data? \n\n2. Some descriptions could be made clearer. For example, throughout the paper I do not see how the probability measure on the transformation group is defined for the data-augmented ERM.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cxbZ2R7z2YE", "reviewer": "Reviewer_vPzm", "summary": "Modern computer vision models are trained to be robust to various kinds of transformations such as rotation, tilt, reflection of input images. This is usually achieved with data augmentation when the transformed images are explicitly added to the training set. In an attempt to have a theory that takes into account this feature of modern approaches to learning the authors propose to expand the classical PAC framework by introducing transformation invariant hypotheses and distributions. Realizable and agnostic cases are considered. The modifications of the VC dimension are given, which characterize learnability in different realizability modes. Optimal (in sample complexity) learning algorithms are discussed.", "questions": "Perhaps I missed it in the papaer, but I have this question: if we perform data augmentation under standard PAC learning, but define the sample size as the number of examples in the original (non-augmented) dataset, how does this compare with your estimate of the sample complexity $\\tilde{O}\\left(\\frac{\\text{VC}_{\\text{ao}}(\\mathcal{H},\\mathcal{G})}{\\epsilon}\\right)$ in the invariantly realizable case?", "limitations": "It seems to me that the proposed theory has a limited scope. See item 1 in Strengths and Weaknesses above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) As far as I know, data augmentation techniques are rather simple in the case of image data, but not so simple in the case of textual data. Say, to implement the technique that the authors mentioned at the beginning of the paper (replacement of noun phrases), some external resources will be required (for example, an already trained constituent parser) which we may not assume to be readily available for a wide variety of languages. Therefore, it seems to me that the proposed theory has a limited scope.\n\n2) The proposed theory does not provide a simple characterization of realizable and agnostic learnability, as does the VC dimension in classical PAC learning. In the proposed theory, different modes of realizability entail different characterizations of learnability.\n\n3) The proposed theory does not provide such a simple principle as the ERM in classical PAC learning. The optimal learning algorithm is again conditioned by the realizability mode. Moreover, in some cases the optimal algorithm is transductive (based on a 1-inclusion-graph predictor), i.e. to calculate the label on any new test point, the entire training set will be used (as it is, for example, in the k nearest neighbors algorithm), which calls into question the computational efficiency of learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YpXpsLlFUz", "reviewer": "Reviewer_Qyfx", "summary": "### **Brief summary**\n\nThis paper studies the sample complexity of PAC learning in a setting where the inputs satisfy invariant properties generated by a group. From a theoretical perspective, this paper compares the sample complexity from such a setting to the sample complexity of ERM, and use this as a lens to theoretically reason about data augmentation, which is a popular heuristic but \"is unclear whether and when data augmentation helps.\"\n\n### **Contribution**\n\nThe set up for learning under transformation invariances, as defined by the paper, is as follows: (i) Given a group of transformations, the *augmented data set* is the set of transformed data. (ii) It is assumed that the labels of the data are invariant. Based on this, a hypothesis is invariant to a transformation group if it predicts the same label for a transformed data as the original data.\n\nThe results of this paper are shown under three settings according to the level of realizability of the hypothesis class.\n- First is the *invariantly realizable PAC learning* setting, which captures scenarios where there exist an invariant hypothesis that makes perfect predictions in the augmented data distribution.\n- Second is the *relaxed realizable PAC learning* setting, which captures scenarios where there exist a hypothesis (which may or may not be invariant) that makes perfect predictions in the augmented data distribution.\n- Third is the *agnostic* setting, for which there may not exist a perfect predictor for the augmented data distribution.\n\nThen, the contribution of this paper is to give nearly tight upper and lower bounds on the sample complexity of DA--ERM over the augmented data--for all three settings.\n- For setting one, the sample complexity of DA is given by the VC dimension across the orbits of the augmented data.\n    - However, it is also shown that the optimal sample complexity is instead determined by the VC dimension of the orbits, where the labelings need to be realized by an invariant hypothesis.\n- For setting two, the sample complexity of DA depends on a certain graph orientation.\n    - On the other hand, the optimal sample complexity for learning this setting is given by the VC dimension across orbits (i.e. without requiring the invariant hypothesis)\n- For the agnostic setting, the optimal sample complexity also depends on the VC dimension across orbits.", "questions": "- In the problem setup, it seems that the transformations are assumed to be known a prior. What if they are not given? For example, works like Autoaugment often require finding the \"right\" transformation to apply for a particular task/dataset.", "limitations": "The authors provided a discussion of the limitations of this paper in the main text. The potential negative societal impact is not discussed (possibly but due to the technical nature of the paper); this should be addressed in a revised version.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strength**\n\n- The sample complexity bounds concerning DA depend on the VC dimension of/across the orbits, depending on the exact setting. These bounds provide a new theoretical lens to examine data augmentation. For example, it is argued from the VC dimension bounds that\n    - In the invariantly realizable setting, DA helps compared to ERM. However, it is not necessarily optimal.\n    - In the relaxed realizable setting, DA may actually hurt.\n- This paper also proposes an ERM-based algorithm that achieves the optimal sample complexity. The design of this algorithm is quite interesting in my opinion: It works by first checking whether the test instance can be generated by a transformation of the input. If not, it outputs the ERM prediction.\n- This paper first provides a rigorous mathematical definition of PAC learning under group transformations. I find this formulation nice to read. The contributions and their proofs are well laid out.\n- I find the writing of this paper to be easy to follow. I have some minor comments mentioned below.\n- The discussions section provides a candid narrative of the limitations of this paper.\n\n### **Weakness**\n\n- The discussion concerning the 1-inclusion-graph, starting from L273, could be improved to better explain this concept.\n- In the relaxed realizable setting, the sample complexity of DA depends on a certain edge orientation notion $\\mu(\\mathcal{H}, \\mathcal{G})$. It might help provide some more explanations to give the intuition behind the notion.\n- Some of the proofs in the appendix could use more work to give greater clarity.\n    - L762: The sentence following \"Every labeling\" is broken.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept