# The Exact Sample Complexity Gain from Invariances for Kernel Regression

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 72 references that are in the map.
- First posted on arXiv 24 Mar 2023.

## Builds on (most cited first, 30 of 42)

- [PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation](https://mlsanity.com/paper/1612.00593/) (2016)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [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)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds](https://mlsanity.com/paper/1802.08219/) (2018)
- [Equivariant message passing for the prediction of tensorial properties and molecular spectra](https://mlsanity.com/paper/2102.03150/) (2021)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Cormorant: Covariant Molecular Neural Networks](https://mlsanity.com/paper/1906.04015/) (2019)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Universal approximations of invariant maps by neural networks](https://mlsanity.com/paper/1804.10306/) (2018)
- [Scalars are universal: Equivariant machine learning, structured like classical physics](https://mlsanity.com/paper/2106.06610/) (2021)
- [Incorporating Symmetry into Deep Dynamics Models for Improved Generalization](https://mlsanity.com/paper/2002.03061/) (2020)
- [On Learning Sets of Symmetric Elements](https://mlsanity.com/paper/2002.08599/) (2020)
- [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 Universality of Rotation Equivariant Point Cloud Networks](https://mlsanity.com/paper/2010.02449/) (2020)
- [On the Benefits of Invariance in Neural Networks](https://mlsanity.com/paper/2005.00178/) (2020)
- [Enhanced Convolutional Neural Tangent Kernels](https://mlsanity.com/paper/1911.00809/) (2019)
- [Geometric Deep Learning and Equivariant Neural Networks](https://mlsanity.com/paper/2105.13926/) (2021)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Universal Equivariant Multilayer Perceptrons](https://mlsanity.com/paper/2002.02912/) (2020)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spaces](https://mlsanity.com/paper/1910.06552/) (2019)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)

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

- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [Symmetry Discovery Beyond Affine Transformations](https://mlsanity.com/paper/2406.03619/) (2024)
- [Neural Scaling Laws Rooted in the Data Distribution](https://mlsanity.com/paper/2412.07942/) (2024)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Towards Understanding Inductive Bias in Transformers: A View From Infinity](https://mlsanity.com/paper/2402.05173/) (2024)
- [Sample Complexity Bounds for Estimating Probability Divergences under Invariances](https://mlsanity.com/paper/2311.02868/) (2023)
- [Baking Symmetry into GFlowNets](https://mlsanity.com/paper/2406.05426/) (2024)
- [GradMetaNet: An Equivariant Architecture for Learning on Gradients](https://mlsanity.com/paper/2507.01649/) (2025)
- [Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry](https://mlsanity.com/paper/2512.11855/) (2025)
- [Learning with Exact Invariances in Polynomial Time](https://mlsanity.com/paper/2502.19758/) (2025)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Approximately Piecewise E(3) Equivariant Point Networks](https://mlsanity.com/paper/2402.08529/) (2024)
- [Data Augmentation: A Fourier Analysis Perspective](https://mlsanity.com/paper/2606.24418/) (2026)
- [Equivariant geometric convolutions for emulation of dynamical systems](https://mlsanity.com/paper/2305.12585/) (2023)
- [Tensor learning with orthogonal, Lorentz, and symplectic symmetries](https://mlsanity.com/paper/2406.01552/) (2024)
- [Demystifying Spectral Bias on Real-World Data](https://mlsanity.com/paper/2406.02663/) (2024)
- [Understanding Learning Invariance in Deep Linear Networks](https://mlsanity.com/paper/2506.13714/) (2025)
- [Adaptive Symmetry Discovery for Dynamical System Identification](https://mlsanity.com/paper/2608.08091/) (2026)
- [Efficient Learning and Symmetry Discovery under Exact Invariances](https://mlsanity.com/paper/2609.07031/) (2026)
- [Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoning](https://mlsanity.com/paper/2506.21797/) (2025)
- [Sparse Data Augmentation for Optimization with Provable Guarantees](https://mlsanity.com/paper/2609.08133/) (2026)
- [Reinforcement Learning Using known Invariances](https://mlsanity.com/paper/2511.03473/) (2025)
- [Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization](https://mlsanity.com/paper/2605.20074/) (2026)
- [Representation Gap: Explaining the Unreasonable Effectiveness of Neural Networks from a Geometric Perspective](https://mlsanity.com/paper/2605.21692/) (2026)
- [Group Invariant Spectral Embedding](https://mlsanity.com/paper/2607.08987/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

In practice, encoding invariances into models improves sample complexity. In this work, we study this phenomenon from a theoretical perspective. In particular, we provide minimax optimal rates for kernel ridge regression on compact manifolds, with a target function that is invariant to a group action on the manifold. Our results hold for any smooth compact Lie group action, even groups of positive dimension. For a finite group, the gain effectively multiplies the number of samples by the group size. For groups of positive dimension, the gain is observed by a reduction in the manifold's dimension, in addition to a factor proportional to the volume of the quotient space. Our proof takes the viewpoint of differential geometry, in contrast to the more common strategy of using invariant polynomials. This new geometric viewpoint on learning with invariances may be of independent interest.