CS Paper Radar

Efficient Learning and Symmetry Discovery under Exact Invariances

Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka

cs.LG stat.ML ·submitted 2026-09-07 04:35 UTC · v1
top venuehighly cited

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.

Comment
29 pages. Published at COLT 2026
Journal ref
Conference on Learning Theory (COLT) 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Operators for Symmetry Discovery: From Lie Groups to Local Symmetry Geometry

cs.LG ·2026-10-12 ·Pavan Karjol, Scindhiya Laxmi, Prathosh AP
theory similarity 0.74
Abstract

Continuous symmetry discovery is typically formulated as a separate estimation problem for each function or dataset. We instead investigate whether the map from a function to its symmetry structure can be learned across a family of functions from finite observations. Using the infinitesimal differential characterization of continuous symmetries, we formulate this map as an inverse symmetry operator, analogous to an inverse PDE problem. For global Lie-group symmetries, we establish a representation-theoretic population characterization: the symmetry Lie algebra is the nullspace of a positive-semidefinite operator constructed from representation coefficients and the infinitesimal group action. We also show that the inverse symmetry operator is equivariant under coordinate changes through the adjoint action. This characterization separates the geometric symmetry map from finite-sample estimation, motivating a hybrid approach that amortizes statistically difficult components while retaining analytic structure. On SO(5) benchmarks, amortized equivariant estimation of harmonic coefficients improves symmetry recovery from sparse observations, whereas ordinary least squares suffices for SL(2,R). We extend this viewpoint to local symmetries, where symmetry directions form smoothly varying tangent distributions rather than a fixed Lie algebra. Under the Lie-bracket consistency condition, Frobenius' theorem guarantees local integral submanifolds along which observables remain unchanged. We recover this geometry using a hybrid estimator that learns observation weights while preserving analytic differential and geometric recovery. Across global, non-compact, local, and physically motivated synthetic benchmarks, our results support learning the statistically difficult finite-sample components while preserving the known geometric structure of symmetry recovery.

0.13

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

cs.LG math.PRstat.ML ·2026-10-06 ·Jivan Waber, Vanessa Piccolo, Yatin Dandi, Florent Krzakala
theory similarity 0.65
Abstract · 71 pages, 3 figures

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in $\mathbb{R}^d$ and $r=Θ(d^δ)$ teacher directions forming a cyclic symmetry orbit, where $0<δ<1/2$. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent $p\ge3$, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in $\widetildeΘ(d^{p-1})$ samples, whereas the symmetry-agnostic learner requires $\widetildeΘ(rd^{p-1})$. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities $\widetildeΘ(d)$ and $\widetildeΘ(rd)$, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For $p\ge3$, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

0.56

How Do Transformers Learn to Represent Symmetries?

cs.LG ·2026-10-07 ·Eduardo Santos-Escriche, Valerie Engelmayer, Ya-Wei Eileen Lin, Stefanie Jegelka
top venuecode/datahot direction similarity 0.65
Abstract · Accepted at NeurIPS 2026

Training Transformer-based architectures with finite data augmentation has become an increasingly popular approach in geometric machine learning. Despite its empirical success, the interplay between the Transformer architecture, invariance to different symmetries, and augmentation budgets remains underexplored. In this paper, we study the ability of a vanilla Transformer to learn various symmetries through finite data augmentation for point cloud datasets. We identify an ordering of increasing learnability across the following symmetry groups: (i) non-angle-preserving symmetries, (ii) angle-preserving symmetries, and (iii) base angle-preserving subgroups, such as translation, rotation, and scale. For the base angle-preserving groups, we further investigate the Transformer's extrapolation behavior and conduct a structural analysis of the trained models, allowing us to identify interpretable mechanisms that induce invariance. Finally, we extend our analysis to equivariant functions and show that the detected mechanisms for approximate invariance can also provide a key building block for learned equivariance. Our project page is available at https://transformers-learn-symmetries.github.io/

0.55

Sample Complexity of Equivariant Reinforcement Learning

cs.CC cs.LGmath.GR ·2026-09-29 ·Rayan Mazouz, Haibo Zhao, Chris Hillar, Christian Shewmake
similarity 0.62
Abstract

Reinforcement learning (RL) is a powerful framework for robotic control, yet its practical application is often hindered by high sample complexity. This is particularly restrictive in physical domains where interaction data is costly. While the world often exhibits geometric and physical symmetries, standard RL algorithms typically fail to exploit this structure. In this paper, we demonstrate that exploiting group symmetries significantly reduces the sample complexity of RL. Focusing on finite-horizon Markov decision processes, we find that leveraging homomorphisms induced by group symmetries significantly reduces the theoretical upper and lower bounds on the number of environment interactions required to reach an optimal return. We further extend these bounds to continuous state and action spaces, providing corresponding sample-complexity guarantees under appropriate regularity assumptions. Beyond theory, we validate our findings through controlled experiments and demonstrate the advantages of symmetry-aware policy learning on high-dimensional continuous robotic simulations. Our results show that integrating symmetry into the learning pipeline yields substantial gains in sample efficiency and performance, offering a principled path toward more data-efficient robotics.

