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

May 19, 2026

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

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

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

Ask PDF

May 11, 2026

Differentially Private Sampling from Distributions via Wasserstein Projection

In this paper, we study the problem of sampling from a distribution under the constraint of differential privacy (DP). Prior works measure the utility of DP sampling with density ratio-based measures such as KL divergence. However, such formulations suffer from two key limitations: 1) they fail to capture the geometric structure of the support, and 2) they are not applicable when the supports of the distributions differ. To deal with these issues, we develop a novel framework for DP sampling with Wasserstein distance as the utility measure. In this formulation, we propose Wasserstein Projection Mechanism (WPM), a minimax optimal mechanism based on Wasserstein projection. Furthermore, we develop efficient algorithms for computing the proposed mechanisms approximately and provide convergence guarantees.

Shokichi Takakura, Seng Pei Liew, Satoshi Hasegawa

LY Corporation

Differential Privacy

Ask PDF

Jun 29, 2026

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

The Sliced Wasserstein (SW) distance has emerged as a computationally attractive alternative to the Wasserstein distance by leveraging one-dimensional optimal transport along random projections. Standard estimators of the SW distance rely on Monte Carlo averages of one-dimensional Wasserstein distances computed via quantile functions, which require sorting projected samples and access to full datasets. In this work, we introduce a new class of estimators for the Sliced Wasserstein distance based on cumulative distribution functions (CDFs) of projected measures, that avoid sorting and scale via massive dataset parallelism. This class includes several estimators, some of them being indexed by hyperparameters controlling their variance or smoothness. We show that they are especially well suited to scenarios in which CDFs are more tractable than quantile functions, such as mixtures of Gaussians, and moreover that they are also naturally compatible with federated learning, since CDFs of projected data can be computed and aggregated locally without requiring the exchange of raw samples.

Christophe Vauthier, Quentin Mérigot, Anna Korba

Laboratoire de Mathématiques d’Orsay, Université Paris-Saclay Gif-sur-Yvette, France · Centre de recherche en économie et statistique, ENSAE Palaiseau, France

Sliced Wasserstein Distance Optimal Transport Wasserstein Distance

Ask PDF

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