Efficient Learning and Symmetry Discovery under Exact Invariances
Abstract Overview
This paper studies supervised regression under exact group invariances and addresses whether invariant estimators can be computed efficiently when the symmetry group is finite, infinite, or unknown. By extending the spectral-averaging framework with a randomized subset selection procedure, the authors establish a polynomial-time algorithm that enforces exact invariance with runtime independent of group cardinality. The theoretical guarantees cover both finite-dimensional feature spaces and Sobolev regression on manifolds, where invariance constraints are formulated via linear representations. The authors also investigate symmetry discovery, proposing an efficient method to identify an unknown bounded-index subgroup of a known finite reference group from data and learn an exactly invariant estimator.
Novelty
The paper provides the first polynomial-time algorithm for learning with exact group invariances that applies uniformly to finite and infinite groups, eliminating runtime dependence on group size via randomized subset selection. Additionally, it introduces a provable symmetry-discovery algorithm based on random Cayley graph expansion and held-out validation to recover unknown bounded-index subgroups from data.
Results
For known groups, the proposed method computes an exactly invariant estimator in polynomial time, achieving excess risk of O(n^{-s/(s+d/2)}) in Sobolev spaces and minimax-optimal risk of O(dim(H^G)/n) in finite-dimensional feature spaces. For unknown bounded-index subgroups in finite reference groups, the algorithm discovers a generating set of size O(log|H|) and returns an exactly invariant estimator in poly(n, d, 1/kappa, log|G|, log(1/delta)) time, matching the finite-dimensional known-symmetry sample complexity.
Key Points
- Randomized subset selection adaptively identifies a small set of group elements whose linear constraints fully capture the invariant subspace, avoiding dependence on group cardinality.
- The learning framework integrates spectral coefficient estimation with constrained quadratic programming to guarantee exact invariance across both finite-dimensional and Sobolev regression regimes.
- For unknown symmetries in finite groups, random group sampling combined with empirical risk comparisons on held-out data reliably recovers a generating set for bounded-index subgroups.