Sample Complexity Bounds for Estimating Probability Divergences under Invariances

Estimating the optimal transportation distance [50, 51, 40] between probability measures is a fundamental problem in statistics, with many applications in machine learning, from Generative Adversarial Networks (GANs) [22, 2, 39, 31] to domain adaptation and generalization [18, 14, 13], geometric data processing (e.g., Wasserstein barycenters [15] and intrinsic dimension estimation [7]), biomedical research [53], and control and dynamical systems [9]. Estimating the Wasserstein distance is known to be a difficult task in general, and it suffers from the curse of dimensionality [49]. The slow convergence rate is generally unimprovable, as there exist probability measures that are difficult to estimate. However, those hard instances barely appear in practice when we study more structured probability measures. Indeed, in many applications (e.g., graphs, point clouds, molecules, spectral data), the underlying probability measures are invariant with respect to a group action on the input space. As observed in recent works [6, 12], considering the group invariances in the mathematical model can help improve the convergence rate of the Wasserstein distance and the Sobolev Integral Probability Metrics (Sobolev IPMs), with applications, e.g., to generative models for invariant data.