mlsanityData to 7 Oct 2026

Generalization Error of Invariant Classifiers

arXiv 1610.04574 ↗First posted 14 Oct 2016stat.ML cs.AI cs.CVcited by 42

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 9; 2023: 7; 2024: 8; 2025: 3; 2026: 4.

42 papers.

Sort:

  1. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  2. 2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 90
  3. 2021Equivariant Imaging: Learning Beyond the Range Spacecited by 83
  4. 2022Theory for Equivariant Quantum Neural Networkscited by 60
  5. 2024Does equivariance matter at scale?cited by 49
  6. 2021Random Noise Defense Against Query-Based Black-Box Attackscited by 46
  7. 2022Out-of-distribution Generalization with Causal Invariant Transformationscited by 45
  8. 2023Approximation-Generalization Trade-offs under (Approximate) Group Equivariancecited by 45
  9. 2021Discrete-Valued Neural Communicationcited by 39
  10. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  11. 2021Provably Strict Generalisation Benefit for Invariance in Kernel Methodscited by 29
  12. 2023The Exact Sample Complexity Gain from Invariances for Kernel Regressioncited by 27
30 more
  1. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 25
  2. 2022Robustness Implies Generalization via Data-Dependent Generalization Boundscited by 23
  3. 2021Understanding the Generalization Benefit of Model Invariance from a Data Perspectivecited by 22
  4. 2023A General Theory of Correct, Incorrect, and Extrinsic Equivariancecited by 18
  5. 2022A PAC-Bayesian Generalization Bound for Equivariant Networkscited by 17
  6. 2022An Analysis of Attention via the Lens of Exchangeability and Latent Variable Modelscited by 15
  7. 2021On the Sample Complexity of Learning under Invariance and Geometric Stabilitycited by 13
  8. 2023Sample Complexity of Probability Divergences under Group Symmetrycited by 13
  9. 2022Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARLcited by 12
  10. 2023Hyperparameter Optimization through Neural Network Partitioningcited by 8
  11. 2021Recent Advances in Large Margin Learningcited by 7
  12. 2023On the Implicit Bias of Linear Equivariant Steerable Networkscited by 7
  13. 2023Statistical Guarantees of Group-Invariant GANscited by 4
  14. 2024Gentle Local Robustness implies Generalizationcited by 4
  15. 2022CNNs Avoid Curse of Dimensionality by Learning on Patchescited by 3
  16. 2021Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?cited by 2
  17. 2026Efficient Learning and Symmetry Discovery under Exact Invariancescited by 2
  18. 2024Optimal Symmetries in Binary Classificationcited by 1
  19. 2024On the VC dimension of deep group convolutional neural networkscited by 1
  20. 2024Scale-aware Message Passing For Graph Node Classificationcited by 1
  21. 2025Statistical Learning Guarantees for Group-Invariant Barron Functionscited by 1
  22. 2021Understanding Adversarial Examples Through Deep Neural Network's Response Surface and Uncertainty Regionscited by 0
  23. 2022Symmetry Defense Against CNN Adversarial Perturbation Attackscited by 0
  24. 2024Approximating invariant functions with the sorting trick is theoretically justifiedcited by 0
  25. 2024ScaleNet: Scale Invariance Learning in Directed Graphscited by 0
  26. 2025Generalization Bounds for Equivariant Networks on Markov Datacited by 0
  27. 2025Leveraging Label Potential for Enhanced Multimodal Emotion Recognitioncited by 0
  28. 2026The Normalized Difference Layer: A Differentiable Spectral Index Formulation for Deep Learningcited by 0
  29. 2026On the Generalization Behavior of Deep Residual Networks From a Dynamical System Perspectivecited by 0
  30. 2026Representation Redundancy and Structural Complexity in Finite-Field Inversioncited by 0