The Exact Sample Complexity Gain from Invariances for Kernel Regression
This work addresses the theoretical understanding of sample complexity gains from invariances for researchers in machine learning, offering foundational insights with broad implications for model design.
The paper tackles the problem of quantifying how encoding invariances into models improves sample complexity in kernel ridge regression on compact manifolds, providing minimax optimal rates that show gains such as multiplying sample count by group size for finite groups or reducing manifold dimension for positive-dimensional groups.
In practice, encoding invariances into models improves sample complexity. In this work, we study this phenomenon from a theoretical perspective. In particular, we provide minimax optimal rates for kernel ridge regression on compact manifolds, with a target function that is invariant to a group action on the manifold. Our results hold for any smooth compact Lie group action, even groups of positive dimension. For a finite group, the gain effectively multiplies the number of samples by the group size. For groups of positive dimension, the gain is observed by a reduction in the manifold's dimension, in addition to a factor proportional to the volume of the quotient space. Our proof takes the viewpoint of differential geometry, in contrast to the more common strategy of using invariant polynomials. This new geometric viewpoint on learning with invariances may be of independent interest.