summaries: 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.   The 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. 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.
abstractText: 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 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 potentially 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.
references.authors: D. Anguita A. Ghio L. Oneto S. Ridella
references.title: A deep connection between the vapnik–chervonenkis entropy and the rademacher complexity
references.venue: IEEE Transactions on Neural Networks and Learning Systems,
references.authors: Peter L. Bartlett Shahar Mendelson
references.title: Rademacher and gaussian complexities: Risk bounds and structural results
references.venue: J. Mach. Learn. Res.,
references.authors: Peter L. Bartlett Olivier Bousquet Shahar Mendelson
references.title: Localized rademacher complexities
references.venue: Computational Learning Theory,
references.authors: Peter L. Bartlett Olivier Bousquet Shahar Mendelson
references.title: Local rademacher complexities
references.venue: Ann. Statist., 33(4):1497–1537,
references.authors: Anselm Blumer A. Ehrenfeucht David Haussler Manfred K. Warmuth
references.title: Learnability and the vapnik-chervonenkis dimension
references.venue: J. ACM,
references.authors: Y. Bu S. Zou V.V. Veeravalli
references.title: Tightening mutual information based bounds on generalization error
references.venue: IEEE Journal on Selected Areas in Information Theory,
references.authors: Taco S. Cohen Max Welling
references.title: Group equivariant convolutional networks
references.venue: In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48,
references.authors: Taco S. Cohen Max Welling
references.title: Group equivariant convolutional networks
references.venue: International Conference on Machine Learning (ICML),
references.authors: Thomas M Cover Joy A Thomas
references.title: Elements of information theory
references.authors: Mahdi Haghifam Jeffrey Negrea Ashish Khisti Daniel M. Roy Gintare Karolina Dziugaite
references.title: Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms
references.venue: arXiv e-prints, art
references.authors: Pengzhan Jin Lu Lu Yifa Tang George Em Karniadakis
references.title: Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
references.venue: arXiv e-prints, art
references.authors: Eric Kauderer-Abrams
references.title: Quantifying translation-invariance in convolutional neural networks
references.venue: arXiv e-prints, art
references.authors: Hugo Larochelle Dumitru Erhan Aaron Courville James Bergstra Yoshua Bengio
references.title: An empirical evaluation of deep architectures on problems with many factors of variation
references.venue: In Proceedings of the 24th International Conference on Machine Learning,
references.authors: Qianli Liao Brando Miranda Andrzej Banburski Jack Hidary Tomaso Poggio
references.title: A Surprising Linear Relationship Predicts Test Performance in Deep Networks
references.venue: arXiv e-prints, art
references.authors: Colin McDiarmid
references.title: On the method of bounded differences
references.venue: Surveys in combinatorics,
references.authors: D. Russo J. Zou
references.title: How much does your data exploration overfit? controlling bias via information usage
references.venue: IEEE Transactions on Information Theory,
references.authors: Jure Sokolic Raja Giryes Guillermo Sapiro Miguel Rodrigues
references.title: Generalization Error of Invariant Classifiers
references.venue: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics,
references.authors: Ivan Sosnovik Michał Szmaja Arnold Smeulders
references.title: Scale-Equivariant Steerable Networks
references.venue: arXiv e-prints, art
references.authors: D.H. Wolpert W.G. Macready
references.title: No free lunch theorems for optimization
references.venue: Trans. Evol. Comp,
references.authors: Aolin Xu Maxim Raginsky
references.title: Information-theoretic analysis of generalization capability of learning algorithms
references.venue: Advances in Neural Information Processing Systems
references.authors: C. Xu T. Liu D. Tao
references.title: Local rademacher complexity for multi-label learning
references.venue: IEEE Transactions on Image Processing,
sections.heading: 1 INTRODUCTION
sections.text: In the context of supervised classification, a 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 a classifier. Two prominent examples of such measures include the Rademacher Complexity Rm(F) (Bartlett & Mendelson (2003)) and the VC dimension (Blumer et al. (1989)) V C(F). Both measures directly estimate the flexibility of a function space, i.e., how likely is it for F to contain functions that can fit any random labelling over a set of data points. In this paper, we work with Rademacher complexity and propose extensions that provide a new perspective on generalization error.
  From a statistical perspective, the generalization gap can be understood through convergence bounds on the error function, i.e., the expected deviation of the error function on the test data compared to the
  training data. Traditional generalization error bounds (Bartlett & Mendelson, 2003) state that function complexity (i.e., Rm(F)) directly corresponds to the generalization gap. Thus, higher Rm(F) usually leads to a greater generalization gap and slower convergence. Although the originalRm(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 et al., 2018). Note thatRm(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.
sections.heading: 1.1 WHY THE GROUND TRUTH LABEL GENERATING FUNCTION MATTERS
sections.text: 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 function space F . The main direction proposed in this work is the investigation of the unknowability 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.,Rm(F)). In other words, whatever the training error, the test error will always be likely to be greater by an amountRm(F) 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 on the fact that the true LGF will always be unknown, i.e., for any finite training data containing data-label pairs (zi, g(zi)), we would only truly know the output of the label generating function on the given training data samples. Only when we have infinite training data samples, the values of LGF are known at each z ∈ 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 to 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 at 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 −→ {−1, 1}. In this case, the function g 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 ∈ F produces a very good fit on the training data and F happens to have a low complexity measure Rm(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 Rm(F) and training error are low. Note that although a typical training dataset extracted from this LGF may be hard to fit using a low-complexity classifier F , there will be examples of training instances with non-zero probability on which a low-complexity classifier can have a 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 1 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 a good fit on the training data, thusRm(F) is low. In example (a), the LGF has no constraints; while, in example (b), the LGF has constraints such as local smoothness. In example (a), the classifier
  clearly exhibits poor generalization performance on the test data. This agrees with our previous argument that if the LGF has no constraints, generalization is essentially impossible. In example (b), the classifier shows much more robust generalization performance on the test data, due to the LGF having significantly more structure.
  Furthermore, it is intuitively clear that a classifier function space F which has a high overlap with the generator space G (and therefore its constraints) should yield good generalization performance. This shows, that in addition to the function spaces F and G individually affecting the generalization gap, the similarities between F and G are also important. Both of these perspectives play leading roles in our construction of generator-and-classifier aware complexity measures and the associated novel generalization error bounds.
sections.heading: 1.2 RELATED WORK
sections.text: To the best of our knowledge, the approach we are proposing to study generalization performance is 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 Wolpert & 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 to 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 to what we also do in 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 Kauderer-Abrams (2017)). In another relevant study (Jin et al. (2019)), a cover-complexity measure of a single dataset was proposed, and the generalization error of fully connected networks was analyzed with respect to the same. However, invariances in the dataset and the learning algorithm were neglected, i.e., the similarities between the generator and the classifier spaces were not studied.
sections.heading: 1.3 KEY CONTRIBUTIONS
sections.text: The contributions of this work are as follows:
  1. We propose a 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-aware generalization error bounds (Theorem 3 and 4). Co-complexity considers not only the complexity of the generator and classifier function spaces, but also the similarities between them. Doing so allows for the a more exhaustive look into generalization error. 2. We decompose co-complexity into two different measures of complexity, invariance co-complexity and dissociation co-complexity, which are used to derive new generalization error bounds, including bounds on the expected training error (Theorem 6). We find that reducing invariance co-complexity while keeping the dissociation co-complexity unchanged, helps reduce the generalization gap (low variance) while maintaining low training error (low bias). This emphasizes
  the importance of having classifiers that share invariance properties with generator spaces, e.g., rotation-invariant CNNs (Cohen & Welling (2016b)) on MNIST-Rot (Larochelle et al. (2007)). 3. We present empirical validation of co-complexity measures of CNN and its scale-equivariant and rotation-equivariant counterparts (SE-CNN in Sosnovik et al. (2019), RE-CNN in Cohen & Welling (2016b)), which explains their superior generalization ability compared to 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 al. (2005).
