Research map / Learning theory and algorithms / Optimal transport

Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants

ICML 2025 · Learning theory and algorithms › Optimal transport · approach: Sliced Wasserstein variants

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives an O(log n)-relative approximation for the p-Wasserstein distance (p≥2, metric costs) in near-quadratic time via multiple HST tree distances and a dynamic bichromatic-closest-pair primal-dual algorithm, and an O(n^2/δ^3) additive approximation for the noise-robust (p,k)-RPW distance, with a hardness reduction for additive approximation of plain p-Wasserstein.

Problem

Computing p-Wasserstein distance (p≥2) between discrete distributions is slow (no near-quadratic relative approximation for general metrics) and sensitive to noise, making additive approximation costly (~n^2/δ^p).

Approach

Replace a single HST tree metric with the minimum over p independent HST embeddings so the tree distance is an O(log n)-approximation in expectation for the p-th power cost, then solve exactly on this tree distance with a primal-dual Hungarian method accelerated by a dynamic weighted bichromatic closest pair structure; for the robust (p,k)-RPW distance, adapt the LMR scaling algorithm to get an ad

Key results

• The tree-based primal-dual algorithm runs in O(n^2 log U log Δ log n) time and gives an O(log n) approximation to the p-Wasserstein distance (Theorem 1.1).
• The (p,k)-RPW additive approximation runs in O(n^2/δ^3) time independent of p (Theorem 1.2), versus n^2/δ^p-type bounds for plain p-Wasserstein.
• Empirically, approximation ratios grow slightly with n but do not change with p, and data structure operations grow sub-n^1.5 in practice.

Measured effects reported in the paper

Surprising findings

• Plain p-Wasserstein additive approximation in o(n^2/δ^p) time would yield a sub-n^2.5 algorithm for perfect bipartite matching, suggesting a barrier.
• Tree distance distortion increases exponentially with p while the resulting approximation factor does not change with p in experiments.

Limitations

• Relative approximation is O(log n) rather than constant, and the guarantee holds in expectation over the random HST constructions.
• Experiments are limited to synthetic 10-dimensional uniform and truncated normal data.
• Additive approximation guarantee is for the (p,k)-RPW distance, not for the plain p-Wasserstein distance, which remains hard.

Experimental setup

Benchmarks: synthetic uniform 10-d hypercube point sets synthetic truncated normal 10-d point sets

Metrics: approximation ratio data structure operation counts average tree distance distortion

Baselines: Hungarian algorithm (Orlin 1988) Raghvendra et al. 2024 (p,k)-RPW algorithm Sharathkumar and Agarwal cost-scaling BCP algorithm

Builds on: Charikar 2002 tree-embedding approximation Fakcharoenphol et al. 2003 HST LMR algorithm (Lahn et al. 2019) Hungarian algorithm Raghvendra et al. 2024 (p,k)-RPW distance

Closest papers by meaning

• A Higher Precision Algorithm for Computing the $1$-Wasserstein Distance (ICLR 2023 · similarity 0.91)
• A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions (ICML 2024 · similarity 0.90)
• Tree-Sliced Variants of Wasserstein Distances (NeurIPS 2019 · similarity 0.89)
• Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances (NeurIPS 2022 · similarity 0.89)
• Asymptotics of smoothed Wasserstein distances in the small noise regime (NeurIPS 2022 · similarity 0.89)
• A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem (NeurIPS 2024 · similarity 0.87)