# Generalization Error of Invariant Classifiers

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2016.

## Built on by (most cited first, 30 of 42)

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Equivariant Imaging: Learning Beyond the Range Space](https://mlsanity.com/paper/2103.14756/) (2021)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [Does equivariance matter at scale?](https://mlsanity.com/paper/2410.23179/) (2024)
- [Random Noise Defense Against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2104.11470/) (2021)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Out-of-distribution Generalization with Causal Invariant Transformations](https://mlsanity.com/paper/2203.11528/) (2022)
- [Discrete-Valued Neural Communication](https://mlsanity.com/paper/2107.02367/) (2021)
- [Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscape](https://mlsanity.com/paper/2201.08025/) (2022)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [Understanding the Generalization Benefit of Model Invariance from a Data Perspective](https://mlsanity.com/paper/2111.05529/) (2021)
- [A General Theory of Correct, Incorrect, and Extrinsic Equivariance](https://mlsanity.com/paper/2303.04745/) (2023)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [An Analysis of Attention via the Lens of Exchangeability and Latent Variable Models](https://mlsanity.com/paper/2212.14852/) (2022)
- [Sample Complexity of Probability Divergences under Group Symmetry](https://mlsanity.com/paper/2302.01915/) (2023)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL](https://mlsanity.com/paper/2209.09845/) (2022)
- [Hyperparameter Optimization through Neural Network Partitioning](https://mlsanity.com/paper/2304.14766/) (2023)
- [Recent Advances in Large Margin Learning](https://mlsanity.com/paper/2103.13598/) (2021)
- [On the Implicit Bias of Linear Equivariant Steerable Networks](https://mlsanity.com/paper/2303.04198/) (2023)
- [Statistical Guarantees of Group-Invariant GANs](https://mlsanity.com/paper/2305.13517/) (2023)
- [Gentle Local Robustness implies Generalization](https://mlsanity.com/paper/2412.06381/) (2024)
- [CNNs Avoid Curse of Dimensionality by Learning on Patches](https://mlsanity.com/paper/2205.10760/) (2022)
- [Efficient Learning and Symmetry Discovery under Exact Invariances](https://mlsanity.com/paper/2609.07031/) (2026)
- [Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?](https://mlsanity.com/paper/2110.07472/) (2021)
- [Optimal Symmetries in Binary Classification](https://mlsanity.com/paper/2408.08823/) (2024)

## Abstract (arXiv)

This paper studies the generalization error of invariant classifiers. In particular, we consider the common scenario where the classification task is invariant to certain transformations of the input, and that the classifier is constructed (or learned) to be invariant to these transformations. Our approach relies on factoring the input space into a product of a base space and a set of transformations. We show that whereas the generalization error of a non-invariant classifier is proportional to the complexity of the input space, the generalization error of an invariant classifier is proportional to the complexity of the base space. We also derive a set of sufficient conditions on the geometry of the base space and the set of transformations that ensure that the complexity of the base space is much smaller than the complexity of the input space. Our analysis applies to general classifiers such as convolutional neural networks. We demonstrate the implications of the developed theory for such classifiers with experiments on the MNIST and CIFAR-10 datasets.