Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing

Debabrota Basu; Debarshi Chanda

cs.LGMar 10, 2025

Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing

Authors: Debabrota Basu, Debarshi Chanda

Organizations: Équipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRIStAL F-59000 Lille, France · Indian Statistical Institute Kolkata, India

Abstract

Resource-efficiently computing representations of probability distributions and the distances between them while only having access to the samples is a fundamental and useful problem across mathematical sciences. In this paper, we propose a generic framework to learn the probability and cumulative distribution functions (PDFs and CDFs) of a sub-Weibull, i.e. almost any light- or heavy-tailed, distribution while the samples from it arrive in a stream. The idea is to reduce these problems into estimating the frequency of an appropriately chosen subset of the support of a properly discretised distribution. We leverage this reduction to compute mergeable summaries of distributions from the stream of samples while requiring only sublinear space relative to the number of observed samples. This allows us to estimate Wasserstein and Total Variation (TV) distances between any two distributions while samples arrive in streams and from multiple sources. Our algorithms significantly improves on the existing methods for distance estimation incurring super-linear time and linear space complexities, and further extend the mergeable summaries framework to continuous distributions with possibly infinite support. Our results are tight with respect to the existing lower bounds for bounded discrete distributions. In addition, we leverage our proposed estimators of Wasserstein and TV distances to tightly audit the fairness and privacy of algorithms. We empirically demonstrate the efficiency of proposed algorithms across synthetic and real-world datasets.

Figures & tables

Panel of Figure 1 — Figure 1: Evolution of summaries constructed using $10^{5}$ samples from $\mathcal{N}(0,5)$ . We set $b=0.05$ and bucket numbers $100,300,500,700$ .

Tail Condition	$\tau_{n}\left({\varepsilon,\delta}\right)$	$\tau_{k}\left({\varepsilon,b}\right)$
$\sigma_{\mu}$ -sub-Gaussian	$\frac{c}{\varepsilon}\log\left({\frac{1}{\delta}}\right)$	$\left\lceil\frac{8\sigma_{\mu}}{b}\sqrt{\log{\left({\frac{4}{\varepsilon}}\right)}}\right\rceil$
$\alpha$ -sub-Weibull	$\frac{c}{\varepsilon}\log\left({\frac{1}{\delta}}\right)$	$\left\lceil\frac{c}{2b}\left({\log\left({\frac{4}{\varepsilon}}\right)}\right)^{\alpha}\right\rceil$

Table 2

Tail Condition	$\tau_{n}\left({\ell_{\mu},\varepsilon,\delta}\right)$	$\tau_{k}\left({\ell_{\mu},\varepsilon}\right)$
$\sigma_{\mu}$ -sub-Gaussian	$\log\left({1/\delta}\right)\max\left\{{\frac{1}{\varepsilon},\frac{1}{\ell_{\mu}^{2}},\ell_{\mu}^{2}}\right\}$	$\frac{\sigma_{\mu}}{\varepsilon}\log\left({\frac{\ell_{\mu}}{\varepsilon}}\right)$
$\alpha$ -sub-Weibull	$\log\left({1/\delta}\right)\max\left\{{\frac{1}{\varepsilon},\frac{1}{\ell_{\mu}^{2}},\ell_{\mu}^{2}}\right\}$	$\frac{1}{\varepsilon}\left({\log\left({\frac{\ell_{\mu}}{\varepsilon}}\right)}\right)^{\alpha}$

Table 3

Tail Condition	$\tau_{n}\left({\ell_{\mu},\varepsilon,\delta}\right)$	$\tau_{k}\left({\ell_{\mu},\varepsilon}\right)$
$\sigma$ -sub-Gaussian	${\log\left({1/\delta}\right)\max\left\{{\frac{1}{\varepsilon^{2}},\frac{1}{\ell^{2}},\ell^{2}}\right\}}$	${\frac{\sigma}{\varepsilon}\log\left({\frac{\ell}{\varepsilon}}\right)}$
$\alpha$ -sub-Weibull	${\log\left({1/\delta}\right)\max\left\{{\frac{1}{\varepsilon^{2}},\left({\log\frac{1}{\delta}}\right)^{2\alpha-1},\frac{1}{\ell^{2}},\ell^{2}}\right\}}$	${\frac{1}{\varepsilon}\left({\log\left({\frac{\ell}{\varepsilon}}\right)}\right)^{\alpha}}$

Table 4

