Efficient Learning and Symmetry Discovery under Exact Invariances

• URL: http://arxiv.org/abs/2609.07031v1
• Date: Mon, 07 Sep 2026 04:35:19 GMT
• Title: Efficient Learning and Symmetry Discovery under Exact Invariances
• Abstract summary: Learning with group invariances is central to many scientific and geometric learning problems.<n>It has been unclear whether one can efficiently compute a regression function that is exactly in subgroup to a given group action.<n>We present the first-time algorithm for learning with exact group invariants that applies uniformly to finite and infinite groups.
• Score: 62.27019402162741
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Data Augmentation: A Fourier Analysis Perspective [52.00584777952869]
  We show that partial data augmentation can achieve the same statistical benefits as full augmentation in terms of generalization and sample complexity.<n>Our results provide a theoretical explanation for why partial augmentation can retain the statistical benefits of full augmentation despite enforcing symmetry only approximately.
  arXiv  Detail & Related papers  (2026-06-23T10:54:14Z)
• Learning with Exact Invariances in Polynomial Time [43.81087760363805]
  We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression.<n>Our approach achieves the same excess population risk as the original kernel regression problem.
  arXiv  Detail & Related papers  (2025-02-27T04:49:52Z)
• Invariant Kernels: Rank Stabilization and Generalization Across Dimensions [7.154556482351604]
  We show that symmetry has a pronounced impact on the rank of kernel matrices.<n>Specifically, we compute the rank of a kernel of fixed degree that is invariant under various groups acting independently on its two arguments.<n>In concrete circumstances, including the three aforementioned examples, symmetry dramatically decreases the rank making it independent of the data dimension.
  arXiv  Detail & Related papers  (2025-02-03T23:37:43Z)
• Accelerated Discovery of Machine-Learned Symmetries: Deriving the Exceptional Lie Groups G2, F4 and E6 [55.41644538483948]
  This letter introduces two improved algorithms that significantly speed up the discovery of symmetry transformations. Given the significant complexity of the exceptional Lie groups, our results demonstrate that this machine-learning method for discovering symmetries is completely general and can be applied to a wide variety of labeled datasets.
  arXiv  Detail & Related papers  (2023-07-10T20:25:44Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• On the Sample Complexity of Learning with Geometric Stability [42.813141600050166]
  We study the sample complexity of learning problems where the target function presents such invariance and stability properties. We provide non-parametric rates of convergence for kernel methods, and improvements in sample complexity by a factor equal to the size of the group.
  arXiv  Detail & Related papers  (2021-06-14T03:51:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.