sections.heading: 2 DEFINITIONS
sections.text: Assume that we have m number of d-dimensional i.i.d sampled instances S = [z1, z2, .., zm] drawn from some distribution P , and another set ofm i.i.d sampled instances S′ = [z′1, z ′ 2, .., z ′ m] also drawn from P . Define σ = [σ1, σ2, .., σm] where σi are i.i.d random variables following the Rademacher distribution (Pr(σi = +1) = Pr(σi = −1) = 0.5). F and G are two function spaces from Rd −→ {−1, 1} and we assume that they are defined at all points in Rd. In the context of our problem, F will be the classifier’s function space, whereas G will be the generator space. Rademacher Complexity (Bartlett & Mendelson (2003)): First, we provide the definition of Rademacher Complexity:
  Rm(F) = E σ,S [ sup f∈F ( 1 m m∑ i=1 f(zi)σi )] (1)
  It can be seen thatRm(F) indicates the noisy-label fitting ability of the classifier’s function space F . Correlated Rademacher Complexity: We propose a modified form of the original Rademacher complexity, called Correlated Rademacher Complexity,RCm(F), which is defined as follows:
  RCm(F) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] (2)
  We have 0 ≤ RCm(F) ≤ 1/2. We also show thatRCm(F) ≤ Rm(F) (see Appendix C.1). It has been argued thatRm(F) (and thereforeRCm(F)) can be considered as ”entropy” measures of the entire function space F (Anguita et al. (2014)). Note that, likeRm(F),RCm(F) is also eventually depends on the noisy label fitting ability of F , but computes it via ability of the function space to assign the same or a different label to two random points zi and z′i (via f(zi)f(z ′ i)). Thus we denote it as the correlated Rademacher complexity of F . Co-Complexity: Now we propose various complexity measures between two separate function spaces F and G. Similar toRm(F) andRCm(F), these measures assess the noisy label fitting abilities of the union of the function spaces F and G. In doing so, these measures compute a joint-entropy like metric over the two function spaces. First, we define the Co-complexity between F and G as follows.
  Rm(F ,G) = 1
  2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )] (3)
  Some of the properties of co-complexity are as follows:
  P1 Rm(F ,G) = Rm(G,F), i.e., co-complexity is symmetric. P2 Rm(F ,G) ≥ RCm(F) and Rm(F ,G) ≥ RCm(G), i.e., the co-complexity between F and G is
  always greater than the individual correlated Rademacher complexities of F and G. P3 Rm(F ,G) ≤ RCm(F) +RCm(G) ≤ Rm(F) +Rm(G), 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 ,G) behaves like a joint-entropy measure ofF and G. To see this, let us define Im(F ,G) = RCm(F) +RCm(G) − Rm(F ,G), called the mutual co-complexity between F and G. We later find that Im(F ,G) behaves like a mutual-information measure. This, coupled with the fact that RCm(F) andRCm(G) can be construed as entropy measures of F and G, implies the result.
  Invariance Co-Complexity: Next, we quantify some of the properties of the ground truth generator space G in terms of its invariance transformations. We define the Invariance Classes of G as follows:
  IC(G) = {τ1(., θ1), τ2(., θ2), ..., τn(., θn)}, (4)
  where {τi(., θi)|i = 1, 2, · · · , n} are functions from Rd −→ Rd, and θi represents the extent of the transformation τi. Each θi ∈ R is a scalar and takes on a set of admissible values depending on the transformation (possibly infinite). The functions are constrained such that, ∀τ ∈ IC(G),∀g ∈ G, g(τ(z), t) = g(z) for all data points z ∈ Rd, and for all admissible values of the transformation parameter t. Also, note that setting θi = 0 leads to the identity function, i.e., τi(z, 0) = 1 for all z ∈ Rd and all i. Based on the above we define a transformation-indicator function I(z, zi), such that I(z, zi) = 1 if z = τ1(., t1) ◦ τ2(., t2) ◦ .... ◦ τn(., tn)(zi), for a certain t1, t2, ...tn and otherwise I(z, zi) = 0. Additionally, with respect to a generator space G, we also define the invariance extended set of a datapoint zi ∈ Rd as follows:
  IG(zi) = {z ∈ Rd | I(z, zi) = 1} (5)
  Note that that invariance extended set of z will always have the same ground truth label as z. Next, we define the Invariance Co-complexity between two function spaces F and G as follows:
  RIm(F ,G) = 1
  2 × E S,S′ [ sup f∈F ( 1− ( 1 m m∑ i=1 f(zi)f(z ′ i) ))] ,where z′i ∼ P (z)I(z, zi),∀i . (6)
  Note that RIm(F ,G) ≤ 1. Each data point z′i in S′ is contained within the invariance extended set IG(zi) of zi, and is sampled according to the un-normalized distribution P (z)I(z, zi) over z ∈ Rd. The invariance co-complexity between F and G indicates the degree to which F obeys the invariance transformations within G. For instance, a low RIm(F ,G) would indicate that f(zi)f(z′i) = 1 (i.e., f(zi) = f(z ′ i)) for most zi and z ′ i which are related via some invariance transformation in G.
  Dissociation Co-Complexity: We now define the Dissociation Co-complexity between F and G when the corresponding datapoints in S and S′ are not related by any invariance transformation. That is, for all zi ∈ S and z′i ∈ S′, z′i 6∈ IG(zi), and is sampled from the distribution P (z)(1− I(z, zi)) over z ∈ Rd. The dissociation co-complexity can then be defined as:
  RDm(F ,G) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] ,where z′i ∼ P (z)(1− I(z, zi)),∀i. (7)
  Note thatRDm(F ,G) measures the average flexibility of F in its label assignment to any two points zi and z′i which are not related via any invariance transformation in G. Thus, a largerRDm(F ,G) would indicate that the classifier function space F is able to easily assign separate labels to datapoints which are not related via any invariance transformation in G. We also define a variant of RDm(F ,G), in which S contains only one instance, instead of m instances, denoted asRD,1m (F ,G). RD,1m (F ,G) is defined as follows.
  RD,1m (F ,G) = 1
  2 × E σ,z0∼P,S′ [ sup f∈F ( 1 m m∑ i=1 f(z0)f(z ′ i)σi )] ,where z′i ∼ P (z)(1− I(z, z0)),∀i.
  (8)
  Note thatRDm(F ,G) ≤ 0.5 andRD,1m (F ,G) ≤ 0.5. Rademacher Smoothness: For our final result in Theorem 6, 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. G, then any quantity of the form ES,S′ [ supf∈F ( 1 m ∑m i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )] or
  ES,S′ [ supf∈F,g∈G ( 1 m ∑m i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )] , where the expectation is over datapoint permutations S, S′, should lie between the two following cases : (i) S′ ∈ IG(S) (i.e., z′i ∼ P (z)(I(z, zi)) for all i) and (ii) S′ /∈ IG(S) (i.e., z′i ∼ P (z)(1− I(z, zi)) for all i). Then, for some non-zero value
  of α, 0 ≤ α ≤ 1, the following holds:
  E S,S′ [ sup f∈F 1 m ( m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )]
  = (α) E S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )]
  + (1− α) E S,S′,S′ /∈IG(S) [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )] . (9)
  Similarly, the same applies to ES,S′ [ supf∈F,g∈G ( 1 m ∑m i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi )] .
