# Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

arXiv: https://arxiv.org/abs/2605.20122 · HTML: https://mlsanity.com/paper/2605.20122/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 19 May 2026.

## Builds on (most cited first, 10 of 10)

- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests](https://mlsanity.com/paper/1509.02237/) (2015)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms](https://mlsanity.com/paper/1901.06482/) (2019)
- [Statistical optimal transport](https://mlsanity.com/paper/2407.18163/) (2024)
- [Nonparametric Density Estimation under Adversarial Losses](https://mlsanity.com/paper/1805.08836/) (2018)
- [A Graph Theoretic Additive Approximation of Optimal Transport](https://mlsanity.com/paper/1905.11830/) (2019)
- [Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs](https://mlsanity.com/paper/1805.07416/) (2018)
- [A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow](https://mlsanity.com/paper/2309.16629/) (2023)

## Abstract (arXiv)

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 ∈ 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"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 W22(P,Q) within ε error in ε^-max(2,fracd+1+o(1)1+α) time for 0 < α < 1 H"older smooth distributions P,Q on (0,1)d; an optimal Theta(ε-2) for α > 1/2 when d=2 and nearly optimal as α → 1 when d = 3.