Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
The authors propose a generic framework to learn mergeable sublinear summaries of probability distributions from data streams. This allows for estimating Wasserstein and Total Variation distances between distributions using only sublinear time, space, and communication complexity, significantly improving upon existing methods that require super-linear time or linear space.