sections.heading: 3 THEORETICAL RESULTS
sections.text: We now present a 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 F contains the constant function f(z) = c ∀z, c ∈ {−1, 1}. We use the definitions provided in the previous section. Specifically, F is be the classifier’s function space and G is the generator space. Given that the data labels are generated by g ∈ G, we extend the definition of the sampled instances S by adding the output labels, i.e., S = [(z1, g(z1)), (z2, g(z2)), .., (zm, g(zm))]. Then for f ∈ F , we denote the 0-1 loss on S by
  êrrS(f) = m∑ i=1 (1− f(zi)g(zi)) 2m . (10)
  We also denote the generalization error over the data samples generated by distribution P as
  errP (f) = lim N→∞,zi∼P N∑ i=1 (1− f(zi)g(zi)) 2N . (11)
  First, we describe the generalization error bound originally proposed in Bartlett & Mendelson (2003). Theorem 1. (Bartlett & Mendelson (2003)) For 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP (f) ≤ êrrS(f) +Rm(F) + √ log (1/δ)
  2m . (12)
  The above theorem assumes that the ground truth function is completely knowable from the given training examples, and therefore the generator space contains only a 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 of G as well. Also note that the following results hold for every choice of f ∈ F and g ∈ G. First we present the extended Theorem 1 when the LGF is unknowable (Rm(G) > 0). Theorem 2. For 0 < δ < 1, with probability p ≥ 1− δ, we have,
  errP (f) ≤ êrrS(f) +Rm(F) +Rm(G) + √ log (1/δ)
  2m . (13)
  Remark 1. 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,Rm(G) will be low, reducing the expected generalization gap of classifiers, and vice-versa. Note that in the knowable ground truth scenario where G has a single element, we have Rm(G) = 0, which returns the error bound in Theorem 1. 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 additionalRm(G) 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.
  The following result presents tightens Theorem 2 using co-complexity. Theorem 3. For 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP (f) ≤ êrrS(f) +Rm(F ,G) + √ log (1/δ)
  2m . (14)
  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 Theorem 2 (co-complexity P3). We also find that the generalization gap, for the case when the roles are reversed, is unchanged (see corollary 3.1 in Appendix C). This demonstrates an inherent symmetry in the problem. Also note that Theorem 3 leads to potentially tighter bounds when specialized to the conventional setting where Rm(G) = 0 (Appendix A).
  The following result outlines a lower bound on the generalization error, using co-complexity. Theorem 4. For 0 < δ < 1, with probability p ≥ 1− δ,
  errP (f) ≥ êrrS(f)−Rm(F ,G)− √ log (1/δ)
  2m . (15)
  Remark 3. This result, coupled with Theorem 3, demonstrates that if one interprets the êrrS(f) term as the bias of the classifier,Rm(F ,G) can be interpreted as the variance.
  The following result addresses the joint-entropy like behaviour ofRm(F ,G). Theorem 5. We are given the mutual complexity measure Im(F ,G) as defined in co-complexity P4. Consider another ground truth generator space G′, such that Im(G′,G) = 0, i.e., G and G′ are independent. Then we have,
  Rm(F) ≥ Im(F ,G) + Im(F ,G′). (16)
  Remark 4. Let H(X) represents the Shannon entropy of the random variable X and I(X;Y ) represents the mutual information between random variables X and Y . Then, it is known that H(X) ≥ I(X;Y ) + I(X;Y ′), when Y and Y ′ are independent random variables (I(Y ;Y ′) = 0). This observation, coupled with the fact thatRCm(F) can be considered as an entropy measure of the function space (see section 2) indicates that the quantity Im(F ,G) behaves like a mutual information estimate between the function spaces F and G. Furthermore, asRm(F ,G) = RCm(F) +RCm(G)− Im(F ,G), we can see thatRm(F ,G) behaves as a joint entropy measure of two function spaces.
  The following result demonstrates how the co-complexity measureRm(F ,G) can be decomposed into separate co-complexity measures. Lemma 1. Consider function spaces F and G, such that F is Rademacher smooth w.r.t. G. Let us defineRC,Dm (G) as 12 × Eσ,S,S′,S′ /∈IG(S) [ supg∈G ( 1 m ∑m i=1 g(zi)g(z ′ i)σi )] . For some non-negative real constant 0 ≤ α ≤ 1, we then have
  Rm(F ,G) ≤ αRIm(F ,G) + (1− α)(RDm(F ,G) +R C,D m (G)), (17)
  whereRIm(F ,G) andRDm(F ,G) are the invariance and dissociation co-complexity, respectively. Remark 5. This decomposition allows us to differentiate the impact of RIm(F ,G) and RDm(F ,G) on the generalization error bound. Note that value of α 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 3, in terms of the invariance and dissociation co-complexities. For purposes of simplification, we denote RIm(F ,G) as RIm, RDm(F ,G) as RDm and similarly forR D,1 m .
  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 f ∈ F which showcase the best fit on the training data samples (averaged across all g inG). RC,Dm (G) is defined in Lemma 1. For some non-negative real constants 0 ≤ α, β ≤ 1 and 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP ≤ (1− β) ( 1
  2 −RD,1m
  ) + αRIm + (1− α)(RDm +RC,Dm (G)) + √ 2 log(1/δ)
  m (18)
  Remark 6. The first term in the generalization error bound in (18) represents an upper bound on the average training error of the function which best fits the training data. We find that smaller RI leads to a 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 RI will lead to smaller generalization error. Also note that when the generator space only contains a single element,RC,Dm (G) = 0.
  The next proposition gives interpretable bounds on invariance and dissociation co-complexity. Let z = z1, z2, ..., zm, and z’ = z′1, ..., z′m, where zk, z′k ∈ Rd ∀ k. Define the well known growth function of binary valued functions F as A = ΠF (m) = maxz |{f(zk) : k = 1, 2, ...,m, f ∈ F}|. Define the invariance-constrained and dissociation-constrained growth functions of F w.r.t. G as:
  B = ΠIF | G(m) = maxz,z’,z′i∈IG(zi),∀i |{f(zk), f(z′k) : k = 1, 2, ...,m, f ∈ F}|
  C = ΠDF | G(m) = maxz,z’,z′i /∈IG(zi),∀i |{f(zk), f(z′k) : k = 1, 2, ...,m, f ∈ F}|
  Proposition 1. Define RI ′ m(F ,G) = 12 × Eσ,S,S′,S′∈IG(S) [ supf∈F ( 1 m ∑m i=1 f(zi)f(z ′ i)σi )] , where z′i ∈ IG(zi),∀i. Note that R I′ m(F ,G) ≤ R I m(F ,G). Given the definitions above, we haveRI ′ m(F ,G) ≤ √ logB 2m ≤ √ logA m andR D m(F ,G) ≤ √ logC 2m ≤ √ logA m .
  Remark 7. Reducing ΠIF | G(m) while keeping Π D F | G(m) unchanged would result in low invariance co-complexity without affecting dissociation co-complexity, which can’t be achieved by simply reducing ΠF (m) (or the V C(F)). This shows that although RIm and R D m are not completely independent, careful construction of F makes it possible to reduceRIm while maintainingR D m.
sections.heading: 4 EXPERIMENTS AND DISCUSSIONS
sections.text: Our experiments (on MNIST and STL-10) explore the implications of Theorem 6, which states that low RIm while maintaining R D m 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 a binary classification scenario.
sections.heading: 4.1 MEASURING INVARIANCE CO-COMPLEXITY
sections.text: 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 1 for four different transformations. For each transformation τ , we choose the datapoint pairs S and S′ in (6) such that z′i = τ(zi, t), where t is the transformation parameter. The parameter t is randomly chosen as follows: 0◦-180◦ for rotation, 0.7-1.2 for scale, 0◦-90◦ for shear angle and 0.5-4 pixels for translation. The computed RIm values indicate the extent to which these networks naturally allow for invariance to various transformation types. To approximately compute RIm, 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 RIm for multi-layered perceptrons (MLPs), CNNs and their transformation-equivariant extensions: scale-equivariant CNN (SE-CNN in Sosnovik et al. (2019)) and rotation-equivariant CNN (RE-CNN in Cohen & Welling (2016b)). Note that the scale-equivariant CNN and the rotation-equivariant CNN are known to outperform the vanilla CNN on MNIST and its rotation and scale extensions (Sosnovik et al. (2019); Cohen & Welling (2016b)). Hence, these transformation-equivariant extensions showcase better generalization 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 D for architecture details.
  In every case in Table 1, we find that CNNs have lower RIm than MLPs. As expected, we see that SE-CNN and RE-CNN have even lower RIm. CNNs are primarily expected to be robust to translation, due to max-pooling layers. However, even for other transformations such as rotation and shear, the RIm of 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.
