Entropic optimal transport rates improve with discrete measures
Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime
Machine Learning
Summary
This work looks at how quickly statistical estimates improve when one dataset is discrete (like a fixed list of points) and the other follows a well-behaved spread called subGaussian. The authors show that in this setting, estimation improves much faster than when both datasets are general subGaussian distributions. This means some data arrangements allow simpler and more accurate calculations. They also apply this understanding to improve a certain algorithm (Sinkhorn-EM) used for clustering data mixtures, proving it works efficiently in some cases.
What this means in practice
- •For data scientists: Improve clustering algorithms for mixture models by using Sinkhorn-EM with provable faster convergence.
- •For machine learning engineers: Use faster and more accurate entropic transport estimations when one data source is finite and the other is subGaussian distributed to enhance model training.
Tested on simulated data.
Authors
Tomas Gonzalez, Gonzalo Mena
Abstract
We study statistical rates in entropic optimal transport in the semi-discrete regime where one measure has finite support and the other is subGaussian. Our main result establishes parametric convergence rates for the empirical dual potentials to their population counterparts, with no dimension dependence in the leading term. Our result relies on tailored strong concavity analysis of the semi-dual objective, coupled with specialized bounds for the semi-discrete potentials. As a consequence, we obtain fast rates for downstream quantities derived from the optimal coupling. Chiefly, the empirical barycentric projection achieves a squared-error rate $n^{-1}$, matching the fully compact case and improving over the less favorable $n^{-1/2}$ rate known for fully subGaussian settings. Altogether, these results may indicate a lower complexity adaptation phenomenon whereby the statistical complexity of the barycentric projection is governed by the discrete measure. As an application, we analyze Sinkhorn-EM, an EM-type algorithm in which the E-step is replaced by an entropic optimal transport problem. In a well-specified and balanced two-component Gaussian mixture model, we prove $\sqrt{n}$-consistency of the empirical iterates to their population counterparts for any fixed number of iterations, matching classical EM rates up to a $\sqrt{\log n}$ factor. Simulations support the theory.