Co-complexity: An Extended Perspective on Generalization Error
Authors: Rohan Ghosh
Mehul Motani
Venue:  (2021)
Keywords: Generalization
Theoretical Machine Learning
Convolutional Neural Networks

Abstract: It is well known that the complexity of a classifier's function space controls its generalization gap, with two important examples being VC-dimension and Rademacher complexity (R-Complexity). We note that these traditional generalization error bounds consider the ground truth label generating function (LGF) to be fixed. However, if we consider a scenario where the LGF has no constraints at all, then the true generalization error can be large, irrespective of training performance, as the values of the LGF on unseen data points can be largely independent of the values on the training data. To account for this, in this work, we consider an extended characterization of the problem, where the ground truth labels are generated by a function within another function space, which we call the \textit{generator} space. We find that the generalization gap in this scenario depends on the R-Complexity of both the classifier and the generator function spaces. Thus, we find that, even if the R-Complexity of the classifier is low and it has a good training fit, a highly complex generator space could worsen generalization performance, in accordance with the no free lunch theorem. Furthermore, the characterization of a generator space allows us to model constraints, such as invariances (translation and scale in vision) or local smoothness. Subsequently, we propose a joint entropy-like measure of complexity between function spaces (classifier and generator), called co-complexity, which leads to tighter bounds on the generalization error in this setting. Co-complexity captures the similarities between the classifier and generator spaces. It can be decomposed into an invariance co-complexity term, which measures the extent to which the classifier respects the invariant transformations in the generator, and a dissociation co-complexity term, which measures the ability of the classifier to differentiate separate categories in the generator. Our major finding is that reducing the invariance co-complexity of a classifier, while maintaining its dissociation co-complexity, improves the training error and reduces the generalization gap. Furthermore, our results, when specialized to the previous setting where the LGF is fixed, lead to tighter generalization error bounds. Theoretical results are supported by empirical validation on the CNN architecture and its transformation-equivariant extensions. Co-complexity showcases a new side to the generalization abilities of classifiers and can potentially be used to improve their design.  

Under review as a conference paper at ICLR 2021
CO-COMPLEXITY: AN EXTENDED PERSPECTIVE ON GENERALIZATION ERROR
Anonymous authors Paper under double-blind review
ABSTRACT
It is well known that the complexity of classifier's function space controls its gen- eralization gap, with two important examples being VC-dimension and Rademacher complexity (R-oomplexity). We note that these traditional generalization error bounds consider the ground truth label generating function (LGF) be fixed. How- ever, if we consider a scenario where the LGF has no constraints at all, then the true generalization error can be large, irrespective of training performance, the values of the LGF on unseen data points can be largely independent of the values the training data. To account for this, in this work, we consider extended characterization of the problem, where the ground truth labels are generated by a function within another function space, which we call the generator space. We find that the generalization gap in this scenario depends on the R-C R-Complexity of both the classifier and the generator function spaces. Thus, we find that, even if the R-Complexity of the classifier is low and it has good training fit, highly complex generator space could worsen generalization performance, in accordance with the no free lunch theorem. Furthermore, the characterization of a generator space allows us to model constraints, such as invariances (translation and scale in vision) or local smoothness. Subsequently, we propose a joint entropy-like measure of complexity between function spaces (classifier and generator), called co-complexity, which leads tighter bounds on the generalization error in this setting, Co-complexity captures the similarities between the classifier and gener- ator spaces. It can be decomposed into an invariance co-complexity term, which measures the extent to which the classifier respects the invariant transformations in the generator, and a dissociation co-complexiyy term, which measures the ability of the classifier to differentiate separate categories in the generator. Our major finding is that reducing the invariance co-complexity of classifier, while maintaining its dissociation co-complexity, improves the training error and reduces the gener- alization gap. Furthermore, our results, when specialized to the previous setting where the LGF is fixed, lead to potentially tighter generalization error bounds. Theoretical results are supported by empirical validation on the CNN architecture and its transformation-equivaal side to the generalization abilities of classifiers and can potentially be used to improve their design.
extensions. Co-complexity showcases new
INTRODUCTION
In the context of supervised classification, major factor for consideration is the generalization error of the classifier, i.e., how good a classifier generalizes to test (unseen) data points. The notion of overfitting describes the case when the test error significantly exceeds the training error. Naturally, the objective for building a robust classifier entails the minimization of this generalization gap, to avoid overfitting, To that end, statistical studies on generalization error (Blumer et al. (1989); ); [Bartlett & Mendelson (2003) find that complexity measures on the classifier function space, F. often directly control the generalization gap of classifier. Two prominent examples of such measures include the Rademacher Complexity Rm, (F) (Bartlett & Mendelson (2003) and the VC dimension (Blumer ct al. (1989) VC(F). Both measures directly estimate the flexibility of a function space, i.c., how likely it for F to contain functions that can fit any random labelling over set of data points. In this paper, we work with Rademacher complexity and propose extensions that provide new perspective on generalization error.
From a statistical perspective, the generalization gap can be understood through convergence bounds on the emrr function, i.e., the expected deviation of the error function on the test data compared the

---

Under review as a conference paper at ICLR 2021
training data. Traditional generalization error bounds (Bartlett & Mendelson 2003 state that function
complexity (i.e., (F) directly corresponds to the generalization gap. Thus, higher Rm (F) usually leads to a greater generalization gap and slower convergence. Although the original Rm (F) was proposed for binary classification, similar results have been shown for multi-class settings and a larger variety of loss functions (Xu et al. 2016; Liao al.. 2018). Note that R. (F) is over the entire function space and thus global in nature. Local forms of Rademacher complexity, which involve restricting the function space and lead to minimum error on the training data samples, have been proposed (Bartlett et al. 2005 2002). Apart from function complexity based measures, there is also considerable work which uses an information theoretic perspective (Xu & Raginsky 2017] Russo &
Zou 2020
Bu et al. 2020 Haghifam et al. 2020) in treating the subject.
1.1
WIYY THE GROUND TRUTH LABEL GENERATING FUNCTION MATTERS
We define the label generating function for a classification problem as the function which generates the true labels for all possible datapoints. Note that most generalization error bounds, including the traditional ones, primarily are introspective in nature, i.e. they consider the size and flexibility of the classifier's 's function space F. The main direction proposed in this work is the investigation of the unknowabilityy of the ground truth label generating functions (LGF), using another function space which we call the generator space.
The generalization error bounds in Bartlett & Mendelson 2003) state that the difference in test and training performance is roughly bounded above by the Rademacher Complexity of the classifier's function space (i.e., R.m (F)) In other words, whatever the training error, the test error will always be likely to be greater by an amount (FF on average. We note that, in deriving the original bound, a major assumption is that the LGF g is fixed and knowable from the data.
We now outline our main argument for taking the generator space into account. The LGF is indeed fixed, i.e., there cannot be two different ground truth label generating functions applicable to the same problem. However, our primary emphasis is the fact that the true LGF will always be unknown, i.., for any finite training data containing data-label pairs (2,. (2)),, we would only truly know the output of the label generating function on the given training data samples. Only when have infinite training data samples, the values of LGF are known at each E Rd In this work, we denote the function space of all possible LGFs, within which the true LGF is contained, as the generator space. Note that the generator space arises due the unknowability of the LGF. We show in this work that due to the generator space, the true generalization gap is greater than the Rademacher complexity of the classifier, and also depends on the Rademacher complexity of the generator. Note that the size of the generator space, which dictates its complexity, will be dependent on the amount of constraints that the LGF has: if the LGF has no constraints all, then generator spaces are larger, whereas if the LGF is constrained to be smooth/invariant to many transformations, generator spaces are smaller (as the set of functions which are smooth and invariant are also much smaller, for instance in vision).
Let us consider the case where the LGF g has no constraints at all, i.e., it is sampled from a generator space G which contains all possible functions g Rd - 13. In this case, the function is expected to have no structure and behaves like a random function, and thus the expected test accuracy of any classifier will be 50% (i.e., random chance). Therefore, even if the classifier function f E F produces a very good fit on the training data and FF happens to have a low complexity measure RR, (F). the generalization performance will still be poor, as no knowledge of the LGF values on the unseen datapoints is available from the training samples. This is in contrast to the generalization error bounds based on Rademacher complexity, which would estimate that the classifier should have good generalization performance (i.e., low test error), as both R RmFF) and training error are low. Note that although a typical training dataset extracted from this LGF may be hard to fit using low-complexity classifier F, there will be examples of training instances with non-zero probability on which low-complexity classifier can have good fit. The takeaway from this example is that the structure of the data (here represented using the complexity of the generator space) can additionally dictate whether a classifier can generalize. Note that, in this scenario, the expected generalization performance would be better if the LGF had more structure.
Figure I illustrates the role of both generator and classifier spaces in generalization via the two example scenarios discussed earlier. In both examples, the same low-complexity classifier has good fit on the training data, thus (F) is low. example (a), the LGF has no constraints; while, in example (b), the LGF has constraints such as local smoothness. In example (a), the classifier
2

---

Under review as a conference paper at ICLR 2021
Genenatoo Constrainta)
Generator Space Constraints)
Training Data
Test Data
Training Data
Test Data
Figure I: Two examples where the same low-complexity classifier shows similar fit training samples, but in (a) the LGF has no constraints (large generator space) and (b) the L.F is constrained by smoothness and other invariances (small generator space).
clearly exhibits poor generalization performance the test data. This agrees with our previous argument that if the LGF has no constraints, generalization essentially impossible. In example (b), the classifier shows much more robust generalization performance on the test data, due the LGF having significantly more structure.
Furthermore, it is intuitively clear that a classifier function space F which has high overlap with the generator space G (and therefore its constraints) should yield good generalization performance. This shows, that in addition the function spaces and G individually affecting the generalization gap, the similarities between F and G are also important. Both of these perspectives play leading roles our construction of generator-ande mmneratoranndcllasifee aware complexity measures and the associated novel generalization eтror bounds.
1.2 RELATED WORK
To the best of our knowledge. the approach novel and there is not much directly related work. Here, we describe some examples of works which discuss relevant concepts. The no free lunch theorem proposed in WWlpert & Macready (1997) indirectly sheds light on the behaviour of the LGFs. However, it does not incorporate ways to reduce variability in the LGFs by considering constraints related the classification problem. Invariance constraints in learning algorithms were studied in Sokolic et al. (2017). where the input space was factored into invariant transformations, similar what we also do this work. In doing so, the complexity of the data was indirectly explored, based on the number of invariant transformations present in the input space. However, the generalization bounds were derived with an assumption of perfectly invariant classifier function spaces, which is not applicable for CNNs and their variants (as shown in Kauddree-AAbram (2017)). In another relevant study (Jin et al. (2019)), a cover-complexity measure of single dataset proposed, and the generalization eπror of fully connected networks was analyzed with respect to the same. However, invariances in the dataset and the learning algorithm
proposing to study generalization performance
neglected, i.e., the similarities between the generator and the classifier spaces were not studied.
1.3 KEY CONTRIBUTIONS
The contributions of this work are as follows:
1. We propose novel complexity measure between the classifier function space F and the generator function space G called co-complexity, which we use to derive new, more accurate global estimates of generator-awen not only the complexity of the generator and classifier function spaces, but also the similarities between them. Doing so allows for the more exhaustive look into generalization error.
generalization error bounds (Theorem 3 and 4p. Co-complexity considers
2. We decompose co-complextty into two different measures complexity, invariance co-complexity and dissociation co-complexity, which used to derive generalization error bounds, in- cluding bounds on the expected training eтror (Theorem (6). We find that reducing invariance co-complexity while keeping the dissociation co-complexity unchanged, helps reduce the gener- alization gap (low variance) while maintaining low training error (low bias). This emphasizes
3

---

Under review as a conference paper at ICLR 2021
the importance of having classifiers that share invariance properties with generator spaces, e.g.. rotation-ing iattionninvariant CNNs (Cohen Welling (016b)) on MNIST-Ro (Larochelle et al. (2007)).
3. We present empirical validation of co-complexity measures of CNN and its scale-cquivariant and rotation-equiii -nuation-equivarriant counterparts (SE-CNN Sosnovik et al. 2019), RE-CNN in Cohen & Welling (20T6b)), which explains their superior generalization ability compared MLPs.
Our proposed error bounds are easily specialized to the case where ground truth label function is fixed, leading to potentially tighter generalization error bounds (see Appendix A). Although our proposed measures are global in nature, local variants can be derived via similar extensions used in Bartlett et (2005).
DEFINITIONS
Assume that we have m number of d-dimensional i.i.d sampled instances S [21. 22, 2m| drawn from some distribution P, and another set of m i.i.d sampled instances 5' [z 222 ... z/m also drawn from P. Define a = [0i, 02 Jm, where are i.i.d random variables following the Rademacher distribution (Pr(o:
+1) Pr(a, -)) 0.5). F and are function spaces from Rd - 1-1, } and we assumee that they are defined at all points in R In the context of our problem,
FF will be the classifier's function space, whereas will be the generator space.
Rademacher Complexity (Bartlett & Mendelson 2003)): First, we provide the definition of Rademacher Complexity:
Σ f(z))s ]
1 m
Run (F)
E 0,8
sup SEF
It can be seen that R. (F) indicates the noisy-label fitting ability of the classifier's function space F.
Correlated Rademacher Complexity: We propose modified form the original Rademacher complexity, called Correlated Rademacher Complexity, R (F), which is defined as follows:
]
Re
E 2 O.S.S'
sup JEF
Σ ((x))(2))o 1=1
We have RC S 1/2. We also show that R (F) S. Rm (F) (see Appendix C.I)p has been argued that R,, (J) (and therefore R (F)) can be considered as "entropy" measures of the entire function space F (Anguita et al. )2 Note that, like R,, (F), R (F) is also eventually depends on the noisy label fitting ability of F, but computes via ability of the function space assign the same different label to two random points z; and z (via ((()) Thus we denote it as the correlated Rademacher complexity J.
Co-Complexity: Now propose various complexity measures between two separate function spaces F and G. Similar to (m) and R. (F), these measures assess the noisy label fitting abilities of the union of the function spaces F and G. doing so, these measures compute a joint-entropy like metric over the two function spaces. First, define the Co-complexity between F and G follows.
L
)
Rm (F,9)
2 X
sup JEF,gED
(3)
S,S,S'
Some of the properties of co-complexity are as follows:
P1 Rm (F, (G. i.e., co-complexity is symmetric.
P2 Rm,FF (F,9) 2 R (F) and Rm (F, 2 R_ (9), i.e., the co-complexity between F and G is always greater than the individual correlated Rademacher complexities of J and G.
P3 Rm(FF < RC (F) RC (g) Rm (F) + R.. (9), i.e., the co-complexity between F and G is upper bounded by the sum of the Rademacher complexities of F and G.
P4 Rm (F. F. behaves like a joint-entropy measure F and G. To see this, let us define Im (F, R.C (F) + RC (g) Rm (F. 9). called the mutual co-complexity between F and G. We later find that Im (F,9) behaves like a
measure. This, coupled with the fact that RC (F) and RC (G) be construed as entropy measures of F and G, implies the result.
4

---

Under review as a conference paper at ICLR 2021
Invariance Co- Co-Complexity: Next, quantify some of the properties of the ground truth generator space & in terms of its invariance transformations. We define the Invariance Classes of g as follows:
Ic(G) = (. 01), T2(,, 02), (n 0,)),
(4)
where (.)(., = 1,2. ... n2 are functions from F- + IR and 8, represents the extent of the set of admissible values depending on the
transformation T₁. Each 8, R is scalar and takes transformation (possibly infinite). The functions are constrained such that, Vr E (g),,, Vg E G. g(r(z),t) g(2) for all data points IRd and for all admissible values of the transformation parameter t. Also, note that setting 0, = 0 leads to the identity function, i.c., (2, 0) for all 2 E Rd and all i.
Based on the above we define transformation-indicann function [(z, 2)), such that 2(2,2z) 1 if z (1 f1) (2) o o (., (n,tn)) (2;), for certain f1, f2, ...tn and otherwise (2,24) = 0. Additionally, with respect to generator space g, we also define the invariance extended set of
datapoint E IR as follows:
Io(zi) = {z E RR [122,))
(5)
Note that that invariance extended set of will always have the same ground truth label as Next, we define the Invariance Co-complexity between two function spaces F and G as follows:
m m Σ
) where 2 (2s) (6)
E (F (F,9) = 2 5,5'
X
sup FEF
1
-
Note that (F,9) 1. Each data point z! in S' is contained within the invariance extended set Iz(z;) of 2, and is sampled according to the un-normalized distribution P(z) 2;) over Rd The invariance co-complexity between F and & indicates the degree to which FF obeys the invariance transformations within G. For instance, low R,, (F. 9) would indicate that f(2; = 1 (i.e., f(=.) = f(z()) for most 2; and z/ which are related via some invariance transformation in G.
define the Dissociation Co-complexitt between F and g when the corresponding datapoints in S and S are not related by any invariance transformation. That is, for all 2; and 2/ S" z & [z.),, and is sampled from the distribution P(z) (x,, over Rd The dissociation co-complexity can then be defined as:
Dissociation Co-Complexity: We
1 Σ Mos))))) )] where 2/ (1=) [(z, z,), Vi. (7)
1 2 X
R (F,9) 9)
E S,S,S'
sup
JEF
Note that (F 9) measures the average flexibility of F in its label assignment to any two points 2; and of which are not related via any invariance transformation in G. Thus, a larger R (F.9) 9) would indicate that the classifier function space F is able to easily assign separate labels to datapoints which not related via any invariance transformation in G. We also define variant of R (F, 9), in which S contains only one instance, instead of m instances, denoted as (F,)). R.. (F,)) is defined as follows.
((s))(()))))) )] where ~ P(z)(1 1(20 20)), Vi.
1
R.
= 2
x
E
sup JEF
PSS
Note that R. F) < 0.5 and R.D. (F,9) < 0.5.
Rademacher Smoothness: For our final result in Theorem we assume that the function space F is Rademacher smooth w.r.t. G. We define Rademacher Smoothness as follows. If F is Rademacher smooth w.r.t. 9, then any quantity of the form Eg.ss [supyer (+) Σm (z))((())))) (=)))(=))))) (=))))) or (2x)) )g(
Es.s' (sup (1) Em f(x)) (2())(2)
(((4))a)] where the expectation is over datapoint per-
mutations S, S". should lie between the two following cases: (i) St E (S( (i.e., 2 ~ P()) (I,, for all i) and (ii) S' & (S) (i.e., 2 P1=)(1 T(2, =)) for all i). Then, for some non-zero value
5