sections.heading: 4.2 MEASURING DISSOCIATION CO-COMPLEXITY
sections.text: 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 (8)) to check whether lower values of RIm also affect their discriminatory potential. We compute RDm similarly toR I m, 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 2 shows the results, where we find that the values of RDm 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 (lowerRIm) and its transformation-equivariant extensions, those networks preserve discriminatory potential necessary for differentiating images that belong to different categories.
sections.heading: 5 REFLECTIONS
sections.text: The proposed co-complexity measures lead to an 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 (RIm) and dissociated co-complexity (RDm), which are found to measure the degree to which the classifier’s function space obeys the invariance transformations in the data (RIm), and also the degree to which the classifier is able to differentiate between separate categories in the data (RDm). If we interpret Rm(F ,G) as the variance of the classifier (see Theorems 3 and 4) and the training error as the bias, we see thatRIm andR D m affect the training error (bias) and generalization gap (variance) differently (see Theorem 6). Theorem 6 outlines a clear objective for reducing variance while maintaining low bias: reduceRIm while keepingR D m and R D,1 m unchanged. We note that monitoringR I m andR D m 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,RIm plays a greater role in controlling the generalization gap (as α will be higher).
  Experiments on MNIST and STL-10 reveal that the invariance co-complexity RIm for CNNs and their transformation-equivariant extensions is always lower than MLPs, while their dissociation co-complexities,RDm and RD,1m , are comparable to MLPs (see Appendix B.1 for experiments which measure RD,1m ). Furthermore, transformation-equivariant versions of CNN show lowerR I m than the vanilla CNN itself, while maintainingRDm, i.e., they have low variance and low bias. Appendix B.3 presents results when neural networks of varying complexity are used as generator spaces and verifies that higher complexity generator spaces lead to a larger generalization gap.
sections.heading: A APPENDIX - TIGHTENING EXISTING RESULTS
sections.text: For the following results, we primarily work in the setting where the ground truth generator space only contains a 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 complexityRCm(F), which was defined in section 2. We note thatR C m(F) involves two instantiations of the dataset in S and S′. Furthermore, we also observe that the finalRCm(F) depends on how each datapoint zi in S is paired with the corresponding datapoint z′i in S ′,
  RCm(F) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] (19)
  For the following results, we define the invariance-matched correlated Rademacher complexity RCinvm (F), which chooses a pairing (i,M(i)) between the points in S and S′, such that
  M = arg max M ∑ i |z′M(i) ∩ IG(zi)|. (20)
  That is, the matching function M is chosen such that there exists the largest number of pairings zi, z ′ M(i) where z ′ M(i) is present the invariance extended set of zi. Thus, the invariance-matched correlated complexity can then be defined as
  RCinvm (F) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ M(i))σi )] , (21)
  where M is chosen using equation 20. Given this, we have the following theorem.
  Theorem 7. Consider the classifier function space F , and the previous defined correlated Rademacher complexity of F , RCm(F). Furthermore, let us assume that the generator space only contains a single element, i.e., the conventional setting (Rm(G) = 0). Then we have for any f ∈ F , with a probability p ≥ 1− δ, we have
  errP (f) ≤ êrrS(f) +RCinvm (F) + √ log (1/δ)
  2m . (22)
  Proof. First, we will show that for any f ∈ F , with a probability p ≥ 1− δ, errP (f) ≤ êrrS(f) +RCm(F) + √ log (1/δ)
  2m . (23)
  This result trivially follows from Theorem 3, when G contains a single element denoted by g0, as then
  Rm(F ,G) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)g0(zi)g0(z ′ i)σi )] (24)
  = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] (25)
  = RCm(F) (26)
  Note that asRCm(F) ≤ Rm(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 zi and z′i 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 σi, and thus the subsequent steps follow in the same way as in (67). Subsequently, we still have with a probability p ≥ 1− δ,
  errP (f) ≤ êrrS(f) +RCinvm (F) + √ log (1/δ)
  2m . (27)
  Note that when the invariance co-complexity of F w.r.t. G is smaller than its dissociation cocomplexity, then the above is expected to be a tighter bound than (23). This is because the invarianceaware matching function M leads to a greater number of pairings zi, z′i where z ′ i ∈ IG(zi) (thus lies in its invariance extended set).
sections.heading: B APPENDIX - ADDITIONAL EXPERIMENTS
sections.text: B.1 EXPERIMENT: MEASURING DISSOCIATION CO-COMPLEXITY (RD,1m (F ,G))
  In the main paper, we measure the invariance co-complexities RIm(F ,G) and the dissociation cocomplexities RDm(F ,G) of four different network types: Multi-layer Perceptron (MLP), Vanilla CNN (CNN), Scale-Equivariant CNN (SE-CNN in Sosnovik et al. (2019)) and Rotation Equivariant CNN (RE-CNN in Cohen & Welling (2016b)). In this experiment, we measure the single-sample dissociation co-complexityRD,1m (F ,G) of these networks, asR D,1 m (F ,G) also affects the training error in the generalization error bound in Theorem 6. Please note that the datasets used in our experiments (MNIST and STL-10), have 10 categories. However, since the invariance and dissociation co-complexities can only be computed binary classifiers, we use random subsets of the data which contain only two categories, for computing the value of co-complexity.
  Table 3 shows the results. We find that in both datasets, theRD,1m (F ,G) values of the tested networks are very close to each other. This is consistent with the dissociation co-complexity RDm(F ,G), shown in Table 2 of the main paper. Together with those results, it is clear that only the invariance co-complexitiesRIm(F ,G) will mainly contribute to the generalization error of these networks, as the dissociation co-complexitiesRD,1m (F ,G) andR D m(F ,G) do not show any significant variation.
  For example, from Table 1 and 2 of the main paper, we see that the invariance co-complexity (rotation) of the RE-CNN (0.357) is smaller than that of the MLP (0.424), whereas theRD,1m (F ,G) (0.4492 vs. 0.4472) andRDm(F ,G) (0.438 vs. 0.4415) of these two networks do not show much variation.
sections.heading: B.2 EXPERIMENT: MEASURING INVARIANCE CO-COMPLEXITY FOR DIFFERENT TRANSFORMATION PARAMETER CHOICES
sections.text: In addition to the experiments which estimate the overall invariance co-complexity of the various network baselines, we also showcase how RIm depends on the exact transformation parameter t for each case, in Fig. 3. Note that equivariant networks usually have low RIm for most values of t, except for the RE-CNN which is tuned to be invariant to rotations of 90◦, and therefore only showcases significant drops in RIm when t is near 90 ◦ or 180◦.
sections.heading: B.3 EXPERIMENT: TESTING GENERALIZATION ERROR BOUNDS WITH NEURAL NETWORK GENERATOR SPACES
sections.text: We consider a setting where F is the space of linear classifiers and the generator space G is the space of relu-activated neural networks with a single hidden layer containing H hidden neurons. We have Rm(F) ∝ √ 1/m and Rm(G) ∝ √ H/m. Closed form expressions for co-complexity Rm(F ,G) are non-trivial to compute, but we use the property Rm(F ,G) ≤ Rm(F) +Rm(G) (Theorem 2). Theorem 2 implies that only increasing the complexity of G (by increasing H), 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 0.6%-8.9%) as we increase the complexity of the generator class (for both m = 10 and m = 100). Furthermore, we find a very high degree of correlation (0.982 for m = 10 and 0.976 for m = 100) between the generalization gap trend predicted by Theorem 2 (≈ √ 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 bothRm(G) andRm(F).
sections.heading: C APPENDIX - PROOF OF THEORETICAL RESULTS
sections.text: In what follows, we provide the proofs of Theorems 2 to 6. The proof of Theorem 1 of the main paper is available in Bartlett & Mendelson (2003). We also prove, in Lemma 2, the properties of co-complexity stated in Section 5 of the main paper. We use the definitions provided in Section 5 of the main paper.
  Please note that for the following proofs, a variable z which follows the Rademacher distribution (Pr(z = +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 a 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 ,G) = Rm(G,F) (28) Rm(F ,G) ≥ RCm(F) (29) Rm(F ,G) ≥ RCm(G) (30) Rm(F ,G) ≤ RCm(F) +RCm(G) (31) RCm(F) ≤ Rm(F) (32)
  Proof. (i) To prove the first statement, it is trivial to see that interchanging f and g in the expression ofRm(F ,G) keeps it unchanged. Thus,Rm(F ,G) = Rm(G,F). (ii) Let us define σ′i = g0(zi)g0(z ′ i)σi. To prove the second statement, we choose any fixed function g0 within G and we have,
  1 2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )]
  ≥ 1 2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 g0(zi)g0(z ′ i)f(zi)f(z ′ i)σi )] (33)
  = 1
  2 × E σ′,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σ ′ i )] (34)
  = RCm(F). (35)
  Here, we use the fact that σ′i is also a Rademacher variable.
  (iii) We can prove the third statement in the same manner, fixing f0 ∈ F instead. (iv) The fourth statement can be proven as follows. First, we note that f(zi)f(z′i) and g(zi)g(z ′ i) are variables which take the value of 1 or −1. Thus, f(zi)f(z′i)g(zi)g(z′i) can be expressed as (1− |f(zi)f(z′i)− g(zi)g(z′i)|) = (1− f(zi)f(z′i)− g(zi)g(z′i)vi), where vi ∈ {−1,−1} depends on f(zi)f(z′i) and g(zi)g(z ′ i) together, but is independent of each of them individually. We can therefore write,
  1 2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )]
  = 1
  2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (1− |f(zi)f(z′i)− g(zi)g(z′i)|)σi
  )] (36)
  = 1
  2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)f(z ′ i)− g(zi)g(z′i)) viσi
  )] . (37)
  Now, consider any fixed σ = {σ0, ..., σm} = {σ00 , ..., σ0m}, and fix S and S′. First, let us denote
  fopt, gopt = arg max f∈F,g∈G
  [ 1
  m m∑ i=1 (f(zi)f(z ′ i)− g(zi)g(z′i)) viσ0i
  ] (38)
  Let us denote the final vi for fopt and gopt by v opt i . Note that v opt i here depends on fopt(zi)fopt(z ′ i) and gopt(zi)gopt(z′i). Note that v opt 1 , v opt 2 , ..v opt m will be independent of each other, as σ1, σ2, ..σm are independent. Also observe that vopt1 , v opt 2 , ..v opt m will be independent of σ 0 1 , σ 0 2 , ..σ 0 m respectively, as they only depend on fopt and gopt. We define σ′i = v opt i σ 0 i . We note that σ ′ 1, σ ′ 2, ..σ ′ m will be independent across all samples, and Pr(σ′i = +1) = Pr(σ ′ i = −1) = 0.5, same as σi. Thus σ′1, σ ′ 2, ..σ ′ m are i.i.d Rademacher variables like σ1, σ2, ..σm. We thus note,
  sup f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)f(z ′ i)− g(zi)g(z′i))viσ0i
  )
  = 1
  m m∑ i=1 (fopt(zi)fopt(z ′ i)− gopt(zi)gopt(z′i)) v opt i σ 0 i (39)
  = 1
  m m∑ i=1 (fopt(zi)fopt(z ′ i)− gopt(zi)gopt(z′i))σ′i (40)
  ≤ sup f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)f(z ′ i)− g(zi)g(z′i))σ′i
  ) , (41)
  where in the final supremum σ′i are kept fixed at their original values (σ ′ i = v opt i σ 0 i ). We then have,
  1 2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )]
  ≤ 1 2 × E σ′,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)f(z ′ i)− g(zi)g(z′i))σ′i
  )] , (42)
  = RCm(F) +RCm(G). (43)
  The final result RCm(F) ≤ Rm(F) can be shown as follows. To prove this, we use the fact that f(zi)f(z ′ i) = 1− |f(zi)− f(z′i)|. We have,
  RCm(F) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] (44)
  = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 (1− |f(zi)− f(z′i)|)σi )] (45)
  = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 (f(zi)− f(z′i))viσi )] (46)
  Here, vi takes values in {−1, 1}, depending on whether f(zi) or f(z′i) is greater. Note that as σi is a Rademacher variable, viσi is also a Rademacher variable. We also note that vi is independent of f(zi) and f(z′i) individually. Thus we have,
  RCm(F) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 (f(zi)− f(z′i))viσi )] (47)
  ≤ 1 2 × E σ′,S [ sup f∈F ( 1 m m∑ i=1 f(zi)(σ ′ i) )] + 1 2 × E σ′,S′ [ sup f∈F ( 1 m m∑ i=1 f(z′i)(−σ′i) )] ,
  (48)
  where σ′i = viσi. As −σ′i is also a Rademacher variable, we finally have
  RCm(F) ≤ 1
  2 × E σ′,S [ sup f∈F ( 1 m m∑ i=1 f(zi)(σ ′ i) )] + 1 2 × E σ′,S′ [ sup f∈F ( 1 m m∑ i=1 f(z′i)(σ ′ i) )] (49)
  = Rm(F) +Rm(F)
  2 (50)
  = Rm(F). (51)
  This completes the proofs.
