A Theory of PAC Learnability under Transformation Invariances

Han Shao, Omar Montasser, Avrim Blum

TL;DR

This paper provides the first rigorous theoretical framework for understanding how transformation invariances (like rotations or flips in images) affect learning. The authors prove that while common data augmentation (DA) helps, it is often sub-optimal and can even "harm" accuracy in certain settings, leading them to propose new complexity measures and optimal algorithms based on 1-inclusion graphs.

What Problem Does This Paper Address?

In machine learning, we often know that certain transformations shouldn't change a label—a picture of a cat is still a cat if you rotate it. The standard way to handle this is Data Augmentation (DA): creating transformed versions of your training data to teach the model these invariances.

Despite its massive empirical success, we lack a solid theoretical understanding of DA. Does it always help? Is it the best way to use invariance information? This paper tackles these questions within the PAC (Probably Approximately Correct) learning framework, specifically looking at how many samples a model needs (sample complexity) to learn effectively when invariances are present.

Methods

The authors categorize the problem into three levels of "realizability" (how well a model can fit the data):

  1. Invariantly Realizable: A perfect model exists that is invariant across all transformations.
  2. Relaxed Realizable: A perfect model exists for the "natural" data, but it might fail on transformed data that falls outside the natural distribution.
  3. Agnostic: No perfect model exists in the hypothesis class.

To analyze these, they introduce two new combinatorial measures:

  • VC Dimension of Orbits ($VC_o$): Measures the complexity of the hypothesis class when restricted to invariant functions.
  • VC Dimension Across Orbits ($VC_{ao}$): A broader measure that accounts for functions that might not be perfectly invariant.

They then adapt the 1-inclusion graph predictor—a classic but powerful theoretical algorithm—to work with these "orbits" of transformed data. They also propose ERM-INV, a modified Empirical Risk Minimization algorithm that explicitly distinguishes between original and augmented data.

Datasets

As a theoretical paper, this work does not use standard empirical benchmarks like ImageNet or CIFAR-10. Instead, it uses synthetic mathematical constructions to prove its theorems. For example:

  • Example 2 & 5: Use sign-flipping groups on discrete sets to show how DA can fail or be sub-optimal.
  • Example 3: Uses a circle instance space with rotation groups to illustrate infinite VC dimension scenarios.
  • Example 4: Uses a set of "upright" vs "rotated" images to demonstrate the gap between their new complexity measures.

Key Insights and Ideas

  • DA is Sub-optimal: Even in the best-case scenario (invariantly realizable), DA is a "proper learner" (it must pick a hypothesis from the original class $H$). The authors show that "improper" learners, which can consider the entire orbit of a test point, can achieve much better sample complexity.
  • DA Can "Hurt": In the "relaxed" setting, where the target function isn't perfectly invariant across all possible transformations, DA can actually perform worse than standard ERM without any augmentation. This happens because DA forces the model to treat original and transformed data as identical, losing valuable information.
  • The Importance of Distinction: To reach optimal accuracy in most settings, an algorithm must distinguish between original natural data and the "fake" augmented data. DA's failure to do this is its primary theoretical weakness.
  • Test-Time Adaptation: The optimal algorithm for invariant settings naturally incorporates information about the test point's orbit, providing a theoretical justification for modern "test-time adaptation" techniques.

Key Results

  • Sample Complexity Gaps: The authors prove that the sample complexity of DA is characterized by $VC_{ao}$, while the optimal complexity is characterized by $VC_o$. The gap between these two can be arbitrarily large.
  • Optimal Bounds: They provide tight upper and lower bounds for all three settings. For the invariant setting, the optimal complexity is roughly $\tilde{O}(VC_o / \epsilon)$, whereas DA requires $\tilde{O}(VC_{ao} / \epsilon)$.
  • Adaptive Learning: They present an adaptive algorithm (Algorithm 1) that automatically adjusts to the level of invariance in the target function, performing optimally whether the target is fully invariant or only partially so.

Limitations and Future Work

  • Group Theory Constraints: Most of the results assume that the set of transformations forms a mathematical group. While some results extend to non-groups (like cropping), a general theory for arbitrary transformations remains an open challenge.
  • Binary Focus: The work is currently limited to binary classification. Extending this to multi-class or regression problems is a logical next step.
  • Probabilistic Labels: The paper assumes deterministic labels (a car is 100% a car). The authors note that defining "invariance" under probabilistic or "fuzzy" labels is an unresolved conceptual problem.
  • Complexity Measure Refinement: There is an open question regarding whether one of their measures ($\mu$) is strictly bounded by another ($dim(H, G)$), which would further simplify the theory.

Summary updated

Abstract

Transformation invariances are present in many real-world problems. For example, image classification is usually invariant to rotation and color transformation: a rotated car in a different color is still identified as a car. Data augmentation, which adds the transformed data into the training set and trains a model on the augmented data, is one commonly used technique to build these invariances into the learning process. However, it is unclear how data augmentation performs theoretically and what the optimal algorithm is in presence of transformation invariances. In this paper, we study PAC learnability under transformation invariances in three settings according to different levels of realizability: (i) A hypothesis fits the augmented data; (ii) A hypothesis fits only the original data and the transformed data lying in the support of the data distribution; (iii) Agnostic case. One interesting observation is that distinguishing between the original data and the transformed data is necessary to achieve optimal accuracy in setting (ii) and (iii), which implies that any algorithm not differentiating between the original and transformed data (including data augmentation) is not optimal. Furthermore, this type of algorithms can even "harm" the accuracy. In setting (i), although it is unnecessary to distinguish between the two data sets, data augmentation still does not perform optimally. Due to such a difference, we propose two combinatorial measures characterizing the optimal sample complexity in setting (i) and (ii)(iii) and provide the optimal algorithms.
BibTeX
@inproceedings{shao2022theory,
  author = {Han Shao and Omar Montasser and Avrim Blum},
  title = {{A Theory of PAC Learnability under Transformation Invariances}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=l1WlfNaRkKw},
}
Figure