Computing distances between probability distributions from samples is a recurring task in statistics, machine learning, and data analysis. The new preprint, "Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing," focuses on doing this resource-efficiently. The authors describe algorithms that estimate two common distances—Wasserstein and total variation—using only sample access, in sublinear time.
The motivation is practical. In fairness auditing, one often compares distributions of outcomes across groups; in privacy auditing, one compares the behavior of algorithms with and without particular records. Both rely on distance measures that are expensive to compute exactly on large datasets. The paper positions its sublinear algorithms as a way to make these audits more feasible.
Because the abstract is truncated, the specific algorithmic techniques and guarantees are not detailed here. The stated contribution is the combination of sublinear estimation with applications to fairness and privacy, which could lower the barrier to routine auditing of large-scale systems.