sections.heading: C.2 PROOF OF THEOREM 2
sections.text: The following result proves a generalization error bound which incorporatesRm(F) andRm(G). Theorem 2. For 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP (f) ≤ êrrS(f) +Rm(F) +Rm(G) + √ log (1/δ)
  2m . (52)
  Proof. First, we reiterate that êrrS(f) = ∑m i=1 (1− f(zi)gtruth(zi)) /2m, for some gtruth ∈ G, and similarly for errP (f), where m −→∞.
  Then, we retrace the steps of the original proof in Bartlett & Mendelson (2003), noting that
  errP (f) ≤ êrrS(f) + sup f∈F,g∈G,g(S)=gtruth(S) (errP (f)− êrrS(f)) (53)
  ≤ êrrS(f) + sup f∈F,g∈G (errP (f)− êrrS(f)). (54)
  Here we initially only consider functions g in G such that g(z0) = gtruth(z0), g(z1) = gtruth(z1), ..., g(zm) = gtruth(zm). Notice, that differently from (Bartlett & Mendelson (2003)), the supremum eventually considers the generator space G in addition to the classifier’s function space F . We define φ(S) = supf∈F,g∈G(errP (f)− êrrS(f)), and notice that
  sup z1,z2,...,zm,z′i∈Z
  |φ(z1, z2, ..., zi, ...., zm)− φ(z1, z2, ..., z′i, ...., zm)| ≤ 1
  m . (55)
  This leads to the application of McDiarmid’s Inequality (McDiarmid (1989)) on the concentration bounds for φ(S), which results in the the following bound, with a probability of at least 1− δ,
  errP (f) ≤ êrrS(f) + E S
  [ sup
  f∈F,g∈G (errP (f)− êrrS(f))
  ] + √ log (1/δ)
  m . (56)
  Finally, we express ES [φ(S)] as follows.
  E S
  [ sup
  f∈F,g∈G (errP (f)− êrrS(f))
  ] = E
  S
  [ sup
  f∈F,g∈G E S′ [êrrS′(f)− êrrS(f)|S]
  ] (57)
  = E S
  [ sup
  f∈F,g∈G E S′
  [ 1
  m m∑ i=1 ( 1− f(z′i)g(z′i) 2 − 1− f(zi)g(zi) 2 ) |S ]] (58)
  ≤ E S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)g(zi)− f(z′i)g(z′i) 2
  )] . (59)
  The last inequality (Jensen’s inequality (Cover & Thomas (2012)) is applicable because sup is a convex function. We proceed by multiplying the terms with Rademacher variables σi, which randomly take on {−1, 1} with equal probability. This keeps the expected value unchanged. Note that E[σi] = 0. In what follows, we express f(zi)g(zi) = 1 − |f(zi) − g(zi)|. This is enabled because both have their range in {−1, 1}.
  E S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)g(zi)− f(z′i)g(z′i) 2
  )]
  = E S,S′,σ
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)g(zi)− f(z′i)g(z′i))σi 2
  )] (60)
  ≤ E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 |f(zi)− g(zi)|σi 2
  )]
  + E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 |f(z′i)− g(z′i)|σi 2
  )] . (61)
  Note that multiplication with the Rademacher variables does not change the value of the expectation, as the Rademacher variable σi simply controls whether zi and z′i belong to S and S
  ′ (σi = 1), or to S′ and S′ (σi = −1). Coupled with the fact that E[σi] = 0, we note that this keeps the expectation in (59) unchanged. Now, note that (|f(zi)− g(zi)|)σi = (f(zi)− g(zi)) viσi. Here vi is also a
  variable that takes its values in {−1, 1}. Since σi is a Rademacher variable, viσi = σ′i is also a Rademacher variable. In what follows, we use the fact that vi is independent of fi and gi individually.
  E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 |f(zi)− g(zi)|σi 2 )] ≤ E σ′,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)σ ′ i 2 )]
  + E σ′,S,S′ [ sup g∈G ( 1 m m∑ i=1 g(zi)σ ′ i 2 )] (62)
  = Rm(F) +Rm(G)
  2 . (63)
  Similarly, we can derive the same for Eσ,S,S′ [ supf∈F,g∈G ( 1 m ∑m i=1 |f(z′i)−g(z ′ i)|σi 2 )] . Thus, finally, we can represent the upper bound on E[φ(S)] as follows .
  E[φ(S)] ≤ Rm(F) +Rm(G) 2 + Rm(F) +Rm(G) 2 = Rm(F) +Rm(G). (64)
  This leads to the final form of the generalization error bound. With probability at least 1− δ, we have
  errP (f) ≤ êrrS(f) +Rm(F) +Rm(G) + √ log (1/δ)
  m . (65)
