Sample complexity of optimal transport barycenters with discrete support

Computational implementation of optimal transport barycenters for a set of target probability measures requires a form of approximation, a widespread solution being empirical approximation of measures. We provide an O(√N/n) statistical generalization bounds for the empirical sparse optimal transport barycenters problem, where N is the maximum cardinality of the barycenter (sparse support) and n is the sample size of the target measures empirical approximation. Our analysis includes various optimal transport divergences including Wasserstein, Sinkhorn and Sliced-Wasserstein. We discuss the application of our result to specific settings including K-means, constrained K-means, free and fixed support Wasserstein barycenters.