GMOS Weekly Seminar - Empirical Optimal Transport with Smooth Costs

We revisit the question of quantifying the expected convergence rate of empirical estimators of optimal transport costs. It is well known that i.i.d. samples from an absolutely continuous distribution on R^d converge to that distribution at the rate n^{-1/d}, which implies by the triangle inequality that a plug-in estimator of the p-Wasserstein distance between two measures achieves this same rate. Surprisingly, we show that if the two measures are not the same, then this rate is typically loose—instead of n^{-1/d}, convergence occurs at the rate n^{-2/d} for all p >= 2. We also prove minimax lower bounds, showing that the n^{-2/d} rate is optimal up to logarithmic factors. We derive these results as corollaries of more general theorems on the convergence of empirical optimal transport with smooth convex costs, for which we prove new regularity results of independent interest. Based on joint work with T. Manole.