sections.heading: C.3 PROOF OF THEOREM 3
sections.text: The following statements propose the generalization error bound in terms of co-complexity. Theorem 3. For 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP (f) ≤ êrrS(f) +Rm(F ,G) + √ log (1/δ)
  2m . (66)
  Proof. We proceed in the same way as in appendix C.2, until we arrive at (57). In what follows, we note that we can write f(zi)g(zi) − f(z′i)g(z′i) = (1 − f(zi)g(zi)f(z′i)g(z′i))vi, for some binary valued variable vi with range in {−1, 1}. We also multiply the original Rademacher variable σi to (57), and derive the following set of bounds.
  E S
  [ sup
  f∈F,g∈G (errP (f)− êrrS(f)) ] ≤ E S,S′ [ sup f∈F,g∈G ( 1 m m∑ i=1 f(zi)g(zi)− f(z′i)g(z′i) 2 )] (67)
  = E S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (1− f(zi)g(zi)f(z′i)g(z′i)) vi 2
  )] (68)
  = E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (1− f(zi)g(zi)f(z′i)g(z′i)) viσi 2
  )] (69)
  ≤ E σ′,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)g(zi)f(z ′ i)g(z ′ i))σ ′ i 2
  )] . (70)
  The last step follows from the fact that E[σi] = 0, and the assumption that σ′i = viσi, are 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
  largeRm(F)). As 12×Eσ′,S,S′ [ supf∈F,g∈G ( 1 m ∑m i=1 f(zi)g(zi)f(z ′ i)g(z ′ i)σ ′ i )] = Rm(F ,G), we have the final generalization bound as follows. With probability ≥ 1− δ,
  errP (f) ≤ êrrS(f) +Rm(F ,G) + √ log (1/δ)
  m . (71)
  The above theorem leads to the following corollary. Corollary 3.1. We consider the hypothetical case where the roles are reversed, i.e., when the generator function space G is used to fit the labels, which are now generated by a function f ∈ F . For any function g ∈ G, for 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP (g) ≤ êrrS(g) +Rm(F ,G) + √ log (1/δ)
  2m . (72)
  Proof. This is a direct outcome of the fact thatRm(F ,G) = Rm(G,F). When the data labels in S is generated by functions in F rather than G, we will simply have with probability p ≥ 1− δ,
  errP (g) ≤ êrrS(g) +Rm(G,F) +
  √ log ( 1 δ ) m
  (73)
  = êrrS(g) +Rm(F ,G) +
  √ log ( 1 δ ) m . (74)
  Note that here the labels in S are generated by a certain f ∈ F . This completes the proof.
sections.heading: C.4 PROOF OF THEOREM 4
sections.text: The following result outlines the lower bound on the error function. Theorem 4. For 0 < δ < 1, with probability p ≥ 1− δ,
  errP (f) ≥ êrrS(f)−Rm(F ,G)− √ log (1/δ)
  2m . (75)
  Proof. First, we note that
  errP (f) ≥ êrrS(f)− E S
  [ sup
  f∈F,g∈G (êrrS(f)− errP (f))
  ] (76)
  Next, we denote
  φ(S) = sup f∈F,g∈G
  (errS(f)− êrrP (f)). (77)
  We then proceed similarly to Theorem 2 and Theorem 3, and we can show that
  E S [φ(S)] ≤ Rm(F ,G). (78)
  Furthermore, note that
  sup z1,z2,...,zn,z′i∈Z
  |φ(z1, z2, ..., zi, ...., zm)− φ(z1, z2, ..., z′i, ...., zm)| ≤ 1
  m . (79)
  This allows us to apply another consequence of Mcdiarmid’s inequality, which leads to the following, with probability p ≥ 1− δ,
  errP (f) ≥êrrS(f)− E S
  [ sup
  f∈F,g∈G (errS(f)− êrrP (f))
  ] − √ log (1/δ)
  m (80)
  ≥êrrS(f)−Rm(F ,G)− √ log (1/δ)
  m . (81)
  This completes the proof.
sections.heading: C.5 PROOF OF THEOREM 5
sections.text: Now, we outline a set of results pertaining to the joint-entropy like behaviour ofRm(F ,G). Theorem 5. We are given the mutual complexity measure Im(F ,G) as defined in co-complexity P4 (Section 5 of main paper). We consider an alternative ground truth generator space G′, such that Im(G′,G) = 0, i.e., G and G′ are independent. Then we have,
  Rm(F) ≥ Im(F ,G) + Im(F ,G′). (82)
  Proof. To prove the above, note that it is sufficient to prove the following:
  Rm(F ,G) +Rm(F ,G′) ≥ RCm(F) +R C m(G) +R C m(G ′) (83)
  We elaborate on the left hand side of the above inequality as follows
  Rm(F ,G) +Rm(F ,G′) = 1
  2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )]
  + 1
  2 × E σ,S,S′
  [ sup
  f∈F,g′∈G′
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g ′(zi)g ′(z′i)σi
  )] (84)
  We introduce i.i.d Rademacher variables { 0, ..., m}, by multiplying them with the terms within Rm(F ,G′). As E[ i] = 0 ∀i, this maneuver does not change the value of the expectation.
  Rm(F ,G) +Rm(F ,G′) = 1
  2 × E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi
  )]
  + 1
  2 × E σ, ,S,S′
  [ sup
  f∈F,g′∈G′
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g ′(zi)g ′(z′i)σi i
  )] (85)
  ≥ 1 2 × E σ, ,S,S′
  [ sup
  f∈F,g∈G,g′∈G′
  ( 1
  m m∑ i=1 f(zi)f(z ′ i) (g(zi)g(z ′ i) + ig ′(zi)g ′(z′i))σivi
  )] (86)
  Now note that one can re-express g(zi)g(z′i) + ig ′(zi)g ′(z′i) as (1 + ig(zi)g(z ′ i)g ′(zi)g ′(z′i))vi. Here vi ∈ {−1, 1} ∀i. Note that the value of vi depends on the values of g(zi), g(z′i), g′(zi), g′(z′i) and i. However, note that with so many dependencies vi ultimately is independent of all of these terms, individually. We have,
  Rm(F ,G) +Rm(F ,G′) ≥
  1 2 × E σ, ,S,S′
  [ sup
  f∈F,g∈G,g′∈G′
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)σivi
  + 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)g ′(zi)g ′(z′i) iσivi
  )] . (87)
  Note that the expectation is over a fixed values of σ, , S and S′. For the next step, we recognize that viσi = σ ′ i is a Rademacher variable itself in the first term to the R.H.S of the inequality above, as vi is independent of f(zi) and f(z′i). For a fixed value of those parameters, we then consider
  f∗ = arg max f∈F
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)σ ′ i
  ) . (88)
  Then, we can compute a lower bound for the expression in (87) as follows,
  Rm(F ,G) +Rm(F ,G′) ≥ 1 2 × E σ′,S,S′ 1 m m∑ i=1 f∗(zi)f ∗(z′i)σ ′ i
  + E σ, ,S,S′
  [ sup
  f∈F,g∈G,g′∈G′
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)g ′(zi)g ′(z′i) iσivi
  )] , (89)
  ≥ RCm(F) + 1
  2 E σ, ,S,S′
  [ sup
  g∈G,g′∈G′
  ( 1
  m m∑ i=1 g(zi)g(z ′ i)g ′(zi)g ′(z′i) ( iσivif ∗(zi)f ∗(z′i))
  )] .
  (90)
  It is important to note here that the variable iσivif∗(zi)f∗(z′i) is a Rademacher variable, but however, is not yet independent of the other terms being multiplied to it. The terms i, σi, f∗(zi) and f∗(z′i) are all independent of g(zi), g(z′i), g ′(zi)&g ′(z′i), but however, the same cannot be said of vi. Therefore, to resolve this issue we note that the product g(zi)g(z′i)g ′(zi)g
  ′(z′i) itself can be expressed as another function g′′(zi, z′i) = g(zi)g(z ′ i)g ′(zi)g
  ′(z′i), as an instance of another function space G′′ and the second term in (89) can then be re-expressed as,
  1 2 × E σ, S,S′ [ sup g′′∈G′′ ( 1 m m∑ i=1 g′′(zi, z ′ i) ( iσivif ∗(zi)f ∗(z′i)) )] . (91)
  Note that although vi was not independent of the g(zi), g(z′i), g ′(zi)&g ′(z′i), it is independent of the product g(zi)g(z′i)g ′(zi)g ′(z′i), and thus independent of g ′′(zi, z ′ i). Thus, now we can finally express the variables {σ′i = ( iσivif∗(zi)f∗(z′i)) |i = 1, 2, · · · ,m} as i.i.d Rademacher variables themselves. This leads to the lower bound as follows:
  Rm(F ,G) +Rm(F ,G′) ≥
  ≥ RCm(F) + 1
  2 × E σ′,S,S′
  [ sup
  g∈G,g′∈G′
  ( 1
  m m∑ i=1 g(zi)g(z ′ i)g ′(zi)g ′(z′i) (σ ′ i)
  )] . (92)
  = RCm(F) +Rm(G,G ′) = RCm(F) +R C m(G) +R C m(G ′). (93)
  The last step follows from the fact that Im(G′,G) = 0, that is, the function spaces G and G′ are independent (i.e. Rm(G,G′) = RCm(G) +R C m(G ′)). This concludes our proof.
  We now prove a corollary to Theorem 5, where we discuss implications of Theorem 5 on the generalization error bound in Theorem 3.
  Corollary 5.1. Given a function space G′, such that Im(G′,G) = 0. Suppose that Rm(F) = Im(F ,G) + Im(F ,G′) + , for some ≥ 0. We have with probability p ≥ 1− δ,
  errP (f) ≤ êrrS(f) +Rm(G) + Im(F ,G′) + + √ log (1/δ)
  m . (94)
  Proof. This is a direct consequence of the fact that Rm(F) ≥ Im(F ,G) + Im(F ,G′), combined with the generalization bound in Theorem 3.
  Now we 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 measureRm(F ,G) can be decomposed intoRIm(F ,G) andRDm(F ,G).
