Sample Complexity Gain from Invariances: Kernel Regression, Wasserstein Distance, and Density Estimation

In practice, encoding group invariances into models improves sample complexity. In this talk, we study this phenomenon from a theoretical perspective. In the first part, we provide minimax optimal rates for kernel ridge regression on compact manifolds, with a target function that is invariant to a Lie group action on the manifold. 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.

In the second part, we apply our techniques to group-invariant probability distributions that appear in many data-generative models in machine learning, such as graphs, point clouds, and images, and we prove tight sample complexity bounds for the Wasserstein distance estimation under invariances, as well as the density estimation problem.

This talk is based on joint work with Stefanie Jegelka.