Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This submission derives model complexity bounds using the idea of transformation-induced sample covering numbers, proposes an algorithm for estimating them, and implements the algorithm on a few data sets.
main_review: Overall, the paper is clearly written, and of relatively high quality and originality. I think its significance could be improved by devoting more space to the algorithm for estimating the sample cover number (see below); by making more explicit the role of invariance in the theoretical results; and fully considering the trade-off between model complexity and empirical risk in generalization bounds.

The theory is missing the connection between invariance-induced model complexity reduction and improved generalization. In particular, both in the main text and in the appendix, the role of invariance isn't clear. Generating the sample cover from a set of transformations is intuitive, but once we have that, the role of invariance doesn't seem particularly important. I'm guessing that I missed something so it would be helpful for the authors to clarify. 

Further to that point, all of the theoretical results bound the covering number or Rademacher complexity of $\mathcal{H}$, and of course that's only one part of a generalization bound. One could map all points to a singleton and have a covering number of 1, but that won't do well empirically. What assumptions are needed about the underlying data distribution in order to either i) guarantee that the empirical risk won't increase (at least in probability); or ii) control the trade-off between empirical risk increase and model complexity decrease?

The theoretical development seems correct, and is a nice complementary perspective to the function-space perspective (though I would argue that the distinction isn't meaningful---the function space simplifies because the data space simplifies and vice versa). I am much more enthusiastic about the proposed techniques for estimating sample cover numbers. These are potentially very useful. However, the algorithmic challenges are swept to the appendix, where they are mostly swept under the rug. The challenges should be brought front-and-center, and identified as important for subsequent work. With that in mind, I think the paper would be improved by moving most or all of the linear model class special case to the appendix and devoting additional page space to algorithmic considerations and challenges.

Finally, there are some minor typos scattered throughout the text that the authors should fix.
limitations_and_societal_impact: The authors haven't made clear the extent to which their results focus only on model complexity, nor the potential limitations of their proposed algorithm.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper provides a bound on the Rademacher complexity of a class of Lipschitz and transformation-invariant functions by upper bounding the covering number of the function class by a similar covering number which uses a "sample cover induced by data transformations". This is the induced covering number which accounts for transformations of the original sample set and can be smaller due to the transformation invariance of the function. This directly gives improved generalization bounds for transformation-invariant functions. The paper gives some helpful intuition and simple cases where these bounds may be applied.

Furthermore, the paper presents experiments in which the sample covering number induced by different transformations is approximated, and the generalization ability of a model which is trained to be invariant to those respective transformations is shown to be strongly correlated with the sample covering number. 
main_review: I think this is a great paper, with nice theoretical results and simple yet surprisingly insightful experimental results (though I note that only briefly skimmed the proofs). I particularly appreciate that this paper gives not only meaningful improvements to generalization bounds, but also a concrete prescription for how to choose data augmentations to improve generalization in practice.

I do think it's a bit limiting that these results hold only for functions which are *fully* invariant, as this rarely holds without some sort of strong structural prior. Would the proof techniques not work for functions which are *close to* invariant? For example, suppose we assume the function class is $\kappa$-Lipschitz generally, but $\kappa'$-Lipschitz over group transformations, for $\kappa' \ll \kappa$ (or some other measure of "approximate invariance", as Lipschitzness may not appropriately capture such invariance for certain transformations). Would this not allow for a similar result, with an additional error term?

minor nits:
* In line 95, the definition of covering number for function classes is presented with an argument ordering which is permuted; this should be made consistent to match the orderings used later on.
* Line 206, these are classes of functions, so this should be "subset of" ($\subset$), not "element of" ($\in$).
limitations_and_societal_impact: Sure
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors tried to understand the generalization benefit based on the invariant transformation by improving the sample covering number. Although the paper focuses on an interesting question (how model invariance helps generalization), it seems that it is still not in its best shape. I believe this paper will benefit from (a) careful polishment on the writing, (b) some more insightful results, and (c) more experiments on some complex datasets.
main_review: I think the paper has the potential to be accepted after some careful polishment. However, I think the current version has some nonnegligible flaws. 


## Contributions

1. The authors show that the Rademacher complexity can be reduced when the model is invariant to some transformation (via sample covering number) under Lipschitz and linear regimes.

2. The authors propose an algorithm to estimate the sample covering number empirically.


## Concerns

1. During the proof of Proposition 3.3, since the requirement of Proposition 3.6 is much stronger (a Lipschitz requirement), it cannot be directly applied during the proof of Proposition 3.3.

2. The current conclusion (theory part) in this paper is still not insightful enough. I believe if the transformation can greatly reduce the sample complexity, the generalization could be better. If the authors want to claim "the theory just gives some intuition and the most surprising part is that the practice agreed with the theory", more experiments should be conducted to verify the statements, e.g., CIFAR-100 and ImageNet.

## Writtings.

I believe this paper can benefit from careful writing.

1. For example, is Proposition 3.3 a well-known result? If so, I wonder why the authors give the proof based on Proposition 3.6 (see Line 498-499). Besides, During the proof of Proposition 3.6, I wish the authors can distinguish between Equation 3.3 and Proposition 3.3 (see line 556). When I first read the proofs, I am a little bit puzzled.

2. Line 118-119, why c(r) = |r| instead of |r-x1|?


limitations_and_societal_impact: No Societal Impact.
review_title: null

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