Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
Authors: Peter Matthew Jacobs, Jeff M. Phillips
Summary
arXiv:2605. 20122v1 Announce Type: new Abstract: Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions.
Relevance
Read next because Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation overlaps with clean result "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)", clean result "Only continuous soft prefixes hit both EM axes at once on Qwen-2.5-7B-Instruct: discrete prompt searches split between the alignment objective and the distributional objective, and both discretizations of the soft prefix collapse (MODERATE confidence)", experiment "Add C2 control arm (donor sees marker_B without marker_A) to disambiguate paired-marker binding from marker_B leaking alone". Matching terms: under, alpha, without. Source: arxiv stat.ML (Machine Learning).
Abstract
arXiv:2605.20122v1 Announce Type: new Abstract: 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 $\epsilon$-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 $\alpha$-H"older 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 $\epsilon$ error in $\epsilon^{-\max(2,\frac{d+1+o(1)}{1+\alpha})}$ time for $0 1/2$ when $d=2$ and nearly optimal as $\alpha \to 1$ when $d = 3$.