Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the PAC learnability of hypothesis classes with different levels of invariance realizability, assuming that the data distribution is group-transformation-invariant. For each realizability case, the authors derive sample complexity bounds for data-augmented ERM and a 1-inclusion-graph-based learning algorithm, using two “invariant versions” of VC-dimension that limit the choices of samples and hypotheses. They show that the sample complexity of the former algorithm is sub-optimal or even worse than ERM while the latter one achieves the optimal sample complexity.

strengths_and_weaknesses: ### Strengths:
1. This paper addresses two important problems: PAC learnability under transformation invariance and theoretical understanding of data augmentation.

2. The theoretical analyses are sound and interesting — the two “invariant versions” of VC-dimension are novel and the lower and upper sample complexity bounds in each realizatiliby case are comprehensive.

3. The conclusions, suggesting that the DA can be sub-optimal in practice and using the 1-inclusion-graph-based algorithm could help achieve the optimal sample complexity, are inspiring.

### Weaknesses:
1. My major concern is to what extent the theoretical results in this paper hold on real data and how much practical insight we could gain from this paper. Specifically,
    1. The two proposed combinatorial complexity measures seem hard to evaluate in practice. Evaluating the VC-dimension of a neural network class while limiting data points to lie in disjoint orbits seems non-trivial to me. I wonder how many previous results on VC-dimension calculation for neural networks could be adapted here. If we cannot evaluate the proposed combinatorial complexity measures in practice, how can we gain insight from the sample complexity results based on it?
   2. Many of the main theoretical results, including the arbitrarily large gap between different versions of VC-dimension and all the lower bounds of the sample complexity (which are used to show the sub-optimality and harm of data augmentation), are based on specific data distribution constructions. I understand that these are common proof practices for VC-dimension but am also wondering to what extent they hold on real data? 

2. Some descriptions could be made clearer. For example, throughout the paper I do not see how the probability measure on the transformation group is defined for the data-augmented ERM.

questions: 1. I suggest that the authors give an intuitive explanation for the term “distinguish between the original and transformed data” in the main text.
2. Readers could also benefit from an intuitive description about the 1-inclusion-graph-based learning algorithm in the main text.
limitations: Yes, the authors address the limitation of assuming invariant data distributions.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: ### **Brief summary**

This paper studies the sample complexity of PAC learning in a setting where the inputs satisfy invariant properties generated by a group. From a theoretical perspective, this paper compares the sample complexity from such a setting to the sample complexity of ERM, and use this as a lens to theoretically reason about data augmentation, which is a popular heuristic but "is unclear whether and when data augmentation helps."

### **Contribution**

The set up for learning under transformation invariances, as defined by the paper, is as follows: (i) Given a group of transformations, the *augmented data set* is the set of transformed data. (ii) It is assumed that the labels of the data are invariant. Based on this, a hypothesis is invariant to a transformation group if it predicts the same label for a transformed data as the original data.

The results of this paper are shown under three settings according to the level of realizability of the hypothesis class.
- First is the *invariantly realizable PAC learning* setting, which captures scenarios where there exist an invariant hypothesis that makes perfect predictions in the augmented data distribution.
- Second is the *relaxed realizable PAC learning* setting, which captures scenarios where there exist a hypothesis (which may or may not be invariant) that makes perfect predictions in the augmented data distribution.
- Third is the *agnostic* setting, for which there may not exist a perfect predictor for the augmented data distribution.

Then, the contribution of this paper is to give nearly tight upper and lower bounds on the sample complexity of DA--ERM over the augmented data--for all three settings.
- For setting one, the sample complexity of DA is given by the VC dimension across the orbits of the augmented data.
    - However, it is also shown that the optimal sample complexity is instead determined by the VC dimension of the orbits, where the labelings need to be realized by an invariant hypothesis.
- For setting two, the sample complexity of DA depends on a certain graph orientation.
    - On the other hand, the optimal sample complexity for learning this setting is given by the VC dimension across orbits (i.e. without requiring the invariant hypothesis)
