mlsanityData to 7 Oct 2026

The Exact Sample Complexity Gain from Invariances for Kernel Regression

arXiv 2303.14269 ↗First posted 24 Mar 2023cs.LGcited by 27

Not on the map. Why?

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.

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

Builds on

42 of 72 references.

References · 42

  1. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,223
  2. 2017PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Spacecited by 4,384
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2017Deep Setscited by 1,394
  6. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2018Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point cloudscited by 735
  9. 2021Equivariant message passing for the prediction of tensorial properties and molecular spectracited by 438
  10. 2018Invariant and Equivariant Graph Networkscited by 339
  11. 2019Cormorant: Covariant Molecular Neural Networkscited by 262
  12. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
30 more
  1. 2019On the Universality of Invariant Networkscited by 151
  2. 2021Hyperbolic Deep Neural Networks: A Surveycited by 138
  3. 2018Universal approximations of invariant maps by neural networkscited by 127
  4. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
  5. 2020Incorporating Symmetry into Deep Dynamics Models for Improved Generalizationcited by 123
  6. 2020On Learning Sets of Symmetric Elementscited by 97
  7. 2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 90
  8. 2021Learning with invariances in random features and kernel modelscited by 89
  9. 2020On the Universality of Rotation Equivariant Point Cloud Networkscited by 80
  10. 2020On the Benefits of Invariance in Neural Networkscited by 78
  11. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  12. 2021Geometric Deep Learning and Equivariant Neural Networkscited by 64
  13. 2022Optimally tackling covariate shift in RKHS-based nonparametric regressioncited by 53
  14. 2020Universal Equivariant Multilayer Perceptronscited by 49
  15. 2016Generalization Error of Invariant Classifierscited by 42
  16. 2019Improved Generalization Bounds of Group Invariant / Equivariant Deep Networks via Quotient Feature Spacescited by 34
  17. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  18. 2019Universal approximations of permutation invariant/equivariant functions by deep neural networkscited by 29
  19. 2021Provably Strict Generalisation Benefit for Invariance in Kernel Methodscited by 29
  20. 2020Permutationless Many-Jet Event Reconstruction with Symmetry Preserving Attention Networkscited by 22
  21. 2021Understanding the Generalization Benefit of Model Invariance from a Data Perspectivecited by 22
  22. 2018How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?cited by 19
  23. 2021Implicit Bias of Linear Equivariant Networkscited by 18
  24. 2019Gaussians on Riemannian Manifolds: Applications for Robot Learning and Adaptive Controlcited by 17
  25. 2020A Functional Perspective on Learning Symmetric Functions with Neural Networkscited by 16
  26. 2015Learning with Group Invariant Features: A Kernel Perspectivecited by 13
  27. 2021HamNet: Conformation-Guided Molecular Representation with Hamiltonian Neural Networkscited by 13
  28. 2020Sample complexity and effective dimension for regression on manifoldscited by 8
  29. 2018Localized Structured Predictioncited by 5
  30. 2021Symmetry-adapted graph neural networks for constructing molecular dynamics force fieldscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 10; 2025: 7; 2026: 7.

27 papers.

Sort:

By area:

  1. 2023Approximation-Generalization Trade-offs under (Approximate) Group Equivariancecited by 45
  2. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 25
  3. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  4. 2024Symmetry Discovery Beyond Affine Transformationscited by 14
  5. 2024Neural Scaling Laws Rooted in the Data Distributioncited by 14
  6. 2024On the hardness of learning under symmetriescited by 13
  7. 2024Towards Understanding Inductive Bias in Transformers: A View From Infinitycited by 13
  8. 2023Sample Complexity Bounds for Estimating Probability Divergences under Invariancescited by 11
  9. 2024Baking Symmetry into GFlowNetscited by 7
  10. 2025GradMetaNet: An Equivariant Architecture for Learning on Gradientscited by 7
  11. 2025Beyond Statistical Learning: Exact Learning Is Essential for General Intelligencecited by 6
  12. 2025Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetrycited by 6
15 more
  1. 2025Learning with Exact Invariances in Polynomial Timecited by 5
  2. 2024Approximately Piecewise E(3) Equivariant Point Networkscited by 4
  3. 2023Equivariant geometric convolutions for emulation of dynamical systemscited by 3
  4. 2024Tensor learning with orthogonal, Lorentz, and symplectic symmetriescited by 3
  5. 2024Demystifying Spectral Bias on Real-World Datacited by 3
  6. 2025Understanding Learning Invariance in Deep Linear Networkscited by 3
  7. 2026Data Augmentation: A Fourier Analysis Perspectivecited by 3
  8. 2026Adaptive Symmetry Discovery for Dynamical System Identificationcited by 2
  9. 2026Efficient Learning and Symmetry Discovery under Exact Invariancescited by 2
  10. 2025Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoningcited by 1
  11. 2025Reinforcement Learning Using known Invariancescited by 0
  12. 2026Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimizationcited by 0
  13. 2026Representation Gap: Explaining the Unreasonable Effectiveness of Neural Networks from a Geometric Perspectivecited by 0
  14. 2026Group Invariant Spectral Embeddingcited by 0
  15. 2026Sparse Data Augmentation for Optimization with Provable Guaranteescited by 0