提出新方法加速计算概率分布间Wasserstein距离，显著提升效率。
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
- 用网格压缩样本数据，保持误差不变且结构更规则
- 在d=2时达到ε⁻²最优时间复杂度，d=3时近乎最优
- 适合需要高效估算分布差异的研究者
平方Wasserstein距离是衡量概率分布差异的常用工具，通常在大小为n的样本经验测度间计算。然而，即使在低维欧氏空间（d∈{2,3}）中，现有算法在计算精度和运行时间上仍表现不佳。为此，本文引入计算-统计运行时间概念，目标是在采样误差期望下以ε-加性误差估计真实分布间的W₂²(P,Q)，并允许每次采样成本为O(1)。我们提出“样本-草图-求解”范式，采用规则笛卡尔网格对样本进行草图化。结果显示，在α-霍尔德光滑分布条件下，该方法可压缩数据而不增加渐近误差，并使结构更规整，从而支持更快的精确算法。最终，对于(0,1)ᵈ上满足0<α<1霍尔德光滑性的分布P,Q，可在ε⁻⁽²,⁽ᵈ⁺¹⁺ₒ⁽¹⁾⁾⁄⁽¹⁺ᵃ⁾⁾时间内实现ε误差逼近；当d=2且α>1/2时达到最优Θ(ε⁻²)，当d=3且α→1时接近最优。
原文摘要 · Abstract (English)
Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size $n$ from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems $\left( d \in \{2,3\} \right)$, algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of $n$ and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to $ε$-additive error in expectation with respect to the sampling; we allow $O(1)$ computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under $α$-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate $W_2^2(P,Q)$ within $ε$ error in $ε^{-\max(2,\frac{d+1+o(1)}{1+α})}$ time for $0 < α< 1$ Hölder smooth distributions $P,Q$ on $(0,1)^{d}$; an optimal $Θ(ε^{-2})$ for $α> 1/2$ when $d=2$ and nearly optimal as $α\to 1$ when $d = 3$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。