# Provably Strict Generalisation Benefit for Invariance in Kernel Methods

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 49 references that are in the map.
- First posted on arXiv 4 Jun 2021.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Spherical CNNs](https://mlsanity.com/paper/1801.10130/) (2018)
- [On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups](https://mlsanity.com/paper/1802.03690/) (2018)
- [A General Theory of Equivariant CNNs on Homogeneous Spaces](https://mlsanity.com/paper/1811.02017/) (2018)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Equivariance Through Parameter-Sharing](https://mlsanity.com/paper/1702.08389/) (2017)
- [Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks](https://mlsanity.com/paper/1810.00825/) (2018)
- [Universal approximations of invariant maps by neural networks](https://mlsanity.com/paper/1804.10306/) (2018)
- [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)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [3D G-CNNs for Pulmonary Nodule Detection](https://mlsanity.com/paper/1804.04656/) (2018)
- [Better, Faster Fermionic Neural Networks](https://mlsanity.com/paper/2011.07125/) (2020)
- [Improving Transformation Invariance in Contrastive Representation Learning](https://mlsanity.com/paper/2010.09515/) (2020)
- [Learning with Group Invariant Features: A Kernel Perspective](https://mlsanity.com/paper/1506.02544/) (2015)
- [Local Group Invariant Representations via Orbit Embeddings](https://mlsanity.com/paper/1612.01988/) (2016)
- [Unsupervised Learning of Invariant Representations in Hierarchical Architectures](https://mlsanity.com/paper/1311.4158/) (2013)

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

- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [A Theory of PAC Learnability under Transformation Invariances](https://mlsanity.com/paper/2202.07552/) (2022)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Dimensionless machine learning: Imposing exact units equivariance](https://mlsanity.com/paper/2204.00887/) (2022)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Machine learning and invariant theory](https://mlsanity.com/paper/2209.14991/) (2022)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Partial Domain Adaptation without Domain Alignment](https://mlsanity.com/paper/2108.12867/) (2021)
- [Towards fully covariant machine learning](https://mlsanity.com/paper/2301.13724/) (2023)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (2024)
- [Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry](https://mlsanity.com/paper/2512.11855/) (2025)
- [Koopman-Equivariant Gaussian Processes](https://mlsanity.com/paper/2502.06645/) (2025)
- [Learning with Exact Invariances in Polynomial Time](https://mlsanity.com/paper/2502.19758/) (2025)
- [Non-parametric Hypothesis Tests for Distributional Group Symmetry](https://mlsanity.com/paper/2307.15834/) (2023)
- [Tensor learning with orthogonal, Lorentz, and symplectic symmetries](https://mlsanity.com/paper/2406.01552/) (2024)
- [Efficient Learning and Symmetry Discovery under Exact Invariances](https://mlsanity.com/paper/2609.07031/) (2026)
- [Testing for Geometric Invariance and Equivariance](https://mlsanity.com/paper/2205.15280/) (2022)
- [A tradeoff between universality of equivariant models and learnability of symmetries](https://mlsanity.com/paper/2210.09444/) (2022)
- [Optimal Symmetries in Binary Classification](https://mlsanity.com/paper/2408.08823/) (2024)
- [Statistical Learning Guarantees for Group-Invariant Barron Functions](https://mlsanity.com/paper/2509.23474/) (2025)
- [Returning The Favour: When Regression Benefits From Probabilistic Causal Knowledge](https://mlsanity.com/paper/2301.11214/) (2023)
- [Approximating invariant functions with the sorting trick is theoretically justified](https://mlsanity.com/paper/2403.01671/) (2024)
- [Generalization Bounds for Equivariant Networks on Markov Data](https://mlsanity.com/paper/2503.00292/) (2025)
- [Implicit Bias and Invariance: How Hopfield Networks Efficiently Learn Graph Orbits](https://mlsanity.com/paper/2512.14338/) (2025)
- [The geometry of invariant learning: an information-theoretic analysis of data augmentation and generalization](https://mlsanity.com/paper/2602.14423/) (2026)
- [When and How to Canonize: A Generalization Perspective](https://mlsanity.com/paper/2605.11008/) (2026)
- [Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization](https://mlsanity.com/paper/2605.20074/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

It is a commonly held belief that enforcing invariance improves generalisation. Although this approach enjoys widespread popularity, it is only very recently that a rigorous theoretical demonstration of this benefit has been established. In this work we build on the function space perspective of Elesedy and Zaidi arXiv:2102.10333 to derive a strictly non-zero generalisation benefit of incorporating invariance in kernel ridge regression when the target is invariant to the action of a compact group. We study invariance enforced by feature averaging and find that generalisation is governed by a notion of effective dimension that arises from the interplay between the kernel and the group. In building towards this result, we find that the action of the group induces an orthogonal decomposition of both the reproducing kernel Hilbert space and its kernel, which may be of interest in its own right.