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

Estimating distances between probability distributions is vital for tasks like generative modeling, fairness assessment, and privacy protection. Traditional methods rely on full data access or parametric assumptions, which are computationally expensive and impractical for large-scale streaming data. Recent efforts focus on sublinear algorithms for finite support distributions, but extending these to continuous or infinite support remains challenging. The need for scalable, memory-efficient, and mergeable algorithms is driven by applications in federated learning, real-time monitoring, and privacy auditing, where data arrives from multiple sources and must be processed efficiently without sacrificing accuracy.

The core challenge is to estimate Wasserstein and Total Variation distances between distributions from sample streams with minimal memory and communication. Existing algorithms either require linear or super-linear space, or are limited to finite support. In multi-source environments, merging summaries without losing accuracy is difficult. The problem becomes more complex for continuous distributions with infinite support, where discretization introduces approximation errors. Addressing these issues requires developing mergeable, sublinear summaries that maintain theoretical guarantees across broad distribution classes, including heavy-tailed distributions.

This paper introduces a framework that constructs mergeable, sublinear summaries for distributions with potentially infinite support, under tail assumptions like sub-Gaussian and sub-Weibull. Key innovations include: 1) discretizing support into buckets and maintaining frequency summaries via MMG algorithms; 2) designing SWA and STVA algorithms that leverage inverse CDF and bucketed summaries for high-accuracy distance estimation; 3) theoretical analysis proving error bounds that match lower bounds, ensuring optimality. These methods enable efficient, scalable estimation in streaming and federated settings, supporting continuous distributions and multi-source merging, a significant advancement over prior finite-support-only algorithms.

• �� Discretize the distribution support into a finite set of buckets, each representing a support interval. • Use the MMG (Mergeable Misra-Gries) algorithm to maintain frequency counts of buckets in a streaming environment, ensuring sublinear space. • Adjust bucket width and number based on tail properties (sub-Gaussian/sub-Weibull) to control approximation errors. • Convert bucketed frequencies into empirical PDFs and CDFs, then apply inverse CDF formulas to estimate distribution distances. • Develop SWA (Wasserstein) and STVA (TV) algorithms that utilize these summaries for high-precision distance estimation. • In multi-source scenarios, merge summaries efficiently, maintaining theoretical guarantees. • Theoretical analysis confirms that the error bounds are tight and match known lower bounds, validating the approach.

Experiments involve synthetic Gaussian data (N(0,5)) and real datasets from finance and healthcare. The algorithms are evaluated on their accuracy in estimating Wasserstein and TV distances, with varying sample sizes and number of buckets. Comparisons with baseline methods show that the proposed algorithms achieve errors below 0.05 for Wasserstein and O(n^(-1/3)) for TV, with space savings of over 50%. Multi-source and federated setups demonstrate efficient merging with minimal communication overhead. Hyperparameters like bucket width and number are tuned based on distribution tail properties, and robustness is tested across different heavy-tail scenarios. Results confirm theoretical predictions and practical viability.

The algorithms achieve near-optimal error bounds with significantly reduced storage and communication costs. SWA estimates Wasserstein distance with errors below 0.05, using O(√n) space, outperforming traditional linear methods. STVA estimates TV distance with error O(n^(-1/3)), requiring only O(n^(1/3)) space, suitable for infinite support distributions. In federated settings, merging summaries across multiple streams incurs minimal overhead, maintaining accuracy. Empirical results on real datasets validate the algorithms' robustness, accuracy, and efficiency, making them suitable for large-scale, real-time distribution monitoring.

These algorithms are applicable in large-scale data environments such as financial risk assessment, healthcare analytics, and privacy-preserving machine learning. They enable real-time distribution change detection, fairness auditing, and privacy verification with minimal storage and communication. The ability to handle continuous and heavy-tailed distributions broadens their utility in practical scenarios where data streams are high-dimensional and complex. Future integration with deep learning models could facilitate adaptive, end-to-end distribution monitoring in dynamic systems.

The approach relies on tail assumptions (sub-Gaussian/sub-Weibull), which may not hold for extremely heavy-tailed data, potentially increasing errors. Extending to high-dimensional or multi-dimensional distributions remains computationally challenging. Parameter tuning (bucket width, number) requires prior knowledge or adaptive schemes, adding complexity. Handling distributions with unknown tail properties or non-standard behaviors is an open problem, necessitating further research to improve robustness and applicability.