Learning Probability Measures with respect to Optimal Transport Metrics
This work addresses the challenge of measure estimation in machine learning, providing theoretical insights for unsupervised learning methods, but it appears incremental as it builds on existing algorithms like k-means.
The paper tackles the problem of estimating probability measures using optimal transport metrics, deriving new probabilistic bounds for the k-means algorithm's performance in producing such measures from data. It establishes connections between optimal transport, quantization, and learning theory, resulting in new lower and upper bounds on convergence rates applicable to a broad class of measures.
We study the problem of estimating, in the sense of optimal transport metrics, a measure which is assumed supported on a manifold embedded in a Hilbert space. By establishing a precise connection between optimal transport metrics, optimal quantization, and learning theory, we derive new probabilistic bounds for the performance of a classic algorithm in unsupervised learning (k-means), when used to produce a probability measure derived from the data. In the course of the analysis, we arrive at new lower bounds, as well as probabilistic upper bounds on the convergence rate of the empirical law of large numbers, which, unlike existing bounds, are applicable to a wide class of measures.