# Learning with Exact Invariances in Polynomial Time

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

## 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 (most cited first, 26 of 26)

- [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)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [E(3)-Equivariant Graph Neural Networks for Data-Efficient and Accurate Interatomic Potentials](https://mlsanity.com/paper/2101.03164/) (2021)
- [A Survey of Convolutional Neural Networks: Analysis, Applications, and Prospects](https://mlsanity.com/paper/2004.02806/) (2020)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Equivariant Flows: Exact Likelihood Generative Learning for Symmetric Densities](https://mlsanity.com/paper/2006.02425/) (2020)
- [Frame Averaging for Invariant and Equivariant Network Design](https://mlsanity.com/paper/2110.03336/) (2021)
- [Equivariance Through Parameter-Sharing](https://mlsanity.com/paper/1702.08389/) (2017)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)
- [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)
- [SE(3)-equivariant prediction of molecular wavefunctions and electronic densities](https://mlsanity.com/paper/2106.02347/) (2021)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Low Dimensional Invariant Embeddings for Universal Geometric Learning](https://mlsanity.com/paper/2205.02956/) (2022)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Scalable Normalizing Flows for Permutation Invariant Densities](https://mlsanity.com/paper/2010.03242/) (2020)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Sample Complexity of Probability Divergences under Group Symmetry](https://mlsanity.com/paper/2302.01915/) (2023)
- [On the hardness of learning under symmetries](https://mlsanity.com/paper/2401.01869/) (2024)
- [Sample Complexity Bounds for Estimating Probability Divergences under Invariances](https://mlsanity.com/paper/2311.02868/) (2023)
- [On the Complexity of Learning with Kernels](https://mlsanity.com/paper/1411.1158/) (2014)

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

- [Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetry](https://mlsanity.com/paper/2512.11855/) (2025)
- [Data Augmentation: A Fourier Analysis Perspective](https://mlsanity.com/paper/2606.24418/) (2026)
- [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)
- [Sparse Data Augmentation for Optimization with Provable Guarantees](https://mlsanity.com/paper/2609.08133/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## 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.