Title: Optimality of empirical measures as quantizers Show Chinese title

Title: 经验测度作为量化器的最优性

Abstract: A common way to discretize a probability measure is to use an empirical measure as a discrete approximation. But how far from being optimal is this approximation in the p-Wasserstein distance? In this paper, we study this question in two contexts: (1) optimality among all uniform quantizers and (2) optimality among all (non-uniform) quantizers. In the first context, for p=1, we provide a complete answer to this question up to a polylog(n) factor. From the probabilistic point of view, this resolves, up to a polylog(n) factor, the problem of characterizing the expected 1-Wasserstein distance between a probability measure and its empirical measure in terms of non-random quantities. We also obtain some partial results for p>1 in the first context and for p>=1 in the second context. Show Chinese abstract

Abstract: 将概率测度离散化的一种常见方法是使用经验测度作为离散近似。 但这种近似在p-Wasserstein距离上偏离最优有多远？ 在本文中，我们在两种情况下研究了这个问题：(1) 所有均匀量化器中的最优性，以及(2) 所有（非均匀）量化器中的最优性。 在第一种情况下，对于p=1，我们给出了该问题的完整答案，最多相差一个polylog(n)因子。 从概率的角度来看，这解决了以非随机量表示的概率测度与其经验测度之间的期望1-Wasserstein距离的表征问题，最多相差一个polylog(n)因子。 我们还在第一种情况下获得了p>1的一些部分结果，并在第二种情况下获得了p>=1的一些部分结果。