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

CREATORDebabrota Basu [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-07775

Browse the full library · About the Tower of Babel