# A Theory of PAC Learnability under Transformation Invariances

arXiv: https://arxiv.org/abs/2202.07552 · HTML: https://mlsanity.com/paper/2202.07552/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 15 Feb 2022.

## Builds on (most cited first, 18 of 18)

- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [AutoAugment: Learning Augmentation Policies from Data](https://mlsanity.com/paper/1805.09501/) (2018)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups](https://mlsanity.com/paper/1802.03690/) (2018)
- [Harmonic Networks: Deep Translation and Rotation Equivariance](https://mlsanity.com/paper/1612.04642/) (2016)
- [Equivariance Through Parameter-Sharing](https://mlsanity.com/paper/1702.08389/) (2017)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [A Kernel Theory of Modern Data Augmentation](https://mlsanity.com/paper/1803.06084/) (2018)
- [Exploiting Cyclic Symmetry in Convolutional Neural Networks](https://mlsanity.com/paper/1602.02660/) (2016)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [On the Benefits of Invariance in Neural Networks](https://mlsanity.com/paper/2005.00178/) (2020)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Affinity and Diversity: Quantifying Mechanisms of Data Augmentation](https://mlsanity.com/paper/2002.08973/) (2020)
- [Adversarial Robustness May Be at Odds With Simplicity](https://mlsanity.com/paper/1901.00532/) (2019)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (2021)

## Built on by (most cited first, 21 of 21)

- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Sample Efficiency of Data Augmentation Consistency Regularization](https://mlsanity.com/paper/2202.12230/) (2022)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Sample, estimate, aggregate: A recipe for causal discovery foundation models](https://mlsanity.com/paper/2402.01929/) (2024)
- [Automatic Data Augmentation via Invariance-Constrained Learning](https://mlsanity.com/paper/2209.15031/) (2022)
- [Learning with Explanation Constraints](https://mlsanity.com/paper/2303.14496/) (2023)
- [On the Computability of Robust PAC Learning](https://mlsanity.com/paper/2406.10161/) (2024)
- [On The Statistical Limits of Self-Improving Agents](https://mlsanity.com/paper/2510.04399/) (2025)
- [Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization](https://mlsanity.com/paper/2410.23461/) (2024)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [An Analysis of Causal Effect Estimation using Outcome Invariant Data Augmentation](https://mlsanity.com/paper/2510.25128/) (2025)
- [VC dimensions of group convolutional neural networks](https://mlsanity.com/paper/2212.09507/) (2022)
- [Automatic Data Augmentation Learning using Bilevel Optimization for Histopathological Images](https://mlsanity.com/paper/2307.11808/) (2023)
- [Learning Tree-Structured Composition of Data Augmentation](https://mlsanity.com/paper/2408.14381/) (2024)
- [On the VC dimension of deep group convolutional neural networks](https://mlsanity.com/paper/2410.15800/) (2024)
- [Optimizing Data Augmentation through Bayesian Model Selection](https://mlsanity.com/paper/2505.21813/) (2025)
- [Sparse Data Augmentation for Optimization with Provable Guarantees](https://mlsanity.com/paper/2609.08133/) (2026)
- [Randomized Dimension Reduction with Statistical Guarantees](https://mlsanity.com/paper/2310.01739/) (2023)
- [PAC Learnability under Explanation-Preserving Graph Perturbations](https://mlsanity.com/paper/2402.05039/) (2024)
- [Approximate Nullspace Augmented Finetuning for Robust Vision Transformers](https://mlsanity.com/paper/2403.10476/) (2024)
- [The geometry of invariant learning: an information-theoretic analysis of data augmentation and generalization](https://mlsanity.com/paper/2602.14423/) (2026)

## Abstract (arXiv)

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.