Source-linked AI summary
Efficient Learning and Symmetry Discovery under Exact Invariances
Ashkan Soleymani, Behrooz Tahmasebi, Patrick Jaillet, Stefanie Jegelka
TL;DR
The paper asks whether exact invariant regression can be computed efficiently for infinite or unknown symmetry groups. It answers by combining randomized group-element sampling with invariant learning and symmetry discovery, obtaining polynomial-time guarantees and statistically optimal finite-dimensional regression under bounded-index assumptions.
Problem
Prior work left open efficient exact-invariant learning for infinite groups and learning when the symmetry group is unknown.
Method
The paper samples a small subset of group elements and uses randomized projection and hypothesis-testing procedures, supported by random Cayley graph expansion.
Results
The algorithms run in polynomial time independent of group size for finite and infinite known groups, while finite-group symmetry discovery recovers the underlying symmetry and matches known-symmetry minimax sample complexity.
Takeaways & Limitations
The results provide computational and statistical guarantees for exact invariant learning and discovering unknown symmetries.
Takeaways & Limitations
The symmetry-discovery guarantee is limited to finite groups under a bounded-index assumption and does not directly extend to infinite groups.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses the computational cost of exact invariant learning and unknown-symmetry discovery. It develops polynomial-time methods that work beyond finite known groups and recover finite-group symmetries from data.
- Exact invariance remains computationally insufficiently understood despite its empirical benefits for learning and generalization.
- Brute-force augmentation and group averaging can become infeasible for large groups, while canonicalization and frame averaging may introduce discontinuities or require group-specific designs.
- The paper proposes a polynomial-time exact-invariance algorithm whose runtime is polynomial in n and d and independent of group size, for both finite and infinite groups.
- The algorithm uses randomized, data-independent preprocessing to select a small group subset, after which the procedure is deterministic and provides excess population-risk guarantees.
- For symmetry discovery, the paper studies an unknown subgroup H of a known finite group G under a bounded-index assumption and seeks both a generating set and an exactly H-invariant regressor.
- The discovery algorithm identifies the underlying symmetry in polynomial time, recovers a generating set of size O(log |H|), and matches the known-symmetry minimax-optimal sample complexity in finite-dimensional regression.
- Random Cayley graphs and expander theory support the sampling-based symmetry-recovery procedure and control its runtime and success probability.
2 Related Work
Related work spans invariant architectures, kernel and post-hoc invariantization methods, and data-driven symmetry discovery. The paper positions its contribution as a general exact-invariant procedure rather than a group-family-specific architecture.
- Invariant learning appears across GNNs, CNNs, PointNet, and generative models, using permutation, translation, or other modality-specific symmetries.
- The paper frames its method as post-hoc invariantization: regression-coefficient estimates are projected onto fixed-point subspaces determined by sampled group elements.
- Prior finite-group work used generating sets of size at most log |G|, whereas this paper develops randomized subset selection for broader group settings.
- Existing symmetry-discovery research includes deep-learning, Lie-algebraic, finite-group, latent-representation, augmentation, and heuristic approaches.
3 Problem Statement
The problem is supervised regression on compact geometric domains with group actions, where estimators must be accurate and exactly invariant. The formulation also covers unknown finite subgroups and separates statistical learning from the computational problem of sampling group elements.
- The setting uses a smooth, compact, boundaryless Riemannian manifold M and independent labeled samples for supervised regression.
- The group acts smoothly and isometrically on M, and the target function is required to respect the relevant invariance.
- Finite-dimensional ERM and Sobolev KRR provide minimax-optimal baseline risk rates, but standard procedures do not generally return invariant estimators.
- Naive group averaging requires O(|G|) operations even to evaluate an estimator, making it intractable for large or infinite groups.
- The paper assumes a compact effective group and oracle access to independent Haar-uniform samples, while noting that uniform sampling can itself be computationally nontrivial.
- For symmetry discovery, the true invariance group is an unknown subgroup H of a known finite G, and brute-force subgroup search is infeasible because the subgroup lattice can be combinatorially large.
- The discovery analysis restricts H to bounded-index subgroups, with κ controlling the size of the candidate search space.
4 Main Results
The paper develops a randomized subset-selection method that enforces exact invariance in polynomial time, independently of group cardinality, and extends these guarantees to symmetry discovery for finite groups. It combines exact invariance with minimax-optimal finite-dimensional rates while identifying scope limits for Sobolev and infinite-group settings.
- Known symmetries: A randomized subset-selection procedure identifies sufficient group constraints for spectral-averaging quadratic programs and applies to finite and infinite groups.The procedure adaptively samples group elements and updates the constraint intersection when a sampled constraint is informative.
- Known symmetries: The selected subset has size and runtime independent of |G|, so the approach remains applicable when G is infinite.This contrasts with generating-set methods whose complexity depends polylogarithmically on finite-group cardinality.
- Known symmetries: The resulting estimator runs in poly(n, d, log(1/δ)) time, is exactly G-invariant, and achieves excess risk O(dim(HG)/n) in finite-dimensional settings.This rate is minimax optimal over the class of G-invariant functions in H.
- Sobolev rates: In Sobolev settings, the procedure attains the corresponding no-invariance convergence rate without requiring full group averaging.The paper does not claim this rate is the sharp invariant minimax rate; sharper invariant rates require group-adapted regularization and potentially expensive full averaging.
- Symmetry discovery: For symmetry discovery over finite groups, Algorithm 3 returns an exactly H-invariant estimator and a generating set for H in polynomial time.The finite-dimensional guarantee achieves the minimax-optimal rate over H-invariant functions.
- Symmetry discovery: The symmetry-discovery guarantee is restricted to finite groups because it relies on random Cayley graph constructions and other finite-group tools.Extension to compact Lie groups is left for future work and would require different techniques.
5 Conclusion
The paper establishes randomized polynomial-time learning with exact invariances for both finite and infinite groups, and efficient symmetry discovery when the group is unknown. Together, these results provide statistical–computational guarantees for invariant learning and symmetry discovery.
- 5 Conclusion: Randomized subset selection enforces exact invariance for finite and infinite groups in polynomial time without dependence on group cardinality.A fully deterministic polynomial-time procedure for infinite groups remains open.
- 5 Conclusion: Under a bounded-index assumption, sampling grounded in random Cayley graph theory identifies unknown symmetry groups efficiently from data.Combining discovery with invariant learning yields computationally efficient and statistically optimal estimators.
- 5 Conclusion: The results provide rigorous statistical–computational guarantees for learning exact invariances and discovering unknown symmetries.The paper presents these guarantees as a theoretical foundation for the empirical success of symmetry-aware learning methods.
A Preliminaries on Groups and Manifolds
The preliminaries establish a smooth geometric setting in which compact groups act faithfully and isometrically on compact manifolds and induce structured actions on finite-dimensional feature spaces. These assumptions reduce invariance to fixed-point subspaces and compatible linear representations.
- Manifolds: The data domain is a smooth, compact, boundaryless manifold, with the presentation assumption extendable to other sufficiently regular domains.The restriction avoids technicalities involving boundaries, noncompactness, and singularities.
- Group actions: A group action on a manifold is smooth when each transformation is a smooth diffeomorphism, with joint smoothness required for Lie-group actions.The action satisfies identity and composition laws, and the effective action is assumed faithful after quotienting its kernel.
- Compact groups: Compactness provides normalized Haar measure, while quotienting the action kernel leaves a compact effective transformation group acting on the data domain.The geometric setting treats the group as a compact subgroup of the manifold's isometry group.
- Representations: A representation realizes each group element as an invertible linear operator preserving the group law, and orthogonal or unitary representations preserve the inner product.Restricting the function action to a finite-dimensional feature space produces matrices D(g) satisfying D(gh)=D(g)D(h).
- Invariant geometry: Averaging the metric over a compact group yields a smooth G-invariant metric, making every group transformation an isometry and preserving the associated volume measure.This makes the isometric-action assumption nonrestrictive for compact group actions.
- Spectral and feature spaces: Because the action is isometric, it is unitary on L2(M) and commutes with the Laplace–Beltrami operator, so each eigenspace carries an orthogonal representation.Finite-dimensional invariant feature spaces therefore reduce invariance to intersections of fixed-point subspaces.
B.1 Proof of Proposition 4.1
The proof shows that randomized sampling detects every remaining discrepancy between invariance under a subset of group elements and full-group invariance. With sufficiently many trials, the resulting subset exactly captures the invariant subspace while remaining small.
- Dimension-ratio argument: An isotropic distribution on the current span makes the quadratic-form expectation equal to a dimension ratio involving the full-group projection.Orthogonality of the representation preserves norms and permits averaging the representation or its transpose.
- Discrepancy detection: The statistic A(S) measures the expected deviation of sampled representation actions from the identity on vectors supported by the current candidate subspace.If A(S)=0, the candidate span is already fixed by the full group and the subset intersections coincide.
- Dimension decrease: When A(S)>0, its lower bound follows from a strict dimension gap between the candidate and full invariant subspaces.The smallest possible positive dimension difference is one, establishing the claimed quantitative bound.
- Probabilistic argument: Each fresh random trial detects a remaining discrepancy with probability at least 2/r, and successful detections reduce the candidate dimension by one.A Chernoff bound controls the number of trials needed to obtain all required detections.
- Termination: With T trials, the procedure terminates with probability at least 1−δ after T=O(r2+r log(1/δ)) iterations.At most r successful detections are needed because the dimension can decrease no more than r times.
- Conclusion: With probability at least 1−δ, the selected subset defines exactly the true invariant subspace and uses at most r group elements.This completes the proof of the randomized subset-selection guarantee.
B.2 Proof of Theorem 4.2
The theorem proof combines spectral decomposition, randomized subset selection, constrained quadratic programs, and bias–variance analysis. It yields an exactly invariant estimator with the finite-group risk rate and runtime polynomial in sample size and dimension, independent of group cardinality.
- Spectral reduction: The Laplace–Beltrami eigenspace decomposition reduces invariant regression to independent quadratic programs with fixed-point constraints in each retained eigenspace.Empirical coefficient means are projected onto the corresponding fixed-point subspaces.
- Randomized constraints: A single block-diagonal representation and randomized subset selection provide sufficient constraints simultaneously across all retained eigenspaces.The subset has size at most r and succeeds with probability at least 1−δ after Θ(r2+r log(1/δ)) iterations.
- Exact invariance: Projection onto the subset-defined fixed-point spaces equals projection onto the G-invariant spaces, so the estimator is exactly G-invariant with probability at least 1−δ.The equality holds blockwise for every retained eigenspace.
- Risk bound: The risk analysis decomposes error into spectral bias and estimation variance, with projection reducing squared error in each eigenspace.Choosing D=n1/(1+α) yields the same excess-risk rate as in the finite-group setting.
- Running time: The algorithm runs in time polynomial in n, d, and log(1/δ), independent of the cardinality of G.The subset size is polynomially bounded because D=n1/(1+α)≤n1/2.
B.3 Proof of Theorem 4.4
The proof shows that Algorithm 3 recovers the unknown symmetry group by sampling candidate elements, distinguishing true symmetries from nonsymmetries through population-risk separation, and resolving that separation empirically.
- Generating H: Algorithm 3 succeeds once its sampled set contains a generating set for the true symmetry group H.The final estimator is then exactly H-invariant, with statistical guarantees following from invariant regression results.
- Generating H: Random sampling from G contains a generating set for H with high probability because each draw lands in H with probability at least κ.Random Cayley graph results provide the generating-set bound within H, while concentration transfers it to sampling from G.
- Testing candidates: The algorithm accepts sampled g ∈ H and rejects g ∉ H by comparing empirical risks of unconstrained and g-invariant estimators.These comparisons control both false rejection of true symmetries and false acceptance of nonsymmetries.
- Testing candidates: Under maximality of H, invariance under g ∈ H has zero population bias, whereas g ∉ H has strictly positive bias.The corresponding constrained subspace equals W for true symmetries and is a strict subspace for nonsymmetries.
- Uniform separation: With high probability, all tested elements simultaneously satisfy bg = 0 for g ∈ H and bg ≥ γ for g ∈ Gtest \ H.When T = poly(d) and dH ≤ r = poly(d), the separation is inverse-polynomial in d.
- Uniform separation: A polynomial-size independent validation sample estimates all candidate risks within o(γ), so threshold η = γ/4 correctly separates symmetries from nonsymmetries.The required validation size is polynomial in r, 1/γ, and log(T/δ).