---

Under review as a conference paper at ICLR 2021
of a, 0 S 1, the following holds:
Σ
sup [EF
5,3'
(4)))()) )
= (a)
E
sup [EF
S,8',S' (Lg(()
==1
(400f(4)o(2)00121000) 1=1
+ (1 S,8' (I)
E
sup JEF
(9)
Similarly, the same applies to Es,s sup SEF.EFE ( f404
THEORETICAL RESULTS
We now present series of results which extend the generalization framework using generator spaces. The proofs of all our results are available in Appendix C For the following results, we assume that the classifier's function space contains the constant function f(z) c Vz, c {-1,
We use the definitions provided in the previous section. Specifically, FF is be the classifier's function space and is the generator space. Given that the data labels are generated by E g, we extend the definition of the sampled instances S by adding the output labels, i.c., ((1)), (22, ((2)). (Zm, (2m))). Then for f F, denote the 0-1 loss on by
(1 [(x)g(Z))
efrs(f)
(10)
2m
We also denote the generalization error over the data samples generated by distribution as
(1-g(1))()))
(1
errp(s)
lim N
(11)
2N
First, describe the generalization emror bound originally proposed in Bartlett & Mendelson (2003). Theorem 1. (Bartlett & Mendelson (2003)) For 0 < 5 < 1, with probability 2 1 6, we have
log (1/8)
errp(f) s (ers(() + Rm (F) +
(12)
2m
The above theorem assumes that the ground truth function completely knowable from the given training examples, and therefore the generator space contains only single element (Bartlett & Mendelson (2003)). For all of our results that follow, we assume the extended case where the generator space can contain more than one element due to the unknowability of the LGF, and construct generalization error bounds that consider the complexity & as well. Also note that following results hold for every choice of f E F and g G. First we present the extended Theorem when the LGF is unknowable (Rm (9) > 0).
Theorem 2. For
1, with probability p 2 1 8, we have.
log (1/5)
errp(f) S efrs(f) + (m) + R.
(13)
2m
This result states that the complexity of the generator space also directly contributes towards increasing the generalization gap. In problems where the LGF is known to be heavily constrained and structured, RR,, (9) will be low, reducing the expected generalization gap of classifiers, and vice-versa. Note that the knowable ground truth scenario where G has a single element, we have Rm,(9) 0, which returns the error bound in Theorem [ This result shows that larger complexity of G results in a greater generalization gap. We demonstrate this with neural network generator spaces of varying complexity (see Appendix B.3). Intuitively, the additional R (9) term comes from the fact that given the training data labels, there still exists a subspace of functions in g which are potential candidates for the ground truth function.
Remark 1.

---

Under review as a conference paper at ICLR 2021
The following result presents tightens Theorem usinn co-complexity. Theorem 3. For 0 < ó < 1, with probability p 2 1 - 8, we have
erro(f) S (fr + Rm (F,9) log (1/8)
(14)
2m
Remark 2. Co-complexity measures the degree of similarity between F and G, instead of simply adding their respective complexities, and therefore is tighter than (reorem2[co-comppler also find that the generalization gap, for the case when the roles are reversed, is unchanged (see
P3). We
corollary 3. in Appendix C). This demonstrates an inherent symmetry in the problem. Also note that
Theorem leads to potentially tighter bounds when specialized to the conventional setting where Rm (Appendix(A)
The following result outlines a lower bound on the generalization error, using co-complexity.
Theorem 4. For 0 < ò < I, with probability p 2 1 - 8.
errp(f) 2 (fr - Rm (F.9)) log (1/6)
(15)
2m
Remark 3. This result, coupled with Theorem 3 demonstrates that if one interprets the (fr as the bias of the classifier, R.m (F,9) can be interpreted as the variance.
term
The following result addresses the joint-entropy like behaviour of Rym (F,)).
Theorem 5. We are given the mutual complexity measure Im (F,9 as defined in co-complexity
P4 Consider another ground truth generator space G' such that (9', 9) = 0, i.e., 9 and G' are independent. Then we have,
( + (F.g')
(16)
Let (X) represents the Shannon entropy of the random variable X and I(X; represents the mutual information between random variables X and Y. Then, it is known that H(X)= 2 T(X:Y)+ + T(X:Y'). when Y and Y' are independent random variables (T(Y; This observation, coupled with the fact that (F) can be considered as an entropy measure of the function space (see section 2 indicates that the quantity Im Im G) behaves like mutual information estimate between the function spaces F. and G. Furthermore, as ( (F, = Re (F) + R (9)
Remark 4.
0)-
(F, (F.9), we can see that Rm, (F, F. behaves as a joint entropy measure of two function spaces.
The following result demonstrates how the co-complexity measure Rm (F,9) can be decomposed into separate co- complexity measures.
Lemma 1. Consider function spaces F and G. such that F is Rademacher smooth w.r.. G. Let us define R PG) as } E,,,, .S' (TgIa(S) [supyes ( 1 (()))((2)0))) For some non-negative real constant 0 < a S 1, we then have
+ (1 Ru (F,9) S (1- RCP
(17)
where R1, (F, and R (F, () are the invariance and dissociation co-complexity, respectively. Remark 5. This decomposition allows us differentiute the impact of RR. (F, 9) and RD (F, G) on the generalization error bound. Note that value of a here will be proportional to the cardinality of the invariance transformation classes Ig of G.
Using this, we proceed to our final result, where we express the generalization error bound in Theorem B in terms of the invariance and dissociation co-complexities. For purposes of simplification, we denote Ri, (F, .)) as R/,,- R. (F, 9) as R and similarly for R.D.1
Theorem 6. Consider function spaces F and G, such that F is Rademacher smooth w.r.t. G. Let errp denote the generalization error for the functions of E F which showcase the best fit on the training data samples (averaged across all in G). RC) is defined in Lemma ] For some non-negative real constants 0 E a, 3 S 1 and 0 < 8 < 1, with probability p - ô, we have
errp & (1 - (8) (1 R.D.1 - + RR + (1 - RR + +CCP(() + 2lgg
(18)
m
7

---

Under review as a conference paper at ICLR 2021
Remark 6. The first term in the generalization error bound in (88) represents upper bound on the average training error of the function which best fits the training data. We find that smaller R' leads smaller generalization gap (variance), while keeping the training error unchanged. However, the same cannot be said for the dissociation co-complexity RD. Thus, for a fixed RD and RD:1, classifier function spaces with smaller R! will lead smaller generalization error. Also note that when the generator space only contains a single element, R.. (g) =.
The next proposition gives interpretable bounds on invariance and dissociation co-complexity. Let Z 21, 22, ...y 2m, and z' z11 Znpa where Zk. 2iz E I V k. Define the well known growth function of binary valued functions F as A = (m = max, (zx)) k = 1.2, .... m, ʃ E FH-
Define the mnvariance-constrrined and con.oiaatioo-coosttainneddddd growth functions of F w.r.t 9 as:
max B = I1s)g(()) 2. E. (f(=)), 1...... m.
C= 1= = x (T [()) k 1,,, m. EFH
max
Proposition 1. Define (F.9)
1/2 S. (sup)er ( E (()
where 2/ Ig(2s). Vi. Note that (F,(F S (F,9). Given the definitions above, have R n (F.9)= S V
log B
SV "oRR and R (F.9) S
log
Iog
2m
2m
Remark 7. Reducing 1l's= g (( while keeping _ (m) unchanged would result in low invariance co-complexity without affecting dissociation co-complexity, which can't be achieved by simply reducing [1)(m) (or the V VC())). This shows that although Ri, and R are not completely independent, careful construction of F makes it possible to reduce Rr, while maintaining Rm.
EXPERIMENTS AND DISCUSSIONS
Our experiments (on MNIST and STL-10) explore the implications of Theorem which states that low R while maintaining R improves generalization while keeping training error unchanged. As all of our proposed complexity metrics assume binary classifiers, we create subsets of these datasets containing only two randomly chosen categories, which converts the problem into binary classification scenario.
4.1 MEASURING INVARIANCE CO-COMPLEXITY
As invariance co-complexity is defined w.r.t. a transformation class (Ig), we compute the invariance co-complexity (in (6) of various networks shown in Table T for four different transformations. For each transformation we choose the datapoint pairs S and S' in (6) such that z! = L), where t the transformation parameter. The parameter is randomly chosen as follows: 18-180 for rotation, 0.7 for scale, -0-90- for shear angle and 0.5-4 pixels for translation. The computed Ry, values indicate the extent to which these networks naturally allow for invariance to various transformation types. To approximately compute R2 we take 1000 randomly weighted networks to construct F to compute (6. We average the results over 100 batches of data (S and S'), each containing 1000 examples (m 1000) from their respective datasets. We compute R2, for multi-layered perceptrons extensions: scale-equivariant CNN (SE-CNN
(MLPs), CNNs and their rransformation-cquivarin Sosnovik et al. (2019) and rotation-equivariiat CNN (RE-CNN in Cohen & Welling 2016b)). Note that the scale-eet seulve-auvaaiann CNN and the rotation- equivariant CNN are known to outperform the vanilla CNN on MNIST and its rotation and scale extensions (Sosnovik al. (2019); Cohen & Welling (2016))) Hence, these pransfrrattioneequiaann performance. One of the objectives of this experiment is to verify whether the invariance and dissociation co-complexities of these networks indeed point to better generalization performance, as is observed in literature, Please see Appendix for architecture details.
extensions showcase better generalization
In every case in Table 1 we find that CNNs have lower R2, than MLPs. As expected, we see that SE-CNN and RE-CNN have even lower R/ CNNs are primarily expected to be robust to translation, due to max- mao-pooling layers. However, even for other transformations such rotation and shear, the Ri, the CNN is less than that of an MLP. Please see Appendix B.2 for a more detailed analysis on how invariance co-complexity varies with choice of the transformation parameter.
8

---

Under review as a conference paper at ICLR 2021
Invariance Co-Complexity (R,).)
Architecture
Rotation
Scale
Shear
Translation
MNIST
STL-10
MNIST
STL-10
MNIST
STL-10
MNIST
STL-10
MLP
0,424
0.393
0.2585
0.2545
0.409
0.386
0.425
0.2565
CNN
0.3875
0.375
0.2435
0.2205
0.3885
0.3725
0.365
0.213
SE-CNN
n/a
n/a
0.1845
0.1905
0.385
0.3535
n/a
n/a
RE-CNN
0.357
0.3455
n/a
n/a
0.3385
0.3545
n/a
n/a
Mean invariance co-complexity values for all 4 networks over 4 transformations, rotation, scale, shear, and translation. We approximate the computation of the invariance co-complexity in (6) by taking 1000 randomly initialized networks in each case (for the supremum in (6)). For fairness, all architectures share approximately the same number of parameters (around 16k).
Table 1:
MLP
CNN
RE-CNN
SE-CNN
Dissociation Co-Complexity (MNIST)
0,4415
0.44
0.438
0.438
Dissociation Co-Complexity (STL.-10)
0.4295
0.436
0.43
0.4375
Table 2:
Mean dissociation co-complexity values for all networks. Note that CNN and its variants maintain the dissociation co-complexity at similar level to that of MLP.
4.2 MEASURING DISSOCIATION Co- CO-COMPLEXITY
Smaller invariance co-complexity can be inconsequential. if the network's ability to discriminate between two different categories in G also suffers. Hence, we measure the dissociation co-complexity (in check whether lower values of Ry also affect their discriminatory potential. We compute RR similarly to R by using 1000 randomly initialized networks (for the supremum in (8), and then averaging the measure for 100 batches of data (S and S'). Table the results, where we find that the values of R. for all studied networks are very close to each other. Therefore, only the invariance co-complexity of these architectures will majorly decide the generalization error bounds in Theorem 6 This shows that, in spite of better invariance capabilities of CNNs (lower Ri,,) and its transformation taassformattonneqqivviaan extensions, those networks preserve discriminatory potential necessary for differentiating images that belong different categories.
REFLECTIONS
The proposed co-complexity measures lead to extended perspective on generalization error by accounting for ground truth generator spaces. The objective of introducing the generator space is to consider the structure in the ground truth labelling functions. New error bounds are proposed which consider various aspects of interaction between generator and classifier function spaces.
Co-complexity can be decomposed into two separate components, invariance co-complexity (R',.) and dissociated co-complexity (R which are found to measure the degree to which the classifier's s function space obeys the invariance transformations in the data (R_,.) and also the degree to which the classifier is able to differentiate between separate categories in the data (R.)) If we interpret R., (F, 9) as the variance of the classifier (see Theorems 3 and 4 and the training error as the bias, we see that R. ca and R, affect the training error (bias) and generalization gap (variance) differently (see Theorem O Theorem outtinees a clear objective for reducing variance while maintaining low bias: reduce R,, while keeping R. and R&D.1 unchanged. We note that monitoring R,, and R can be useful for finding better learning architectures for a specific problem. Furthermore, it is also clear that classification problems which contain more invariance constraints, R', plays greater role in controlling the generalization gap (as will be higher).
Experiments MNIST and STL-10 reveal that the invariance co-complexity R., for CNNs and their wtw.iformmaiio-eqqvvviiiiie extensions is always lower than MLPs. while their dissociation co-complexitics, R.P. and R are comparable to MLPs (see Appendix Bor experiments which measure R. Furthermore, transforatiion-quivvaiaa versions of CNN show lower R than the vanilla CNN itself, while maintaining R,, i.e., they have low variance and low bias. Appendix B.3 presents results when neural networks of varying complexity used as generator spaces and verifies that higher complexity generator spaces lead to a larger generalization gap.

---

Under review as a conference paper at ICLR 2021
REFERENCES
D. Anguita, A. Ghio, L. Oneto, and S. Ridella. A deep connection between the vapnik-chi chervonenkis entropy and the rademacher complexity. IEEE Transactions on Neural Networks and Learning Systems, 25(12):2222-2211 2014.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and Structural results. J. Mach. Learn. Res., 3:463-482, March 2003. ISSN 1532-4435.
Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Localized rademacher complexities. In Jyrki Kivinen and Robert H. Sloan (eds.), Compulational Learning Theory, pp. 44-58. Springer, 2002.
Peter Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. Ann. Statist., 13(4):1497-1537) 08 2005, doi: 101111400005500000000000333
Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Leamability and the vapnik-chervonenkis dimension. J. ACM, 36(4):929-96) October 1989. ISSN 0004-5411, doi: 10.1145/763399763777
Y. Bu, Zou, and V. Veeravalli. Tightening mutual information based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, pp. 1-1, 2020.
Taco S. Cohen and Max Welling. Group equivariant convolutional networks. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML'16, 16, pp. 199002999 JMLR.org, 201 6a.
Taco S. Cohen and Max Welling, Group equivariant convolutional networks. International Conference Machine Learning (ICML), 2016b.
Thomas M Cover and Joy Thomas. Elements of information theory. John Wiley & Sons, 2012.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M. Roy, and Gintare Karolina Dziugaite. Sharpened Generalization Bounds based Conditional Mutual Information and an Application to Noisy, Iterative Algorithms. arXiv e-prints, art. arXiv:2004. 12983, April 2020.
Pengzhan Jin, Lu Lu. Yifa Tang, and George Em Karniadakis. Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness. arXiv e-prints, art. arXiv:1905. 14277, May 2019.
Eric Kauderer-Abrama Quantifying reanlation-invariincee in convolutional neural networks. arXiv e-prints, art. arXiv: 1801 .04500 December 2017.
Hugo Larochelle, Dumitru Erhan, Aaron Courville, James Bergstra, and Yoshua Bengio. An empirical evaluation of deep architectures on problems with many factors of variation. Proceedings of the 24th International Conference Machine Learning, ICML '07, pp. 473-480, New York, NY, USA. 2007. Association for Computing Machinery. ISBN 97959999379 doi: 10.1145/1273496 1273556.
Qianli Liao, Brando Miranda, Andrzej Banburski, Jack Hidary, and Tomaso Poggio. A Sur- prising Linear Relationship Predicts Test Performance in Deep Networks. arXiv e-prints, art. arXiv: www:1807.099 807.0965,, July 2018.
Colin McDiammid. On the method of bounded differences. Surveys in combinatorics, 141(1):148-188, 1989.
D. Russo and J. Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory. 66(1):302-33) 2020.
Jure Sokolic, Raja Giryes, Guillermo Sapiro, and Miguel Rodrigues. Generalization Error of Invariant Classifiers. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1094-1 103, Fort Lauderdale, FI., USA, 20-22 Apr 2017. PMLR.
10

---

Under review as a conference paper at ICLR 2021
Ivan Sosnovik, Michal Szmaja, and Amoll Smeulders. Scale-Equivariig Steerable Networks. arXiv e-prints, art, arXiv: 1 1093, October 2019.
D. H. Wolpert and Macready. No free lunch theorems for optimization. Trans. Evol. Comp, (1):67-82, April 1997. ISSN 1089-778X. doi: 10. 10.1 1,.11992335888889.
Aolin Xu and Maxim Raginsky, Information-theorrci analysis of generalization capability of learning algorithms. In Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 2524-2534 Curran Associates, Inc., 2017.
C. Xu, T. Liu, D. Tao, and C. Xu. Local rademacher complexity for multi-label learning, IEEE Transactions on Image Processing, 25(3):195-11507, 2016.
A APPENDIX TIGHTENING EXISTING RESULTS
For the following results, we primarily work in the setting where the ground truth generator space only contains single element, which pertains to the conventional treatment of generalization error bounds with Rademacher complexity. Note that in this setting, we can still define the invariance classes of G. which we will make use of. Furthermore, we primarily work with the correlated Rademacher complexity R (F), which was defined section 2 We note that R (F) involves two instantiations of the dataset S and S". Furthermore, we also observe that the final R (F) depends on how each datapoint in S is paired with the corresponding datapoint 2/ in S"
(a)))))) ]
RSd (F)
E S.S,"'
sup fEr
(19)
For the following results, define the awvriancc-mmtehee correlated Rademacher complexity Ri (F), which chooses a pairing (i, M()) between the points in S and S', such that
M arg max M
Σ 1a [Ig(2))
(20)
That is, the matching function M is chosen such that there exists the largest number of pairings 24, M(()) where <MM()) is present the invariance extended set of 2,- Thus, the invariance-matched correlated complexity can then be defined as
Cine (F)
E a.S.sy
sup [EF
Σ Hasd(e)r)))) 1=1
(21)
2
where M is chosen using equation 20 Given this, have the following theorem.
Theorem 7. Consider the classifier function space F, and the previous defined correlated Rademacher complexity of F, (F). Furthermore, let us assume that the generator space only contains a single element, i.e., the conventional setting (Rm(9) = 0). Then we have for any f E F, with probability p 2 8, have
log (1/5)
errplf) S err((f) + RCnn (F)+
(22)
2m
Proof. First, we will show that for any f E F, with probability p2 1 6,
log (1/6)
errp(f) S efs RC
(23)
2m
This result trivially follows from Theorem
3 when & contains single element denoted by go. then
11

---

Under review as a conference paper at ICLR 2021
1 m
(()))((22000220000000))) ]
Rm (F.9)
X E
sup
(24)
2
",S,S'
/EF
m ==1
x
E
sup
f()))(2))))))
(25)
2 a,5,''
FEF
m
R (F)
(26)
Note that as (F) S (F), this is a tighter global bound that the original Rademacher bound.
Then, the result immediately follows when we recognize that changing the ordering of z and z/ does not affect the value of the generalization gap in (57). Furthermore, the matching M for each sampled S, S' is independent of the choice of the Rademacher variables d,, and thus the subsequent steps follow in the same way as in (67). Subsequently, we still have with a probability 2 1-
(f) s (ft + R (F) + log (1/8)
(27)
2m
Note that when the invariance co-complexity of F w.r.t. G smaller than its dissociation co- complexity, then the above is expected to be tighter bound than (23). This is because the invariance-
aware matching function M leads to greater number of pairings 24, 2/ where 2/ II(2s) (thus lies in its invariance extended set).
B APPENDIX ADDITIONAL EXPERIMENTS
B. EXPERIMENT: MEASURING DISSOCIATION CO-COMPLEXITY (R..) (F,9))
In the main paper, we measure the invariance co-complexities Rd (F,9) and the dissociation co- complexities Rn (F, () of four different network types: Multi-layer Perceptron (MLP), Vanilla CNN (CNN), Scale-Equivariant CNN (SE-CNN in Sosnovik et al. (019)) and Rotation Equivariant CNN (RE-CNN in Cohen Welling (2016))). In this experiment, we measure the single-sample dissociation co-complexity R.,1T (F, 9) these networks, as P.1 (F.9) g) also affects the training error in the generalization error bound in Theorem 6 Please note that the datasets used in experiments (MNIST and STL-10), have 10 categories. However, since the invariance and dissociation co-complexities can only be computed binary classifiers, use random subsets of the data which contain only two categories, for computing the value of co-complexity.
Table shows the results. We find that in both datasets, the R,P.1 (F,9 9) values of the tested networks are very close to each other. This is consistent with the dissociation co-complexity R (F, (F,9), 9). shown in Table 2 of the main paper. Together with those results, it is clear that only the invariance co-complexities R2 (F, 9) will mainly contribute to the generalization error of these networks, as the dissociation co-complexities R.D.1 RD, 9) and RD (F, 9) do not show any significant variation.
For example, from Table I and of the main paper, we see that the invariance co-complexity (rotation) of the RE-CNN (0.357) is smaller than that of the MI.P (0.424), whereas the R D.1 (F, (0.4492 vs. 0.4472) and R. (F, G) (0.438 vs. 0.4415) of these two networks do not show much variation.
MLP
CNN
SE-CNN
RE-CNN
Dissociation Co-Complexity (R D.1 (F. G), MNIST)
0.4492
0.4589
0.4479
0.4472
Dissociation Co-Complexity (R... D. (F, 10)
0.4352
0.4465
0.4405
0.4570
Table 3: Mean dissociation co-complexity values for all networks. Note that CNN and its variants maintain the dissociation co-complexity at similar level to that of MLP.
12

---

Under review as a conference paper at ICLR 2021
B.2 EXPERIMENT: MEASURING INVARIANCE CO- CO-COMPLEXITY FOR DIFFERENT TRANSFORMATION PARAMETER CHOICES
In addition to the experiments which estimate the overall invariance co-complexity of the various network baselines, we also showcase how R depends on the exact transformation parameter for each case, in Fig. 3 Note that equivariant networks usually have low Rt for most values of I, except for the RE-CNN which is tuned to be invariant rotations of 90", and therefore only showcases significant drops in R when t is near 90" or 180%
Invariace Co-complexity
Inveriance Co-complexiyy
0.35
0.400
0.30
0.375
0.350
0.325
0.20
25
50
75
100
125
150
175
0.7
0.6
0.9
1.0
1.1
1.2
18)
Orientation Shift
(b)
Scale Factor
SE-CNN
Invariance Co-complexiity
RE-CNN
0.45
Invariance Co-complexty
0.44
TTanslation]
0.42
(Shear)
0.40
0.40
0.35
0.38
0.30
0.32
0.20
0.30
3.0
3.5
Shear Angle
(d)
Translational
Invariance co-complexity values for the relevant networks on MNIST, when the datapoint pairs S and S' are separated by varying degrees of rotational, scale, shear and translational shifts.
Figure 2:
B.3 EXPERIMENT: TESTING GENERALIZATION ERROR BOUNDS WITH NEURAL NETWORK GENERATOR SPACES
We consider setting where F is the space of linear classifiers and the generator space G is the space of aettvactivated neural networks with a single hidden layer containing hidden neurons. We have
Rm (F) ε 11/m and Rm (9) x / H//m Closed form expressions for co-complexity R.n (F, non-trivial to compute, but we use the property Rm, (F,9) < (F) + Rm (9) (Theorem 2). Theorem 2 implics that only increasing the complexity of & (by increasing If), should lead to a steady increase in the difference between training and testing error (i.e. the generalization gap). We execute
this scenario with two variations: m = 10 and m = 100. H was chosen from {2, 4, 8, 16, 32). Note that the data distribution is kept fixed for all H. Therefore, in this experiment, only the label generating function is changed.
We observe that the expected generalization gap steadily increases (ranged between (.6%-.9%) as we increase the complexity of the generator class (for both m = 10 and m 100). Furthermore, find very high degree of correlation (0.982 for generalization gap trend predicted by Theorem (ss / /H/m) and the empirically observed average generalization gap. This shows that the complexity of the generator class also directly controls the generalization gap. when everything else is unchanged. This result clearly highlights that when additional information about the generator space is known, more accurate trends of generalization error can be estimated by using both Rm(9) and Rm (F).
10 and 0.976 for m 100) between the
C APPENDIX PROOF OF THEORETICAL RESULTS
In what follows, we provide the proofs of Theorems to The proof of Theorem of the main paper is available in Bartlett & Mendelson (2003). We also prove, in Lemma 2 the properties of co-complexity stated in Section the main paper. use the definitions provided in Section 5 of the main paper.
13

---

Under review as a conference paper at ICLR 2021
(H Number of Hidden Neurons of Generator)
Avarage Ganeralization Gap
0.09
Average Generalization Gap
0.018
0.08
0.016
0.07
0.014
0.012
0.05
0.010
0.008
0.04
0.006
2
4
5
2
3
5
VH
H
(a) m = 10
(b) m = 100
Figure 3: Plots depicting the average generalization gap (difference between test and training error) when 2-1ayer neural networks of variable hidden neuron number H, are chosen as the label generating function, and single layer neural network is chosen the classifier. The generalization gap trend is plotted for two scenarios, (a) m 10 and (b) m 100, where m is the numher of training examples. As here Rm, (F) is fixed, but Rm (9) x / H changes with H, we plot the generalization gap averages against v H. Note that the trend is linear in nature in both cases (correlation of z 0.98 for both), showing that the generalization gap depends directly on the complexity of the generator space.
Please note that for the following proofs, a variable 2 which follows the Rademacher distribution (Pr(= +1) = Pr(z -1) = 0.5) are referred to as Rademacher variable.
C.1 PROOFS OF PROPERTIES P1-P3 OF CO-COMPLEXITY
We begin with the proof of the properties of co-complexity (P1-P3) and property of the correlated Rademacher complexity, which are described in Section 5 of the main paper.
Lemma 2. For any two function spaces F and G, the following statements hold.
Rm (F. (9,F
(28)
Rm (F,9) (/ 2 (F)
(29)
Rm (F,9) 2 (9)
(30)
(F, (F,9) 9) < R (F) + R (9)
(31)
(x) Rm (F)
(32)
Proof. (i) To prove the first statement, it is trivial that interchanging f and g in the expression of "mm (F,9) keeps unchanged.
Thus, (F, 9) Rm,
(ii) Let us define of go (z, (2)))((2()),, To prove the second statement, we choose any fixed function Do within G and have,
14

---

Under review as a conference paper at ICLR 2021
1
X
E
sup /EF,9ES
0,S,8'
==1
X
IP
sup fEF
g0(=)gg0 (=))))
(33)
2
0,S,5'
1
Σ Mos))
E
sup fEF
(34)
2
S,,'
R (F).
(35)
Here, we use the fact that of is also a Rademacher variable.
(iii) We can prove the third statement in the same manner, fixing fo E F instead.
(iv) The fourth statement can proven as follows. First, we note that ((() and g(<))g(=()
variables which take the value of 1 or -1. Thus, ((=))(()))()))((() can be expressed as
(1- (() (())g()))) = (1 - f(z) g(4 (())) (z())) where v; E (11 depends f(2) and ((2)) together. but is independent of each of them individually. We can therefore write,
1
E
sup
Σ
2
S,S,''
fEF.gEG
i=1
1
X
E
sup fEF.gEG
Σ (1- [f{))(())) -1- -((i))(()))))
(36)
2
3,3,8'
i=1
1
E
sup fEF
(f(z)f(2) s(21)g(2))) v.0,
(37)
2
6,8,8'
i=1
Now, consider any fixed {oo...., mm) = (o) ... o b, and fix S and S First, let us denote
1 m m
Sopts Jopt
arg max SEF.gE9
(())(()))) ((=))(t))) ooof
(38)
Let us denote the final v; for fopt and Jopt by o Note that Thth here depends on Sopa (z:)) and Hopt (zs (ept))))))).. Note that opt .pt
.t2 spp will be independent of each other, σı, 02 ..0m opt
independent. Also observe that 01 .12 ,.. will be independent of of, o2. respectively, they only depend Sopt and Jopt- We define of v. of We note that o1,02 .. will be independent across all samples, and Pr(a) = +1) Pr(a = 11 = 0.5, same as o, Thus of o2 "''n are i.i.d Rademacher variables like T1. 02 mm. We thus note,
m Σ ((())(()))))))))) - -(()))))))))))))))))))))) m
sup JEF.gEg
m
(Jopt (oo) Jops (ze 20pp (z()) uopr
(39)
Σ (fopt (xs)fopc(2) Sope (2.)) of
(40)
sup feF.ggg
Σ E=
(41)
15

---

Under review as a conference paper at ICLR 2021
where in the final supremum of are kept fixed at their original values (a¹ U; opt o.). We then have,
1
X
E
sup SEF
2
0,5,S'
1=1
1
Σ (f(z)f(2) o(())0()))))
$ x
E
sup /EFggEg
(42)
"',8
R ( (F)
R (9).
(43)
The final result (F) - Rm (F) can be shown follows. To prove this, the fact that f(x) = 1f(2)) - -(z))]. We have,
)
(F)
X
sup FEF
(E))(E))
(44)
2
0,8,8'
i=1
1
X
R 0,
sup
(1 15(z)) 1(=2)0a)))
(45)
2
FEF
1
1 (f(=)) ((e)))o
x
E
sup
(46)
2 3,5
[EF
Here, en takes values in (-1,1) }, depending on whether f(z;) or f(=() is greater. Note that as a; is Rademacher variable, 040; is also Rademacher variable. We also note that v is independent of fz,) and f(2;) individually. Thus we have,
R
1
E
sup
Σ -((z)-
m - -((E)))
(47)
S,S.S!
fEF
m
)
$
1
E
sup
1 m
f(2)(())
E a'.
sup
1
Σ
f(+))(
of)
2
fET
feT
m
(48)
where o/== = 1200, As - is also a Rademacher variable, we finally have
R (F) S
E
sup fEr
Σ ((=))(3)
+
E o'.S'
sup
1
Σ
)
(49)
0'
m i=1
fEF
m
i=1
Rmm (F) + Rm (F)
(50)
2
(F).
(51)
This completes the proofs.
C.2 PROOF OF THEOREM 2
The following result proves generalization error bound which incorporates R.,. (F) and R,, (9).
Theorem 2. For 0 < < 1, with probability p 2 1 - 8, we have
errp(f) @frs(f) Rm, (F) + Ry, (9) log (1/8)
(52)
2m
Proof. First, we reiterate that (f) = E (1 ((1))ttraa (2:)) /2m, for some Struth E G. and similarly for efr) where co.
16

