Sublinear Algorithms for Estimating Wasserstein and TV Distances: Applications to Fairness and Privacy Auditing
Debabrota Basu [email protected] · 2025
Read Sublinear Algorithms for Estimating Wasserstein and TV Distances: Applications to Fairness and Privacy Auditing by Debabrota Basu [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-07775.txt.
Description
Basu and Chanda built streaming algorithms that estimate distances between probability distributions in twenty twenty-five. Comparing distributions underlies fairness and privacy auditing, but data often arrive as streams from many sources, and storing everything is impossible. Their framework learns a distribution's shape functions from samples on the fly.
The trick reduces the problem to counting how often samples land in a cleverly chosen slice of a discretized distribution. From those counts they build mergeable summaries needing far less space than the number of samples seen. Wasserstein and total variation distances between any two distributions can then be estimated from the summaries. Results match known lower bounds for bounded cases. Experiments on synthetic and real data confirmed the efficiency gains.
Catalog record
| CREATOR | Debabrota Basu [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-07775