mlsanityData to 14 Oct 2026

Learning with Exact Invariances in Polynomial Time

arXiv 2502.19758 ↗First posted 27 Feb 2025cs.LG cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with exact invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (not approximate) invariances in this context. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 26 of its 55 references that are in the map. First posted on arXiv 27 Feb 2025.

Builds on

26 of 55 references.

References · 26

  1. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  2. 2017PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Spacecited by 4,401
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  5. 2021E(3)-Equivariant Graph Neural Networks for Data-Efficient and Accurate Interatomic Potentialscited by 708
  6. 2020A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospectscited by 397
  7. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 270
  8. 2020Equivariant Flows: Exact Likelihood Generative Learning for Symmetric Densitiescited by 250
  9. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 168
  10. 2017Equivariance Through Parameter-Sharingcited by 141
  11. 2022Equivariance with Learned Canonicalization Functionscited by 109
  12. 2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 91
14 more
  1. 2021Learning with invariances in random features and kernel modelscited by 89
  2. 2021SE(3)-equivariant prediction of molecular wavefunctions and electronic densitiescited by 67
  3. 2023Approximation-Generalization Trade-offs under (Approximate) Group Equivariancecited by 46
  4. 2024Equivariant Frames and the Impossibility of Continuous Canonicalizationcited by 43
  5. 2022Low Dimensional Invariant Embeddings for Universal Geometric Learningcited by 38
  6. 2021Provably Strict Generalisation Benefit for Invariance in Kernel Methodscited by 30
  7. 2023The Exact Sample Complexity Gain from Invariances for Kernel Regressioncited by 28
  8. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 27
  9. 2020Scalable Normalizing Flows for Permutation Invariant Densitiescited by 22
  10. 2022A PAC-Bayesian Generalization Bound for Equivariant Networkscited by 18
  11. 2023Sample Complexity of Probability Divergences under Group Symmetrycited by 14
  12. 2024On the hardness of learning under symmetriescited by 13
  13. 2023Sample Complexity Bounds for Estimating Probability Divergences under Invariancescited by 12
  14. 2014On the Complexity of Learning with Kernelscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 5.

6 papers.

  1. 2025Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetrycited by 7
  2. 2026Data Augmentation: A Fourier Analysis Perspectivecited by 4
  3. 2026Adaptive Symmetry Discovery for Dynamical System Identificationcited by 3
  4. 2026Efficient Learning and Symmetry Discovery under Exact Invariancescited by 3
  5. 2026Sparse Data Augmentation for Optimization with Provable Guaranteescited by 1
  6. 2026Dimension-Free Scaling Laws for Size Generalization: An Exponential Separationcited by 0