---

Under review as a conference paper at ICLR 2021
Then, retrace the steps of the original proof in Bartlett & Mendelson 2003).
noting that
errr(f) S efr +
sup JEF.gEG.g(5) gimatn (e cT)s
(erra(f) efrs
(53)
< {fts(() + sup feJ.geD
(54)
Here we initially only consider functions g in G such that g(2o) Struth (20 Bal.g9
(2): .... ((m) ((truth(Em)) Notice, that differently from (Bartlett & Mendelson 2003 ), the
supremum eventually considers the generator space & in addition to the classifier's s function space F. We define ((S) supjez WeF. JeF.geg (eTT(()) (firss)) and notice that
sup
(0(21, 22, .. 26 - 2m) Φ(21 22 by 2/ my 2m $
(55)
E/EZ
This leads to the application of McDiarmid's Inequality (McDiarmid (989)) on the concentration bounds for (SS), which results in the the following bound, with a probability of least 1 8,
log (1/6)
errp(f) S errss +
sup -ump(f)-eisslee + SEF
(56)
Finally, we express Es [o(S)] as follows.
E
sup gEB
(eITp (f) - cfts())
= E
sup
E St
ertg (f) - eπts (f)ss
(57)
JEJ geg
f(
1 f(z))g(2))
sup
E
(58)
gEg.
2
2
(Z))g(()) (2)) - [(())(=)) )
<
EE S.5'
sup EEF
(59)
2
The last inequality (Jensen's inequality (Cover & Thomas (2022) is applicable because sup is convex function. We proceed by multiplying the terms with Rademacher variables as which randomly take on {-1, 1} with equal probability. This keeps the expected value unchanged. Note that B(o,,] In what follows, we express of (2))((2)) - ff()) g(2.)). This is enabled because both have their range in 1}.
m (2))g((;) - -((())(()) )
sup
S.5'
fEF,
m
2
i=1
(f(=x)g(z1)
((())1(2())0
sup
(60)
8.5
fEF.gEG
2
1=1
If(z)) - g(z:)lo,
sup fEF.gEG
0,S,8
m i=1
2
[((+)) - g( g(=1))os
+
sup FEF.EEG
(61)
S,S,''
m
2
Note that multiplication with the Rademacher variables does not change the value of the expectation, the Rademacher variable o; simply controls whether 2; and 2 belong S and S' (a, = 1), or to S' and S' (o, = -1). Coupled with the fact that E(o,] = O. we note that this keeps the expectation in (59) unchanged. Now, note that (1)( g(x))) a; (f(z:) 9(2:)) Uo Here v, is also
17

---

Under review as a conference paper at ICLR 2021
variable that takes its values in {-1, 1}. Since o, is Rademacher variable, 2; oa is also Rademacher variable. In what follows, we use the fact that es is independent of f, and 9s individually.
m f(z) g(22)l0s
]
1
f(z)
E o,S,s'
sup fEFieEG
E of S',
sup fEF
m
1 170
g(z))
E o' S,,'
sup gEg
(62)
771
RS (F)
+ Rm (9)
(63)
Similarly, we can derive the same for E,,,, sup SEF we can represent the upper bound on Blo(S) as follows.
1 -
[f (()))=(e(]oo; }
Thus, finally,
2
B[o(S)] < Rm (F) + (9)
Rm (F) + Rm)
Rm + Rm (9).
(64)
2
This leads to the final form of the generalization error bound. With probability at least - 8, we have
log (1/8)
erTp(f) cft Rm (F) Rm
(65)
m
C.3 PROOF OF THEOREM 3
The following statements propose the generalization error bound in terms of co-complexity.
Theorem 3. For 0 < 8 < 1, with probability p 2 1 8, we have
err((f) s (f) + (F,9))) log (1/8)
(66)
2m
Proof. We proceed in the same way as in appendix C.2 until we arrive at 57 In what follows, we note that can write (=,)g(=;)) ((²))((=)) valued variable with range in 111,1}. We also multiply the original Rademacher variable to (57). and derive the following of bounds.
(=))(=))(==))tt ), for some binary
1
f(z1)(<2) - f(z())(2))
E
sup (errp(f) (fir(())
S JE S,5'
sup FEF.
(67)
S
fEFF.gEG
m
2
i=1
1
((
E S.3'
sup JEFWEE
(68)
m
2
1
E S,S,S'
sup JEF .ge
(69)
m i=1
2
1
(((=.)) (=))))
E
sup fEF.ge
(70)
SS.
The last step follows from the fact that E[o,] 0. and the assumption that of 0 also i.i.d Rademacher variables. This assumption will hold for most well behaved classifiers. for which less than half of the terms in (68) are greater than zero (which is applicable for classifiers with not too
18

---

Under review as a conference paper at ICLR 2021
large Rm((F) As 2 Eo'' (e ge9 [ E have the final generalization bound as follows. With probability 2 1 1 6.
Rn (F, (F,
log (1/6)
emp((f S cfts(f) + Rm (F,9) +
(71)
L
The above theorem leads the following corollary.
Corollary 3.1. We consider the hypothetical case where the roles reversed, i.e., when the generator function space G is used to fú the labels, which are now generated by a function F. For any function g E G. for 0 < 8 < 1, with probability p 2 - 8. we have
egrp(g) errs(g) Rm (F,9) log (1/8) 2m
(72)
Proof. This a direct outcome of the fact that Rm (F. = Rm (G, F). When the data labels in generated by functions in FF rather than 9, will simply have with probability 1 6,
log (+) m
e/rp(g) egr + Rm, +
(73)
log (+) m
e + Rm (F,9) +
(74)
Note that here the labels in S are generated by certain f e F. This completes the proof.
C.4 PROOF OF THEOREM
The following result outlines the lower bound on the error function.
Theorem 4. For 0 8 1, with probability p N 1 ô.
log (1/8)
errp(f) 2 efrs(f) Rm (F.9)-
(75)
2m
Proof. First, we note that
eITP(f) 2 cff -
sup fEF
(eiss() -erp(f))
(76)
Next, we denote
(SS) sup (errs(f) - (f)).
(77)
JEf
We then proceed similarly to Theorem and Theorem and can show that
E [o([]] S Rm,(F.)
(78)
Furthermore, note that
1
sup F1. .. E
(0 22, 24 mny 2m) 0(21, 22, ... 2/ .... 3m
(79)
m
This allows us to apply another consequence of Mediarmid's inequality, which leads to the following, with probability p 8,
19

---

Under review as a conference paper at ICLR 2021
log (1/6)
eπrp(f) 2c -
sup (erts - cfT)
(80)
[EF
log (1/6)
(fm Rm (F,g)
(81)
This completes the proof.
C.5 PROOF THEOREM
5
Now, we outline a of results pertaining to the joint-entropy like behaviour of Rm (F,
Theorem 5. We are given the mutual complexity measure (F, 9) defined in co-complexity P4 (Section of main paper). We consider an alternative ground truth generator space G', such that (g' G) = 0, i.e., G and G' are independent. Then we have,
(m) 2 (F, (I.
(82)
Proof.
To prove the above, note that it is sufficient to prove the following:
(F, R.. (F, ( R (G) R (g')
(83)
We elaborate on the left hand side of the above inequality as follows
1
Rm (F.
x
sup /EF,gEg
2
a,8,8'
i=1
+ x E 2 0,5.S'
sup fEFig'E
(84)
We introduce i.i.d Rademacher variables {co, Jm by multiplying them with the terms within R., (F, F'). As E[e]] = 0 Vi, this maneuver does not change the value of the expectation.
m
( ]
R. (F,9) + Rm (F,
I
sup JEF.gES
o,S,S'
1
1 m
+ 2
sup
(85)
S,S
g'
m
m
f(z)f(() (9(2))9(2) + ag (2))g (2)) o,00 ]
E
sup
(86)
2
JEF.9E9.0'E9
m
Now note that Here 0 E (-1, Vi. Note that the value of v depends on the values of g(z)) g(2(). (2,). (2) and e,. However, note that with so many dependencies e; ultimately is independent of all of these terms, individually. We have,
re-express ((2)9(2() egg (2))g (2/) (1 + (g(2))9((())
(2 yu
Rm (F,9) + Rm (F,
1
Σ f())f(2)om
E
sup SEF
2
d,E.S.8'
[()) (s)))) (2)(())))))))) )
(87)
20

---

Under review as a conference paper at ICLR 2021
Note that the expectation is over fixed values of and S For the next step, recognize that 0, = of is Rademacher variable itself the first term to the R.H.S of the inequality above, as Us is independent of f(z)) and f(z)). For fixed value of those parameters, then consider
1 Σ
(())(())))
arg max JEF
(88)
==1
Then, we can compute a lower bound for the expression in 87 as follows,
Rm (F, + Rm (F,9))
m
E
(z))
a' S'S'' m
1 m
E
sup
(89)
0,
sEF
m
m
sup gEg,g'E9" 2 R + 0,5
(40 m
(90)
is important to note here that the variable e, ff (" (2,) (*)))((()))))))))) (x/) is Rademacher variable, but however, not yet independent of the other terms being multiplied to it. The terms E,, Ts. f (2,) and (z() are all independent of g(z;), g g(2(), g g'(zi (()g(((()))) but however, the same cannot be said of vú. Therefore, to resolve this issue note that the product g(2)) (()))((2())) (')))) (z() itself can be expressed as another function g" (z,, 2 = (()))g(5)) (24))' (2+)g' (2(), as an instance of another function space g" and the second term in 89 then be re-expressed as,
1 X
Σ (old
E
sup E"
(91)
2 S.S..S'
Note that although the product g(1))g()) (24gg'( and thus independent of g" (2), 2(). Thus, now we can finally express the variables (of (=))) themselves. This leads to the lower bound as follows:
not independent of the g(2,), g(2)), (z) it is independent of
1,2, ... ,.mm as i.i Rademacher variables
Rm(F.9) + Rm (F,
1
m
( + 2
x
E
sup
(92)
a' "',
g' E'g
i=1
Rc + Rmm (G, g') = (F) R (g) + (g))
(93)
The last step follows from the fact that Im (9', = 0, that is, the function spaces & and g' are independent (i.e. Rm, (G.g'' R. (g) + R (g')). This concludes our proof.
We now prove a corollary to Theorem where we discuss implications of Theorem 5 on the generalization error bound Theorem 3
Corollary 5.1. Given function space G', such that I ( 0. Suppose that Rm((F)
[F, + (F, + e, for some 2 0. We huve with probability
8.
log (1/0)
errp(f) < errs() + R. (9) + Im (F,9)) +6+
(94)
Proof. This is direct consequence the fact that Rm (F) Imn (F.9) + Im G"). combined with the generalization bound in Theorem
21

---

Under review as a conference paper at ICLR 2021
Now proceed to the final set of results, where we decompose the co-complexity into two other complexity terms, as defined in Section 5 of the main paper. First, we show how the co-complexity measure Rm (F, g) can be decomposed into R,, (F, () and Rm,
C.6 PROOF OF THEOREM 6
The following results discuss the impact of dissociation co-complexity and invariance co-complexity on generalization error bounds.
Lemma 2. Consider function spaces F and 9, such that is Rademacher smooth w.rl G. Let us define RCP(()) (g) as S, S (S) |supyeg ( Σ (z=)(())(())))))) For some non-negative real constant 0 S a I 1, we then have
+ R. (F,9) 9) R (1- (
(95)
where R,, (F,)) and R (F,G) are the invariance co-comllxxtty and the dissociation co-complexity respectively.
Proof. As the functions are Rademacher smooth, we can decompose the expectation over S, S' to only the ones where 5' E IIg(S), and the ones where S' $ (S). We begin from (67) as follows.
(()))(=)((()))))) 0i ]
1
Rm (F,))
sup JEF.gE
(96)
a,8,8'
m
2
Then, using the Rademacher smoothness constraint, we have for certain 0 a s
1 m
Rm (F,)) =a
E ".8,S",9'EIgl
sup IEFigEg sup gEF.gE
m
2
(1 a)
0,8,8' S (8)(
Y
2
]
m
{Z)))(=) 2
sup fET
(8)
m
m
E
sup
(98)
SEFIDED
m
2
m
f(zif((2))0
Sa
sup
+ (1 (1- (1-0))(R((.0)) R. (C)
(8)
SEF
m
2
1=1
(99)
m
(z)){()))
Sa 5,5' (To((
sup [Er
(1- ([ (100)
m
2
= =RR (F,9) + (1 (1-a) (R (F,
+ R.C
RCD (g)).
(101)
We use the fact that E,,,, S.. (S) sup ( Σm (e)))ee)aa
S R (F, 9)
2
R.D. (g). which follows trivially from a derivation similar to that of co-complexity P3 in Lemma (F,9) RC (F) + R (9)). This completes the proof.
Using this, we proceed to the proof of Theorem where we re-express the generalization error bound in terms of the invariance and dissociation co-complexities, including bounds on the training error. For purposes of simplification, we denote R/, (F, 9). R. (F, G) as R.D and D. (F,9) g) as RPP1
22

---

Under review as a conference paper at ICLR 2021
Theorem 6. Consider function spaces F and g, such that F is Rademacher smooth w.r.f and
FF contains the constant function f(z) = c, V2, c E {-1,1}. Let errp denote the generalization ervor for the functions E F which showcase the best fit on the training data samples. For some non-negative real constants 0 S a, < and O < < with probability 2 6, we have
errp (1 - 3) ( ) aR + (R + Pg)(())) +V
2 logg(1/8)
(102)
m
Note:
Recall that R.D (g) defined in Lemma 2
Proof. We note that erTp the generalization error for the case when only the best fitting function Sopt J (fFTs())) is chosen for each training data set S, and is averaged over all possible ground truth functions E G. Note that the labels in S is subject to change, depending on the choice
of g. Thus for fixed datapoints 21, 22, .. 2m S. (53) changes to
erTp - E lerrs [fos((
gEG E (erT((fopd) @Frs(fopt)
(103)
DEg
<
lerr (rrs(Japl) (J
+ sup(errr((op)) - =
(104)
8E9
gEg
- E (errs (fopt) DEg
sup fEF.EEG
(errr(f) -Frs(f)).
(105)
We now denote (S) Bygglinffer (errs(fopt) sup setpeer.ec(eer((( errs(f)) Let us also denote (55) Eg lin (err then have the following for a fixed fopt-
(errs(fopt)) (fopt)) and ((S) sup (e(r (f)) We
(6'221 (21, 2 mr Zm) 0'(21, 2/...., 2m)
sup
sup
[1(2) Zig ... (m))))) 122 2....... 2m)
sup
17(21, .i............... 2....,, (,1, 2m
(106)
21 20
1
2
(107)
m
1
m
is easy to show that sup st.... 5 ./EZ [2
22, 22, 2t..., 2m) (21,,, 22 24, ,.., 2m) S 1
m
and su....:........./E (n(21, 22, .... ..... 2m) - 7211 22, 2/1 ..... 2m) I m. Applying Medi- armid's inequality, we have with probability 2 5,
1.
2log (1/8) +
erTP S [errs(fopt)] +
E S.ges
sup SEF,gED
-
(108)
m
We already have that Es [sup gerg/eeeeer efrs s Rm s & (R- RC,P (G), for certain 0 s a I (Lemma 2. The first term (expected training error) can be expressed as,
1 (11 2
Σ (+)))(t))) ))
E lerss S
(Sopt)
E
sup /EF
(109)
9.gEg
As iterated in the main statement of this theorem, we assume that the classifier function space is complex enough to allow for rate < 50% (chance level for binary classification) on the training data itself. This indicates that we can safely assume that supfer (# Σ, f())g(<2)) 2 We then have,
23

---

Under review as a conference paper at ICLR 2021
(Z)))(Z)))
Σ (()))(()))
sup fEJ
sup fEF
m
m
Σ (())(())))))))) 1
= sup fer
(110)
m
sup JEF
(111)
m
f
1 Σ ((s))()))(()))))))
sup
(112)
fEF
m
where we make use of the fact that ((=)))()))(())))(( 1. Here, the datapoint a' is sampled from the same distribution P. Thus have,
1 (((a)a) m
m E [=NMMM))))))) (113)
E .EE
sup sEF
E S.=' 9,E6
sup fET
As before, we assume that the function space f is Rademacher smooth, i.e. for a certain 0 5 1. we can express
)
Σ ((=))(=))(()))((
sup fET
m
=3
E
sup fEF
Σ (())((())))
S (ETgee")
m
E [[NaDoda)))))))))
+ (1 -1-))
E
sup fEF
(114)
S,a ".d,,
Σ s(AD)tte
2,9
E
sup FEF
S,²', (e"gg('')
m Σ (EN)SOO))))
+ 3)
E S SEI
sup
(115)
fEF
The last step above involves the reasonable assumption that the function space is going to on average worse at fitting random noise labels, rather than labelling provided by element of the generator space G. Finally, we note that
1 Σ ((Ss)())))
E S.2' (EE)
sup fEF
=
(116)
simply by choosing the constant function f(z) c, which is assumed be present within the classifier's function space F. Also, note that St. [sup (. E, ((s))(()))) 2 2.R.D. (F,9). We then have
Σ ((000(1)))01))0(1) fEF m
sup
2 2 2(1 B) (F,)).
(117)
S. .EG
24