0.18

Rotational Equivariance in Machine Learning: A Comprehensive Tutorial

cs.LG ·2026-08-31 ·Peter Lippmann, Fred A. Hamprecht
similarity 0.62
Abstract

Rotational symmetry is one of the most important structural principles in machine learning on 3D data. In applications ranging from physics and materials science to 3D computer vision, predictions should not depend on an arbitrary choice of coordinate frame. Rotational equivariance captures this requirement mathematically by enforcing that a rotation of the input induces a corresponding transformation of the model output. This tutorial provides a comprehensive introduction to rotational equivariance, starting from the physical and geometric intuition behind coordinate independence and building up the necessary machinery from geometric deep learning, group theory, and representation theory. We introduce message passing on Euclidean graphs, group actions and representations, spherical harmonics, Wigner matrices, tensor products, and Clebsch-Gordan decomposition, and explain how these ingredients give rise to modern equivariant architectures. We then survey the principal strategies for incorporating rotational equivariance in deep learning, including group convolutions, internal tensorial representations, and canonicalization-based methods, and discuss their practical strengths and limitations. The tutorial aims to lower the barrier to the subject by connecting the underlying mathematics to practical model design, by unifying ideas that are often expressed in different formal languages, and by helping practitioners choose among competing approaches through a clear discussion of their trade-offs.

0.11

Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

cs.LG math.GRstat.ML ·2026-10-13 ·Xiaoyu Li
theory similarity 0.62
Abstract · 55 pages, 5 figures. The abstract has been shortened to meet arXiv's submission requirements

We study learning an unknown element $g$ of a group acting with finite orbits on a countable set, from examples $(x,gx)$. After a sample on $A$, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of $A$, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups $A_5$ and $S_5$ of the quintic they are $2<3$ and $3<4$, and $A_5$ is the smallest group with a gap. For the Galois group $S_n$ of the general equation of degree $n$, they coincide exactly when $n\le 4$, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group $\mathrm{PSL}(2,8)$ has no gap. For linear, orthogonal and unitary maps of $\mathbb R^d$ or $\mathbb C^d$ both dimensions equal $d$, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.

0.25

Equivariant Modeling with Polynomial Features via Minimal Homogeneous Generators

cs.LG stat.ML ·2026-11-18 ·Michael Liaofan Liu, Joe Kileel
similarity 0.60
Abstract

We present a general framework for modeling and learning equivariant functions between finite dimensional semisimple real group representations, unifying constructions developed across many application areas. Our model is a linear combination of equivariant polynomial features whose coefficients are arbitrary learnable functions of invariant polynomial features. We take as features minimal homogeneous generators for the invariant algebra and the covariant module over the invariant algebra, up to prescribed degrees. We provide a Python package that automatically computes these features and fits the resulting models to training data. The algorithm for feature computation requires explicit isotypic decompositions of the input and output representations, along with explicit Clebsch-Gordan decompositions of the tensor product of irreducible representations, and achieves speedups over alternative methods in computational algebra. Numerical experiments in scientific modeling demonstrate the full learning pipeline and yield accurate predictors with few trainable parameters, using the model both for end-to-end prediction and within layers of larger architectures.

0.30

Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers

cs.LG stat.MLmath.ST ·2026-09-25 ·Jaehee Seo, Jisu Kim
top venuetheory similarity 0.60
Abstract · 63 pages, 3 figures. Accepted at NeurIPS 2026

Transformers have become a central architecture for in-context learning (ICL), particularly through their state-of-the-art performance in large language models. This success motivates understanding how transformers exploit intrinsic geometry of real-world data. However, existing nonparametric ICL theory has largely focused on simplified settings, such as Euclidean domains or single manifold models, failing to fully explain its phenomenal empirical success in complex tasks. To address this gap, we study the prediction problem under unknown heterogeneous geometry, modeled by sample size-dependent mixtures of manifolds with heterogeneous dimensions, smoothness, and sampling masses. Under the growing geometric complexity model, we establish a minimax lower bound capturing the aggregate difficulty of the components and construct an oracle tangent local polynomial estimator with a matching upper bound. This estimator is connected to a structure-informed, two-stage softmax transformer with a geometric preconditioner and local polynomial solvers. The transformer achieves negligible approximation error relative to the minimax rate with logarithmic depth and polynomial size. Finally, we derive an in-context generalization bound for near empirical risk minimizers (ERM) over this class. Together, these results identify conditions under which the resulting predictor exploits local geometry and attains minimax rate.

0.58