Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

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

–

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

Here is a list of suggestions for the authors:
1. 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).
2. LGF is not properly defined, whereas it is a central notion.
3. Section 2 is based on the complexity measure $R_m(f)$. However, this concept is only defined in Section 5, two pages later.
4. 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.
5. 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.
6. The definition of "Rademacher smoothness" mixes intuition with mathematical definition, making it difficult to understand.
7. 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?
8. As with Section 5, the presentation of Section 6 and the appendices could be improved.
9. Computations 9 and 10 would benefit from being stated with "real" fractions, i.e. displaystyle fraction.
10. 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.
11. In Appendix C, several references are made to the definitions in Section 3. I think the authors meant to refer to Section 5.
12. The demonstrations should be shorted, particularly those in Appendix C.1. Evidence (i) is clearly too trivial to be detailed, for example.
13. 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.
14. Evidence (iv) page 13: I think there is a parenthesis error when introducing $v_i$. A $\frac12$  is missing from calculations (36) and (37).
15. 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$.
16. 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.

Typos: 
* Page 4, penultimate line: "that" is doubled without reason;
* Page 5, 2nd paragraph of Section 6: is/be;
* 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.

review_title: Interesting work but, in this form, the paper not ready for publication.

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################
Summary:
 
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.
##########################################################################
Reasons for score: 
 
Overall, 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.
 
##########################################################################Pros: 
 
1. The paper takes an important issue of generalization error estimation. For me, the problem itself is of significance and interest.
 
2. The proposed method to measure complexity is novel for capturing the relationship between generator and classifier space and how the given constraints affect complexity. 
 
3. This paper provides comprehensive experiments, including both qualitative analysis and quantitative results, to show the effectiveness of the proposed framework. 
 
##########################################################################
Cons: 
 
Although the proposed method provides several ablation studies, I still suggest the authors conduct the following ablation studies to enhance the quality of the paper: 
1. 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.
2. 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.
3. 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?
4. 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.

#########################################################################
Some typos: 
(1) abstract: large irrespective -> largely irrespective
(2) Does Eq (6) miss \sigma.
(3) Remark 4 is not coherent to Theorem 5 very well. It needs more clarification.
(4) It is not clear that why R_m^I' m(F; G) <= R_m^I m(F; G) 


review_title: Nontitle's

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.  

This paper is written in clear form and easy to follow.  There are some points I did not fully understand.

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

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

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

With 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.
review_title: Official Blind Review #1

final_score: rating: 4: Ok but not good enough - rejection
review_content: ** Description

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

** Pros

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

** Cons

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

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

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

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

** And Yet...

I 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
be an important contribution to the field, but in it present form I think the paper adds more confusion than light.

review_title: A New Perspective on Generalisation Error

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