Tail Condition	$\sigma_{\mu}$ -sub-Gaussian	$\alpha$ -sub-Weibull
$\tau_{b}\left({\varepsilon,\ell_{\mu}}\right)$	$\frac{\varepsilon}{\sigma_{\mu}\ell_{\mu}\sqrt{\log\left({2/\varepsilon}\right)}}$	$\frac{\varepsilon}{\ell_{\mu}\left({\log\left({2c_{\alpha}/\varepsilon}\right)}\right)^{\alpha}}$

Table 5

Tail Condition	$\sigma_{\mu}$ -sub-Gaussian	$\alpha$ -sub-Weibull
$\tau_{n}\left({\varepsilon,b,\delta}\right)$	$c\varepsilon^{-2}\max\left\{{\frac{4\sigma_{\mu}\sqrt{\pi}}{b},\log\left({1/\delta}\right)}\right\}$	$c\varepsilon^{-2}\max\left\{{\frac{2c_{\alpha}}{b}\Gamma(1+\alpha),\log\left({1/\delta}\right)}\right\}$

Table 6

Tail Condition	$\tau_{n}\left({\varepsilon,\delta}\right)$	$\tau_{k}\left({\varepsilon,b}\right)$
$\sigma_{\mu}$ -sub-Gaussian	$\frac{c}{\varepsilon}\log\left({\frac{1}{\delta}}\right)$	$\left\lceil\frac{8\sigma_{\mu}}{b}\sqrt{\log{\left({\frac{6}{\varepsilon}}\right)}}\right\rceil$
$\alpha$ -sub-Weibull	$\frac{c}{\varepsilon}\log\left({\frac{1}{\delta}}\right)$	$\left\lceil\frac{c}{b}\left({\log\left({\frac{6}{\varepsilon}}\right)}\right)^{\alpha}\right\rceil$

Table 7

Tail Condition	$\tau_{n}\left({\varepsilon,\ell,\delta}\right)$	$\tau_{k}\left({\varepsilon,\ell}\right)$	$\tau_{b}\left({\varepsilon,\ell}\right)$
$\sigma$ -sub-Gaussian	${\varepsilon^{-2}\max\left\{{\frac{\sigma^{2}\ell\log\left({1/\varepsilon}\right)}{\varepsilon},\log\left({\frac{1}{\delta}}\right)}\right\}}$	$\frac{\sigma^{2}\ell}{\varepsilon}\log\left({\frac{1}{\varepsilon}}\right)$	$\frac{\varepsilon}{\sigma\ell\sqrt{\log\left({2/\varepsilon}\right)}}$
$\alpha$ -sub-Weibull	${\varepsilon^{-2}\max\left\{{\frac{\ell\left({\log\left({1/\varepsilon}\right)}\right)^{\alpha}}{\varepsilon}\Gamma(1+\alpha),\log\left({\frac{1}{\delta}}\right)}\right\}}$	$\frac{\ell}{\varepsilon}\left({\log\left({\frac{1}{\varepsilon}}\right)}\right)^{2\alpha}$	$\frac{\varepsilon}{\ell\left({\log\left({2c_{\alpha}/\varepsilon}\right)}\right)^{\alpha}}$

Table 8

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

TV Distance Computation

See all 8 papers

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized Sketching Approximation Algorithms
Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101
Differentially Private Sampling from Distributions via Wasserstein Projection
May 11, 2026Shokichi Takakura, Seng Pei Liew, Satoshi HasegawaDifferential Privacy
LY Corporation
Highly Data Parallelizable Estimation of the Sliced-Wasserstein Distance Using Cumulative Distribution Functions
Jun 29, 2026Christophe Vauthier, Quentin Mérigot, Anna KorbaSliced Wasserstein Distance Optimal Transport
Laboratoire de Mathématiques d’Orsay, Université Paris-Saclay Gif-sur-Yvette, France · Centre de recherche en économie et statistique, ENSAE Palaiseau, France

May 19, 2026J/K move · Enter open · S save

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Peter Matthew Jacobs, Jeff M. Phillips

Department of Statistics University of Wisconsin-Madison Madison, WI 53706 · Kahlert School of Computing University of Utah Salt Lake City, UT 84101

Randomized Sketching Approximation Algorithms Optimal Transport Wasserstein Distance

Open paper AskPDF 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 \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

(0,1)^{d}

; an optimal

Θ(ε^{-2})

for

α> 1/2

when

d=2

and nearly optimal as

α\to 1

when

d = 3

Abstract

TV Distance Computation

Explore similar work

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Differentially Private Sampling from Distributions via Wasserstein Projection

Highly Data Parallelizable Estimation of the Sliced-Wasserstein Distance Using Cumulative Distribution Functions