Understanding the Generalization Benefit of Model Invariance from a Data Perspective
Authors: Sicheng Zhu
Bang An
Furong Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Data Transformations
Model Invariance
Generalization
Covering Number
Model Complexity

Abstract: Machine learning models that are developed to be invariant under certain types of data transformations have shown improved generalization in practice. However, a principled understanding of why invariance benefits generalization is limited. Given a dataset, there is often no principled way to select "suitable" data transformations under which model invariance guarantees better generalization. This paper studies the generalization benefit of model invariance by introducing the sample cover induced by transformations, i.e., a representative subset of a dataset that can approximately recover the whole dataset using transformations. For any data transformations, we provide refined generalization bounds for invariant models based on the sample cover. We also characterize the "suitability" of a set of data transformations by the sample covering number induced by transformations, i.e., the smallest size of its induced sample covers. We show that we may tighten the generalization bounds for "suitable" transformations that have a small sample covering number. In addition, our proposed sample covering number can be empirically evaluated and thus provides a guidance for selecting transformations to develop model invariance for better generalization. In experiments on multiple datasets, we evaluate sample covering numbers for some commonly used transformations and show that the smaller sample covering number for a set of transformations (e.g., the 3D-view transformation) indicates a smaller gap between the test and training error for invariant models, which verifies our propositions.