---

Under review as a conference paper at ICLR 2021
This leads to the final upper bound for enrp by replacing the terms in (108) by the above. With probability p 2 1 6, we then have,
errp S (1 3) ( -RRRi + aR (1 (R + (G) 2 log(1/))
(118)
m
Finally, we provide the proof of Proposition co-complexity and dissociation co-complexity.
1 which gives interpretable bounds on invariance
Proposition 1. Define the well known growth function of binary valued functions F as A 11=(m) max; (z(z))) k = 1,2. m E FJ.. Define the invariance-comstrainee and dissociation con.riiiinnno growth functions of w.r.l G as:
B (mm)
Kf((z), f(zk) k- 1,2, .... m. f FFI
z 2 (I
C C= 11 ( K(((z),, f(zk) k= 1,2, =1, m. FH
max
where 2f E Iz(z)), Vi. Note that (F,F9) S R4, (F,9). Given the definitions above, we have Rym (F, S log and Rm (F,9) V Cog log
Define R (F,9) = R,,,, ('),(() [SUP]EF ( Ei
log B
2m
Proof. First we show that R (F,g) < R 2n (F,9). This follows from the fact that
m
)]
R (F,9)
E
sup
Σ (()))(2)))))
(119)
feF
m
i=1
m
[(;)\(2))) )
E
sup
(120)
5.8.9t,S'E (S)
FEF
m
1 m
] =R/, (F,
$
E 3,5' " (Ig
sup
Σ (())((2))
(121)
SEF
m
The proof of the main proposition immediately follows from the application of Massart's finite class lemma, which states that for a finite subset KC of Rmm and Rademacher variables 0,, o2, Omn we have
Σ Lowl S <rv / 2og [C]
sup gEK
(122)
07 GL. This immediately leads the well known result for Rademacher complexity Ry, (F), which states
2 log (1)
Rm Rm(FF S
(123)
m
The result above directly follows from the fact that the cardinality of the finite subset I. is upper bounded by the growth function (m))),, when K. is the set of all possible function outputs from functions f E F, on any m points. our case, as we have that
Σ 1())) t=1
R (F.
sup JEF
(124)
2
T.S
we can directly apply Massart's lemma. by the using the invariance-constrained growth function I ((m) to obtain the first result as follows. First, choose the finite subset K. such that
25

---

Under review as a conference paper at ICLR 2021
contains all possible outputs of the function product f2) when S, is chosen such that each element in S' lies in the invariance extended subset each corresponding element in For this X. the cardinality |A]] is bounded above by the previously defined growth function I1' (m)) This immediately leads to the first result,
2 log IT 1 (m)
(F, S 2
(125)
m
log IT's ( 2m
(126)
We can similarly show the equivalent result for dissociation co-complexity (F, 9), to obtain
2 log 11 / (m)
(F,)) 2
(127)
log 11/ ig (m) 2m
(128)
Finally, recognize that the growth functions It's g (m) and 11 (m) are bounded above by the cardinality of all possible function values taken in S,S', which in turn is bounded above by (1)(m) (m). This implies ( [I=(m)² and 11 (m() S [I>(m)², from which we then have
log 11 FFg(m)) 2m
log (m)
(F,9))
(129)
and
log 11 (m))
log mm
Ry, (F,9)
(130)
2m
m
This concludes the proof.
D NEURAL NETWORK ARCHITECTURE DETAILS
Here present the architectures that were used in experiments. As mentioned in section 4 four different architectures were tested. In Table we show the layer-wise details of each architecture. Note that all architectures share similar parameter count, and also evoke similar dissociation co-complexity as result (see Table of size 28 28 (same size in the MNIST dataset). For STL-10, we resized the input (96 96) to 28 x 28 and used the same architectures for consistency.
2 and 3). Note that the input to all these architectures is an image
26

---

Under review as a conference paper at ICLR 2021
2-Layer NN (15.8k)
Standard CNN (16.1k)
Scale Equivariant CNN (15.9k)
Rotation Equivariant CNN (16k)
FC-20
Conv- 15 (3x3)
ScaleConv-10 (IIx11, 2.2:1)
P4ConvZ2-10 10 (3x3)
FC-2 (Output)
(3x))
(3x3
Maxpool (3x3)
Conv-30 (3x3)
ScaleConv-22 (11x11,2.2:1
P4ConvP4-15 (3x3)
Maxpool (3x3)
Maxpool(3x3)
Maxpool (3x3)
Conv-40 (3x3)
ScaleConv-32 (11x11, 2.2:1)
P4ConvP4-19 (3x3)
Maxpool (3x3)
(3x)
Maxpool (3x3x4)
FC-20
Scale-Pool (4x1)
FC-10
FC-2 (Output)
FC-20
FC-2(Oulput)
FC-2 (Output)
Table 4: Shown are the architectural details all neural networks used in our experiments. Scale- Conv represents scale-equivariant convolution and P4Conv -Z2 and P4Conv-Z4 represents rotation equivariant convolution (as detailed in Cohen & Welling (a)) For the ScaleCony layers, note that 2.2:1 represents the ratio of the maximum to the minimum scale of the filters. A total of 4 scale pathways were chosen for those layers. FC represents the fully connected layers. Networks are chosen such that overall they share similar parametric count (shown within the brackets).
27


Reviews:
[{"review_id": "n4VWg7Vi6kY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims to propose a new complexity measure, called co-complexity, to control classifiers' generalization gap. This new measure acts like a joint-entropy and leads to tighter bounds on the generalization error in this setting. The main idea is to extend the classical complexity measure of Barlett & Mendelson (2003) by introducing a new function space: the generator space is defined as the function space of all possible LGFs satisfying ad hoc constraints. Thus, the authors claimed to be able to measure the extent to which the classifier's function space obeys the invariance transformations in the data and measure the extent to which the classifier can differentiate between separate categories in the data.\n\nSection 2 aims at justifying the introduction of this generator space, Section 5 gives useful definitions, and Section 6 provides theoretical results. Evidence of these results is reported in the supplementary material. Section 7 presents some experiments, but most of them are in the appendix.\n\n–\n\nAs it stands, this work does not seem to me to be ready for publication. Indeed, despite some interesting developments, the presentation needs to be deeply improved. My main reproach concerns Sections 5 and 6: definitions and evidence are chained together without any link between them, little contextualization, explanation, thought process. The experimental part suffers from a great lack of detail. Finally, the writing of the evidence in the appendix can be improved. However, unless I am mistaken, they are accurate (and easy to follow).\n\nHere is a list of suggestions for the authors:\n1. The numbering of some paragraphs is weird. In particular, I am quite surprised that Sections 2, 3 and 4 are not subsections of the introduction (Section 1).\n2. LGF is not properly defined, whereas it is a central notion.\n3. Section 2 is based on the complexity measure $R_m(f)$. However, this concept is only defined in Section 5, two pages later.\n4. Section 5 looks like a chain of definitions without motivation and intuition. It is necessary to better motivate the definitions, for example, by providing intuitions about the nature of the objects concerned, especially since there are many of them.\n5. Revise the definitions of \"co-complexity of invariance\" and \"co-complexity of dissociation\". Currently, it is not clear at first reading whether $z_i'$ are constrained to belong (or not) to $I_G(z_i)$ and that this is not always the case a priori.\n6. The definition of \"Rademacher smoothness\" mixes intuition with mathematical definition, making it difficult to understand.\n7. In the definition of Dissociation Co-Complexity, \"We also define a variant [...], in which $S$ contains only one instance, instead of $m$ instances, denoted as $R_m^{D,1}(\\mathcal{F},\\mathcal{G})$\" What is the sum then about?\n8. As with Section 5, the presentation of Section 6 and the appendices could be improved.\n9. Computations 9 and 10 would benefit from being stated with \"real\" fractions, i.e. displaystyle fraction.\n10. As noted above, Appendix A suffers from a lack of context. Besides, there is no mention of this appendix in the text's body, other than in the outline.\n11. In Appendix C, several references are made to the definitions in Section 3. I think the authors meant to refer to Section 5.\n12. The demonstrations should be shorted, particularly those in Appendix C.1. Evidence (i) is clearly too trivial to be detailed, for example.\n13. In many places, the writing could be improved: often, variables are used before being defined. For example, this is the case in Calculation (34), where the $\\sigma_i'$ are defined only two lines later. The same is true at several locations in the rest of the appendix.\n14. Evidence (iv) page 13: I think there is a parenthesis error when introducing $v_i$. A $\\frac12$  is missing from calculations (36) and (37).\n15. Many superfluous parentheses in the demonstration of Theorem 2 do the reading of the latter tedious. There are superfluous parentheses in the numerator of fractions in almost all computations: (58), (59), (60), (61), (62), (63), once in the body of the text just after (64), (69). Equation (59), fractions should be presented in extended form. Twice the authors write $[-1,1]$ for $\\lbrace-1,1\\rbrace$.\n16. For me, the main subtlety of the demonstration concerns the multiplication of each of the terms of the sum by $\\sigma_i$ (Equation (61)). I am not convinced by the way the authors justify this point. The same argument is used several times thereafter.\n\nTypos: \n* Page 4, penultimate line: \"that\" is doubled without reason;\n* Page 5, 2nd paragraph of Section 6: is/be;\n* Page 17, just after (72): There is an extra parenthesis in this sentence. On the other hand, the way of introducing the $\\sigma_i'$ as a set seems to me unnecessarily cumbersome.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TQ7y_O6pETh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n \nThe paper provides an interesting perspective to view generalization error for the machine learning model. In particular, it proposes to investigate the constraint on the label generating function space. They propose a concept of co-complexity analogous to the entropy-ish concept which measures complexities between two function spaces. This co-complexity can be decomposed into two parts which measure the categorization ability of the classifier in generator and extent level in classifier for the invariance transformation in the generator.\n##########################################################################\nReasons for score: \n \nOverall, I vote for accepting. I think a reconsideration of the established theory is good. My concern is about the clarity of the paper and experiments (see cons below). Hopefully, the authors can address my concern in the rebuttal period.\n \n##########################################################################Pros: \n \n1. The paper takes an important issue of generalization error estimation. For me, the problem itself is of significance and interest.\n \n2. The proposed method to measure complexity is novel for capturing the relationship between generator and classifier space and how the given constraints affect complexity. \n \n3. This paper provides comprehensive experiments, including both qualitative analysis and quantitative results, to show the effectiveness of the proposed framework. \n \n##########################################################################\nCons: \n \nAlthough the proposed method provides several ablation studies, I still suggest the authors conduct the following ablation studies to enhance the quality of the paper: \n1. The experiment can be better designed to verify the theorems. Probably the proportion of data generated by invariant transforms can be set with different levels so that it can be verified that the second term in co-complexity reflects the change of R_d.\n2. A couple of comparisons on certain simple models between extended Rademacher complexity and the original R-complexity can be given to show the better tightness of the new bound.\n3. Though this paper is full of theorems, I would be happier to see more insights that can be used in practice. I would appreciate that if the authors can bridge this extended Rademacher complexity to the real guidance on how to train the model with better generalization. E.g. is data augmentation useful to reduce R_I?\n4. The paper seems very like a journal paper w.r.t. the length and structure. I am just thinking that the paper's content could be better presented and a better fit with its full journal version.\n\n#########################################################################\nSome typos: \n(1) abstract: large irrespective -> largely irrespective\n(2) Does Eq (6) miss \\sigma.\n(3) Remark 4 is not coherent to Theorem 5 very well. It needs more clarification.\n(4) It is not clear that why R_m^I' m(F; G) <= R_m^I m(F; G) \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q6oryK0UcEb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied a novel perspective on generalization error bounds, by introducing the \"label generating function \"(LGF). Several new complexity measures (correlated Rademacher complexity, co-complexity, invariance co-complexity, dissociation co-complexity, Rademacher smoothness) were proposed. The properties of the measures and generalization error bound with respect to these complexity measures are studied.  \n\nThis paper is written in clear form and easy to follow.  There are some points I did not fully understand.\n\n1. In formula (4) , the invariance classed of G contains n functions.  However, there may be uncountably infinitely many function \\tau's satisfying g(\\tau(z)) = g(z). In this case, how is I_G(z) in (5) defined? And the definition R_m^I(F, G) and R_m^D(F, G) rely on z'_i in I_G(z_i) or z'_i not in I_G(z_i), but what is the distribution of z'_i over I_G(z_i) (for finite I_G(z_i), countably infinite I_G(z_i) and uncountably infinite I_G(z_i) respectively)? I think I did not fully understand this part so I could not understand Theorem 5 and Theorem 6 in Section 6.\n\n2. Theorem 1 of Section 6 holds true for \\hat{err}_S(f) = \\sum_i (f(z_i)/m) and err_P(f) = E[f(z)]. Does it also hold true if we introduce g in the definitions of \\hat{err}_S(f) and err_P(f) in formulas (9) and (10)? If it still holds true, then would Theorem 2 just mean nothing because it is just a looser upper bound of Theorem 1?\n\n3. If we consider h=1-f*g and consider the Radamacher complexity of function h in Theorem 1, we can have an upper bound which is a simple corollary of Theorem 1. What is the relationship of this corollary and Theorem 2-4?\n\nWith these unclear questions, I vote for a marginal reject. I would like to change my score if these questions are well addressed by the authors.", "extra_scores": {}, "extra_text": {}}, {"review_id": "COWs8TUj__f", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Description\n\nThis paper attempts to derive a new set of generalisation bounds using the idea of matching the function space of the learning machine with the function space describing the generation of labels.\n\n** Pros\n\nThis may be a mechanism for capturing the fact that generalisation performance will depend on the structure of the data and not just on the complexity of the function space of the learning machine.  This is potentially an important contribution.\n\n** Cons\n\nI find the set up of this framework very confusing.  In the motivation (paragraph 3 of section 2) we are invited to imagine a random function with a very good fit to the training data and a low complexity measure.  Complexity measures tell us that with overwhelming probability a low complexity will not fit the training data well provided we have a sufficiently large training set.  What we would expect is that a low complexity machine would do little better than chance so the generalisation gap is small.  It is difficult to give this paper much credence after paragraph.\n\nIn the discussion around Figure 1 there seems to be a confusion between generalisation performance and generalisation gap.  A linear separable function will with high probability have a much lower generalisation error for a perceptron than learning a completely unstructured function, but the complexity provides guarantees on the generalisation gap not on the generalisation performance.\n\nI am deeply puzzled by your comments that traditional bounds are optimistic (e.g. Remark 1).  What is the learning scenario when the label generating function is not fixed.  Clearly the function being learned is not known. it may belong to a large class of functions, with known constraints but in normal classification it is fixed.  I cannot make sense of the learning framework you are modelling.\n\nI don't know what your experimental section is trying to say.  It sits awkwardly with the theorems and doesn't, in my view, really says anything useful.  Or, at least, this is not well explained in the text.\n\n** And Yet...\n\nI think there is potentially a lot to be gained from this approach. The generalisation performance does depend on the problem being learned and not just on the architecture of the learning machine (or complexity of function space F).  This work points to a way to incorporate this information.  The joint Rademacher complexity might provide a useful way of expressing how attuned a learning machine is to the problem being learned.  I just think the story around the theorems is confused.  In my judgement this work is probably too immature for ICLR.  Maybe I am being dull and with minor modifications the authors can make this paper more coherent and allay my doubts.  With a clearer explanation of what these theorems are telling us I believe this could\nbe an important contribution to the field, but in it present form I think the paper adds more confusion than light.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers generalization in setups in which the training sample 
may be generated by a different distribution than the one genertaing the test data.
This sounds much like transfer learning, and similarly sounding considerations,
of a space of possible generating distributions, ways of measuring the statictical complexity
of such spaces and implied error generalization results were analyzed in e.g.,
Jonathan Baxter's "Theoretical models of learning to learn" 1998 and
S Ben-David, R Schuller "Exploiting task relatedness for multiple task learning"
S Ben-David, RS Borbely "A notion of task relatedness yielding provable multiple-task learning guarantees"
Machine learning 73 (3), 273-287

The current submission does not mention these earlier works.

Furthermore, the paper suffers from mathematical sloppiness. The model uder which the generalization theorems 
hold is not clearly defined. For example,  Theorem 2, Theorem 3 and Theorem 4  do not stae what are the probability spaces to which the "probaility p > 1-\delta" quantifications refer.



Decision: Reject