mlsanityData to 7 Oct 2026

On the Sample Complexity of Learning under Invariance and Geometric Stability

arXiv 2106.07148 ↗First posted 14 Jun 2021stat.ML cs.LGcited by 13

Not on the map. Why?

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.

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

Builds on

17 of 32 references.

References · 17

  1. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  2. 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
  3. 2017Sobolev Norm Learning Rates for Regularized Least-Squares Algorithmcited by 113
  4. 2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 90
  5. 2021Learning with invariances in random features and kernel modelscited by 89
  6. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  7. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  8. 2016Deep vs. shallow networks : An approximation theory perspectivecited by 63
  9. 2016Inductive Bias of Deep Convolutional Networks through Pooling Geometrycited by 53
  10. 2014Convolutional Kernel Networkscited by 47
  11. 2016Generalization Error of Invariant Classifierscited by 42
  12. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
5 more
  1. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  2. 2018How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?cited by 19
  3. 2020Computational Separation Between Convolutional and Fully-Connected Networkscited by 19
  4. 2021Relative stability toward diffeomorphisms indicates performance in deep netscited by 12
  5. 2018Localized Structured Predictioncited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 5; 2025: 2; 2026: 3.

13 papers.

Sort:

By area:

  1. 2023The SSL Interplay: Augmentations, Inductive Bias, and Generalizationcited by 40
  2. 2023Approximately Equivariant Graph Networkscited by 16
  3. 2024Towards Understanding Inductive Bias in Transformers: A View From Infinitycited by 13
  4. 2024Morphological Symmetries in Roboticscited by 9
  5. 2024How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Modelcited by 7
  6. 2025Beyond Statistical Learning: Exact Learning Is Essential for General Intelligencecited by 6
  7. 2024Demystifying Spectral Bias on Real-World Datacited by 3
  8. 2023Randomized Dimension Reduction with Statistical Guaranteescited by 0
  9. 2024Approximating invariant functions with the sorting trick is theoretically justifiedcited by 0
  10. 2025Reinforcement Learning Using known Invariancescited by 0
  11. 2026Diffeomorphism-Equivariant Neural Networkscited by 0
  12. 2026Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimizationcited by 0
1 more
  1. 2026Representation Redundancy and Structural Complexity in Finite-Field Inversioncited by 0