Understanding the Generalization Benefit of Model Invariance from a Data Perspective
Sicheng Zhu", Bang An", Furong Huang Department of Computer Science University of Maryland, College Park {sczhu, bangan, furongh/@umd, edu
Abstract
Machine learning models that are developed to be invariant under certain types data transformations have shown improved generalization in practice. However, a principled understanding of why invariance benefits generalization is limited. Given dataset, there is often principled way select "suitable" data transfor- mations under which model invariance guarantees better generalization. This paper studies the generalization benefit of model invariance by introducing the sample cover induced by transformations, i.e., a representative subset of a dataset that can approximately recover the whole dataset using transformations. For any data transformations, we provide refined generalization bounds for invariant models based on the sample cover. We also characterize the "suitability" of a set of data transformations by the sample covering number induced by transformations, i.c., the smallest size of its induced sample covers. We show that we may tighten the generalization bounds for "suitable" transformations that have a small sample cover- ing number. addition, our proposed sample covering number can be empirically evaluated and thus provides a guidance for selecting transformations to develop model invariance for better generalization. In experiments on multiple datasets, we evaluate sample covering numbers for some commonly used transformations and show that the smaller sample covering number for set of transformations (c.g.. the 3D-view transformation) indicates smaller gap between the test and training error for invariant models, which verifies our propositions.
1 Introduction
Invariance is ubiquitous in many real-world problems. For instance, categorical classification of visual objects is invariant to slight viewpoint changes [18, 2, 23], text understanding is invariant to synonymous substitution and minor typos [53, 36, 27]. Intuitively, models capturing the underlying invariance exhibit improved generalization in practice [21, 13, 50, 14, 45, 14]. Such generalization benefit is especially crucial when the data are scarce as some medical tasks [46], or when the task requires more data than usual in cases of distribution shift [38] and adversarial attack [40, 49, 5].
commonly accepted intuition attributes the generalization benefit of model invariance to the reduced model complexity, especially the reduced sensitivity to spurious features. However, a principled understanding of why model invariance helps generalization remains elusive, thus leaving many open questions. Since model invariance may come at a cost (e.g., compromised accuracy, increase computational overhead), given a task, how should we choose among various data transformations under which model invariance guarantees better generalization? If existing data transformations are not good enough for given task, what the guiding principle to find new ones? The lack of a principled understanding limits better exploitation of model invariance to further improve
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

((4)
24
2
Py ce
Ps (x(xx1))== =r
sample cover = (g.
Pg(2) ( n sample cover (g.
(a) G 0
(b) g ("rotation")
Figure 1: Illustration of the pseudometric and sample cover induced by data transformations.
generalization. addition, since identifying instructive generalization bound is a central topic in machine learning, may expect to tighten existing generalization bounds by additionally considering the data-dependent model invariance property.
The many faces of data transformations and model classes pose significant challenges to a principled understanding of model invariance's generalization benefit. 'o address this, [2, 4, 34, 42, 39] characterize the input space and show that certain data transformations equivalently shrink the input space for invariant models, which then simplify the input and improves generalization. From another perspective, [19, 30] directly characterize the function space and show that the volume of the invariant model class is reduced, which then simplifies the learning problem and improves generalization. These understandings provide valuable insights, yet they may become less informative on high- -ige--iinnsional imput data or require the model invariance to be obtained exclusively via feature averaging. Some certain assumptions data transformations (e.g.. finiteness, group structure with certain measure) also make these understandings less applicable to more general data transformations.
In this paper, we derive generalization bounds for invariant models based on the sample cover induced by data transformations and empirically show that the introduced notion can guide the data transformations selection. Different from previous understandings, we first identify data-dependent property of data transformations in a model-agnostic way, and then establish its connections with the refined generalization bounds of invariant models. The analysis applies to more general data transformations regardless of how the model invariance is obtained and naturally provides a model- agnostic guidance for data transformations selection. We summarize
contributions follows.
Contributions. At the core of our understanding is the notion of sample cover induced by data transformations, defined informally as representative subset of dataset that can approximately recover the whole dataset using data transformations (illustrated in Figure 1). We show that this notion identifies a lata-dependent property of data transformations which is related to the generalization benefit of the corresponding invariant models. Under a special setting of the sample cover, we first bound the model complexity of any invariant and output-bounded model class in terms of the sample covering numbers. Since this general bound requires a restrictive condition on data transformations in order to be informative, we then assume the model Lipschitzness to relax the requirement and refine the model complexity bound for invariant models. Finally, we outline a framework for model- wwwarinnce-sessttive generalization bounds based on the invariant models' complexities, and use it to discuss the generalization benefit of model invariance.
Given the usefulness of sample cover in the analysis, we propose an algorithm to empirically estimate the sample cover. This algorithm exactly verifies whether given subset of sample forms valid sample cover, and always estimates sample covering number that upper-bounds the ground- truth. Inspired by our analysis, we also propose to use the sample covering number as a suitability measurement for practical data transformation selections. This measurement is data-driven, widely applicable, and empirically correlates with invariant models' actual generalization performance. We discuss its limitations and the empirical mitigation.

---

To empirically verify our propositions, we first estimate the sample covering number for some commonly used data transformations on four image datasets, including CIFAR-10 and ShapeNet (D) dataset). Under typical settings, the 3D-view transformation induces a much smaller sample covering number than others on ShapeNet, while cropping induces the smallest sample covering number on others datasets. For those data transformations, we then train invariant models via data augmentation and invariance loss regularization to evaluate the actual generalization benefit. Results show clear correlation between smaller sample covering numbers induced by data transformations and the better generalization benefit enjoyed by invariant models.
2 Preliminaries
Data transformations. We refer to the data transformation as function from the input space X' X, and data transformations as a set of such functions. Unless otherwise specified, we do not assume data transformations have group structures since many non-invertible transformations (e.g.. cropping) do not fit into a group structure directly. For a set of data transformations 9 = {g X + X and a data point (also referred as an example) æ E X. we overload the notion of orbit in group theory and denote by ((x) the orbit of x defined as follows. The orbit of æ generated by data transformations
the collection of outputs after applying any transformation g on æ: ((x) = (9(x) E X : 9).
Model invariance. Let D be the underlying data distribution and supp (D) be its support. A model : X' + y is said to be invariant under data transformations g on D h(g(z)) = h(x) for any supp(D) and any g E G. We refer to class of invariant models the G-invariant model class.
Complexity measurements. Covering number and Rademacher complexity [33] are two commonly used complexity measurements for model classes (including neural networks [6]) that can provide uniform generalization bounds. The covering number can also be directly used to upper bound the Rademacher complexity via Dudley's entropy integral theorem [17,35 32].
Covering number. Let (F, d) be (pseudo) space with some (eetrce) d. An e-cover of a set H S F is defined as a subset H C H such that for any E H. there exists E H. such that d(h, T)) Σ e. The covering number (e, H. d) is defined as the minimum cardinality of an e-cover (among all e-covers) of H. In this paper, we use the concept covering number both for measuring model class complexities and for defining the sample covering number on datasets.
Empirical Rademacher complexity. Let H. be class of functions h X - R. Given sample = [xz))_,, the empirical Rademacher complexity of model class 7. is defined as: Rs(H) = E,, [suрдeи Σ oxh():)) where o = [0], on] is the vector of i.i.d. Rademacher random variables, each uniformly chosen from 13.
Generalization error and gap. Let S (x; 1a be a sample drawn i.i.d. from some data distribution D, and H be model class. Given a loss function E R [0, 1]. for a h H. we define the empirical error as Rs(h) = E ((h(z;). y:), the generalization error as R(h) E( (((((())))))))) and the generalization gap as R(h) R& (h).
3 Generalization Benefit of Model Invariance
In this section, derive the generalization bounds for invariant models by identifying the model invariance properties. We start by introducing the notion of sample cover induced by data transfor- mations and based on bound the Rademacher complexity of any invariant models with bounded output (Section 3. Then, we assume model I. Lipschitzness to provide a more informative model complexity bound for any data transformations (Section 3.2). Finally, we provide framework for saadel-ivvarianc--snntti generalization bounds and discuss the generalization benefit of model invariance (Section 3.3).
A pseudometric is metric if and only if it separates distinct points, namely d(x, y) 0 for any +
3

---

3.1 Sample Cover Induced by Data Transformations
Existing empirical results suggest that, compared with standard models, invariant models may have certain properties reducing their effective model complexities. To identify such properties. we alternatively identify the related properties the corresponding data transformations via the notion of sample cover induced by data transformations. We now formalize the introduced notion.
The definition of sample cover relies the pseudometric induced by the data transformations G. Note that G generates an orbit (ax) S X' for each example æ E S. Let || be any norm on the input space X. Given set of transformations G, we define the G-induced pseudometric* as
inf (E((m) J, c(r)ds, where c(r)
{ 0, if E (x))9(x) 1, otherwise
(a 02)
(3.1)
where ds ||dr|l, and I' denotes the set all paths (curves) in from 01 to 22. The Pg is essentially caleulating the line integral along the shortest (if achievable) path y in the scalar field where с can also be viewed as the "moving cost" function depending on G. The norm be selected as any meaningful norm the input space (e.g., Euclidean norm in our experiments) and will later be used in defining the model's 's Lipschitz constant. It can checked that Pg satisfies pseudometric axioms.
|| here can
Definition 3.1 (Sample cover induced by data transformations). Let (X, pg) be a pscudometric space and S {a,}; )i= be a sample of size n. An e-sample cover Sg, of the sample induced by data transformations G at resolution is defined
subset of the sample S such that for any S, there
exists Sç,e satisfying Pe (a: .) S
Definition 3.2 (Sample covering number induced by data transformations). The sample covering
number N(c, Pg) induced by data transformations G is defined as the minimum cardinality of an c-sample cover:
S, min (ine Sg.. is an e-sample cover of S}.
(3.2)
Informally, the G-induced sample cover specifies a representative subset of examples which can approximately recover all the original examples using the given data transformations G. This notion is closely related to the sample compression [20] which represents a scheme to prove the Icarnability of concepts through a compressed set of sample. While identifying the generalization-rcaaed properties of data transformations, this notion is insensitive to other unrelated properties (e.g., finiteness, group structures) and thus applies to any data transformations.
The intuition behind sample cover is that G-invariant models may have consistent behaviors on an example and its associated approximation in the G-induced sample cover. As such, analyze the model complexities of invariant models by considering the models' behaviour only on the potentially small-sized sample covers. Indeed, we directly have the following model complexity result. The proof is in Appendix B.
Proposition 3.3. Let S = { be sample of size n. Let H. be a model class mapping from X' to [-B, B] for some B >> 0 and is invariant to data transformations G. Then the empirical Rademacher complexity of H satisfy
N(0, S.
Rs(H) S 24B
(3.3)
Proposition 3.3 generally bounds the model complexity of any output- bouuuud and G-invariant model class in terms of the sample covering number (00 S, pg) induced by G. small G-induced sample covering number at resolution = 0 thus tightens the model complexity bound for a general class of G-invariant models.
Note, however, that Proposition 3.3 is informative only when the data transformations G yields N (O, S, Pq) & n on the sample S- a condition requiring G be able exactly recover S from small-sized subset of S. This condition is unfortunately too strict to hold for many commonly used
Note that pg is not metric since it allows pz(z, y) 0 y-

---

data transformations which only generate orbits with measure zero (with respect to the data measure) most data points. For example, the rotation transformations on CIFAR-10 do not satisfy this condition, since no two images in CIFAR-10 are rotated versions of each other. To better understand the generalization benefit brought by any data transformations (e.g., rotation), we further assume specific model properties which equivalently expand the orbits in order to get more general results. We study Lipschitz models in Section 3.2, and relegate a sharper (and relatively independent) analysis for linear models under linear data transformations to Appendix C.
3.2 Refined Complexity Analysis of Lipschitz Models
This subsection refines the model complexity analysis for Lipschitz models that are invariant. Char- acterizing the Lipschitz constant of models has been the focus of a line of work. For example, the Lipschitz constant of ReLU networks can be the weight matrices, considering the worst-case inputs [6, 22]. Assuming Lipschitzness, the following theorem refines the covering number analysis for invariant models. The proof is in Appendix B.
by the product of the spectral norms of
Theorem 3.4. Let S h E H is k<-Lischhiz with respect to || (used in defining the sample cover) and invariant to Then the covering number of H satisfies
{= be sample of size n. Let H be a model class such that every
1 - [g,ee (T, H,, S inf N(T (TT- -e--Ke// c20,8g..
.H, _2,.2(P
(3.4)
n
where gh g E H. the (2(sss metric is defined as ||h 100gglgl((p)) = (EwEs 1 n (h(x)) g(x)))²)
and the (F so.) metric is defined as? ||h g glle,(( = (Enese. p(a) (h(x) - g(z)))
Theorem 3.4 upper-bounds the covering number of HH evaluated at the sample S by the new covering number evaluated at any sample cover Sg.., under modified metric and at the cost of an additional error term depending on and K. The equality trivially holds by taking Sg.c S, while by searching over all sample covers with different resolution c it is possible to tighten the covering number bound for invariant models. Additionally, Theorem 3.4 leads to refined version of Dudley's 's entropy integral theorem (see Lemma B. that bounds the Rademacher complexity of invariant models.
Theorem 3.4 suggests that we may improve existing covering-numinnn number-mameeee model complexity analysis by weakening the dependence on input dimensions. Note that covering numbers that do not yield N (T. H., L (IPss) /n + 0 as n + 0o are vacuous. Therefore, existing covering number results typically avoid linear dependence on n at the cost of (cxplicitly or implicitly) increased dependence on the input dimension [52]. With the refined result in Theorem 3.4, however, covering number linear in can now be replaced by one that is linear in potentially much smaller sample covering number (c, S, Pg) and consequently become informative, thus circumvent the increased dependence on input dimensions. An interesting direction for future work is to instantiate the result in Equation 3.4 for specific model classes to get more interpretable results.
3.3 Framework for Model--nnvariance-ensiiiv Generalization Bounds
This subsection presents the framework for generalization bounds sensitive to the model invariance. While the results are straightforward applications of the derived complexities of invariant models, our goal is to justify the selection of suitable data transformations to maximize the generalization benefit. We start with the generalization analysis of invariant models and then present the framework.
Generalization benefit for invariant models. The generalization bounds of invariant models follow immediately by applying the Rademacher model complexities (Proposition 3.3, Proposition B. and Theorem C.1) to the standard generalization bound (Theorem A.2). Compared with standard models, invariant models' tightened model complexity bounds already imply their reduced generalization gaps,
'The term p(æ)/n / can be viewed as the probability mass at x where the numerator indicates the number of examples that æ covers. See Appendix B.I for the formal definition of p(æ).
5

---

whereas for reduced generalization error they further need to have low empirical error. Since enforcing the model invariance may simultaneously increase the empirical error, we can use standard model selection techniques (e.g., structural risk minimization [33]) to select suitable data transformations and control the trade-off.
flodel-ivvrrianc--ssstttt generalization bound. We outline the generalization bound that identi- fies model invariance properties based the derived invariant models' complexities. It follows by the post-hoc analysis which specifies proper set of invariant models using the "invariant loss" - the loss when composed with any model, makes the composition invariant. For data transformations with group structures, we can construct such loss by averaging (assuming Haar measure) or adversarially perturbing any given loss over the orbits of input examples [30, 19]. Specifically, the adversarial loss with respect to data transformations G is defined as 4g (h(z), y) = max é (h(x'), y), where any given loss. Using the adversarial loss, the following proposition provides the model-invariance dependent generalization bound by applying the model selection framework [33]. Appendix B.3 further describes binary coding construction of combinations of data transformation classes.
Proposition 3.5. Let S { be sample of size Let H. be any given model class and l be any given loss. Suppose we have K sets of group-structured data transformations { G2,.., 9x J. Then with probability at least 1 ö, the following generalization bound holds for any h E and any k E [
log k:
log 2n
R(h) S
lo (M((;))) v.) + (Fg H) +
3/
(3.5)
where Rs(Lg, H)) is upper-bounded by the complexity of Ge-invariant models. For any model trained on S, Proposition 3.5 shows that we can optimize over all selections of data transformations to improve its generalization bound. Note that the selection of Gk is subject to a potential trade-off between the reduced model complexity AGG H)) and the increased empirical error E Eg (h(arz), ys). Thus, a suitable GR reduces the model complexity while keeping the empirical error low, then the trained model will benefit from tightened generalization bound. This generalization bound does not require the models to be (strictly) invariant and potentially explains the improved generalization of models with trained invariance (c.g., via data augmentation [43, 41] or consistency regularization [31, 47]). The difficulty in instantiating Proposition 3.5 is that the model complexity with adversarial loss may be hard to compute for general data transformations, Therefore, we discuss more practical data transformations selections based on the sample covering numbers in Section 5.
4 Sample Cover Estimation Algorithm
The sample cover induced by data transformations plays a central role in our understanding of model invariance. Despite the usefulness in the analysis, exactly computing the sample cover turns out to be non-trivial in general. Indeed, computing the transformation-inducaa metrics can be difficult for continuous data transformations, and finding the smallest sample cover is NP-hard. To address this problem, we propose an algorithm to estimate the sample covering number and find the associated sample cover. We outline the algorithm and discuss the algorithmic challenges in this section. The algorithmic details appear in Appendix D.
Setup. The estimation algorithm takes input sample S, set of data transformations G, and the resolution parameter e. then returns the estimated sample covering number N(e, S, Pg) and the associated sample cover Sg.e- The estimation algorithm has the following steps.
Step 1. Compute (or approximate) the direct orbit distance between any two examples in S, The direct orbit distance between any two examples v, By S
(a,, 2.)) = 19(x:) ((
min g1.92
(x:) 02(2,)))
which can be exactly computed for finite transformations (e.g., flipping) with complexity O(g]?),
or can be approximated for continuous transformations (c.g., rotation) via optimization sampling.

---

Step 2. Compute the Pg distance between any two examples in S. Given results in step 1, computing the Pg distance between any two examples can be formulated as a shortest path problem on complete graph, where each node represents an example and the cost of each edge is the direct orbit distance computed in step I (see formulations in Appendix D). Note that the shortest path is always included in our finite candidates even though the Pg distance considers infinitely many paths. This is because any other path outside our finite candidates will be longer than its counterparts (depending on what orbits it intersects) in our finite candidates. Standard shortest path algorithms solve for all pairs of examples in polynomial time ge.g., via Dijkstra's 's algorithm [16] in (nn)).
Step 3. Construct the pairwise distance matrix [2g #;y) ky)]s, and approximate the sample covering number. This step can be formulated as a set cover problem where each example æ covers a subset of S in which each element's ' Pg distance to æ is less than or equal to Our goal is to find a minimum number of those subset such that their union contains S. This problem is known to be NP-hard in general but admits polynomial time approximations [24]. J. In experiments, we use modified k-medoids [35] clustering method to find the approximation of N N S, pG) (see Algorithm 1).
Note that the estimated sample covering number returned by the algorithm is always an upper bound of the ground-truth, regardless of the approximation error in step 1 and 3. When step I is exact, the algorithm also exactly verifies whether a given subset of S forms a valid sample cover. In our experiment, the step 2 becomes the computation bottleneck for large-sized sample. We leave improving the scalability as well as evaluating the approximation quality for future work.
5 Data-driven Selection of Data Transformations
The pool of candidate data transformations on given dataset may be infinitely large. To maximize the generalization benefit of model invariance, we usually make selections based on expensive cross-validations due to the absence of model-training-fiee guidance. Section 3 suggests that invariant models may benefit from improved generalization guarantees if the corresponding data transformations induce small sample covering numbers. Therefore, we propose to use the sample covering number as an empirical suitability measurement to guide the data transformations selection. We discuss its advantages, limitations, and empirical mitigation in this section.
Suitability measurement. To maximize the generalization benefit of model invariance on a dataset S, we measure the suitability of data transformations G by the sample covering number induced by G and favor the small ones.
Advantages. One advantage of this suitability measurement is that it is model-training-free It provides a-priori guidance depending only on the dataset and the data transformations, thus avoids expensive cross-validation. and fuels the exploration of new types of data transformations. Another advantage is that it applies any types of data transformations (including the continuous and non-invertible ones) and provides a uniform benchmark.
Limitations and empirical mitigation. Being model-agnoste also poses two limitations to the suitability measurement. One limitation that this suitability measurement, while capturing invariant models' reduced generalization gap, ignores their potentially increased empirical error. Note that certain data transformations on a dataset may drastically increase invariant models' empirical error and overturn the benefit of reduced generalization gap. To mitigate this limitation, we consider two necessary conditions for maintaining low empirical error. First, the data transformations should preserve the underlying ground-trui truth labeling. We may use domain knowledge to meet this condition. Second, the model class should be rich enough to contain a low-error invariant hypothesis. In our experiment, neural networks which are invariant and achieve low training error suffice this condition.
Another limitation is that this suitability measurement ignores models' potential Lipschitz constant change after enforcing the invariance. Theorem 3.4 suggests that the generalization benefit enjoyed by invariant models depends on models' Lipschitz constant and can overturned if enforeing invariance leads to significantly larger Lipschitz constant. To mitigate this limitation, we use the fact that we are doing classification tasks and use the label information to heuristically offset the Lipschitz constant increase. We use the minimum inter-class distance change after applying data transformations to
7

---

1000
800
750
sample covering number
sample covering number
960
700
940
650
920
600
900
base
550
fllp
flip
rotate
880
rotate
crop
3D-view
860
450
0.0
0.5
2.5
3.0
epsilon
epsilon
(a) CIFAR-10
(b) ShapeNet
Figure 2: Estimated sample covering numbers induced by different data transformations different resolutions c. "base" indicates no transformation. Note that as increases, it starts to exceed the L2 distance between some images and thus some images get covered by others without doing any transformation. Three vertical dashed lines indicate the maximum resolution e at which the "base" yields certain sample covering number, and from left to right they are 100%n, 99%,, 95%n.
capture the Lipschitz constant change and use it to normalize the sample covering number for better data transformation selections (see Appendix E.5.2).
6 Experiments
In this section, we implement the sample cover estimation algorithm and verify the effectiveness of using sample covering numbers guide the data transformations selection. We first estimate the sample covering number induced by different types of data transformations on common image datasets. Then, investigate the actual generalization benefit for models invariant to those data transformations and analyze the correlation'.
Datasets. We report experimental results on CIFAR-10 [29] and ShapeNet [10] in this section, and relegate results on CIFAR-I00 and Restricted ImageNet to Appendix E. ShapeNet is a large-scale 3D data repository which enables to do more complex data transformations (e.g.. change of 3D-view) beyond the common 2D geometric transformations. The work [12] provides 24 multi-view pre-rendered images for each 3D object in 10 chosen categories. For convenience, images to approximate the random perturbation of the 3D-view.
those
Data transformations. We evaluate some commonly used data transformations with typical param- eter settings which we assume be label-preserving. We choose flipping. cropping, and rotation on CIFAR-10. 10, and additionally consider the 3D-view change on ShapeNet. We use the same data transformations with the same parameter settings during estimating the sample covering number and evaluating the generalization benefit. Appendix E provides more details of our experimental settings.
6.1 Estimation of Sample Covering Numbers
We implement the algorithm in Section 4 to estimate the sample covering number induced by different data transformations. For efficiency, randomly sample 1000 training images from CIFAR- 10 and randomly sample 800 training images from ShapeNet. Appendix E compares results with different sample sizes. We use the Euclidean norm for defining the sample cover. For continuous data transformations, we do uniform random sampling to approximate the orbit a data point.
Figure illustrates the estimated sample covering numbers induced by different transformations at different resolution As the resolution increases, the sample covering number ((c,S,Pg) induced
'Code available at http:///gghhbb..ommmmmmaga///nnn invariance..

---

100
1000
all
Model
acc (%)
gap
(%)
gap
(%)
gap
Base
41.05 + 0.52
58.95 + 0.52
68.62 + 0.90
31 31.38 + 0.90
85.43 + 0.35
14.57 + 0.35
Flip
44.19 = 0.74
55.81 + 0.74
75.12 + 0.20
24.88 + 0.20
89.67
0.24
10.33 + 0.24
Rotate
47.02 = 0.46
52.93
+ 0.51
76.07 + 0.28
23.92 + 0.27
89.91
+ 0.13
10.05 + 0.16
Crop
50.47 + 0.48
49.53
+ 0.48
81.84 0.12
18.15 + 0.11
92.52 + 0.08
7.48 + 0.08
Table 1: Classification accuracy and generalization gap (the difference between training and test accuracy) for ResNer18 on CIFAR-10. The number n. denotes the sample size per class.
100
1000
all
Model
acc (%)
gap
acc (%)
gap
acc (%)
gap
Base
67.75 + 2.02
32.25
2.02
83.33 + 0.38
16.67 + 0.38
91.81 + 0.22
8.18 + 01.22
Flip
69.75 + 1.55
30.25 = 1.55
84.24 + 0.30
15.76 - 0.30
92.07
+ 0.20
7.92 + 0.20
Rotate
70.25 +: 1.19
29.50
= 1.15
83.93 + 0.38
15.94 = 0.35
91.85
t 0.20
8.03 : 0.26
Crop
74.88 +: 1.03
23.53
1.30
86.13 + 0.39
13.75 = 0.32
92.64
+ 0.12
7.17 : 0.19
View
78.13 + 1.31
14.94
1 1.76
88.79 + 0.34
8.38
1 0.79
94.38
= 0.08
3.09
+ 0.10
Table 2: Classification accuracy and generalization gap (the difference between training and test accuracy) for ResNet18 on ShapeNet. The number n denotes the sample size per class.
by any data transformation starts to decrease, indicating smaller-sized sample cover needed cover the entire dataset. Mcanwhile, different transformations behave differently. On CIFAR-10. 10, cropping induces the smallest sample covering number. On ShapeNet, 3D-v transformation induces the smallest sample covering number and the gap is significant. Our propositions suggest that data transformations which induce smaller sample covering numbers tends to bring more generalization benefit for the corresponding invariant models. Therefore, Figure 2 indicates that models should generalize well if it is invariant to 3D-view transformation ShapeNet to cropping CIFAR- 10.
6.2 Evaluation of Generalization Benefit
We now evaluate the actual generalization performance of invariant models to verify if the sample covering number is good suitability measurement. We use ResNet18 [25] on both datasets and discuss the influence of model class's 's implicit bias in Appendix E. A simple method to learn invariant models is to do data augmentation. The augmented loss function is Laug x>) L( (g)))) where f(+) denotes the model and g(x) denotes randomly sampled example in x z's orbit induced by transformation G. We use this method on CIFAR-10 and ShapeNet and show results in Table and 2.
Sample covering number correlates well with generalization benefit. We use the generalization gap (the gap between training accuracy and test accuracy) to measure actual generalization benefit. Compared with the baseline, invariant models show an improved reduced generalization gap and also improved test accuracy. On CIFAR-10, cropping-invariin invvarinnn model shows the smallest generalization gap and the highest accuracy. On ShapeNet, the model that is invariant to 3D-view changes shows the smallest generalization gap and the highest accuracy, especially when the training data size small. By comparing results in Figure 2 and Table 1-2, observe clear correlation between the smaller sample covering number and better generalization benefit. This verifies our proposition invariance to more suitable data transformations gives the model more generalization benefit.
Model invariance indeed improves after learning. To verify that the improved generalization is indeed brought by the model invariance, we further enforce the invariance using the invariance regularization loss similar to [48, 51]:
Lats (f(x)) + (f f()()))). Specifically, in addition to minimizing the classification loss on original images, we penalize the model by minimizing the KL divergence between model outputs on original images and on transformed ones. At test time, we use Linr(x) Egg /KL(((g) (z)), [g2 (g)() to evaluate the model invariance under transformation G. Table shows that, as we increase the invariance penalty by increasing X, invariant models enjoy smaller generalization gap. Moreover, the decreased invariance loss and increased

---

X
train acc (%)
test acc (%)
gap
Line
(%)
0
99.99 1 0.01
91.81 + 0.22
8.19 + 0.22
0.0548 1 0.0028
62.0 0.6
0.01
99.98 + 0.00
92.77 1 0.16
7.21 1 0.16
0.0290 0.0029
74.78 1: 1.61
0.1
99.99 1 0.00
93.87 0.19
6.11
0.0152 0.0003
83.12 0.50
0.3
99.98 + 0.00
0.11
5.16
0.0121 = 0.0003
85.10
1
99.58 0.04
94.68
+.68
4.90
0.0095 + 0.0001
86.94 0
3
97.74
94.48
3.26
0.0060 = 0.0003
88.15 1.15
10
95.67
0.26
93.56 0.29
2.11
0.0037 + 0.0002
0.16
100
92.89 + 0.25
91.85 + 0.26
1.03 + 0.03
0.0018 + 0.0001
89.82 0.10
Table 3: Evaluation of 8 on ShapeNet under 3D-view transformations. Live denotes the test invariance loss. Aine denotes the test consistency accuracy (indicating whether model's prediction unchanged after data transformation) under the worst-case data transformations.
consistency accuracy verify that the model invariance indeed improves after training, supporting that the generalization benefit is brought by the model invariance.
Related Work
Understandings from the input space perspective. One line of work characterizes the input space of invariant models. [3, 4] show that the invariant representations equivalently reduce the input dimension for downstream tasks and thus significantly reduce the model complexity (exponential in input dimensions) of downstream linear models. [42, 39] essentially factorize the input space into the product of a base space and a finite set of data transformations. Since the covering number needed to cover the base space smaller, the associated generalization bound for invariant models is reduced. Compared with these works, work tries to cover the sample instead of the input space which circumvents the strong dependence on input dimensions and also enables practical evaluation.
Understandings from the function space perspective. Another line of work directly characterizes the function space of invariant models. [30] uses PAC-Bayes to show the reduction of generalization upper bound when the model class is symmetrized to be invariant. [19] analyzes the function space under feature averaging operator and shows the first strict generalization gap (instead of upper bound) via a linear model. This line of work, while being elegant, so far restricts the model invariance to be obtained exclusively via feature averaging.
Note that the categorization of different understanding perspectives are only for presentation conve- nience and hold no formal distinctions. We also mention some work that studies the model invariance but does not focus on understanding the benefit. [1] proves that the VC-dimension of an invariant model cannot be larger than its counterpart. [9] characterizes the general functional representations of invariant probability distributions as well as neural network structures that implement them. [11] uses group theory show the benefit of learning with aata-augmented loss. In the predicting gener- alization competition at NeurIPS 2020 [26]. the runner-up team [28] shows that model robustness against data transformations can be used
decent empirical proxy for predicting models' gener- alization performance. [37] enforce model invariance to learned data transformations that capture inter-domain variation to improve the out-of mutto--distrbuutio generalization. [8] propose select data transformations automatically from model training via optimizing a parameterized distributions of data transformations. Interestingly, our sample covering number may be used to determine their regularization coefficients for better trade-offs.
8 Conclusion
In this paper, we study the generalization benefit of model invariance by deriving model complexity bounds based on the sample cover induced by data transformations. We also propose an algorithm to estimate the sample cover and empirically show that the sample covering number can guide the data transformations selection. Hopefully, this work will fuel the exploration of more suitable data transformations on specific datasets. An interesting direction for future work to consider the implicit bias of model classes to better understand the generalization benefit of model invariance.
10

---

Acknowledgements
This work is supported by a startup fund from the Department of Computer Science of the University of Maryland, National Science Foundation IIS CRII Award, DOD-DARPA-Defense Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), Air Force Material Command, and Adobe, Capital One and JP Morgan faculty fellowships.
References
[1] Yaser S. Abu-Mostafa. Hints and the VC Dimension. Neural Comput., 5(2):278-22) 288, March 1993. Place: Cambridge, MA, USA Publisher: MIT Press.
[2] Fabio Anselmi, Joel Z. Leibo, Lorenzo Rosasco, Jim Mutch, Andrea Tacchetri, and Tomaso Poggio. Unsupervised learning of invariant representations in hierarchical architectures. arXiv:1311.4158 [cs]. Mar 2014. arXiv: 1311.4158.
[3] Fabio Anselmi, Joel Z. Leibo, Lorenzo Rosasco, Jim Mutch, Andrea Tacchetti, and Tomaso Poggio. Unsupervised Learning of Invariant Representations in Hierarchical Architectures. arXiv:1311.4158 [cs], March 2014. arXiv: 1311.4158.
[4] Fabio Anselmi, Lorenzo Rosasco, and Tomaso Poggio. On Invariance and Selectivity in Representation Learning. arXiv:1503.088 055938 [cs], March 2015. arXiv: 1503.05938.
[5] Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks. arXiv:2004.16617 [cs, stat], April 2020. arXiv: 2004.13617.
[6] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizza margin bounds for neural networks. In Advances Neural Information Processing Systems 30, pages 6240-6249. Curran Associates, Inc., 2017.
[7] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[8] Gregory Benton, Marc Finzi, Pavel Izmailov, and Andrew Wilson. Learning invariances in neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, page 17605-17616. Curran Associates, Inc., 2020.
[9] Benjamin Bloem- Bloem-Reddy and Yee Whye Teh. Probabilistic symmetries and invariant neural networks. 19Xiv:1901 .6082 [cs, stat), September 2020. arXiv: 1901.06082.
[10] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rice 3d model repository. arXiv preprint /512.03 2015.
[11] Shuxiao Chen, Edgar Dobriban, and Jane Lee. A Group- Theoretic Framework for Data Augmentation. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21321-21333. Curran Associates, Inc., 2020.
[12] Christopher B. Choy, Danfei Xu, Jun Young Gwak, Kevin Chen, and Silvio Savarese. 3d-r2n2: A unified approach for single and multi-view 3d object reconstruction. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision ECCV 2016 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part VIII, volume 9912 of Lecture Notes in Computer Science, pages 628 644. Springer, 2016.
[13] Taco Cohen and Max Welling. Group Equivariant Convolutional Networks. In International Conference on Machine Learning, pages 2990-2999 PMLR, June 2016. ISSN: 1938-7228.
[14] Taco S. Cohen, Mario Geiger, and Maurice Weiler. A general theory of equivariant cnns on homogeneous spaces. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché Buc, Emily B. Fox, and Roman Garnett, editors, NeurIPS, page 9142-9153, 2019.

---

for [15] Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. CoRR, abs/1 7.0.04552, 2017.
[16] Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269-271, 1959.
[17] R. M. Dudley, The sizes of compact subsets of hilbert space and continuity of gaussian processes. Journal of Functional Analysis, 133):290-33 -3000 1967.
[18] Shimon Edelman. Class similarity and viewpoint invariance in the recognition of 3d objects. Biological Cybemettcs, 72(3):207-220, Feb 1995.
[19] Bryn Elesedy and Sheheryar Zaidi. Provably Striet Generalisation Benefit for Equivariant Models. vrXiv:2102.10333 [cs, stat], February 2021. arXiv: 2102.10333.
[20] Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the vapnik- chervonenkis dimension, Machine learning, 21 -044,,,4-4, 1995.
[21] Robert Gens and Pedro M. Domingos. Deep symmetry networks. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil Lawrence, and Kilian Q. Weinberger, editors, NIPS, page 2537-2545, 2014.
[22] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299. PMLR, 06-09 09 Jul 2018.
[23] Yena Han, Gemma Roig, Gad Geiger, and Tomaso Poggio. Scale and novel objects in human vision. Scientific Reports, 10(1):1411, Jan 2020.
[24] Sariel Har-Peled Geometric approximation algorithms. Number 173. American Mathematical Soc., 2011.
[25] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[26] Yiding Jiang. Pierre Foret, Scott Yak, Daniel M. Roy, Hossein Mobahi, Gintare Karolina Dziugaite, Samy Bengio, Suriya Gunasekar, Isabelle Guyon, and Behnam Neyshabur. Neurips 2020 competition: Predicting generalization in deep learning. CoRR, abs/2012.07976, 2020. arXiv: 2012.07976.
[27] Erik Jones, Robin Jia, Aditi Raghunathan, and Perey Liang. Robust encodings: A framework for combating adversarial typos. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, page 2752-2722222 2765. Association for Computational Linguistics, Jul 2020.
[28] Sumukh Aithal K. Dhruva Kashyap, and Natarajan Subramanyam. Robustness to augmentations as a generalization metric, 2021.
[29] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Master's 's thesis, Department of Computer Science, University of Toronto, 2009.
[30] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin Bloem- On the Benefits of Invariance in Neural Networks. arXiv:2005.0017. 0017 [cs. stat], April 2020. arXiv: 2005.00178.
[31] Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: a regularization method for supervised and semi-super learning. IEEE transactions on pattern analysis and machine intelligence, 41(8):1979-1999 2018
[32] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
12

---

[33] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. MIT press, 2018.
[34] Youssef Mroueh, Stephen Voinea, and Tomaso A Poggio. Learning with group invariant features:
A kernel perspective. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[35] Hae-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering. Expert systems with applications, 36(2):3336-331,, 2009.
[36] Danish Pruthi, Bhuwan Dhingra, and Zachary C. Lipton. Combating adversarial misspellings with robust word recognition. In Anna Korhonen, David Traum, and Lluís Mårquez, editors, ACL (I), page 5582-58 5591. Association for Computational Linguistics, 2019.
[37] Alexander Robey, George J. Pappas, and Hamed Hassani. Model-based domain generalization. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[38] Shiori Sagawa*, Pang Wei Koh*, Tatsunori B. Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2020.
[39] Akiyoshi Sannai and Masaaki Imaizumi. Improved Generalization Bound of Group Invariant / Equivariant Deep Networks via Quotient Feature Space. arXiv:1910.06552 [cs, stat], March 2020, arXiv: 1910.06552.
[40] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially Robust Generalization Requires More Data. In Advances in Neural Information Processing Systems 31, pages 5014-5026. Curran Associates, Inc., 2018.
[41] Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):1 4-8 2019.
[42] Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Generalization Error of Invariant Classifiers. arXiv: 161004457 [cs, stat], July 2017. arXiv: 1610.04574.
[43] Luke Taylor and Geoff Nitschke. Improving deep learning with generic data augmentation. In 2018 IEEE Symposium Series on Computational Intelligence (SSCI), pages 1542-1547. IEEE, 2018.
[44] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Mądry. Robustness may be odds with accuracy. In International Conference on Learning Representations, 2019.
[45] Maurice Weiler, Mario Geiger, Max Welling, Wouter Boomsma, and Taco S Cohen. 3d steerable cnns: Learning rotationally equivariant features in volumetric data. In S. Bengio, H. Wallach, H. Larochllle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[46] Marysia Winkels and Taco S. Cohen. 3d g-cnns for pulmonary nodule detection. CoRR, abs/ htss/100400466,, 2018
[47] Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoc V Le. Unsupervised data augmentation for consistency training. arXiv preprint arXiv:1904.0 12488, 2019.
[48] Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoe Le. Unsupervised data aug- mentation for consistency training. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, page 6256 6266.6668.22 Curran Associates, Inc., 2020.
[49] Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, page 7085-7094 PMLR, Jun 2019.
13

---

[50] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets, In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, NIPS, page 3391-3401, 2017.
[51] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent EI Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Learning Representations, 2019.
[52] Tong Zhang. Covering number bounds of certain regularized linear function classes. J. Mach. Learn. Res., 2:527-550, Mar 2002.
[53] Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, NIPS, page 657, 2015.
14


Reviews:
[{"review_id": "ycwEowHbpm", "reviewer": "Reviewer_TxB5", "summary": "This submission derives model complexity bounds using the idea of transformation-induced sample covering numbers, proposes an algorithm for estimating them, and implements the algorithm on a few data sets.", "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": "Overall, the paper is clearly written, and of relatively high quality and originality. I think its significance could be improved by devoting more space to the algorithm for estimating the sample cover number (see below); by making more explicit the role of invariance in the theoretical results; and fully considering the trade-off between model complexity and empirical risk in generalization bounds.\n\nThe theory is missing the connection between invariance-induced model complexity reduction and improved generalization. In particular, both in the main text and in the appendix, the role of invariance isn't clear. Generating the sample cover from a set of transformations is intuitive, but once we have that, the role of invariance doesn't seem particularly important. I'm guessing that I missed something so it would be helpful for the authors to clarify. \n\nFurther to that point, all of the theoretical results bound the covering number or Rademacher complexity of $\\mathcal{H}$, and of course that's only one part of a generalization bound. One could map all points to a singleton and have a covering number of 1, but that won't do well empirically. What assumptions are needed about the underlying data distribution in order to either i) guarantee that the empirical risk won't increase (at least in probability); or ii) control the trade-off between empirical risk increase and model complexity decrease?\n\nThe theoretical development seems correct, and is a nice complementary perspective to the function-space perspective (though I would argue that the distinction isn't meaningful---the function space simplifies because the data space simplifies and vice versa). I am much more enthusiastic about the proposed techniques for estimating sample cover numbers. These are potentially very useful. However, the algorithmic challenges are swept to the appendix, where they are mostly swept under the rug. The challenges should be brought front-and-center, and identified as important for subsequent work. With that in mind, I think the paper would be improved by moving most or all of the linear model class special case to the appendix and devoting additional page space to algorithmic considerations and challenges.\n\nFinally, there are some minor typos scattered throughout the text that the authors should fix.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors haven't made clear the extent to which their results focus only on model complexity, nor the potential limitations of their proposed algorithm.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "r7deJ4o8Byu", "reviewer": "Reviewer_omim", "summary": "The authors tried to understand the generalization benefit based on the invariant transformation by improving the sample covering number. Although the paper focuses on an interesting question (how model invariance helps generalization), it seems that it is still not in its best shape. I believe this paper will benefit from (a) careful polishment on the writing, (b) some more insightful results, and (c) more experiments on some complex datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I think the paper has the potential to be accepted after some careful polishment. However, I think the current version has some nonnegligible flaws. \n\n\n## Contributions\n\n1. The authors show that the Rademacher complexity can be reduced when the model is invariant to some transformation (via sample covering number) under Lipschitz and linear regimes.\n\n2. The authors propose an algorithm to estimate the sample covering number empirically.\n\n\n## Concerns\n\n1. During the proof of Proposition 3.3, since the requirement of Proposition 3.6 is much stronger (a Lipschitz requirement), it cannot be directly applied during the proof of Proposition 3.3.\n\n2. The current conclusion (theory part) in this paper is still not insightful enough. I believe if the transformation can greatly reduce the sample complexity, the generalization could be better. If the authors want to claim \"the theory just gives some intuition and the most surprising part is that the practice agreed with the theory\", more experiments should be conducted to verify the statements, e.g., CIFAR-100 and ImageNet.\n\n## Writtings.\n\nI believe this paper can benefit from careful writing.\n\n1. For example, is Proposition 3.3 a well-known result? If so, I wonder why the authors give the proof based on Proposition 3.6 (see Line 498-499). Besides, During the proof of Proposition 3.6, I wish the authors can distinguish between Equation 3.3 and Proposition 3.3 (see line 556). When I first read the proofs, I am a little bit puzzled.\n\n2. Line 118-119, why c(r) = |r| instead of |r-x1|?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No Ethical Concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "LIu6FArfDL", "reviewer": "Reviewer_Q155", "summary": "The paper provides a bound on the Rademacher complexity of a class of Lipschitz and transformation-invariant functions by upper bounding the covering number of the function class by a similar covering number which uses a \"sample cover induced by data transformations\". This is the induced covering number which accounts for transformations of the original sample set and can be smaller due to the transformation invariance of the function. This directly gives improved generalization bounds for transformation-invariant functions. The paper gives some helpful intuition and simple cases where these bounds may be applied.\n\nFurthermore, the paper presents experiments in which the sample covering number induced by different transformations is approximated, and the generalization ability of a model which is trained to be invariant to those respective transformations is shown to be strongly correlated with the sample covering number. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "I think this is a great paper, with nice theoretical results and simple yet surprisingly insightful experimental results (though I note that only briefly skimmed the proofs). I particularly appreciate that this paper gives not only meaningful improvements to generalization bounds, but also a concrete prescription for how to choose data augmentations to improve generalization in practice.\n\nI do think it's a bit limiting that these results hold only for functions which are *fully* invariant, as this rarely holds without some sort of strong structural prior. Would the proof techniques not work for functions which are *close to* invariant? For example, suppose we assume the function class is $\\kappa$-Lipschitz generally, but $\\kappa'$-Lipschitz over group transformations, for $\\kappa' \\ll \\kappa$ (or some other measure of \"approximate invariance\", as Lipschitzness may not appropriately capture such invariance for certain transformations). Would this not allow for a similar result, with an additional error term?\n\nminor nits:\n* In line 95, the definition of covering number for function classes is presented with an argument ordering which is permuted; this should be made consistent to match the orderings used later on.\n* Line 206, these are classes of functions, so this should be \"subset of\" ($\\subset$), not \"element of\" ($\\in$).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sure", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have come to a consensus in favor of this paper being accepted. I agree with this consensus. While there are still some issues described in the reviewers' comments, I expect that these can be addressed satisfactorily in the camera ready, as described in the author response.
Decision: Accept (Poster)