From Finite to Infinite Groups: A Polynomial-Time Algorithm for Learning with Exact Invariances

Despite its broad range of applications in science, the theoretical foundations of learning with invariances have been only sparsely explored. Even in the case of polynomial regression, it has remained unclear whether one can efficiently compute an \emph{exactly invariant} regression function, as traditional methods such as data augmentation, group averaging, and canonicalization fail to provably solve the task in polynomial time. Recent work (Soleymani et al.) has examined the statistical–computational trade-off of learning with invariances, demonstrating that for finite groups there exists a polynomial-time algorithm (in the data dimension, sample size, and logarithm of the group size) that yields functions which both generalize well and are exactly invariant. However, this approach is intrinsically limited to finite groups, leaving the tractability for learning with \emph{infinite groups} unresolved. In this paper, we design and analyze a polynomial-time algorithm that applies to any group, including infinite ones, and learns functions that generalize well in polynomial time with respect to data dimension and sample size, independent of the group. This closes the gap and provides strong theoretical evidence that computationally efficient algorithms for learning under invariances can indeed generalize effectively, a phenomenon consistently supported by the empirical success of geometric machine learning.