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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 71 references that are in the map.
- First posted on arXiv 10 Mar 2025.

## Builds on (most cited first, 30 of 31)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Certifying and removing disparate impact](https://mlsanity.com/paper/1412.3756/) (2014)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [Geometric Dataset Distances via Optimal Transport](https://mlsanity.com/paper/2002.02923/) (2020)
- [Wasserstein Fair Classification](https://mlsanity.com/paper/1907.12059/) (2019)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [Optimal Subsampling for Large Sample Logistic Regression](https://mlsanity.com/paper/1702.01166/) (2017)
- [When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits](https://mlsanity.com/paper/2209.02570/) (2022)
- [Active Fairness Auditing](https://mlsanity.com/paper/2206.08450/) (2022)
- [Justicia: A Stochastic SAT Approach to Formally Verify Fairness](https://mlsanity.com/paper/2009.06516/) (2020)
- [Nearly Tight Black-Box Auditing of Differentially Private Machine Learning](https://mlsanity.com/paper/2405.14106/) (2024)
- [Algorithmic Fairness Verification with Graphical Models](https://mlsanity.com/paper/2109.09447/) (2021)
- [Performance Scaling via Optimal Transport: Enabling Data Selection from Partially Revealed Sources](https://mlsanity.com/paper/2307.02460/) (2023)
- [Sharp Concentration Results for Heavy-Tailed Distributions](https://mlsanity.com/paper/2003.13819/) (2020)
- [On Approximating Total Variation Distance](https://mlsanity.com/paper/2206.07209/) (2022)
- [Federated Wasserstein Distance](https://mlsanity.com/paper/2310.01973/) (2023)
- [On Deterministically Approximating Total Variation Distance](https://mlsanity.com/paper/2309.14696/) (2023)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [Auditing Differential Privacy Guarantees Using Density Estimation](https://mlsanity.com/paper/2406.04827/) (2024)
- [Total Variation Distance Meets Probabilistic Inference](https://mlsanity.com/paper/2309.09134/) (2023)
- [Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms](https://mlsanity.com/paper/1802.08513/) (2018)
- [Testing properties of distributions in the streaming model](https://mlsanity.com/paper/2309.03245/) (2023)
- [A High-Performance Algorithm for Identifying Frequent Items in Data Streams](https://mlsanity.com/paper/1705.07001/) (2017)

## Abstract (arXiv)

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.