# Efficient Learning and Symmetry Discovery under Exact Invariances

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 65 references that are in the map.
- First posted on arXiv 7 Sep 2026.

## Builds on (most cited first, 30 of 46)

- [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)
- [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)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Automatic Symmetry Discovery with Lie Algebra Convolutional Network](https://mlsanity.com/paper/2109.07103/) (2021)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Learning Partial Equivariances from Data](https://mlsanity.com/paper/2110.10211/) (2021)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Generalization Error of Invariant Classifiers](https://mlsanity.com/paper/1610.04574/) (2016)
- [Generative Adversarial Symmetry Discovery](https://mlsanity.com/paper/2302.00236/) (2023)
- [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)
- [Latent Space Symmetry Discovery](https://mlsanity.com/paper/2310.00105/) (2023)
- [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)
- [Learning Layer-wise Equivariances Automatically using Gradients](https://mlsanity.com/paper/2310.06131/) (2023)
- [Scalable Normalizing Flows for Permutation Invariant Densities](https://mlsanity.com/paper/2010.03242/) (2020)
- [A Unified Framework to Enforce, Discover, and Promote Symmetry in Machine Learning](https://mlsanity.com/paper/2311.00212/) (2023)
- [A PAC-Bayesian Generalization Bound for Equivariant Networks](https://mlsanity.com/paper/2210.13150/) (2022)
- [Learning Infinitesimal Generators of Continuous Symmetries from Data](https://mlsanity.com/paper/2410.21853/) (2024)
- [Symmetry-Informed Governing Equation Discovery](https://mlsanity.com/paper/2405.16756/) (2024)
- [Symmetry Discovery Beyond Affine Transformations](https://mlsanity.com/paper/2406.03619/) (2024)
- [Sample Complexity of Probability Divergences under Group Symmetry](https://mlsanity.com/paper/2302.01915/) (2023)

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

- [Sparse Data Augmentation for Optimization with Provable Guarantees](https://mlsanity.com/paper/2609.08133/) (2026)
- [Interpolation Is Not Invariance: Pair Count Is Not Coverage in Transformation Audits](https://mlsanity.com/paper/2609.14870/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

Learning with group invariances is central to many scientific and geometric learning problems, yet its computational foundations remain poorly understood. Even for classical supervised regression settings, it has been unclear whether one can efficiently compute a regression function that is exactly invariant to a given group action. Recent work showed that exact invariance can be enforced in polynomial time when the underlying group is finite and known, but left open the cases of infinite groups and unknown symmetries. In this paper, we resolve both challenges. First, we present the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups. The runtime is polynomial in the data dimension and sample size, and independent of the group, while achieving strong generalization guarantees. This provides a computational explanation for the empirical success of invariant and equivariant methods in geometric machine learning and partially answers a recent open question in the literature. Second, we study learning in the symmetry discovery setting, where the invariance group is unknown. Focusing on the subgroup lattice of a finite group, we show that exact symmetries can be identified from data and exploited for learning in polynomial time. For regression over finite-dimensional feature spaces, our algorithm provably recovers the underlying symmetry, matches the minimax-optimal sample complexity of the known-symmetry setting, and runs in time polynomial in the data dimension and sample size. Our analysis relies on tools from random Cayley graphs and expander theory, which may be of independent interest.