# On the Sample Complexity of Learning under Invariance and Geometric Stability

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 14 Jun 2021.

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

- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [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)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Deep vs. shallow networks : An approximation theory perspective](https://mlsanity.com/paper/1608.03287/) (2016)
- [Inductive Bias of Deep Convolutional Networks through Pooling Geometry](https://mlsanity.com/paper/1605.06743/) (2016)
- [Convolutional Kernel Networks](https://mlsanity.com/paper/1406.3332/) (2014)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [Computational Separation Between Convolutional and Fully-Connected Networks](https://mlsanity.com/paper/2010.01369/) (2020)
- [How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?](https://mlsanity.com/paper/1805.07883/) (2018)
- [Relative stability toward diffeomorphisms indicates performance in deep nets](https://mlsanity.com/paper/2105.02468/) (2021)
- [Localized Structured Prediction](https://mlsanity.com/paper/1806.02402/) (2018)

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

- [The SSL Interplay: Augmentations, Inductive Bias, and Generalization](https://mlsanity.com/paper/2302.02774/) (2023)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Towards Understanding Inductive Bias in Transformers: A View From Infinity](https://mlsanity.com/paper/2402.05173/) (2024)
- [Morphological Symmetries in Robotics](https://mlsanity.com/paper/2402.15552/) (2024)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (2024)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Demystifying Spectral Bias on Real-World Data](https://mlsanity.com/paper/2406.02663/) (2024)
- [Randomized Dimension Reduction with Statistical Guarantees](https://mlsanity.com/paper/2310.01739/) (2023)
- [Approximating invariant functions with the sorting trick is theoretically justified](https://mlsanity.com/paper/2403.01671/) (2024)
- [Reinforcement Learning Using known Invariances](https://mlsanity.com/paper/2511.03473/) (2025)
- [Diffeomorphism-Equivariant Neural Networks](https://mlsanity.com/paper/2602.06695/) (2026)
- [Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimization](https://mlsanity.com/paper/2605.20074/) (2026)
- [Representation Redundancy and Structural Complexity in Finite-Field Inversion](https://mlsanity.com/paper/2609.04583/) (2026)

## Abstract (arXiv)

Many supervised learning problems involve high-dimensional data such as images, text, or graphs. In order to make efficient use of data, it is often useful to leverage certain geometric priors in the problem at hand, such as invariance to translations, permutation subgroups, or stability to small deformations. We study the sample complexity of learning problems where the target function presents such invariance and stability properties, by considering spherical harmonic decompositions of such functions on the sphere. We provide non-parametric rates of convergence for kernel methods, and show improvements in sample complexity by a factor equal to the size of the group when using an invariant kernel over the group, compared to the corresponding non-invariant kernel. These improvements are valid when the sample size is large enough, with an asymptotic behavior that depends on spectral properties of the group. Finally, these gains are extended beyond invariance groups to also cover geometric stability to small deformations, modeled here as subsets (not necessarily subgroups) of permutations.