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

arXiv:2503.07775 · cs.LG, cs.CY, cs.DS, stat.CO · Submitted 2025-03-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Sublinear Algorithms for Wasserstein and Total Variation Distances".

Tom: The gist: The authors propose a generic framework to learn mergeable sublinear summaries of probability distributions from data streams, enabling sublinear time, space,

Jane: First, who's behind it and why it matters.

Title and authors: Tom: This paper, "Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing," focuses on creating tools that can estimate these distribution distances using sublinear space relative to the number of observed samples.

Jane: And they're showing how this framework lets us compute mergeable summaries of distributions from multiple streams, which is a big deal for real-world data coming from different sources.

Lu: The authors are proposing algorithms called SPA and SCA that can approximate the PDF and CDF independently of the stream length.

Meng: This means they are aiming for sublinear space complexity relative to the number of samples, which directly addresses a major bottleneck in current methods.

Lalam: They use this reduction to compute mergeable summaries from the stream, allowing us to estimate Wasserstein and Total Variation distances between any two distributions even when the samples arrive from multiple sources.

The paper's summary: Tom: So, what does their summary of the work actually show us? They are showing that this framework allows for estimating Wasserstein and Total Variation distances between any two distributions while samples arrive in streams and from multiple sources.

Jane: It’s significant because existing methods often require linear space complexity and super-linear time complexity in terms of observed samples to get those Wasserstein distances when you don't know the exact parametric form of the data distribution.

Lu: They specifically use SCA to propose SWA, which PAC-estimates the Wasserstein distance by computing a sublinear summary of a distribution that is O n minus one/two close in Wasserstein distance using Oe, which is square root n, space for n samples <ref:2503.07775#pg3,a sublinear summary of a distribution that is O n>.

Meng: So they claim this SWA operates in the distributed or federated setting with a communication cost of Oe per round while still preserving that estimation guarantee.

Lalam: This sublinear complexity means we can estimate these distances much more efficiently than the previous methods that incurred a communication cost equal to the number of samples in the stream.

The paper's improvements: Tom: The paper points out several improvements they've made over existing literature, focusing on how they tackle those complexity issues we talked about earlier.

Jane: One major improvement is moving away from requiring linear space complexity for estimating the Wasserstein distance between distributions from samples. Instead, they achieve sublinear space complexity using algorithms like SWA which uses Oe, which is square root n, space for n samples while preserving estimation guarantees.

Lu: They also show that they can develop a universal estimator for any bounded-tail distribution; SWA can be used to compute Wp of mu n and mu hat n less than epsilon with probability at least one minus delta <ref:2503.07775#pg3>.

Meng: That means the required sample size is significantly lower than what's needed for exact estimation, which is good for practical applications where data collection is expensive.

Lalam: Another improvement involves using STVA to estimate the Total Variation distance, which they say is equivalent to estimating the HSD between output distributions, allowing for resource-efficient auditing by achieving a sublinear time, space, and communication complexity compared to the number of samples.

Conclusion: Tom: So wrapping things up on this paper about "Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing," it seems the main implication is that we can estimate these critical distribution distances much more efficiently than before.

Jane: It means we can audit fairness and privacy in systems with data streams, even when we don't know the exact mathematical form of the underlying data distribution.

Lu: The authors established a generic framework for learning PDFs and CDFs that is independent of stream length, which opens up possibilities for analyzing complex continuous settings.

Meng: For me, the practical impact is that auditing fairness becomes much more feasible when dealing with real-time streams from many different sources where we can't afford linear space.

Lalam: And Lalam thinks this work is important because it provides a way to compute these distances in sublinear time and space, which should make the auditing process much less resource intensive overall.

Equipe Scool, University of Lille, Inria, CNRS, Centrale Lille · Indian Statistical Institute

cs.LG, cs.CY, cs.DS, stat.CO

Submitted: 2025-03-10

Updated: 2026-10-12

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist: The authors propose a generic framework to learn mergeable sublinear summaries of probability distributions from data streams, enabling sublinear time, space, and communication complexity

Key concepts

Sublinear Summary: This is a compact representation of a probability distribution that requires less than the total number of observed samples to describe. The framework focuses on learning such summaries from data streams, enabling efficient merging and distance estimation even when the total data size is very large.
Wasserstein Distance: This metric measures the minimum 'cost' to transform one probability distribution into another. In practical terms, it calculates the average cost of moving mass from one distribution's points to match another distribution's points, making it useful for comparing distributions in continuous settings.
Total Variation (TV) Distance: TV distance quantifies the maximum difference in probability assigned to any single event between two distributions. It essentially measures the total amount of 'information lost' when approximating one distribution with another, providing a measure of divergence between them.

Terminology

Wasserstein and Total Variation — 2× in this paper

Summary

The gist: The authors propose a generic framework to learn mergeable sublinear summaries of probability distributions from data streams, enabling sublinear time, space, and communication complexity for estimating Wasserstein and Total Variation distances.

How it works

The core idea is to reduce the problem of computing distribution distances into estimating the frequency of an appropriately chosen subset of the support of a properly discretised distribution.
They leverage this reduction to compute mergeable summaries from streams while requiring only sublinear space relative to the number of observed samples.
This framework allows for estimating Wasserstein and Total Variation (TV) distances between any two distributions while samples arrive in streams and from multiple sources.
The proposed estimators significantly improve on existing methods that incur super-linear time and linear space complexities.

Sublinear Representation of Distributions

** The authors propose learning an approximately correct sublinear summary of a distribution from the data stream. This addresses the question of how these sublinear-sized summaries of histograms from multiple streams can be merged efficiently. The framework extends to continuous settings by extending sublinear summarisers to continuous setting and finding minimal conditions to yield theoretical guarantees. The framework is applied for bounded-tail distributions by reducing the problem into estimation of a sublinear summary. This involves learning PDFs and CDFs using algorithms like SPA and SCA. The space complexities of both SPA and SCA are independent of streaming universe’s size. The framework is tight in terms of space complexity as Theorem 27 provides a lower bound on space complexity for any non-trivial solution. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework provides a Oe ε−1 approximation of the true frequencies in l1-norm for any bounded-tail distribution with both infinite and finite supports. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity. The framework is tight in terms of space complexity as Theorem 27 indicates that our algorithms are tight in terms of space complexity.

Improvements for AI systems

No longer require linear space complexity for estimating Wasserstein distance between distributions from samples; instead, achieve sublinear space complexity using algorithms like SWA, which uses Oe (√n) space for n samples while preserving estimation guarantees.
Enable resource-efficient auditing of fairness by leveraging the sublinear estimation of Wasserstein distance to tightly audit the fairness and privacy of algorithms, specifically bounding the maximum of 1-Wasserstein distance between the output distributions of any two subpopulations.
Improve privacy auditing capabilities by using STVA to estimate TV distance, which is equivalent to estimating the HSD between output distributions, allowing for resource-efficient auditing by achieving a sublinear time, space, and communication complexity compared to the number of samples.
Develop a universal estimator for any bounded-tail distribution; SWA can be used to compute Wp (µn, µˆn) ≤ ε with probability at least 1 − δ, where the required sample size is significantly lower than what is needed for exact estimation.
Enhance robustness in continuous data monitoring by using STVA to estimate TV distance between distributions with Lipschitz PDFs, achieving a convergence rate of Θ(e n(1/3)) time, space, and communication complexity with respect to the number of samples required for empirical measure convergence.

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.