sections.heading: C.6 PROOF OF THEOREM 6
sections.text: 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 G, such that F is Rademacher smooth w.r.t. G. Let us defineRC,Dm (G) as 12 × Eσ,S,S′,S′ /∈IG(S) [ supg∈G ( 1 m ∑m i=1 g(zi)g(z ′ i)σi )] . For some non-negative real constant 0 ≤ α ≤ 1, we then have Rm(F ,G) ≤ αRIm(F ,G) + (1− α)(RDm(F ,G) +R C,D m (G)), (95)
  whereRIm(F ,G) andRDm(F ,G) are the invariance co-complexity 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 S′ ∈ IG(S) , and the ones where S′ /∈ IG(S). We begin from (67) as follows.
  Rm(F ,G) = E σ,S,S′
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 (f(zi)g(zi)f(z ′ i)g(z ′ i))σi 2
  )] (96)
  Then, using the Rademacher smoothness constraint, we have for a certain 0 ≤ α ≤ 1,
  Rm(F ,G) = α E σ,S,S′,S′∈IG(S)
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi 2
  )] +
  (1− α) E σ,S,S′,S′ /∈IG(S)
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi 2
  )] (97)
  = α E σ,S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi 2 )] +
  (1− α) E σ,S,S′,S′ /∈IG(S)
  [ sup
  f∈F,g∈G
  ( 1
  m m∑ i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi 2
  )] (98)
  ≤ α E σ,S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 (1− f(zi)f(z′i))σi 2 )] + (1− α)(RDm(F ,G) +RC,Dm (G))
  (99)
  ≤ α E S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 (1− f(zi)f(z′i)) 2 )] + (1− α)(RDm(F ,G) +RC,Dm (G)) (100)
  = αRIm(F ,G) + (1− α)(RDm(F ,G) +RC,Dm (G)). (101)
  We use the fact that Eσ,S,S′,S′ /∈IG(S) [ supf∈F,g∈G ( 1 m ∑m i=1 f(zi)f(z ′ i)g(zi)g(z ′ i)σi 2 )] ≤ RDm(F ,G)+ RC,Dm (G), which follows trivially from a derivation similar to that of co-complexity P3 in Lemma 2 (Rm(F ,G) ≤ RCm(F) +RCm(G)). This completes the proof.
  Using this, we proceed to the proof of Theorem 6, 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 RIm(F ,G), RDm(F ,G) as RDm, andR D,1 m (F ,G) asR D,1 m .
  Theorem 6. Consider function spaces F and G, such that F is Rademacher smooth w.r.t. G and F contains the constant function f(z) = c,∀z, c ∈ {−1, 1} . Let errP denote the generalization error for the functions f ∈ F which showcase the best fit on the training data samples. For some non-negative real constants 0 ≤ α, β ≤ 1 and 0 < δ < 1, with probability p ≥ 1− δ, we have
  errP ≤ (1− β) ( 1
  2 −RD,1m
  ) + αRIm + (1− α)(RDm +RC,Dm (G)) + √ 2 log(1/δ)
  m (102)
  Note: Recall thatRC,Dm (G) is defined in Lemma 2.
  Proof. We note that errP is the generalization error for the case when only the best fitting function fopt = argminf∈F (êrrS(f)) is chosen for each training data set S, and is averaged over all possible ground truth functions g ∈ G. Note that the labels in S is subject to change, depending on the choice of g. Thus for fixed datapoints z1, z2, .., zm ∈ S, (53) changes to
  errP ≤ E g∈G [êrrS(fopt)] + E g∈G (errP (fopt)− êrrS(fopt)) (103)
  ≤ E g∈G [êrrS(fopt)] + sup g∈G (errP (fopt)− êrrS(fopt)) (104)
  ≤ E g∈G [êrrS(fopt)] + sup f∈F,g∈G (errP (f)− êrrS(f)). (105)
  We now denote φ′(S) = Eg∈G [inff∈F (êrrS(fopt))] + supf∈F,g∈G(errP (f) − êrrS(f)). Let us also denote ψ(S) = Eg∈G [inff∈F (êrrS(fopt))] and γ(S) = supf∈F,g∈G(errP (f)− êrrS(f)). We then have the following for a fixed fopt.
  sup z1,...,zn,z′i∈Z
  |φ′(z1, ..., zi, ...., zm)− φ′(z1, ..., z′i, ...., zm)|
  ≤ sup z1,...,zn,z′i∈Z |ψ(z1, ..., zi, ...., zm)− ψ(z1, ..., z′i, ...., zm)|
  + sup z1,...,zn,z′i∈Z
  |γ(z1, ..., zi, ...., zm)− γ(z1, ..., z′i, ...., zm)| (106)
  ≤ 1 m + 1 m = 2 m . (107)
  It is easy to show that supz1,z2,...,zn,z′i∈Z |ψ(z1, z2, ..., zi, ...., zm)− ψ(z1, z2, ..., z ′ i, ...., zm)| ≤ 1m and supz1,z2,...,zn,z′i∈Z |γ(z1, z2, ..., zi, ...., zm) − γ(z1, z2, ..., z ′ i, ...., zm)| ≤ 1m . Applying Mcdiarmid’s inequality, we have with probability p ≥ 1− δ,
  errP ≤ E S,g∈G [êrrS(fopt)] + E S
  [ sup
  f∈F,g∈G (errP (f)− êrrS(f))
  ] + √ 2 log (1/δ)
  m . (108)
  We already have that ES [ supf∈F,g∈G(errP (f)− êrrS(f)) ] ≤ Rm(F ,G) ≤ αRIm+(1−α)(RDm+ RC,Dm (G), for a certain 0 ≤ α ≤ 1 (Lemma 2). The first term (expected training error) can be expressed as,
  E S,g∈G
  [êrrS(fopt)] = 1
  2
  ( 1− E
  S,g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi) )]) . (109)
  As iterated in the main statement of this theorem, we assume that the classifier function space is complex enough to allow for an error rate ≤ 50% (chance level for binary classification) on the training data itself. This indicates that we can safely assume that supf∈F ( 1 m ∑ i f(zi)g(zi) ) ≥ 0. We then have,
  sup f∈F
  ( 1
  m ∑ i f(zi)g(zi) ) sup f∈F ( 1 m ∑ i f(zi)g(zi) )
  = sup f∈F  1 m2 ∑ i,j f(zi)g(zi)f(zj)g(zj)  (110) = sup f∈F  1 m2 ∑ i,j f(zi)g(zi)f(z ′)g(z′)f(z′)g(z′)f(zj)g(zj)
   (111) = ( sup f∈F ( 1 m ∑ i f(zi)g(zi)f(z ′)g(z′) ))2 (112)
  where we make use of the fact that f(z′)g(z′)f(z′)g(z′) = 1. Here, the datapoint z′ is sampled from the same distribution P . Thus we have,
  E S,z′,g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi) )] ≥ E S,z′,g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi)f(z ′)g(z′) )] . (113)
  As before, we assume that the function space f is Rademacher smooth, i.e. for a certain 0 ≤ β ≤ 1, we can express
  E S,z′,g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi)f(z ′)g(z′) )] =
  =β E S,z′,S∈IG(z′),g∈G [ sup f∈F ( 1 m ∑ i f(zi)f(z ′) )]
  + (1− β) E S,z′,S /∈IG(z′),g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi)f(z ′)g(z′) )] . (114)
  ≥β E S,z′,S∈IG(z′),g∈G [ sup f∈F ( 1 m ∑ i f(zi)f(z ′) )]
  + (1− β) E S,z′,S /∈IG(z′),σ [ sup f∈F ( 1 m ∑ i f(zi)f(z ′)σi )] . (115)
  The last step above involves the reasonable assumption that the function space is going to be on average worse at fitting random noise labels, rather than a labelling provided by an element of the generator space G. Finally, we note that
  E S,z′,S∈IG(z′),g∈G [ sup f∈F ( 1 m ∑ i f(zi)f(z ′) )] = 1, (116)
  simply by choosing the constant function f(z) = c, which is assumed to be present within the classifier’s function space F . Also, note that ES,z′,S /∈IG(z′),σ [ supf∈F ( 1 m ∑ i f(zi)f(z ′)σi )] = 2RD,1m (F ,G). We then have
  E S,z′,g∈G [ sup f∈F ( 1 m ∑ i f(zi)g(zi)f(z ′)g(z′) )] ≥ β + 2(1− β)RD,1m (F ,G). (117)
  This leads to the final upper bound for errP by replacing the terms in (108) by the above. With probability p ≥ 1− δ, we then have,
  errP ≤ (1− β) ( 1
  2 −RD,1m
  ) + αRIm + (1− α)(RDm +RC,Dm (G)) + √ 2 log(1/δ)
  m (118)
  Finally, we provide the proof of Proposition 1, which gives interpretable bounds on invariance co-complexity and dissociation co-complexity. Proposition 1. Define the well known growth function of binary valued functions F as A = ΠF (m) = maxz |{f(zk) : k = 1, 2, ...,m, f ∈ F}|. Define the invariance-constrained and dissociation-constrained growth functions of F w.r.t. G as:
  B = ΠIF | G(m) = maxz,z’,z′i∈IG(zi),∀i |{f(zk), f(z′k) : k = 1, 2, ...,m, f ∈ F}|
  C = ΠDF | G(m) = maxz,z’,z′i /∈IG(zi),∀i |{f(zk), f(z′k) : k = 1, 2, ...,m, f ∈ F}|
  Define RI ′ m(F ,G) = 12 × Eσ,S,S′,S′∈IG(S) [ supf∈F ( 1 m ∑m i=1 f(zi)f(z ′ i)σi )] ,where z′i ∈ IG(zi),∀i. Note that RI ′ m(F ,G) ≤ R I m(F ,G). Given the definitions above, we have R I m(F ,G) ≤√
  logB 2m ≤ √ logA m andR D m(F ,G) ≤ √ logC 2m ≤ √ logA m .
  Proof. First we show thatRI ′
  m(F ,G) ≤ R I m(F ,G). This follows from the fact that
  RI ′ m(F ,G) = 1
  2 × E σ,S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] (119)
  = 1
  2 × E σ,S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 (1− f(zi)f(z′i))σi )] (120)
  ≤ 1 2 × E S,S′,S′∈IG(S) [ sup f∈F ( 1 m m∑ i=1 (1− f(zi)f(z′i)) )] = RIm(F ,G) (121)
  The proof of the main proposition immediately follows from the application of Massart’s finite class lemma, which states that for a finite subset K of Rm, and Rademacher variables σ1, σ2, ..., σm, we have
  E σ1,σ2,...,σm [sup ~y∈K ∑ i σiyi] ≤ r √ 2 log |K| (122)
  This immediately leads to the well known result for Rademacher complexityRm(F), which states Rm(F) ≤ √ 2 log ΠF (m)
  m . (123)
  The result above directly follows from the fact that the cardinality of the finite subset K is upper bounded by the growth function ΠF (m), when K is the set of all possible function outputs from functions f ∈ F , on any m points. In our case, as we have that
  RI ′ m(F ,G) = 1
  2 × E σ,S,S′ [ sup f∈F ( 1 m m∑ i=1 f(zi)f(z ′ i)σi )] , (124)
  we can directly apply Massart’s lemma, by the using the invariance-constrained growth function ΠIF | G(m) to obtain the first result as follows. First, we choose the finite subset K such that it
  contains all possible outputs of the function product f(zi)f(z′i) when S, S ′ is chosen such that each element in S′ lies in the invariance extended subset of each corresponding element in S. For this K, the cardinality |K| is bounded above by the previously defined growth function ΠIF | G(m). This immediately leads to the first result,
  RI ′ m(F ,G) ≤ 1
  2
  √ 2 log ΠIF | G(m)
  m (125)
  =
  √ log ΠIF | G(m)
  2m . (126)
  We can similarly show the equivalent result for dissociation co-complexityRDm(F ,G), to obtain
  RDm(F ,G) ≤ 1
  2
  √ 2 log ΠDF | G(m)
  m (127)
  =
  √ log ΠIF | G(m)
  2m . (128)
  Finally, we recognize that the growth functions ΠIF | G(m) and Π D F | G(m) are bounded above by the cardinality of all possible function values taken in S, S′, which in turn is bounded above by ΠF (m)×ΠF (m). This implies ΠIF | G(m) ≤ ΠF (m) 2 and ΠDF | G(m) ≤ ΠF (m) 2, from which we then have
  RDm(F ,G) ≤
  √ log ΠDF | G(m) 2m ≤ √ log ΠF (m) m (129)
  and
  RIm(F ,G) ≤
  √ log ΠIF | G(m) 2m ≤ √ log ΠF (m) m . (130)
  This concludes the proof.
sections.heading: D NEURAL NETWORK ARCHITECTURE DETAILS
sections.text: Here we present the architectures that were used in our experiments. As mentioned in section 4, four different architectures were tested. In Table 4, we show the layer-wise details of each architecture. Note that all architectures share a similar parameter count, and also evoke a similar dissociation co-complexity as a result (see Table 2 and 3). Note that the input to all these architectures is an image of size 28× 28 (same size as in the MNIST dataset). For STL-10, we resized the input (96× 96) to 28× 28 and used the same architectures for consistency.