Learning with Exact Invariances in Polynomial Time

We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with \emph{exact} invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (as opposed to approximate) invariances in this setting, partially addressing a question posed by Diaz (2025) regarding the avoidance of prohibitively large and computationally intensive group averaging methods in kernel regression with exact invariances. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.

We study how to efficiently learn models that are exactly invariant to symmetries in the data—such as rotations or permutations—using kernel methods. Common strategies like data augmentation or group averaging can be computationally expensive or hard to apply in kernel settings. In contrast, we propose a polynomial-time algorithm that enforces exact invariance, assuming access to some geometric structure of the input space. Our method matches the generalization performance of standard kernel regression, while guaranteeing exact symmetry. To our knowledge, this is the first such efficient approach in this setting, addressing a question recently raised in the literature. Our solution is built on a novel optimization reformulation that may also be of independent interest.