- For the agnostic setting, the optimal sample complexity also depends on the VC dimension across orbits.
strengths_and_weaknesses: ### **Strength**

- The sample complexity bounds concerning DA depend on the VC dimension of/across the orbits, depending on the exact setting. These bounds provide a new theoretical lens to examine data augmentation. For example, it is argued from the VC dimension bounds that
    - In the invariantly realizable setting, DA helps compared to ERM. However, it is not necessarily optimal.
    - In the relaxed realizable setting, DA may actually hurt.
- This paper also proposes an ERM-based algorithm that achieves the optimal sample complexity. The design of this algorithm is quite interesting in my opinion: It works by first checking whether the test instance can be generated by a transformation of the input. If not, it outputs the ERM prediction.
- This paper first provides a rigorous mathematical definition of PAC learning under group transformations. I find this formulation nice to read. The contributions and their proofs are well laid out.
- I find the writing of this paper to be easy to follow. I have some minor comments mentioned below.
- The discussions section provides a candid narrative of the limitations of this paper.

### **Weakness**

- The discussion concerning the 1-inclusion-graph, starting from L273, could be improved to better explain this concept.
- In the relaxed realizable setting, the sample complexity of DA depends on a certain edge orientation notion $\mu(\mathcal{H}, \mathcal{G})$. It might help provide some more explanations to give the intuition behind the notion.
- Some of the proofs in the appendix could use more work to give greater clarity.
    - L762: The sentence following "Every labeling" is broken.
questions: - In the problem setup, it seems that the transformations are assumed to be known a prior. What if they are not given? For example, works like Autoaugment often require finding the "right" transformation to apply for a particular task/dataset.
limitations: The authors provided a discussion of the limitations of this paper in the main text. The potential negative societal impact is not discussed (possibly but due to the technical nature of the paper); this should be addressed in a revised version.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: Modern computer vision models are trained to be robust to various kinds of transformations such as rotation, tilt, reflection of input images. This is usually achieved with data augmentation when the transformed images are explicitly added to the training set. In an attempt to have a theory that takes into account this feature of modern approaches to learning the authors propose to expand the classical PAC framework by introducing transformation invariant hypotheses and distributions. Realizable and agnostic cases are considered. The modifications of the VC dimension are given, which characterize learnability in different realizability modes. Optimal (in sample complexity) learning algorithms are discussed.
strengths_and_weaknesses: 1) As far as I know, data augmentation techniques are rather simple in the case of image data, but not so simple in the case of textual data. Say, to implement the technique that the authors mentioned at the beginning of the paper (replacement of noun phrases), some external resources will be required (for example, an already trained constituent parser) which we may not assume to be readily available for a wide variety of languages. Therefore, it seems to me that the proposed theory has a limited scope.

2) The proposed theory does not provide a simple characterization of realizable and agnostic learnability, as does the VC dimension in classical PAC learning. In the proposed theory, different modes of realizability entail different characterizations of learnability.

3) The proposed theory does not provide such a simple principle as the ERM in classical PAC learning. The optimal learning algorithm is again conditioned by the realizability mode. Moreover, in some cases the optimal algorithm is transductive (based on a 1-inclusion-graph predictor), i.e. to calculate the label on any new test point, the entire training set will be used (as it is, for example, in the k nearest neighbors algorithm), which calls into question the computational efficiency of learning.
questions: Perhaps I missed it in the papaer, but I have this question: if we perform data augmentation under standard PAC learning, but define the sample size as the number of examples in the original (non-augmented) dataset, how does this compare with your estimate of the sample complexity $\tilde{O}\left(\frac{\text{VC}_{\text{ao}}(\mathcal{H},\mathcal{G})}{\epsilon}\right)$ in the invariantly realizable case?
limitations: It seems to me that the proposed theory has a limited scope. See item 1 in Strengths and Weaknesses above.
review_title: null

Meta-review: metareview: All reviewers are positive. 

Clear accept.
confidence: Certain
Decision: Accept