Sharp convergence rates for empirical optimal transport with smooth costs
Sharp convergence rates for empirical optimal transport with smooth costs
复制标题
具有平滑成本的经验最优传输的急剧收敛率
DOI：
10.1214/23-aap1986
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Jonathan Niles
中科院分区：
文献类型：
--
作者：
Tudor Manole;Jonathan Niles
我们重新审视的问题，表征的最佳运输成本的插件估计的收敛速度。众所周知，一个由来自$\mathbb{R}^d$上的绝对连续分布的独立样本组成的经验测度以Wasserstein距离中的速率$n^{-1/d}$收敛到该分布，这可以用来证明许多最优运输成本的插入式估计量以相同的速率收敛。然而，我们表明，当成本是平滑的，这种分析是松散的：插件估计的基础上的经验措施二次收敛速度更快，在率$n^{-2/d}$。作为一个推论，我们表明，两个分布之间的Wasserstein距离是很容易估计时，措施是分开的。我们还证明了下界，不仅表明我们的插件估计的分析是紧密的，但也没有其他估计可以享受明显更快的收敛速度均匀对所有措施。我们的证明依赖于经验过程理论参数的基础上严格控制的L^2 $覆盖数的局部Lipschitz和半凹函数。作为一个副产品，我们的证据，我们得到$L^\infty$估计的位移引起的最佳耦合之间的任何两个措施，满足适当的浓度和反浓度条件，广泛的成本函数。
We revisit the question of characterizing the convergence rate of plug-in estimators of optimal transport costs. It is well known that an empirical measure comprising independent samples from an absolutely continuous distribution on $\mathbb{R}^d$ converges to that distribution at the rate $n^{-1/d}$ in Wasserstein distance, which can be used to prove that plug-in estimators of many optimal transport costs converge at this same rate. However, we show that when the cost is smooth, this analysis is loose: plug-in estimators based on empirical measures converge quadratically faster, at the rate $n^{-2/d}$. As a corollary, we show that the Wasserstein distance between two distributions is significantly easier to estimate when the measures are well-separated. We also prove lower bounds, showing not only that our analysis of the plug-in estimator is tight, but also that no other estimator can enjoy significantly faster rates of convergence uniformly over all pairs of measures. Our proofs rely on empirical process theory arguments based on tight control of $L^2$ covering numbers for locally Lipschitz and semi-concave functions. As a byproduct of our proofs, we derive $L^\infty$ estimates on the displacement induced by the optimal coupling between any two measures satisfying suitable concentration and anticoncentration conditions, for a wide range of cost functions.
平滑最优传输图的极小极大估计
DOI：
10.1214/20-aos1997
发表时间：
2021
期刊：
The Annals of Statistics
影响因子：
--
作者：
Hütter, Jan-Christian;Rigollet, Philippe
通讯作者：
Rigollet, Philippe