Sublinear Algorithms for Estimating Wasserstein and TV Distances: Applications to Fairness and Privacy Auditing
Authors: Debabrota Basu
Debarshi Chanda
Venue: Accepted by TMLR ()

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 \textit{appropriately chosen subset} of the support of a \textit{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.

Published in Transactions on Machine Learning Research (01/2026)
Sublinear Algorithms for Estimating Wasserstein and TV Distances: Applications to Fairness and Privacy Auditing
Debabrota Basu
debabroto. bastuirraaa.
Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189- CRISIAL F-59000 Lille, France
Debarshi Chanda
debarshi.chando. chando. -9977@mmai com
Indian Statistical Institute Kolkala, India
Reviewed on OpenReview: https: oppp:eevee.n net/ forum? id= m26nTKIpCr
Abstract
Resource-efficeenlly computing representations of probability distributions and the distances between them while only having access to the samples is 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 sub-Weibull i.e. almost any light- or heavy-tailed, distribution while the samples from arrive in a stream. The idea is to reduce these problems into estimating the frequency of an appropriately cho- 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 sublincar space relative to the number of observed samples. This allows us to estimate Wasserstein and Total Variation (TV) distances between any two distributions while sam- ples arrive in streams and from multiple sources. Our algorithms significantly improves on the existing methods for distance estimation incurring super-lincar time and linear space complexities, and further extend the mergeable summaries framework to continuous distri- butions with possibly infinite support. Our results tight with respect to the existing lower bounds for bounded discrete distributions. In addition, leverage our proposed estimators of Wasserstein and TV distances to tightly audit the fairness and privacy of al- gorithms. We empirically demonst the efficiency of proposed algorithms across synthetic and real-world datasets.
1 Introduction
Computing distances between probability distributions while having access to samples fundamental and practical problem statistics, computer science, information theory, and many other fields. Among the multitude of distances proposed between distributions, we focus on the Wasscrstein and Total Variation distances in this work.
Wasserstein Distance. Optimal transport VVillnn 2009 has emerged popular and useful tool in machinc learning. It involves computing Wassorstein distance between distributions and using it further for learning. The statistical and computational aspects of Wasserstein distances have been extensively stud-
jed, refer to Panaretos & Zemel (2018); Peyré & Cuturi 2011); Chewi et al. (2024). This geometrically
insightful approach has found applications text document similarity mcasurement
(Kusner al. 2015)
dataset distances (Alvarez-Meer Melis Fusi 2020). domain adaption (Courty et al. 2016),
generative adversar-
ial networks (Arjovsky et al. 2017), data selection and valuation (Just et al. 2024 Kang al. 2024 fair

---

Published in Transactions on Machine Learning Research (01/2026)
classification and regression (Jiang et al. 2020 Chzhen et al., 2020 to name a few. Thus, it is a funda- mental question to compute Wasserstein distance between two distributions when we only have access to samples from it. But computing Wasserstein distance is often memory and computationally intensive until we know the exact parametric form of the data distribution (prociscly, location-scatter famílics) (Gelbrich, 1990: Alvarez-Esteban et al., 2016: Cuesta- et al. 1996 Alvarez- Fusi 2020). In absence of such parametric assumptions, we need linear space complexity and super-linear time complexity in terms of observed samples to estimate Wasserstein distances between the underlying data distributions (Cuturi 2013 Panaretos & Zemel 2018 Chizat et al. 2020: Rakotomamoniy et al.) 2024 Chewi et al. 2024]. Additionally,
in practice, the stream might arrive from multiple sources, as in Federated Learning [Kaiouuz et al. 2021)
This has motivated a recent line of work to estimate Wasserstein distance in federated setting (Rakotoma-
monjy et al. 2024 Li et al. 2024). However, these methods incur communication cost equal to the number of samples in the stream. These gaps in literature motivate us to ask
Can we estimate the Wasserstein distance between two continuous distributions with infinite support in sublinear space, time, and communication complexity w.r.t. number of samples n?
Total Variation (TV) Distance. TV (Devroye & Gyorfi 1990 is another well-studied distance between two probability distributions. It. measures the maximum gap ween the probabilities of any event w.r.l. the two distributions. TV also quantifies the minimum probability that X * Y among all couplings of (X, Y) sampled from the distributions. TV distance between the output distributions of an algorithm operated on two neighbouring datasets also central to auditing the privacy level of the algorithm (Koskela & Mohammadii 2024). Additionally, in bandits, the hardness of problem depends on the TV distance between the reward distributions of the available actions (Azize Basu 2022 Azize et al.) 2023). Thus, estimating TV distance from empirical samples emerges a fundamental problem in privacy and machine learning. Estimating TV distance has been studied extensively (Canonne 2022). There is long line of work focusing estimating
TV distance between discrete distributions with finite support (Kamath et al., 2015 Han et al. 2015 Fong let al. 2024 Devroye& & Reddad 2019: Bhattacharyya et al. 2023 2024 2025). Feigenbaur el al. (2002):
Guha et al. (2006]; Roy & Vasudev (2023) propose sublinear algorithm to estimate TV distance while
having access to sample streams. But the question of estimating TV distance for continuous distributions
with infinite supports remains wide open. This motivates the question:
Can we estimate the TV dislance belween two continuous distributions with infinile supporl in sublinear space, time, and commundcation complerity w.r.t. number of somples n?
We address these questions for any bounded tail distribution by reducing them into estimation of a sublin- ear summary, i.e. the frequency of an appropriately chosen subset of the support of a properly discretised distribution.
Mergeable Sublinear Representation of Distributions. We propose to learn an approximately correct sublinear summary of a distribution from the data stream that can address the previous questions (Sec- tion 4.1 Because then we can store, communicate, and compute with only these sublinear and discrete summaries of distributions. In literature, we find that the sublinear summaries of histograms has been ex- tensively studied over decades (Misra & Gries 1982 Alon et al., 1996 Charikar et al. 2002 Cormode & Muthukrishnan 2005). Additionally, in the continuous distributed monitoring setup (Cormode) 2013), one might want to estimate TV and Wasserstein distances when data streams arrive from multiple sources. Also, with the growth of foderated and distributed learning, the question of how these sublinear-sien histograms from multiple streams can be meryed efficiently has gained interest (Agarwal et al.) 2013 Berinde et al. 2010 Anderson et al. 2017]- In machine learning, we work lot with continuous data distributions. Thus, to be practically useful, need to extend these sublinear summarisers to continuous setting and find minimal conditions to yield theoretical guarantees. On the other hand, there is another long line of rescarch to learn histograms from samples of a continuous distribution and control the error in this process (Sootl
sunmaries of
1979. Freedman & Diaconis 1981 Ioannidis 2003 Diakonikolas et al.) 2018 But it is an open question to develop algorithms and analysis to join these two streams of research, i.e.
Con we learn sublinear summaries of (possibly continuous) distributions while having a stream of n samples from it?
2

---

Published in Transactions on Machine Learning Research (01/2026)
Our contributions address these questions affirmatively.
1. Computing Mergeable Sublinear Summary from Multiple Streams. We propose a generic framework to learn summaries of PDF and CDF of a continuous or discrete (possible with infinite support) distribution using sublinear space (Section 4.2l. Given data arriving in a stream (or multiple streams) from an underlying distribution, we propose SPA and SCA 6-approximate corresponding PDF and CDF independent of stream length. To our knowledge, we initiate the study of mergeable sublinear summaries over streams from an infinite set and establish theoretical error bounds for streams from infinite set and any sub- Gaussian sub- Weibull distribution.
2. Sublinearly Estimating Wasserstein distance. We use SCA to propose SWA to PAC-estimate Wasserstein distance (Section 1.3). We first show that mergeable sublinear summaries learned by SCA are universal estimators of the true distribution in Wasserstein distance. In turn, SWA computes a sublinear summary of a distribution that is O (n-1/2) close Wasserstein distance using (yn) space for n sample SWA operates in the distributed cettributee/fedrrateed /federatedd setting with communication cost of O (vn) per round while preserving the estimation guarantee.
3. Sublinearly Estimating TV distance. For TV distance, we leverage SPA and set the parameters properly to propose STVA (Section 4.4 STVA maintains mergeable sublinear summaries of the bucketed versions of the true distributions, which have probably infinite buckets in their supports. We show that we set the bucket width O(n STVA yields O (n- (m/1) estimate of TV distance between two distributions using δ (n 1/) space.
4. Applying estimators for fairness and privacy auditing. In Section 5.1 we demonstrate usefulness of our Wasserstein and TV distances estimators for auditing fairness and privacy of machine learning models, respectively. Experimental results demonstrate the accuracy and sublinearity of the proposed estimators for auditing models trained on real-life datasets from fairness and privacy literatures.
2 Preliminaries
We discuss the fundamentals of distributional distances and the generic algorithmic template to learn merge- able summaries of histograms, which are essential to this work.
Notations. pm and Pa,, denote the true, empirical, and bucketed empirical measure with bucket width b, respectively. Pμ Supp (u) - [0, 1] and Qμ Supp (R) + [0, 1] denote the probability density function (PDF) and cumulative density function (CDF) of μ, respectively. [n] refers to (1, for n N.
2.1 Distances between Probability Distributions
Now, we define the Wasserstein and TV distances between distributions. We start with defining the Wasser- stein distance between distributions defined over metric spaces.
Definition 1 (p-th Wasserstein distance (Villani 2009)). Given two probability measures μ4, v over metric space X, the p-th Wasserstein distance between them
min [ rEll(u.))
Wp (H,,) A
||0 - vll dr (x(
xxxx
is a coupling over and y, and II is the set of all couplings.
Here, Wasserstein distance is the cost calculated for the optimal coupling between the two probability measures over Euclidean distances. For univariate distributions, Wasserstein distance be expressed norms between inverse CDFs of the distributions (Peyré & Cuturi 2019).
Lemma 2. For univariate measures p, over I,, the p-th Wasserstein distance Wp (u, v) is
Wp (u, = 10 1 ((
(1)
SafttOO notations, f.e. (.) and (-), ignore the polylogarithmic and other lower order terms.
3

---

Published in Transactions on Machine Learning Research (01/2026)
where 07 : [0.1] (RUUY-o) of probability measure P is the pseudoincerse function defined as (r) 4 (i0 fx: Qu(x) 2 r) for r E [0.
The other distance that we study is the Total Variation (TV) distance.
Definition 3 (Total Variation (TV) Distance). Given measures μ. v with support X, TV distance between them is
1 TV (H, sup Im(A) - v(A)] 2 l1ee 1/12-
ACX
2.2 Mergable Summaries of Histograms
The principal algorithmic technique that we use is that of summarising a histogram, which is a long-studied problem (Misra & Gries 1982; Allon et al. 1996 Charikar et al.) 2002 Agarwal et al. 2013 Anderson et al. 2017). We refer to Cormode & Hadjieleftherion (2008) for an overview.
First, we formally introduce the problem. We consider data arriving in stream ( of length n, where each element. belongs to a universe U. The j-th element of U, i.e. Uj appears ʃj times in the stream Ç. Our goal is to maintain approximate count of elements fy such that [ 5111, is small for some p. If we separately keep count of all the elements the problem is trivial and get f, = fj. VU Eu. However, the goal is to obtain 'good' approximation while using sublinear, i.c. o (n), space. More generally, the i-th element of the stream can have a weight w, E N. Then, the task is to generate estimates f = { [ E uu). which are close to the true frequency fj Σi= w; = U2} for all j. Now, we extend the problem setup to aggregate from multiple streams (Agarwal et al. 2013). Given S-streams of data S2, Ss, aim to generate estimates Fi, F2, u. Fs and combine them efficienlly to output a globally 'good' frequency estimate f = merge (r F2.., for the concatenated stream S1 S2 o... Cs-
We build on the algorithm of Anderson et al. 2017). which extends the well-known Misra-Gries algo- rithmn Misra & Gries 1982). We refer to it the Mergeable Misra-Gries (MMG) algorithm and provide the details in Algorithm
5 This family of algorithms is broadly known as the counter- algorithms for histogram summarisation and consists of three main modules. First, they operate by maintaining a sublin- ear number of counters, say k = o(n), all initiated with O. Then, the module MMG Update updates them according to the elements in stream. Specifically, for each stream element, if our algorithm has already assigned a counter, it adds the weight to the corresponding counter. If not, it assigns an empty counter to the element if there is an unassigned counter. Otherwise, the values of all counters are reduced by the median value of counters. Second, if the streams are coming from multiple sources, the module MMG Merge takes the counters in all the summaries as an input stream, and update each counter in the final summary by considering the counters as stream elements and their counts as the corresponding weights. For updating, it reuses the module MMG . Update. Finally, given an element, the module MMG Estimate returns an estimate of its frequeney by returning the value stored in the counter if the element assigned a counter, and 0 otherwise. Note that Update, Estimate, and Merge takes amortised Ô (1), O and Ö (k) time to execute, respectively. For brevity, defer the further details to Appendix A
Now, we derive a rectified version of Theorem 2 of Anderson et al. (017 that bounds the error in frequency estimation using the residuals res(1t, k/4) (defined below).
Lemma 4 (Estimation Guarantee of MMG). (a) If MNG uses k counters, MMG- Estimate yields summary res(n.T)
Uiuu salisfying < f3 fG S (k-k (K- for all T S (k (k-k") k*) and U, E [u]. Here, res(n, T) denoles the sum of frequency of all but most frequent items. (b) If we choose k* = k/4, we get that 0 << f, - f res(n.k/4) vU, E [2].
We extend and analyse MMG's design technique, originally developed for the discrete distributions with finite support points, to continuous and discrete distribulions with infinite support points.
4

---

Published in Transactions on Machine Learning Research (01/2026)
3 Problem: Estimating Distances between Distributions from Sample Streams
Now, we formally state our problem setup. Let μ and v be two mcasures on R. We consider that the data is arriving in two streams Sr and çu of size n, and each element of the two streams are independent and identically distributed (i..d.) samples of and v, respectively. We denote by Pn and 8n the two summaries of μ and v computed from the sample streams. Given a probability metric D, our objective is to compute an (e, -esttimaee of D (H, while using sublinear (n() space to store on and by Specifically, we want to yield D (Pm; Pn) ensuring
P 12 (14, - D (p 2nn) 2 5
(2)
- (n), and (e, 0) E (0, (0, In this work, we particularly focus two probability metries: Wasserstein distances D (1, v) = Wip (1, and TV distance 2 (1, = TV (1, v).
such that (essSup(fn.) UessSup(e.)] DesSSppp
For streams coming from multiple sources, like in the federated (or continuous distributed monitoring) setting, we consider the concatenated streams S4 = Su,1 Su.2 o... o Ga.s and So = Su,1 o Su,2 .... o Sv,s, to be the input streams of length n each to estimate the distance D (1,
Structural Assumptions. In this work, we assume that the data generating distributions have bounded tails (Assumption 7). For the case of D (n, v) Wp (H, v), we assume the distribution to have lo bi-Lipschitz CDF (Assumption For the case of D (1, v) TV (u, P), we assume the distribution to have Li-Lschciitz PDF (Assumption
10
To formalise the bounded-tail assumption, we first define the sub-Gaussian and nei-Weibull random variables.
Definition 5 ((r.o))SSu-Gauusiin Distributions). A distribution μ is said to be (1.0)-sub-Gaussian if for any T 2 0, we have PX-D [|X - E[x]] 2 t < 2exp e
When 7 + 00, (T, (r.o))-ub-Gauusss
distribution reduces to the classical definition of sub- Gaussanniia distribu- tion (Vershynin 2018). Sub-Gaussians cover wide-rangs of distributions including any bounded distribu- tion, Gaussians, mixture of Gaussians etc. (Vershynin 2018). It is standard to assume the noise and data to be sub-Gaussian in regression problems (Wainwright 2019). Sub-Ganssianity appears in the underlying scoring mechanism for classification (Wang el al. 2018). We also consider the notion of sub- Weibull dis- tribution that generalises the notion of sub-Gaussianity to any form of exponentially bounded tails. While sub-Gaussian distributions are considered to be light-tailed, sub-Weiil Weibull distributions are considered for heavy-tail distributions in the concentration of mcasure literature {Foss et al. 2011 Vladimirova et al. 2020 Bakhshizadeh et al. 2023
Definition 6 ((r,a)-Sul> Weibull Distributions). A distribution f is said to be (7, Weibull if there exists some constant ca for any 7 2 t 0, we have Prx~a [X 2 S ca exp (-t1/a)..
When + 0o, (r, au- sub--biulll distribution reduces to the classical definition of sub- Weibull distribu- tion (Vladimirova et al. 2020). For simplicity, we denote (oc, a--sub- Weibull Distributions as a-sub-Weibull. 1/2. Now, we formally state our assumptions.
Note that, for sub- tub-Gaussians,
Assumption 7 (Sub-Gaussiar or sub- Data Generating Distributions). We consider the distributions yielding the samples are either r-sub-Gaussia
a-sub- Weibull.
The tail bound assumption is required because we have access to only the samples from the stream rather than the true distribution. Thus, we need to have enough samples such that the empirical measures available to the algorithm are close to the true distributions. The tail bounds provide control of this concentration of measure phenomenon. We now state our assumptions regarding the lipschitzness of the distributions.
Definition 8 (E-Lipschitz Functions). Given two metric spaces dz) and (Y,dy): a function X Y is said to be &-Lipschitz if d, (f11), f(z2) < (21, Ven, E X.
Assumption 9 (Bi-Lipschitz Distributions). The distribution D over (X, dz) with CDF Qp has -D- Lipschilz CDF, if to (a, b) & (Qv(a) QD(b)) (odz(a,)) b), Va X.
5

---

Published in Transactions on Machine Learning Research (01/2026)
This essentially implies that the PDF of D is bounded above and below everywhere. Any distribution with bounded PDF, and continuous and compact support satisfies this, which encompasses most of the common data distributions.
Assumption 10 (Lipschitz PDF Distributions). The distribution D with pdf μrD over (X, has tD- Lipschitz PDF, i.e. (pp(a) (oo()) s (pdz(a,b) b), Va, b E X.
Any exponential family distribution with bounded parameters have Lipschitz PDF. It includes Gaussians with bounded mean and variance, exponential and Poisson distributions, and other commonly used distributions.
4 Sublinear Estimators of Wasserstein and TV Distances
In this section, we explain our methodology for mergeable summary creation of bounded-tail distributions, and estimation of Wasserstein and TV distances from sample streams. We theoretically and numerically demonstrate accuracy and sublinearity of our estimators.
4.1 From Sublinear Distance Estimation to Learning Sublinear Summaries
Let us consider the empirical measure (ln on n points generated from the true (possibly contimuous) measure μ.. Thus, for any probability distance D, we observe that
D (a,v) - D (An: 0x) S D (4, + D (v,un) + 2 (Mmn Ax) + (n)
Concentration of monsures
Sublincar summaries
if all of these distances are well-defined. In that case, the distance of the empirical measure and the true one decreases due to concentration of measures. While we learn sublincar summarics for cach of the empirical distributions and aim to control the distance between the empirical distributions and the sublinear summary, i.. 2 (pm, An); for any bounded-tail true distribution μ.
In Scction 4.2. we propose algorithms estimate PDFs and CDFs of bounded-tail distributions. This allows control D (Nn, (un) and in turn, compute the desired distances if ym. has bounded-tails. We first proof that the empirical distribution Nn corresponding to sub- Weibull, respectively.
or nub-Weibull μ is also aub-Gaussian
Theorem 11 (Empirical Measure is Sub-Gaussian). Given an o-sub- Gaussian true measure p., the empirical measure Pn generated by X2, ...,,, X,, drawn i.i.d. from μ is (T,O) -T.bb--ub- Gaus--an with probobility at least 1-6 8 given cexp
3.
Theorem 12 (Empirical Distribution sub-uuubueeeee Weibull). Given an a-sub- Weibull true measure μ,, the empirical mensure pn generated by X1, X2,..,, drown i.i.d. from μ is (r, -s-b- Weibull with prodability at least given n 2 12
exp( 8/F)
log J.
We show that with high probability, the empirical distribution retains lub-Gaussianity and Bei-Weibull property of the true measure μ. This result is important for learning sublinear summaries of true distribution from sample streams. The proof is in Appendix
4.2 Learning Mergable Sublinear Summaries
In this section, we state results regarding sublinear summary approximation of sub- Gaussian and sub- Weibull distributions satisfying Assumption 7 We use MMG (Algorithm 5 that approximates a data stream generated from bounded number of elements. We design appropriate bucketing techniques, and leverage the tail bounds to approximate the PDF and CDF of continuous distributions using this algorithm.
A. Learning PDF. We first turn the support of the empirical distribution into collection of buckets of width 0, and in turn, construct an empirical bucketed distribution fb, out of the empirical distribution Pa-

---

Published in Transactions on Machine Learning Research (01/2026)
Definition 13 (Bucketed Empirical Distribution). Let D be a distribution supported (finite infinite) closed interval B C IP with (discrete or continuous) measure Given reference point E B, bucket width b, and an index set [ Σ, we can represent B = , P User + ib, zo + (i ((++1)) 1)6.. We define the bucketed empirical distribution, denoted jb,ns to be the empirical distribution generated from n samples of as Mb.n _ where n, is the number of samples falling in the bucket Ud
For brevity, we denote the bucket [mo + ib, vo + (i 1)6] by Lk. We note that inherits the metric structure of I.. Specifically, the distance between two points 21 E Li and 22 E Ly defined as d(#1, x2) = i ji-jjb. j/b.
In Algorithm [1 we first fix number of buckets k, and treat each of the buckets The weight of a bucket is the number of elements in the stream that falls in it, which is n, for Li We apply MMG over these buckets to return the estimated frequency f: for each bucket Ld, Finally, we return the learned PDF (Pu... (i))er SPA.
element of the stream.
4.
as a summary of μn 's PDF. Now, we bound the learning error of maxx Fy iE!
Algorithm Sublinear PDF Approximator:
Algorithm 2 Sublinear CDF Approximator
SPA(C 11dd Jr, b)
SCA(C i.d.d p,
Initialize
1: Initialize
MMG Initialize (A:)
2: MMG Initialize (k)
Update(Gi)
3: Update({:)
4: Lc, + Ll that contains Ç7
4: Lk, +- LJ that contains S
5: MMG Update (G;, 1)
5: MMG Update (L,,,
6: Merge(
6: Merge(Tb)
7: MMG Merge (T2)
7: MMG Merge (T2)
Estimate(()
8: Estimate(()
MMG (stimate((i) ft
9: F, f MMG EstimateCuumlate(((
10: return Pa. (i)
10: return Q +- Px
max, P3
max, F,
Theorem (SPA Learning Error). (a) If SPA uses h buckets and outputs Das then for all i I,
4 res(n, k/4) ()4) fa ʃ
Ipa, (1) - PP (1) max
n
n
72
(b) Further, if corresponding to pn is au sub- Gaussian, I5l = 2 for all 1, P((ppp. (i) PHs.. (i) 2 E) 8. (c) Further, if corresponding un is Sub Weibull, |<| n e log (#), and 2 (log (+)) then for all i e 1, I(P(p,, PH.... (i) 2 $) < d.
e log (t), and k 2
88 b
log (2)
then
Lemma 4 shows that the error in MMG depends on the sum of frequency of clements except the oncs with the highest Trequencies. SPA leverages this observation, the boundedness of the tails of a distribution (Assump- tion 7), and the guarantee on the preservation of tail bounds for the empirical measure (Theorem II and 12
In SPA, we set bucket width as & 2 Tu (c, b) such that the (possibly) uncovered tails have sufficiently small mass. This yields an (c, 6PC estimate of the empirical PDF. The proof is in Appendix C
B. Learning CDF. Now, we want learn a sublinear summary of the CDF of the empirical distribution Pa- Thus, we start by bucketing its support with counters. Given the corresponding PDF PPs... we define the CDF of the bucketed empirical distribution as Qu... (1) A Ej Pro.... (j)-
In general, there total order on the stream universe U4 we can define the cumulant function F:U -
as F. & Ejs: fz. Total order exists for the real line and the bucket B defined on it. Lemma 13 establishes the error bound of MMG EstimateCumulate for the cumulant. F. The proof is in Appendix
Lemma 15 (Error Bound of MMG Est Astimateuumlate). If MMG uses k counters, MMG EstimateCumm late yields a summary (Fylu,eu satisfying 0 < F; F S 2res(n, n, 4)-
7

---

Published in Transactions on Machine Learning Research (01/2020)
Bucket Count: 100
Bucket Count: 300
Bucket Count: 500
Bucket Count: 700
0.25
0.15
0.16
0.15
0.20
Density
Denelty
Denett
Densiy
0.15
0.10
0.10
0.10
0.10
0.05
0.00
0.00
0.00
0.00
-10
Buckets
Buckets
Buckets
Buckets
Figure 1: Evolution of summaries constructed using 109 samples from (O0 5). We set = 0.05 and bucket numbers 100, 300, 500, 700.
Now, in the spirit of Theorem an (c, estimate of the empirical CDF (Appendix Cl.
appropriately set the bucket width and collect enough samples to yield
Thcorem 16 (SCA Learning Error). Given stream length I<| 2 Tn (E,5) generated from bounded-tan -ail distribution μ, SCA with bucket width sets #brckets to 2 tk (e, b) and oulputs Q such that with probability least 1 8, Quain (i) ((1) s for all deL.
Tail Condition
Tn (E,
Tk (E,
Gy-sub-Gaussian
log (1)
80 log (
b
r-sub-Weibun
log
(log (2))
26
Note that the space complexities of both SPA and SCA are independent of streaming universe's size.
Numerical Demonstration. We take a stream of 105 samples from a Gaussian A 5) and estimate its PDF with SPA. We set the bucket width to 0.05 and vary the number of buckets from 100 700. Figure D validates that increasing the number of buckets, while still being sublinear in #samples, in SPA leads to more accurate summaries of continuous sub- nau-Gaussian density function.
4.3 Estimating Wasserstein Distance
In this section, we introduce an algorithm, namely SWA, to estimate Wasserstein distance between distri- butions satisfying Assumption and SWA leverages SCA learn the CDF and use the inverse CDF formulation of Wasserstein (Lemina) obtain good estimation of the Wasserstein distance between two distributions. We present the pseudocode of SWA in Algorithm 3
Algorithm Sublinear Wasserstein Estimator: SWA(Su: So 1.d n, M,M,E, e.
Require: Ea, lu + Tipschitz constant of μ and v, p p-th Wasserstein
1: for D E {H,,), do
2: bD + 9
3: [Q,, (i) + SCA(CD. bp. Ta (E,
end for
return Wp (Ans D.) plug (Qpm (i))& and (Qo, (1)) in Equation
Universal Learning Guarantee of SCA. We show that SCA is universally good estimator of the CDF of any bounded-tail measure with respect to the Wasserstein distance. This is culmination of three results.
First, SCA guarantees an (c, 6) PAC summary of the CDF a bucketed empirical distribution. To leverage that guarantce in the case of Wasserstein distance for (possibly continuous) mcasure J4, we need choose the bucket width b appropriately such that Wp (Mo, (b,,) is small as the distance of the and the bucketed distribution bounded by b (Lemma 32
8

---

Published in Transactions on Machine Learning Research (01/2026)
Second, once have the (c,8)-PAC summary of the CDF, the rest is to show that it yields small error in computing the inverse CDF, and in turn, the Wasserstein distance (Equation (T) We establish guar- antee on the approximation error of the pseudoinverse of a bi-Lipschitz CDF, given a guarantee on the approximation error on the CDF (Corollary 34).
Finally, we show that the empirical measure pn corresponding to true measure μ with bi-Tipschitz CDF also exhibits bi-Lipschitz CDF with high probability.
Theorem 17 (Bucketed Empirical Measure is Bi-Lipschitz). Let the bucketed empirical measure μb, gen- erated by i.idd. samples coming from distribution μ with Ey bi- bi-Lipschitz CDF. For any e, E (0,1) and fized constant e > O, n 2 20 log ( max 1/ ( Mb,n is (1 () bi- Lipshhiti with probability 1 - 6.
Proof of Theorem 17 is in Appendix B Finally, these results logether yield Theorem 18 universal estimator of any measure μ. The proof is in Appendix D
i.e. SCA learns
Theorem 18 (Universal Learning of SCA in Wp (.)). Given [<] = n 2 Ta E, generated from a bounded- tail distribution i and e, 5 E (0, 1), if we set the bucket width b = then SCA uses To (ln.E) buckets (L.. space) and oulputs Pn, such that P(Wp (pn,fn) 2 E) S 8. We omil the constants Tn e, 6) and To (l)) for simplicity.
Tail Condition
Ta (lez E,
Tk (lp,e) log
0F -u--ub--Cr sub-Gaussian
log (1/5) max
12
Eu
2t 27 "
men-Weibull
log (1/8) max
log
8 22
PAC Gurantee of SWA. We know (Equation 3 that controlling the distance between the empirical measure and the sublinear summary is enough to control the distance estimation error if the empirical distribution concentrates to the true one. Lemma 43 of Bhat & L.A. (2019) proposes the concentration guarantces of empirical mcasure in Wasserstein distance. Combining this result and Thcorem 18 yields estimation guarantees of fú, w.rtt. true measure ps.
2 In 26) generaled from bounded-tail E/2, then SCA uses Th (ly.E) space and outputs in such that P(W, (J., P.)) S e) 2 1 - 5. This further shows that for a stream of size n = O (c (c-2 (og(116)) from two distributions μ and v, SWA yields
Theorem 19 (PAC Guarantee of SWA). Given KI distribution μ, with bucket width
W (Rn, - Wi (1, 4e
(3)
with probability 25. Here, e 1/4] and 8 E 1/2]. Here, - max (ax: ov); a max (cps lx). We omit the constants in on 6,) and Th (l) for simplicity.
Tail Condition resub-Gaussian
Ta E, 6,
Tk (Ly1 g log { (log (1))
log (1/8) max 2 p2, E2
log (1/5) max 2 (log 1) 20-1
F2,
Remark 20 (Space, Time, and Communication Complexity of SWA.). SWA requires Ō (t) time, space, and communication cost to learn distribution in Wasserstein distance. Observe that the lower bound on n in Theorem 19 ensures convergence Mn, to μ in Wasscrstein distance. This is the only term that has &- dependence as the rest of the algorithm is deterministic. SWA's time, space and communication complexities are sublinear (0(vz) compared to the number of samples required to ensure convergence of the empirical measure while retaining the same error.
4.4 Estimating TV Distance
In this section, we introduce STVA that yields an estimate of TV distance between two bounded-tail distribu- tions with Lipschitz PDFs. STVA leverages SPA sublinearly learn the PDFs of the distributions, and then, estimates the TV distance La norm between them (Definition
9

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm Sublinear TV Distance Estimator: STVA(G &o iid.d.
n4, u, U,E, b)
Require: Up f- Subgaussian parameter of μ and v, b f- bucket width
1: for D E { do
2: kD - T (e,t,0)
3: bD - Tb (c
4: (pp. (i) = (in( + SPA (D, bp)
end for
return TV (An, Pn) 0.5 E, (a.. Po.(() (max (PA..))-Po.()) > 0})
PAC Guarantee of STVA. We estoblish the estimation guarantee of STVA in three steps. First, prove that if we choose the bucket width properly to discretise the support of μ,, we obtain a control over the TV distance between true distribution and its bucketed version. Second, we leverage the concentration inequalities of [erend & Kontorovich (2013) to control the TV distance between the bucketed distribution and the empirical bucketed distribution from the streamed samples. Finally, we establish the approximation guarantce of SPA control the TV distance between the empirical bucketed distribution and its sublincar summary.
Step 1: Setting the Bucket Width. Standard rules (Scott) 1979 Freedman & Diaconis 1981 I of choosing
optimal bucket width of a histogram depends either on rule of thumbs or crucially depends on paramcters such as sample size _ (x²) dx elc., which are difficult to estimate for an unknown distribution arriving in a stream. We propose a bucketing technique depending on the Lipschitz constant of the true PDF and the sub-Gaussian parameter of the true distribution to tune the bucket width priori. Proof is in Appendix L
Theorem 21 (Bucket Width for TV Distance Estimation). Given bounded- tail distribution μ with En- Lipschitz PDF and a corresponding bucketed measure pb, if we fir the bucket width b = To (E, E), we have TV (1, S c.
Tail Condition
0y su- Gaussian a-sub- Weibull
To (E,
o log(2/e)
E (log(2c./e))
Step 2: Concentration of Bucketed Empirical Distribution in TV. For continuous measures, as- sumption the structure of the distribution is necessary to establish meaningful convergence rates in TV distance [Dikkniikolas 2016). We establish a convergence result for bucketed measure μ4b generated from a bounded-tail measure μ that possibly has infinite buckets in its support (Appendix L
Lemma 22 (Concentration in TV over Infinite Buckets). Let pn be an empirical measure generated from discrete bucketed measure 14 corresponding a bounded-tate tail distribution μt, and, e, (0, 1). Then, for 2 (e, 0), P [TV (n, 2 a| <8. Here, I(-) denotes the Gamma function Dovis 1959).
Tail Condition
Fa gn-sub--aussian Gaussian
U-sub-Weibull
Tn ()
max
4apyF log (1/8)² cs max
2c [(1 + a), log (1/6))
Step 3: Approximation Guarantee of SPA. Theorem shows that SPA learns a pointwise approximation the PDF of any bucketed empirical measure. However, to extend this guarantee to the TV distance, we need to show that the the sum of errors over the entire support is small. Note that bounded-tail distributions have small mass in the tails (i.e. in most of the buckets). Hence, it suffices to control the error in learning PDF of the hhavvirr buckets to control the error in estimating the TV distance. The proof is in Appendix F.
Thcorem 23 (Learning Error of SPA). If SPA accesses a stream of length [c| = n 2 Tn (s, 8) from a bounded- tail distribution, and uses Th (e, 8) buckets to output sublinear sunmary Pp.: then with probability TV (fon nb < I|pa.. Ppe.. II
10

---

Published in Transactions on Machine Learning Research (01/2026)
Tail Condition
Tn (8,6)
Th. (e, 6)
oN ey-sub-Gaussee
log (1)
log (9) 8ay
b
a-sub-Weibue
log (3)
8 (log (9)
These results together yield the PAC guarantce for STVA.
Theorem 24 (PAC Guarantee of STVA). Given e E (0, 1/6], 5 E (0,1/4), a stream of size n 2 In (8, t, from two bounded- tail and t-Lipschitz distributions μ and v, and bucket width b = Tb (E, STVA uses Tk (s, E, space and
P( (Rm: TV (H, 62) S 48.
(4)
Here, _ max fo oyl, l & max (lus Lu}. We omit the constants in on (lps 5) and Toe (lur ) for simplicity,
Tail Condition
Tn (E)
The (E,
To (E,
o-sub-Gaussian
e max
x l'Elog(1/2) log (t)
z't log (1)
o8vlog(2/s)
k-sub-Weibul
max
((log(1/e))) I(1 + a.) log (t) (log (1)) 2x
((log(2c./e)))
Remark 25 (Space, Time, Communication Complexity of STVA). STVA requires Ō time, space, and communication complexity per round to estimate the TV distance between bounded-tall tail distributions Observe that the lower bound ensures convergence of Pa to μ in TV distance (Theorem 24 This is the only term with 5-dependence as the rest of the algorithm is deterministic. Thus, STVA achieves (n.1/3) time, space, and communication complexity with respect to #samples required for convergence of empirical mcasure while retaining the order of error.
Note that the bounds in Theorem 24 ensures that ε is of the order n 11/3 which ensures that the bucket width is of the order n -133 and the error TV distance is of the order n 11/3, Our result consistent with those of other standard histogram bucket width rules, which chooses bucket width of order -1/3 and ensures the integrated mean squared error to be of order n22/3 (Scott 1979 Freedman & Diaconis 1981)
We observe that Theorem 23 does not only yield a guarantec on TV distance estimation error but also have two further implications, which might be of general interest.
Remark 26 (Further Implications of Theorem 23
1. & eiesttmaaionn of True Frequencies: closer look into the result shows that SPA can also yield an & approximation of the true frequencies ((fi)) corresponding any probability distribution when the tails are sufficiently bounded.
2. Estimation of any Integral Probability Metric (IPM): As our algorithms yield pointwise estimates of both the PDF and CDF of distribution, these methods can be used to estimate any Integral Probability Metric (IPM), such as Dudley metric, Maximum Mean Discrepancy (MMD), Kolmogorov distance (Sriperumbudur
et al. 2012).
4.5
Tightness of Space Complexity
We compare upper bounds on space complexities of SPA and SCA to the existing lower bounds for finite universe streams. Frequency estimation have been extensively studied in this setting. Theorem 27 provides Q (E-1) lower bound on space complexity of any non-trivial solution, i.c. not storing the entire stream, or counts of all elements in the universe, the frequency estimation problem with respect to the norm..
Note that for sub- Gaussians
11

---

Published in Transactions on Machine Learning Research (01/2026)
Eut Dhirre
RJ
Appreeiaa eilen Oroe
Aporosimadon Ereor
5.00
Carmatd Cnttenes
(Buchote
60,000
#itudotts
3: Figure 4: Auditing Figure Auditing Figure 6: Privacy of with SWA re- with SWA on clas- Auditing of logis- SWA with NO 5): STVA with (N,,5), 5), gression output of sification output of tic regression on 5), and b 0.05 (l,,5) and b 0.05 ACS Income.
Figure
2: Figure
Performance of Performance
ACS Income
MNIST.
Theorem 27 (Lower Bound of Frequency Estimation in norm (Chakrabarti 2024 of length n coming from a universe U of size m, any algorithm that produces (sn) -ox opproximation of the frequency vector {filie(m) as { kE[m]
Given a stream Ç
must use Q (min (n, m, m)) space.
Our framework provides a Ō 2) approximation of the true frequencies in &-norm for any bounded-tail distribution with both infinite and finite supports, ie. universe of streams (ref. Remark 26 Hence, Theorem 27 indicates that our algorithms are tight in terms of space complexity.
5 Experimental Analysis
Our aim is to understand whether SWA and STVA yield PAC estimates of Wasserstein and TV distances between sub-Gaussiag distributions with sublinear space, i.e. namber of buckets, with respect to the number of samples.
Setup. We compute distances between two Gaussian distributions (00 and (L,,5), where 10at samples from each of them arrive through 5 10 sources. True TV and Wasscrstein distances between them are 0.0797 and 1.00, respectively. We set the bucket width to b = 0.05 and increase the number of buckets {100, 150,... 1000}. We run each of the experiments 50 times. Finally, for SWA, we report the estimated Wasserstein distance and the learning error of SCA, i.e. Wp (Mn, Pn), in Figure 2 Similarly, for STVA, we report the estimated TV distance and the learning error SPA, ie. TV (Aus Pn), in Figure We report the true distances each case as the dotted horizontal lines.
Results.
1. Accuracy and Sublinearity of SWA. The estimation error of SWA and learning error becomes negligible as the bucket number reaches to 750 while using 10 samples. This is better than the theoretical upper limit of buckets, iee 1040, suggested by our results.
2. Accuracy and Sublinearity of STVA. The estimation error of STVA and learning error becomes negligible as #buckets also reaches 750. Thus, the results demonstrate that both STVA and SWA yield accurate estimates of TV and Wasserslein dislances while using only sublineur space w.r.l. #sumples.
5.1 Applications: Auditing Fairness and Privacy
Auditing fairness (Goosh et al. 2021
2022 Yan Zhang 2022 and privacy (Nasr al. 2023 Steinke
et al.) 2024 Koskela & Mohammadi 2024 Annamalai & Cristofaro 2024 Azize Basu 2025 of Machine
Learning (ML) models is important and increasingly studied question for developing trustworthy ML. Here, we deploy SWA and STVA to estimate the fairness and privacy of ML models trained on real-world data, respectively. The details are provided in Appendix
Note that while techniques consider the data arrives from distribution rather than arbitrarily from a universe (as in Theorem 27 suffices if the underlying data are generated from distribution and the order of their arrivals is arbitrary.
12

---

Published in Transactions on Machine Learning Research (01/2026)
6 Discussions and Future Works
We propose algorithmic framework to learn mergeable and sublinear summaries of discrete and continuous, sub-Gaussian and sub-Weibull distributions while data streams arrive from a single or multiple sources. We show that the computed mergeable sublinear summarisers are universal estimators with respect to Wasser- stein distance. We establish the first sublinear time, space, and communication algorithms to estimate TV and Wasserstein distances over continuous and discrete (with infinite support) distributions. We also note that our framework can be used to estimate any ly-norm based distance between distributions with sublinear rosources. However, our work is constrained to distributions over scalars. A future direction to study these problems for multi-variate distributions.
Acknowledgement
Both the authors would like to thank the Inria-ISI Kolkata associate team SeRAI (DRI-012551) for supporting this collaboration. D. Basu acknowledges ANR JCJC project REPUBLIC AANR-22-CE23-000 and PEPR project FOUNDRY (ANR23-PEIA-0000)) partially funding this work. We also thank Uddalok Sarkar and Udvas Das for their support.
References
Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Trans. Database Syst., 38(4), dec 2013. ISSN 0362-5915. doi: 10.1145/25001 22001288 URL
https://doi.coo ort/oogg///1 0eep://...14//55000 2445220012288
Ayoub Ajarra, Bishwamittra Ghosh, and Debabrota Basu. Active fourier auditor for estimating distribut properties ml models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 15330-15338, 2025.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the "wenly-Eightt Anneual ACM Symposium Theory of Compuling, STOC '96, pp. 20-29, New York, NY, USA, 1996. Association for Computing Machinery. ISBN 0897917855. doi: 10.
1145/237814.237822 URL https: org/oogg///o 10. 1et..1171/22884 237823
Pedro C.
Alvarez-Estcban F. del Barrio, J.A. Cuesta-Albertos, and C. Matran. A fixed-point approach barycenters in wasserstein space. Journal of Mathematical Analysis and Applications, 421 762, 2016. ISSN 0022-2477X doi: https::/dooi.org/11... 10.16////0001000........0..///.1 (m0.///..jma.220 2a..aa..0.....04.. URL
David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advonces in Newral Information Processing Systems, 33:21428 21439, 2020.
Daniel Anderson, Pryce Bevan, Kevin Lang, Edo Liberty, Lee Rhodes, and Justin Thaler. A high- performance algorithm for identifying frequent items in data streams. In Proceedings of the 2017 Internet Measurement Conference, TMC '17, pp. 268-282, New York, NY, USA, 2017. Association for Comput- URL https:://oor /tttp::/ddo.oor/10... htrg/10.1155/
ing Machinery. ISBN 9781450351188, doi:
3131365 3131407
Meenatchi Sundaram Muthu Selva Annamalai and Emiliano De Cristofaro. Nearly tight black-box auditing of differentially private machine learning. In The Thirty-eightth Annuua Conference Neural Information Processing Systems, 2024. URL https://openreviae http:a/wwwwwwweeeeooorooeedeeooe www.ee//orrrriicccMMii.itam
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Achraf Azize and Debabrota Basu. When privacy meets partial information: refined analysis of differen-
tially private bandits. Advances in Neural Information Processing Systems, 04:321993322119 2022.
13

---

Published in Transactions on Machine Learning Research (01/2026)
Achraf Azize and Debabrota Basu. Some targets are harder to identify than others: Quantifying the target- dependent membership leakage. In International Conference. on Artificial Intelligence and Statistics, pp. 397 405. PMLR, 2025.
Achraf Azize, Mare Jourdan, Aymen Al Marjani, and Debabrota Basu. On the complexity of differentially private best-arm identification with fixed confidence. Advances in Neural Information Processing Systems, 2023.
Milad Bakhshizadeh, Arian Maleki, and Victor H De La Pena. Sharp concentration results for heavy-tailed distributions. Information and Inference: A Journal of the IMA, 12(3):1655-1655, 2023.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: tight analyses via couplings and divergences. In Proceedings of the 32nd International Conference on Newral Information Processing Systems, NIPS'18, pp. 6280-6290, Red Hook, NY, USA, 2018. Curran Associates Inc.
Daniel Berend and Arych Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics and Probabilily Letters, 83(4):1254 1259, 2013. ISSN 0167-7152. doi:
https://tol.org/100000///./ http:0000000011....1....000000 CRL http:///www.cciencdeeeetttttttt. http://wwwaaaaaaoco.ccoco//o//aa pJ1/80167/1221300222
Radu Berinde, Piotr Indyk, Graham Cormode, and Martin J. Strauss. Space-optimal heavy hitters with strong error bounds. ACM Trans. Dalabase Syst., 35(4), oct 2010. ISSN 0362-5915. doi: 10.1145/1862919.
1862923. URL https://doi org/10. /0. 1145/1862919 191.19922999.11822938888
Sanjay Bhat and Prashanth L.A. Concentration of risk measures: A wasserstein dis- tance approach. In Н. Wallach, Н. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httts::/ppooceedngg..nt neur.ps......p.... wtt.:/uuur.s.ppppeeeeeee cc/paper filess/ppprr/2199//5 021054400660444416666e2222222222
pdf
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinod- chandran. On approximating total variation distance. In Edith Elkind (ed.), Proceedings of the Thirty- Second International Joint Conference on Artificial Intelligence, IJCAT-29 pp- 3479-34 3387. International Joint Conferences on Artificial Intelligence Organization, 2023. doi: 10.24963 /2493//jcaiii.... htt/://aaa...2///3/333 2023/387. URL https://doi.org/// wtt.o////......///oee.e 24963/ijcai. (0tjj//i.22233998 2023/387 Main Track.
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinod- chandran. Computational explorations of total variation distance, 2024. URL https: org/ abs/
2412. 10370
Arnab Bhattacharyya, Sutam Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, and N. V. Vinod- chandran. Total variation distance meets probabilistic inference. In Proceedings of the 41st International Conference on Machine Learning, ICMT.24. JMrg. 2025.
Clément L. Canonne, Topics and techniques in distribution testing: A biased but representative sample. Foundations and Trends in Communications and Information Theory, 1966):1032-1198, 2022. ISSN 1567-2190. doi: 10. 10.1561/000 11.156001100000114, URL http::/dxx. doi 1tt..oor//....11/100000000.
Amit. Chakrabarti. Data stream algorithms lecture notes computer science, Mar 2024. URL https:
//www.
pdf
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams. In
Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Slephan J. Ei- denbenz, and Ricardo Conejo (eds.), Automata, Languages and Programmingg 29th International Col- loquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, volume 2380 of Lecture Notes in Computer Science, pp. 693-703. Springer, 2002. doi: 10.1007/3-540- 90007/38540-44465-99 59. URL https: 7/doi. 0a0pl/..orr/...000073000006-----
14

---

Published in Transactions on Machine Learning Research (01/2026)
Sinho Chewi, Jonathan Niles- Weed, and Philippe Rigollet. Statistical optimal transport, 2024. URL https:
7/arxiv. abs//407.22222.. 22 18163
Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François- Xavier Vialard, and Gabriel Peyré. Faster wasser- stein distance estimation with the sinkhorn divergence. In Proceedings of the 34th International Conference on Newral Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc.
ISBN 9781713829546.
Ben Chugg, Santiago Cortes-Goment Bryan Wilder, and Aaditya Ramdas. Auditing fairness by betting. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advonces in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL httops://proceedings wewiinngsneuuiiiccco wttp:/pp..cppppe////////////////
Doron Cohen, Aryeh Kontorovich, and Geoffrey Wolfer. Learning discrete distributions with infinite support. Proceedings of the 34th International Conference on Newral Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Graham Cormode. The continuous distributed monitoring model. ACM SIGMOD Record, 42(1):5-14, 2013.
Graham Cormode and Marios Hadjieleftherion. Finding frequent items in data streams. Proc. VLDB Endow. 1(2):1530 1541, aug 2008. ISSN 2150-8097. doi:
URL https://doi.orr
14778/1454159 1454225
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58 75, 2005. ISSN 0196-6774. doi: https://
0bi..og//10.101//....o.o... 50196677403001913
URL
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):1833- 2016.
Juan Antonio Cuesta-Albertos, C. Matrán-Bec. and A. Tuero-Diaz. On lower bounds for thel2-wasscrsteri metric in a hilbert space. Journal of Theoretical Probability, 9:263 283, 1996. URL https://api.
semanticscholar. wrtpllo.g//Ceeee http/CorpusID... 121128838
Marco Cuturi. Sinkhorn distances: lightspeed computation of optimal transport. In Proceedings of the 27th
International Conference on Neural Information Processing Systems Volume 2, NIPS' 13, pp. Red Hook, NY, USA, 2013. Curran Associates Inc.
Philip J. Davis. Leonhard euler's integral: A historical profile of the gamma function: In memoriam: Milton abramowitz. The American Mathematical Monthly, 66(10):849 869, 1959. ISSN 00029890, 19300972. URL
http: http://wwwjj.ttr/so///s jstor wtwp/etagg/g/oooooooooooooooeeet 2309786
Lue Devroye and Laszlo Gyorfi. No Empirical Probability Mcasure can Converge in the Total Variation Sense for all Distributions. The Annals of Statislics, 18(3):1496 1499, 1990. doi: 10. 10.1214/aos/ /11//////0/1764777555
URL htttp::/p///do..orr org/ 1214/ 11144///s/11763477700
Lue Devroye and Tommy Reddad. Discrete minimax estimation with trees. Electromic Journal of Statislics, 10.1214/1--.J815666 13(2):2595 2623, 2019. doi: 10.1214/194 EJS1586. URL https://doi. http://2...rrg/11.22221////55351 1214199E11110
1ass Diakonikolas. Learning structured distributions, pp. 267-288. CRC Press, 2016.
Ilas Diakonikolas, Jerry Li, and Ludwig Schmidt. Fast and sample near-optinal algorithms for learning multidimensional histograms. In Conference On Learning Theory, pp. 819 842. PMIR, 2018.
15

---

Published in Transactions on Machine Learning Research (01/2026)
Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: new datasets for fair machine learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems. NIPS 22,, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393.
A. Dvoretzky, Kicfer, and J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator. The Annals of Mathematicul Stalistics, 27(3):642 669, 1956. doi: 10. 10. 00144//mm/117772/
URL https:///oo...... 2ttg://...224///mm/1777799911111
Cyuthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, and Mahesh Viswanathan. An approxinate 11 difference algorithm for massive data streams. SIAM Journal on Computing, 32(1):131-151, 2002. doi: 10.1137/S00997337799011 701. URL https:///oi. http:://......ooooo......//23723 /171111777777077777999100001
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international con- ference on knowledge discovery and data mining, pp. 259 268, 2015.
Weiming Feng, Liqiang Liu, and Tianren Liu. On deterministically approximating total variation distance. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1766 1791, 2024. doi:
URL https://epubs.. siam. ottp//oo//bbb//..13////////
9781611977912.70
S Foss, S Zachary, and D Korshunov. An introduction to heavy-tailed and subexponential distributions. Springer Series in Operations Research and Financial Engineering, 38:1 120, 2011.
Nicolas Fournier and Arnaud Guillin, On the rate of convergence in wasscrstein distance of the empirical measure. Probubilily Theory and Related Fields, 162(3):707 738, Aug 2015. ISSN 1432-2064. doi: 10. 1007/s00440-014--5555 URL htttps://dot
1007/8004400014-65833
David A. Freedman and Persi Diaconis.
On the histogram density estimator:12 theory. Zeitschrift für Wahhsschehniccckeisttttoore und Verwandte Gebiete, 57:453-476, 1981. URL https://api,
semanticacholes org/ http//CoppsiD::::0 org//orrpusD::14470688 14437008
Matthias Gelbrich. On a formula for the 12 wasserstein metric between measures on euclidean and hilbert spaces. Mathematische Nachrichten, 147:185 203, 1990. URL https://api. semantiscchohn org/ Co
Bishwamittra Ghosh, Debabrota Basu, and Kuldeep S. Meel. Justicia: A stochastic SAT approach to formally verify fairness. In Thirty-Fifth AAAI Conference Artificial Intelligence, AAAI 2021, Thirty- Thirty-Third Conference on Innovative Applications of Artificial Intelligence, TAAT 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 7554-7563. AAAT Press, 2021. doi: 10.1609/AA A3309/AALLV3519... 16925. URL httphttts://// //ooi. wrt.....g11111....... 1609..609/aa aaai. v35i9. 16925
Bishwamittra Ghosh, Debabrota Basu, and Kuldoep Moel. Algorithmic fairness verification with graphical models. In Thirly-Sizie Sirth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirly-Fourth Conference on Innovotive Applications of Artificial Intelligence, TAAT 2022, The Twelveth Symposiun on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 1, 2022, pp. 9539 9548, AAAI Press, 2022. doi: 10.1609 (0.1609/AAAA. V3699
URL https://doi. htt///oo.oorg//.// 1609/ 2aa9//aai.... attp/a.aa.............. v3619.
21187
Sudipto Guha, Andrew McGregor, and Suresh Venkatasuubramanian. Streaming and sublinear approximation of entropy and information distances. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pp. 733 132-742, USA, 2006. Society for Industrial and Applied Mathematics. ISBN 089871 1055.
16

---

Published in Transactions on Machine Learning Research (01/2026)
Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax estimation of discrete distributions. In 2015 IEFE International Symposium on Informalion Theory (ISTT), pp. 2291-2295, 2015. doi: 10.1109/ISIT. 2015.7282864.
Yannis Toannidis. The history of histograms (abridged). In Proceedings 2003 VLDB Conference, pp. 19-30. Elsevier, 2003.
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classifi- cation. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pp. 862-872. PMLR, 22-25 Jul 2020. URL
.ml.r.ss.........mmm.m.......... ppwpss//111//janggaaaa..... html
Hoang Anh Just, Feiyang Kang, Tianhao Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. Lava: Data valuation without pre-specified learning algorithms. In The Eleventh International Conference Learning Representations, 2024.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. Foundations and trends0 in machine learning, 14(1-2):1122) 2021.
Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda Theertha Suresh. On learning distributions from their samples. In Peter Grünwald, Flad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1066 1100, Paris, France, 03-06 Jul 2015. PMLR. URL https://pproeeedngg..t mlr pyress/v40/Kamath1 1attaammmaam1.....1.1.11
Feiyang Kang, Hoang Anh Just, Anit Kumar Sahu, and Ruoxi Jia. Performance scaling via optimal trans- port: Enabling data selection from partially revealed sources. Advances in Neural Information Processing Systems, 36, 2024.
Antti Koskela and Jafar Mohammadi. Auditing differential privacy guarantees using density estimation, 2024. URL https://arxiv.. wrt. 04827
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document dis- tances. In International conference on machine learning, pp. 957-966. PMLR, 2015.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun, hee///rmd//mss//.///// 1998.
Wenqian Li, Haozhi Wang, Zhe Huang, and Yan Pang. Private wasserstein distance with random noises, 2024. URL https://arxiv.. wwapsiivvorrgeeee 02////4444088778
J. Misra and David Gries. Finding repeated elements. Science of Computer Programmingg, 2(2): 152, 1982. ISSN 0167-6423. doi: sciencedirect.co aai.aaccaareet.cco////ee///////d http:////ssaaeeeerree///////////
URL htttps://ww
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithmss and Probabilistic Analysis. Cambridge University Press, Cambridge, 2005.
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 1631-1648, 2023.
Victor M. Panaretos and Yoav Zemel. Statistical aspectt of wasserstein distances. Annual Review of Statistics and Its Application, 2018. URL
org hotg/orruuID::882220 88523547)
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2075-,2800-0 2011.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 11 (5-6):355-600) 602, 2019. URL https://arx:: http:///aawwww./aa////eeeee wwt//b/////...0000/000
17

---

Published in Transactions on Machine Learning Research (01/2026)
Alain Rakotomamonjy, Kimia Nadjahi, and Liva Ralaivola. Federated wasserstein distance. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OeenReview.net, 2024. URL https:///peerevviiin
Sampriti Roy and Yadu Vasudev. Testing Properties of Distributions in the Streaming Model. In Satoru Iwata and Naonori Kakimura (cds.), 34th International Symposium Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informalics (LIPlcs), pp. 56:1-56:17, Dagstuhl, Germany, 2023. Schloss Dagstuhl - Zentrum für Informatik. ISBN 978- 978-3-95977-289- doi: 10.4230/LIPIcs.ISA ISA.C.2023... URL Attps://dropps dagstuhl http://nnttieesscccmme/////////t 42300
LIPIcs. ISAAC. 2023.56
David W. Scott. On optimal and data-based histograms. Biometrika, 66(3):605 610, 12 1979. ISSN 0006- 3444. doi: 10.1093/ biomet 1omnet/66. /66.3.605. URL https://doi.... http:://ac..rg//11.11100.0 http:///.r......oooo/////////...
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On the empirical estimation of integral probability metrics. Electromic Journal of Statistics, 6(none):1550 1599, 2012. doi: 10.1214/12-BA) EJS722. URL https::/doi..orrg//geee// http///o..o.ogro111/////////////
1214/12-EJS722
Matthew Staib, Sebastian Claici, Justin Solomon, and Stefanic Jegelka. Parallel streaming wasserstein barycenters. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- tems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 2647-2658, 2017. URL
253
html
Thomas Steinke, Milad Nasr, and Matthew Jagiclski. Privacy auditing with one (1) training run. Advances in Neural Information Processing Systems, 36, 2024.
Roman Vershynin. Ligi--Dimesiooall Probabilily: An Introduction with Applications in Dala Science Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Cédric Villani. Optimal Thansport. Springer Berlin Heidelberg, 2009. ISBN 9783540710509, doi: 10.1007/ 188-3-540-71050-0 URL http:://xxddo. doi http://x.ddi..o//1.....oo 0..00/9778- 540-710500
Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub Sub-weibull distributions: Generaliz-
ing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, 9(1)x3318, 2020. doi: https://doin. http:///doo..rg/1.00002//222 10/p:/1.11000 10..100//////..11 URL http:///ww....boololl.o/////////
318. c318 sta4.318.
Martin J Wainwright. High-dimensional statistics: A non-osymptotic viewpoint, volume 48. Cambridge university press, 2019.
HaiYing Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal of the American Statistioal Association, 113(522):829 844, 2018
Tom Yan and Chicheng Zhang. Active fairness auditing. In International Conference on Machine Learning, pp. 24929 24962. PMLR, 2022.
18

---

Published in Transactions on Machine Learning Research (01/2026)
Appendix
Table of Contents
Mergeable Mísra Gries Algorithm
20
B Properties of Empirical Measure
22
Estimation Guarantees of SPA and SCA
24
Estimation Guarantee
E
Estimation Guarantee of STVA
28
E. Proof of Theorem 21
29
E, Proof of Lemma
30
E.3 Bounding Errors SPA and STVA Theorems 23 and 24
32
Useful Technical Results
34
Experimental Details
Fairness and Privacy Auditing
36
C.1
Fairness Auditing
36
G.2
Privacy Auditing
36
Enlarged Plots
38
19

---

Published in Transactions on Machine Learning Research (01/2026)
A Mergeable Misra Gries Algorithm
Algorithm MMG (Anderson et al. 2017
1: Initializekk)
2: T+0
is the set of items for which counters are assigned
3: k +-b k
Update(i, A) if G E T then
<(G) t- dG)) + A
9: else if [T] < then
10: = {
11: (G) - dG)
12: clsc
13:
DecrementCCunters()
14: end if
15: if A 2 ck- then
16: T Tu
T k + < k after this line
17: c(G) + dG) Ck
18: end
19:
20: DecrementCounters)
21: // Notation: Let Ck- be the k largest value, counting multiplicity,
22: // in the multiset {c(S)): S E T}.
23: for Sj T: do
24: e(G) = c(G) - Ck-
25: if c(G) S 0:
26: T= {(p}
27: end for
28:
29: Estimate(i)
30: if & E T then
31: return c(G)
32: clse
33: return
34: end if
35:
36: EstimateCumlltteG)
37: (G) +- Estimate (G)
38: return A: + Ecs5 C2
39:
40: Merge (T2)
41: for & E T2 do
42: Updaten (Gs, c(:))
43: return Ti
44: end for
First, we outline the proof for the Lemma restated here for ease of reading.
Lemma 4 (Estimation Guarantee of MMG). (a) MMG uses k counters, MNG Estimate yields a summary
res(n.T) (frhueu satisfying Σ fy fr S (k- for all t S (l - k*) and Uj E [4]. Here, res(n, T) denotes the sum of frequency of all but T most frequent items. (b) If we choose = $ r = k/4, we get that S3 -fs S3 < res(n.k/4) vU; E 141-
20

---

Published in Transactions on Machine Learning Research (01/2026)
The proof of the result follows that of Theorem 2 in Anderson al. (017 The change is in the Lemma 4.
We provide the proof for the updated statement here. The notation is kept same that of the original work for ease of reading.
As in the original paper, we define Ni = Ei =i= wj: Ci = -k=E c₁ and Ei = Eie(m) fax fea
Lemma 28. E. (N, Cx) (k (k-k*) k*)
Proof. As in the original proof, we proceed by proof by induction, the case for = 0 is true as No Co = Eg =.
Suppose the hypothesis holds for some 1 - i.e.:
E S - C-1)/ k*)
If the [-th element the stream does not cause DecrementCounteers to be called, we have E, = Ei-1:
C = Ci-1 + wi, N₁- Ni-1 + wi Hence ,we have:
F = 1 s - -Ni-1-C-a)/ k*) (Nr CI/ (I: k*)
The case when DecrementCounters called is more interesting, we have
E = E1-1 + Ck-
(5)
Here, know that at 1 - 1-th step, (k- - k*) counters had value Ck- Therefore, they retain some negative value after being reduced by Cus, while the remaining k- counters have value 0. Hence, we have C S C1-1 - (k - k²)) ck.
Ni Ci
= =N:-1 + Ci
2 Ni + wT Cj-1 + (k - k-) Che
2N-1 - C1-1+ + (I- k²) Ck
(6)
Now, combining Equations 5
and 6 we have:
N C1-1 + Ck
Ni-1 C1-1 + (A:
k Ck
Ni C
E = E + c 5
(k km)
(k: ki*)
(k: k*)
The second part of the proof of Theorem 2 in the original paper follows similarly under the updated statement
of Lemma 28 Giving us the final result of Lemma
To establish the estimation guarantee of EstimateCuuulate, we need a simple corollary of the Lemma g
Corollary 29 (MMG Estimation Guarantees). For E {1,2}, given streams Cj being stored in two seperate sets of counters of size k the merged summary satisfies:
res(n, 4)
0 0 f: S
k
for all j S k², where res(n, j) denotes the sum frequency of all but j of the most frequent items.
Proof. We fix k' }1 and j = 4. These values satisfy the criteria of Theorem i.c. & = ((k) and j < k. Plugging in these values gives the result.
2
We prove the Lemma 15
21

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. We denote by Topk the set of elements with highest true frequency f.. Then, have:
F - P: Σ
-
Σ
- S1
Σ
f1
jSi jeTops
J&Topp
res(nn, $
Σ
fJ
jeTopg hi
jæTopg
k res res(12 (,,
7
Where the first inequality uses Corollary 29 and the last inequality follows from the definition of res(n, k). 7
B Properties of Empirical Measure
In this section provide the proofs for Theorems 11 and 17 We restate the theorems for easy of reading. We introduce the multiplicative Chernoff bound that will be relevant to our analysis.
Lemma 30 (Multiplicative Chernoff Bound Mitzenmachh & Upfal 2005)). Given i. random variables X1, X2.... Xn where Pr[X; = 1] S and, define X Lie(m) X,. Then, we have:
n
Pr[X 2 (1 + e)pl exp
OSE<I
(7)
Theorem 11 (Empirical Measure is Sub- Gabu-asssiin.. Given an Gaub-Gasssian true measure the empirical Xn drawn i.idd from is (T, (T.o)- Gaussian with probobility at least -ubb-Gaaaasi
measure Pn generated by 1-8 8 given n 2 cexp log J.
Proof. To capture the tail behaviour w.r.t. some S T for each sample, we define random variables Z1, ZZ, ZZy,.., m. Za 88:
X; 26
2,
0
X; <t
We denote by 1 Exe(m) Z, Then, we have for the empirical measure Pro
Pr [ X X~nn
Furthermore, we have by Definition 5
(- 12
Pr [2, = 1] S 2cxp
0²
Then, by Lemma 30 we have:
t2 (-
(-e)
t2 ]
nexp
67
Pr 2 2 2 exx
(-
< Pr
Z 2 3exp
(-02) 02
< exp
< 8
6
By setting 6, get the desired result.
Now, we prove Theorem 12 restated here for ease of reading:
22

---

Published in Transactions on Machine Learning Research (01/2026)
Theorem 12 (Empirical Distribution is sub-suuebbeeeee Weibull), Given a-sub- Weibull true measure μ4, the empirical measure Mn generated by X1, X2...., ..., Xn drown i.i.d. from μ is (T, (T,a))-st --s-b Weibull with probability al least. - given n 2 exp( 8/r)
log :
12
Proof. To capture the tail behaviour w.r.t some S T for each sample, we define random variables Z1, ZZ2 .., Zu as:
1 X; 2
2,
0
X; <t
We denote by =
1 n Evenn) Zz Then, we have for the empirical measure Pr
Pr 1x21=2
X X~pm
Furthermore, we have:
Pr Prl 1] S Co exp (-el/a)
Then, by Lemma 30 we have:
Pr Z 2 1.5c. exp (el s exp
nCa exp (-pt/a)
exp (- nCa exp (- (T)
5 8
12
12
Next, we prove the Theorem 17 For that purpose, we need the following lemma.
Lemma 31 (DKW Inequality (Dvoretzky et al.) 1956)). Given sequence of i.i.d. random variables X1, X2,..., Xn generated from distribution P with true edf Qp- Let Qu., be the edf of the empirical measure generaled from the samples X1, N1,X2..., Xa- Then, for all e 2 O, given n 2 2e we have:
In(2)
P sup Q2)()) - Qu, (x) 25 s 2exp (-2nE²) LEE
Theorem 17 (Bucketed Empirical Measure is Bii-iipschitz). Let the bucketed empirical measure μbb. gen- erated by i...d. samples coming from distribution μ with Ep bi- bi-sccichitz CDF. For any e,8 (0,1) and fized constant >> 0, if جभم log (3) max 22 L Ma,n is (1 + E)pp bi- bi-Liscchita with probability 8.
862 we have by Lemma 31
Proof. For n 2 log (2) max
Qu((x) Qua.. (x) 2 min Ebby, eb
4P )]
sup
S
Let us denote foww = min
Then, we have with probability 1-
Ttp
sup sEB
Qu(x) (x) S EDEW
(9)
Now, we have Va, b E B, with probability 8:
1 (a) - Qus.n (b)
< (a)(a) Q,, 25 pxw
<t, la + el, la
<e, (1 +) la bl
23

---

Published in Transactions on Machine Learning Research (01/2026)
Where the first inequality follows from Equation 9 and triangle inequality, and the second inequality follows from the fact that cox S =bb and b S bl. Va, E B. For the other side of the inequality.
2
Qpe, (a) Qp (b)
Qu((a) Qui DEw
E/a bl
||a bll
P/1
26
2 f (1 + +) la bb bl
Where the first inequality follows from Equation and triangle inequality, and the second inequality follows from the fact that cow I 16p and S la b), Va, b E B, and the third inoquality follows from the fact that for all & (0,
Ite
C Estimation Guarantees of SPA and SCA
In this section, we provide the proofs for Theorem and 16 We restate the theorems here for ease of reading:
Theorem (SPA Learning Error). (a) If SPA uses k buckets and oulpuls Pay then for all i I,
4 res(n,, k/4) fa f: f
Pa. (i) - Pun.n (0) max
n
n
71
(b) Further, if corresponding to pn is o₂ sub- Gaussian, IC| = n 2 - log (t), and k 2 for all i I, P((pp..)) (t) PHs.. (i) 2 E) v 5.
80 b
log (t)
then
(c) Further, if corresponding to pm is a-S Weibull, |<| log (t), and k [ (log (1)) 9T, then for all i I, P(IPp.. Pub.. (i) x) < 8.
Proof of Theorem
Proof of (a): We Start with the first equation:
Ji <
f
fi
p(1) Pa (i) max, F5
res n. k/4)
fi
n
res
(o,nn,ni k:/4)
n
1
=fi
12 2 res(n, n2 k/4)
fi
2 res (n, k k/4)
n
12 res (n, k/4)
fz
4 ree((n k/4)
n
n
For the second part,
Pus. (i) -p(i) fz
f.
ff
max; F7
11
71
Finally, we have:
4 res(n, k/4) ft f:
Pps.a (1) -(() = max (PAa.n (t) - -p(1). PHa.. (1)) S max
24

---

Published in Transactions on Machine Learning Research (01/2026)
Now, we also have by Corollary 29 and the fact that fa n,
PP f(1) res(n,, n, k/4)
know that pa generated by μ (7, on) sub-Gaussian given n 2 cexp log (t). Here, we can fix t 20 v log (t). Hence, by the property of sub-Gaussian distributions and the fact that each bucket of size b,
Proof of (b): If on sus-ss-uuuuussiaa Gaussian, by Lemma
res k/4)
log !
P
2
20
SE.
72
Proof of (c): For a-sub Weibull distributions, by Lemma 12 we know that generated by is T, a-sub- Here, can fix (log (t))² and thus 2 1 log & sulfices. Hence, by the property of sub- Weibull distributions (Definition G and the fact that each bucket of size b,
Weibull given 2 exp( yF) log J.-
res(n, k/44)
log -
)) Se
P Pn
X
71
Theorem 16 (SCA Learning Error). Given stream length [<l 2 Tn (5, generated from bounded tail distribution μ. SCA with bucket width sets #buckets to k 2 Tk (E,b) and outputs Q, such that with probability at least 1 5, Qua.n (i) @(1) s for all E I.
Tail Condition
Tu (E,
(E, b)
0₂ Ty-sub-Gaussia
log (t)
Sa
log (1)
b
a-sub-Weibull
log
26 (log (1
Proof of Theorem 16 Step Bounding the residuals in frequency estimation under tail condi- tions. For sub-Gaussiaa distributions, by Lemma 11 we know that Pn generated by p (T, sub-Gaussian given n 2 cexp log (t). Here, we can fix t 20 v log (2). Hence, by the property of sub-Gaussian distributions and the fact that each bucket of size b,
res(n, k/4)
4
E 4
20 u
log
(10)
71
am
12 we know that smn generated by p is (r, (eo-sub--eibull given exp( v/) log 3. Here, we can fix (log )2)) and thus > ze log & suffices. Hence, by the property of sub-Weibull distributions (Definition 6 and the fact that each bucket of size b,
For a-sub- a-sub-Weibull Weibull distributions, by Lemma
res k/44
4 (
)
X
c log
(11)
n
Step 2: Bounding the error in CDF estimation.
25

---

Published in Transactions on Machine Learning Research (01/2026)
Port i. Now, we have:
Fj F.
Qur.n (1)
-Q(1)
N
max, Fj
F Fi
since n 2 max Fj
2 res res(n, (n, k/4)
By Lemia 15
n
E
By Equation 10 and
Parl ü. Now, we look into the other side of the error. First, observe that:
(es(n,k/4) 2 2 (ns,
2 res(n, k/4)
SE
Here, the first inequality given by the fact 2res(n, k/4) S n, and the second inequality follows from Thus,
F.
(1) - Q Qun. (1)
max,
Fj
N
F
F
since F; > F.
max, Fj
N
1
F.
max, F2
12
S F
since max PJ max Fj res(nn = n res(nn
n1 - resl n, k/4)
n
3
2 res(n, k/4)
F.
n (n res(n, k/4))
res(n, k/4)
F; S n
n - res (n, k/4)
4 (es((n,
n 4 res (n, k/4)
S 8
By Equation
10 and 11
D Estimation Guarantee of SWA
In this section, we state the proofs for Theorem 18 We start with Lemma 32 which shows that bucketed
empirical measure Pa,n is close to the underlying empirical measure pn in Wasserstein distance given the bucket size is sufficiently small.
Lemma 32. Given distribution μ and corresponding ph Dise with bucket size we have:
Wp (H, Disc) < b
Proof. For any i-th bucket corresponding to pisc, we have:
b 2 (B. + b +2) Qupiso (Bi (Bi+
26

---

Published in Transactions on Machine Learning Research (01/2026)
2z' (x) - -Q -Q (x) S b
Hence, we have:
: (L. (2)((() (ppina dx) S s <(o 6 dx =
Wp (p, pb ptec)
This concludes the proof.
A general version of Lemma 32 is given in Staib et al. 2017 Theorem 4.1). However, we prove our version here for simplicity and case of access.
Next, we prove the following lemma that characterizes the approximation of a function based on an approx- imation guarantee on its inverse.
Lemma 33 (Inverse Approximation of inverse L-Lipschitz functions). Let be E bi-Lipschitz function. Given an estimate f of f such that f(x) E [f(x) e, f(r) + E), we cun construct an estimate f-1 of the pseudoinverse function f-1 such that Vx E Range(f):
( (a) le, f- (x) Ce]
Proof. We construct f-1 as (y) = ming fo R (-x) f(x) = w). Let us consider x E Range()), and (=) y1 and f-)(x) V2: and w.l.o.g. assume U2 2 V1- Then, we have:
f(y1) f(y2)
f(v)) +E f(y2)
2 f(yz) f(y1)
Next, use the fact that the function f is f bi-Lipschitz to show that y2 81 is bounded by le:
- V1 (f - <e(f(re) - f(vz)) s EE
By definition of f-1
Hence, for any x E Range(f), we have -f) < le, completing our proof.
The following corollary follows directly.
Corollary 34 (From CDF to Inverse CDF). For an i bi-Liscchitz distribution i with CDF Qu and pseu- doinverse CDF Op', given an approzimate CDF Qu satisfying (Q₂z Qn(x)) $ e, V. E R, we construct approrimation of pseudoinverse CDF Q such that Vr [0, 11, QQ (x) Q,)((x) le.
Now, we prove the Theorem 18 We restate the theorems here for ease of reading:
Theorem 18 (Universal Learning of SCA in W. (.)). Given |s| 2 In (e,, E, generated from bounded- tail distribution u and 8 E (0, 1), if we set the bucket width b = e/2, then SCA uses Tx (ly,8) buckets (L.e. space) and outputs Pn, such that P(W, (Mn) 2 8) < 6. We omit the constants in Tn E, 8) and To (Ln for simplicity.
Tail Condition
Tn (L 5, log (1/5) max
Ty. (LyTE)
Aa-sub-Gaussin
12
2u log
p2
a-sub- Weibull
a-sub-Weibull
log (1/5) max
12
log
27

---

Published in Transactions on Machine Learning Research (01/2026)
Proof of Theorem 18 By Theorem 17 16
and Lemma 33 and the parameters we have used, have with
probability 1 - 6:
Que/an - - S 24 Q - 0 e/2
Hence, by Lemma 2 we have with probability at least 1 - 8:
Wp (n)) S Wp (Ma, Me/2,n) + Wp (Pe/2.n
$ = (%/ 10 -r)
1/0
5 + (fo |E/2|P dr)
1/0
=E
The bound on number of buckets can be obtained by plugging in the values in the line 3 of Algorithm 3 Theorem 16
We now proof the Theorem
19 restated here for ease of reading:
Thcorem 19 (PAC Guarantee of SWA). Given Kl distribution μ, with bucket width b e/2, then SCA uses Tk (e) space and oulpuls On such that PPW (a) S E) 2 1 - 5. This further shows that for stream of size =0 (c(-2log(1/00 from two
Tn (,,, generated from bounded-tail
distributions and v, SWA yields
[1 (Prx Pn)) - Wi (H, S 48
(3)
with probability 1 - 28. Here, E 1041/4] and 8 E (0, 1/2]. Here, - max fop ou0, & max (lps (x). We omit the constants in Tn (6)) and Tk ()) for simplicity.
Tail Condition
In (Lyss C,
Th (lyx
σ o-sub-Gaussian
log (1/8) max 22 12
log (2)
a-sub- Weibull
log (1/5) max
:T (log] 1) 20-1
e2
(log
Proof. We combine the results of Corollary for sub-Gaussian distributions, we have with probability 1 26:
44
45 and Theorem 18 to establish this result. By Corollary 44
W (p, 2) - Wi (Mn v22 2:
By Triangle Inequality
(12)
Similarly, by Corollary 45 for a-sub- Weibull distributions, have with probability 25:
Wi (M, v) - Wi (Mn, vw)l S 2e
By Triangle Inequality
(13)
By Theorem 19 we have with probability 26:
[Wi (fis Pa) Wi (Pny Un) 2s
By Triangle Inequality
(14)
A union bound argument and triangle inequality over Equations
12
13 and completes the proof. E
E
Estimation Guarantee of STVA
In this section, we prove the theorems concerning STVA, i.e. Theorem
21
Lemma 22 and Theorems
23 and
24
28

---

Published in Transactions on Machine Learning Research (01/2026)
E.1 Proof of Theorem 21
In this section, we detail the proof of Theorem 21
Theorem 21 (Bucket Width for TV Distance Estimnttion). Given a bounded-tatt taad distribution f with 4p- Lipschilz PDF and a corresponding bucketed measure ph, if we fir the bucket width To (e, E), we have TV (p) S
Tail Condition
Uu-sub-Gaussen 2 (log(2ea/1))
Beib-ll
Th (p)
Proof. Initial Bounds: The distribution μ has fn-Lipschitz PDF. Consider any bucket LI of size then mingeu
u(y) min) Li:
maxyeu m(v) S b6y- As minyeu mly) S ps(x)) maxyeu p(y), Va U, have for any bucket
lu(x) - 1x(x)) $ Plp
Væ EU
J, [(mCa)) pb(x)) (oo())-<(x))1d0 dx s bpp
(15)
The main idea of our proof is that we bound the error due to bucketing in buckets with high frequency and use the fact that the remaining buckets has sufficiently small frequency to achieve our bound. To denote the buckets with high frequency, recall that Topı denotes the of & buckets with highest frequency, b denotes the length of each bucket.
TV (u, Mb)
(m(xr) (1)) dæ
(16)
Σ
(m(x)= - (6(2)) dr
2
LIEB"
[m(x)= (o(x)) dx + Σ / lu(x) - mo(x)) dr
2
LIETopE
LeTTpe
1
Σ [ S. p(z)dr))
bl4 +
By Equation
2
LIETTpE
LETopk
<kb2t 2xb2t//22+
Σ
((r)dx
LeTopp
(17)
Sub-Weibull Distributions: For a-sub-Weibull distributions, we fix h: E, (u(log(2c./e))" 22)) and bucket size 17]. For the first term, we have:
f (log(2ng//)) /c)/" and bound the terms in Equation
1b2 cx 2
en (log(2ca/E))
(
E en (log (2ca/E))
2 E/ SE/2
(18)
2
For the second term:
Σ
1 [())da= = P
x E op ())(2
Xou
Lo e. (0x22/6)22
2ca ) 07
)
P X
X >
log
5 5e/2
(19)
29

---

Published in Transactions on Machine Learning Research (01/2026)
Combining Equations 18 and 19 with the bound from Equation 17 we obtain the result.
Sub- Lub-Gaussian Distributions: For sub-Gaussian distributions, fix k Li log(2/e) and bucket size and bound the terms in Equation 17 For the first term, we have
optn g.lu/log(22) log(2/e)
2 Lx
k62Lz S2lp log(2/s)
S 8/2
(20)
8
oulu ValaVlog log (2/e)
2
For the second term:
/ ((x)dx==
E
E Uue
X-u
of log(2/c)
Top 2 log (2/4)
$ P X~p
x
log (2/e)
S:/2
(21)
Combining Equations (20 and 21
with the bound from Equation
17
we obtain the result.
E.2 Proof of Lemma 22
Consider the two possible ways of looking at histogram. Given histogram defined over I, one can think of it defining (not necessarily probability) measure over R defined so that the mcasure at cach point is equal to the frequency of the bucket the point lies in. Alternatively, one can define a measure over the buckets with the measure at each bucket is equal to the frequency of the bucket. In this section, we formalize these notions and establish the relation between them in term of TV and Wasserstein distances.
Definition (Bucketed Continuous Distribution). Let be a distribution supported on a (finite or infinite) closed interval S E with (discrete or continuous) measure μ. Given zo as reference point in I and 6 as the bucket width, we further represent as (z0, b) & Ufef(m + + xo + (j + 1)6). Here, index set J C Z. We define the corresponding bucketed continuous distribution DCont with mcasure 14 (oCont defined over I C R as:
+oo
Cant (x:
((x)dr
14b
Jo+jb
n (1zo + jb, zo + (j (j+ 1)6))
where x E [mo + jb, xo + (j + 1)8).
Definition 36 (Bucketed Discrete Distribution). Let D be a distribution supported on a (finite or infinite) closed interval C R with (discrete or continuous) measure μ.. Given 2g as a reference point in and as the bucket width, we further represent. as T(rro b) A User|mn + jb, wo + (j + 1)b). We define the correspouding bucketed discrete distribution Dissc with measure ng pise defined over Uses +=o++b+bbb)))) E (10+()+1) u(x)dz= u ([zo + jjj zo (j + 1)6)).
Ho, (isc(() Saa+-5
The support set of pisc inherits the metric structure of R. For ease of notation, we express the distance between the i-th and j-th support points of pa as d(L -
We introduce the following lemma establishing the equivalence of bucketed discrete and continuous measure with respect the TV distance.
Lemma 37 (TV of continuous and discrete bucketed distributions). Given two measures μ., and v, we have:
TV (ngone
Cont
1y Contt TV Pisc ub Dise)
30

---

Published in Transactions on Machine Learning Research (01/2026)
Proof.
/
TV (rg
Cont 1/ v)oon))
140
Cont
(x))(())) do
Cont
2
(
(20-1++110
mottiitjo
u(r)dz
u(z)dr dr
2
JEJ
#0+
100
Jaotso
Bo+(++166
(oo+(+110
1
((x)dx- - 20040
v(x)dx
2 JEJ
z0+56
TV
(ppioe, viscc
We now establish TV distance concentration result on bucketed empirical distribution corresponding to mub-Gaussian distribution.
Lemma 22 (Concentration in TV over Infinite Buckets). Let pn be empirical measure generated from
discrele buckeled measure Nh corresponding to a bounded-late lail distribution μ4, and, s, (0, 1). Then, for
2 b)), P P(TV (n, 2 E) < 8. Here, T() denotes the Gamma function
Davis 1959
Tail Condition
-u-sub- Gaussian
Q-sub- Weibull
Tn ())
max
40pyE log (1/6) c- max
2a [(1 + a), log (1/8)}
b
Proof. Let us consider the standard bijection from E to N as:
2x
i
f(x) = 2x+11 if
Su--Su--auussan Gaussian Distributions:
For sub-Gaussian distributions,TI is even, we have:
Pb²
pli) = 14
Disc (iso((Us/2) S 4b
Disc (Ug20/2L1r) S u(fx|x 2 bi/2}) s 2exp
40 (-ozz
If is odd, have:
1i-1)
(i- 1)
p(1) - 14b (U-(i-1)/2) S 1b
Disc
Disc (U/s-((-1)2LU)) u((x|x < -bi 1)/23) 2exp
4 14
Combining these terms, we have:
Σ Pin( Σ 4exp 4exp((i86//40))) S VEN
/ exp(-x20²² 20 /2 = 2/ ATO
40 40
b
SEN
We now combine this with Lemma 42 to complete the proof.
a-SubWeibull Distributions: For a-Subleibull distributions, if even, we have:
p(i) uuf (isso(UL/22) S 1e Dise (U)28/2L)) S u([x|v 2 bi/2)) s c. exp (-(1))aa)
If is odd, have:
31

---

Published in Transactions on Machine Learning Research (01/2026)
p(i) = (L- S 14
Disc (U/5-((-1)22L5) s u((=|> S -b(i 1)/22) s ca exp (-((i- (1))))))/oo
Combining these terms, we have:
2ca exp (-(1b)2/a) 2ca (" exp (-(xb)lia) dr 2ca
T(1 + a)
Σ VPP(() Σ
2ca
b
iEN
We now combine this with Lemma 42
complete the proof.
E.3 Bounding Errors of SPA and STVA (Theorems 23 and 24
Theorem 23 (Learning Error of SPA). If SPA accesses stream of length [5|= n 2 (e,6) 6) from a bounded- tail distribution, and uses Th () buckets to output sublinear summary Pan then with probability 5, TV (Pas n) S Ilpan Pus. E.
Tail Condition
Tn (e, 6)
(e, b)
of casssuuGGassin
log (1)
8e log (9)
a-sub-Weibull
llog (1)
j (log (E))
Proof. Step 1: Bounding the residuals in frequency estimation under tail conditions. For sub- Gaussian distributions, by Theorem 11 know that Ma.n generated by p pisc is (r, sub-Gaussian given 2 cexp log (t). Here, we can fix 20 2 / (9). Hence, by the property of sub-Gaussian distributions and the fact that length of each bucket is b,
(ns(n,
6 log
P Mb.n
X >
20 w0
(22)
6
For kesub-Weibull distributions, by Lemma 12 we know that en generated by p is (r, (r,a)--ub-Warr Weibull given exp( (7) log J. Here, fix (log (g)) and thus log suffices. Hence, by the property of weibll distributions (Definition 6 and the fact that each bucket of size b,
12
res res(n,, k/4)
n1
2)
6
P pn
X >
log
(23)
32

---

Published in Transactions on Machine Learning Research (01/2026)
Bounding the error in PDF estimation. Now, proceed to bound the TV Distance. We denote by Tops the set of k elements with highest true frequency Si- Then, we have:
Step 2:
p Pa 111 = Σ PM (1) -(()
4 res(n,
Sa Si
max
Theorem
n
n1
n
res(n, fess(n//// k/4)
J1
fi f
res (n, k/4)
fi
<
iEToPH/4
iēTOpk/a
4 kn,
Eie LearrnniiggTTop St EigToppjs fi
n
71
4 res (n,
res(n,k/4)
Lemma
n
ress(n (n,,k44))
n
<
E
Equation 22 and 23
We now proof the Theorem 24 restated here for case of reading:
Theorem 24 (PAC Guarantee of STVA). Given e E (0, 1/6), 5 E (0,1/4), a stream of size n 2 Tn (8, E, from two bounded- tail and L-pisschitz distributions i and v, and bucket width b = Tb (E,E, STVA uses Tk (s, 8) space and
P TV (Dan Pv) - TV (m, 2) 62) S 48
(4)
Here, max o
Jy l
max (lus lv). We omit the constants in nn (L e, and To (lus for simplicity.
Tail Condition
Tn (,)
Th (E,
(E,
--sub-Gaussian
max
a PElog(1/E) log (1)
a²t log (2)
af 1og(2//c)
a-sub-Weibul Weibull
max
Alog(1/c)) T(1 + a:), log (1)
(log (t)
E(log (2))
Proof. Composing Lemma 22 Lemma
37
Theorem
21 and Theorem 23 yiclds the proof.
By Theorem
21 and Lemina
37
have:
TV (1, v) - TV (nnont wfout)) < 28
By Theorem
21 and Triangle Inequality
TV (4,v) TV (n Soplec,pieg Disc)) <
By Lemma 37
(24)
From Lemma 22 and fixing the b, we have with probability 28:
TV (po,ns Ph.n) TV pisc, (epee, piso) < 2e
By Triangle Inequality
(25)
From Theorem 23 we have with probability 1 28:
TV (Dny Pa) TV (Ju,,, vb < 2s
By Triangle Inequality
(26)
A union bound argument and triangle inequality over Equation
24
25
and
26
completes the proof. 7
33

---

Published in Transactions on Machine Learning Research (01/2026)
F Useful Technical Results
Lemma 38 (Inverse of Bi-Lipschitz function is Bi-Lipschitz ). Given invertible function f Dom f + Range f that is l bi- bi-Lipschitz, the corresponding inverse function f=! RRange f - Dom f is also bi- Lipschitti with parameter& l.
The following corollary is directly implied from Lemma 38
Corollary 39 (Bi-Lipschitz CDF implies Bi-Lipschitz Inverse CDF). A distribution satisfying Assumption g has bi-Lipschita inverse CDF.
Definition 40 (eibulWeibull Distribution and Random Variable Vladimirova el al. 2020 ). A distribution is said to be a-SubWeibull if there exists some constant Ca for any 2 0, we have:
xx S ca exp (-t!/a)
Pr X-p
(27)
Correspondinly,, the random variable X drawn from ju said be SubWeibull random variable.
Lemma 41 (MGF Charecterization of Sub Theoerr 2.1 in Vladimirova et al. (2020))). )). Given X be a-Sub Weibull rendom voriable, then the MGF of |X| satisfies:
3c 0 such that E expp (17 (1(1x))))) s exp (17))//a
for all 7 such that < 1/c.
Lemma 42 (Truc Mcasure Concentration (Cohen al.] 2020)). For measure μ defined over a simpler An and corresponding empirical distribution Un, generated by n samples, for any E, E (0, 1), there erists constant such that 2 c2 mmax Eien vp(i), log (1/6)..
have with probability 1 1- 8,
Pr[TV (1, pm) 2 6) 2
Lemma 43 (Concentration of Empirical Measure In Wasserstein Distance (Theorem 2 in Fournier & Guillin 2015 Let be distribution on R. Then for all p E N,
Tf Ba < 1 0 such that E. FOXD (()1 < 00, then,
FMW (H, 2 8) S exp (-one?) + exp (-onsl/na
If (2.20), ,y> 0 such that E exp (xx1x)) < 0o, then,
P PM (M. 2 E exp (-ene²) + exp (-o(ne) 1/2pa
The Lemma 43 implies the following two corollaries:
Corollary 44 (Concentration in Wasserstein distance of Empirical Measures over R Bhat & L.A. 2019
Given an empirical measure pn generated by n i.i.d. samples generated from a subGaussian measure l over R, we have:
P [[W (p, 26 S exp (-one?)
Corollary 45. Let μ be distribution on R such that 3o E (1, 00), x such that E Texp (z/11)) 00, then,
P [Wi (m)) 2 2) S exp (-ene?) + exp (-c (nE)2/222) 2/2a)
34

---

Published in Transactions on Machine Learning Research (01/2026)
Lemma 46 (Strong Demographic Parity and W1 (.) distance (Jiang et al. 20201). Let f. I [R] [0. be function where [k] denotes the sensitive altribule. Let us denote the output distribution of f corresponding to the sensitive attribute s E [k]. Then, we have for all s, E [k]:
8 2 d
Wi (1a))e))
U
Lemma 47 (Privacy and Hockey Stick Divergence Balle et. al. 2018
For given E R, mechanism
M is (oiffrllilyyentiaall private if for all X, X' with Ham X, X
= 1:
Ha (M(X)IMM x)) S 3
where Hoa (ull)) is colled the Hockeystick divergence between μ and v. Lemma 48 (From HSD to TV Approximation (Koskela Mohammadij 2024)). Given two mensured p., v and their TV distance approzimations Pnns in satisfying TV (p, E, and TV (pay Pn) S E; have for all R:
Hew (u|lv) S H (An (px) (1 + e
35

---

Published in Transactions on Machine Learning Research (01/2026)
G Experimental Details Fairness and Privacy Auditing
G.1 Fairness Auditing
Group faimesss measures in ML model's prediction mcasure the disparity in prodictions of ML models across different subpopulations. The subpopulations correspond to a sensitive attribute (e.g. gender, economic status, ethnicity etc.) on which they should not be discriminated. Fairness auditors try to estimate violations of such group fairness measures by querying a model and then collecting the responses (Ghosh et al. 2021
Yan & Zhang 2022 Chugg et al. 2024 Ajarra et al. 2025
A popular group fairness measure is demographic parity (Feldman et al. 2015).
Definition 49 (Demographic Parity). Given O C IR and sensitive attributes [k], a regression function
f : 1 x [k] + satisfies demographic parity if for all 8, s' E [K], we have supteo P(f((,,) s) s t) t)-P(f(X,s) s') S
0) = 0. For classification, S = [0, 1] and the definition is referred as strong demographic parity (Jiang et al.
2020).
Jiang et al. 2020 show that bounding strong demographic parity is equivalent parity is equivalent to bound- ing the maximum of 1-Wasserstein distance between the output distributions of any two subpopulations. This motivates us to use SWA to estimate demographic parity for ML models.
We test accuracy and sublinearity of SWA for fairness auditing on the well-known ACS Income datasct (Ding et al.) 2021). We test both on lincar regression (d = 10) for income as output and classification with logistic regression (d 10) for income above and below 40000 USD as outputs. We compute Wasserstein Distance between the distribution of outputs of linear and logistic regression models for male and female data points of model trained ACS Income data. We use 3 1 train-test split for both cases. We use scikit-lcarn (Pedregosa et al.) 2011) to train both the models, and use the 'liblincar' solver for logistic regression. For reference, we compute the distance between the bucketed versions of the output distribution exactly. We choose the bucket size to be 10 and 0.01, for the regression and classification tasks, respectively. For the regression task, we increase the number of buckets as {500, 1000, 20000]; and for the classification task, we increase the number of buckets as {50, 100, ................................ 1250}. Finally we report the multiplicative approximation error of our estimates w.r.t. the true distance in both the cases with increasing nunber of buckets. We run each of the experiments 50 times.
Experimental Setup:
Results: Sublinearity of SWA in Fairness Auditing: We use 416625 total samples consisting of almost half male and female samples each. The sample streams arrive via S = 10 sources. For the linear regression model, the approximation error drops below 0.1 when we use 12500 buckets. For the logistic regression model, the approximation error drops below 0.1 when we use 750 buckets. The difference #buckets is due to the difference in variance and the width of buckets used in each case.
G.2 Privacy Auditing
Differential privacy (woork 2006) is now considered as the gold standard for data privacy protection. It aims to keep imput datum indistinguishable while looking into outputs of an algorithm.
Definition 50 ((a,3) Differential Privacy (Wwork 2006)). An algorithm f X + y is (a, 3)- differentially private if for any X, X' with Ham X, X') 1 and VS S V, we have P(f(x) E S S ea (]]
An equivalent representation of differential privacy is Hat (M(X)JMM(X)) (X)) S B Balle et al. 2018 where Hockey Stick Divergence (HSD) is defined Hr (ы(lи) & fxlu(s) -x(x)) Recently, Koskela & Mohammadil (2024) show that estimating the HSD of two distributions is equivalent to estimating the HSD and TV distance between their empirical counterparts. They construct histograms over outputs of a black-box auditor and use this result to estimate TV distances for privacy auditing. As auditing privacy is data intensive, it motivates us to use STVA in this setting.
We adopt the experimental setting of Annamalai & Cristofaro 2024)) and compute the TV distance between the output distributions of logistic regressors trained on neighbouring datasets, say IN and OUT, sampled from MNIST (LeCun 1998
36

---

Published in Transactions on Machine Learning Research (01/2026)
We study the performance of STVA in the case of privacy auditing. We generate losses for datasets with and without canary using the work of Annamalla & Cristofaro (024). We run logistic regression on MNIST dataset with 50 epochs and a = 10. We denote the losses with and without canary to be lossesin and lossesin, respoctively. We obtain 1000 samples losses for both the cases and take these losses as the distribution of interest. We choose the bucket size be 0.01 for the logistic regression task. The mean of lossesin and lossesout are -2.3194 and -233241, respectively. The standard deviation of lossesin and lossesout are 0.005654 and 0.005535, respectively. We increase the number of buckets {10, 20.................... 100). Finally report the multiplicative approximation error of our estimates w.r.t. the true distance in both the cases with increasing number of buckets. We run each of the experiments 50 times.
Experimental Setup:
Results: Given 1000 samples, Figure c show that STVA computes the TV distance between output dis- tributions for IN and OUT datasets. The sample streams arrive via S = 10 sources. The approximation error drops below 0.1 while using only 250 buckets. This shows STVA can conduct resource-efficient privacy auditing of large-scale datascts.
37

---

Published in Transactions on Machine Learning Research (01/2026)
G.3
Enlarged Plots
0.8
2.5
Estimated Distance Approximation Error
Wasserstein Distance
2.0
0.6
True Distance
TV Distance
1.5
0.4
1.0
0.2
Estimated Distance
0.5
Approximation Error
0.0
True Distance
0.0
200
400
600
800
200
400
600
800
#Buckets
#Buckets
Figure 7: Performance SWA with 5), W(1,5) Figure 8: Performance of STVA with (11,))
and 0.05
and b = 0.05
0.30
0.150
Approximation Error
0.125
Approximation Error
0.25
0.20
0.100
0.075
0.15
0.050
0.10
0.025
0.05
0.000
0.00
5000
10000
15000
20000
200
400
600
#Buckets
#Buckets
Figure Auditing with SWA on regression output of Figure 10: Auditing with on classification out- ACS Income
put of ACS Income
Approximation Error
1.5
1.0
0.5
0.0
20
40
60
80
#Buckets
Figure 11: Privacy Auditing of logistic regression MNIST.
38


Reviews:
[{"review_id": "Iox3WaY3yF", "reviewer": "Reviewer_pZMk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of estimating the distance, in either the TV or Wasserstein sense, between two distributions. The distributions are assumed to be either sub-Gaussian or sub-Weibull, and have densities satisfying certain Lipschitzness properties. The authors build on previous techniques which estimate distributions using bucketed empirical distributions, for appropriately chosen buckets. The authors also analyze the space complexity of their algorithms. Notably, the authors allow the support of the distributions in question to be infinite.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Unfortunately, there are several issues with the analysis.\n\n- Lemma 29: It is not true that a bounded second moment implies subgaussianity, nor is this what Proposition 2.5.2. of Vershynin 2018 states. \n\n- Theorem 16 claims the discrete distribution is bi-Lipschitz. How can a non-continuous function be Lipschitz? It seems to me the proof is also incorrect as it does not take into account the case where |a-b| is very small. Sometimes people call the property $|f(a)-f(b)| \\leq \\ell |a-b| + \\tau$, for small $\\tau$, the \"generalized Lipschitzness\" property. I believe this property would be satisfied by the bucketed distribution, and may suffice for the authors proof ideas.\n\n- The paper claims that \"Any bounded distribution with continuous and compact support\" has bi-Lipschitz CDF. Could the authors elaborate on what bounded means? I don't see how bounded support implies bi-Lipschitzness. Even a distribution over the unit interval could ''spike'' arbitrarily quickly at some point. In any case, this statement does not mean much without some comment on what the bi-Lipschitz constant is.\n\n- Related, the authors claim that Gaussians are Lipschitz. I suppose this is true, but this Lipschitz constant could scale poorly in the variance. \n\n- Are Lipschitz/bi-Lipschitz assumptions on the CDF/PDF standard/reasonable assumptions? I am not overly familiar with the literature on distribution estimation, but it seems odd to assume this in addition to sub-Gaussianity.\n\nMinor comments:\n\n- $n^{Res(\\tau)}$ notation is confusing. If this is not $n$ raised to the power $Res(\\tau)$, why not just use $Res(n,\\tau)$?\n\n- What is does $k^* $ represent in Lemma 4? Why can we pick it to be $k/2$? I could not find an explanation of $k^*$.\n\n- For Algorithm 5 in Appendix A, what does ``$T=T\\cup {\\xi_i} // |T| \\leq k^* + 1 \\leq k$ after this line'' mean?", "audience_yn": "Yes", "audience_explanation": "Ostensibly these result would be of interest to the TMLR community, but only with more explanation on what the Lipschitz and bi-Lipschitz conditions imply. Noting that exponential family distributions satisfy these assumptions is great, but is of limited use without explaining what the Lipschitz constants evaluate to. This is something I believe could be easily fixed, and after that I believe these results would be more useful to the broader community.", "requested_changes": "The errors I mentioned previously need to be fixed if this paper is to be accepted. It may be possible that the analysis still works after these errors are fixed, but unfortunately, these errors occur at early and fundamental points of the analysis. Fixing them may require substantial changes to the paper, which worry won't be practical during the review process.", "broader_impact_concerns": "N/A", "additional_comments": "Edit: Based on the authors response, it seems the concerns raised in my review have succinct fixes that do not have significant downstream impacts on the paper. As such, I have updated my review and will indicate acceptance.\n\nAs a minor final point regarding the Lipschitzness issue. In my review I'm referring to Lipschitzness in the sense the authors have defined via definition 8 (over a continuous domain). However, I see the author's point that this will not affect the mechanics of the proof. An updated definition would be nice if it is important for the paper to use the more general notion of Lipschitzness.", "extra_scores": {}, "extra_text": {}}, {"review_id": "KeH0kMtHsk", "reviewer": "Reviewer_3TFq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a method for estimating the pdf and cdf of a distribution from a stream of samples with (a) bounded estimation error while (b) ensuring sublinear space and time complexity in the number of samples.\nHaving such estimates for two distributions $P,Q$ also allows for estimation of their Wasserstein distance and total variation distance with bounded error. These, in turn, have applications in auditing fairness and privacy, respectively.\n\nThe proposed method build upon existing methods for \"mergeable summaries of histograms\" (MMG). These methods essentially keep track of the $k$ most frequent values from a stream. If $k$ is large enough to contain most values observed in the stream, then it is possible to provide a good estimate of the complete histogram of observed values. \nNaturally, for finite $k$ this approach breaks down when the stream of data is sampled from a continuous distribution.\n\nThe first contribution, estimation of pdfs and cdfs for continuous distributions, largely proceeds as follows:\nAll samples coming from the distribution are quantized to allow for computation of a histogram (with infinitely many quantization bins).\nInstead of materializing the full histogram with infinite space complexity, or a sparse histogram with linear space complexity, an approximation is computed via MMG with $k$ bins.\nAssuming expontentially decaying tails on the continuous distribution, and sufficiently large $k$, it is likely that the sparse histogram is estimated with small error. This is because most values from the stream will fall into one of the $k$ buckets. The authors further prove that these small errors in the MMG histogram translate to a small gap between its empirical pdf/cdf and the pdf/cdf of the continuous distribution.\n\nThe second contribution, estimation of Wasserstein distances, can be summarized as follows:\nIt is known that Wasserstein distance can be computed via the inverse cdf of two distributions.\nThe authors show that, under mild regularity conditions, the previously derived error bounds on empirical cdfs translate to small differences between the true inverse cdf and the empirical quantile function. This is shown to impliy a good approximation of the Wasserstein distance.\n\nFor the third contribution, the authors show similarly that the small errors in approximating the pdf lead to small error in apprxoimating total variation distance.\n\nThe proposed methods are evaluated in their ability to approximate known total variation / Wasserstein distance for simple distributions (Gaussians) for varying numbers of MMG buckets. They are further evaluated by plugging them in as better estimators of total variation / Wasserstein distance in two experiments from prior work on fairness / privacy auditing, respectively.\n\n### Strengths\n* The proposed method is a sound and natural solution to the considered problem and makes creative use of methods developed for a different purpose\n* The method has applications in ML fairness and privacy, including federated settings, and is thus a good fit for the venue.\n* The level of abstraction in discussion of the overall proof strategy and presentation of key theoretical results is well-chosen\n* The manuscript is indredibly well-structured and has a clear narrative. For example, Section 1 uses a parallel structure to discuss TV / Wasserstein distances / mergeable history, which always ends in some clearly defined research question.\n* Related work is discussed in sufficient breadth\n* Limitations (end of Section 6) and underlying assumptions are discussed to a sufficient degree. The assumptions are, in fact, explicitly highlighted (see bottom of p.5), and the authors make a good argument for why they are reasonable / not overly restrictive\n\n### Weaknesses\nI don't see anything that I would consider a major weakness within the TMLR reviewing framework. Nevertheless, here are some points that I would generally consider a weakness, \n\n* The method assumes scalar distributions. This limits its useful in fairness/privacy auditing (e.g., directly auditing model parameters released by DP-SGD or auditing models other than classifiers/regressors).\n* The usefulness for privacy auditing of scalar mechanisms also seems a little overstated. The proposed method can, of course, be used for auditing $(\\epsilon, 0)$-DP, i.e., total variation distance for scalar mechanisms. But the discussion of (Koskela & Mohammadi (2024)) in Appendix G.2 implies that it could also be user for auditing $(\\epsilon, \\delta)$-DP. However, looking at their Lemma 11, it appears like the proposed method can only be used to test some sufficient conditions for a bound on privacy profiles, but not to actually evaluate the bound\n* The evaluation on Gaussian distributions in Section 5 is somewhat narrow. What about other Sub-Weibull distributions, other number of samples, other parameters for the Gaussians etc.? But since these figures only serve to illustrate results that have already been formally proven, I would not consider this a major weakness.\n* Section 4.2 lacks some motivation, which disturbs the narrative flow. See \"Requested Changes\" below\n* Algorithm 1/2 are not self-contained and thus hard to follow. They refer to a larger algorithm from Appendix A, which is never referenced in Section 4. See \"Requested Changes\" below", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes, all claims around errors / space complexity / runtime complexity are supported via proofs\n* that follow a sound and clearly presented strategy\n* whose intermediate technical steps are clearly laid out in the Appendix\n\nAs mentioned above, the empirical evaluation based on approximating distances between Gaussian distributions for some narrow range of parameters is somewhat weak. But since these experiments serve more of an illustrative function than to support any claims about SOTA-ness, I would not consider this as violating the acceptance criterion.\n\nSimilarly (even though it is not an explicit claim), the discussion of auditing for approximate DP in Appendix G.2 is potentially a little misleading. However, it does not contradict any explicit claims made in the paper.", "audience_yn": "Yes", "audience_explanation": "The connection to fairness/privacy makes this work relevant to the trustworthy ML community, and estimation of optimal transport distances is also obviously relevant for various other sub-fields (e.g., generative modelling.)", "requested_changes": "### Critical\n* Update Appendix G.2 to make it clear whether the proposed method can be used for auditing $(\\epsilon,\\delta)$-DP or only $(\\epsilon, 0)$-DP. If I misunderstood something here, feel free to correct me during the discussion period.\n\n### Presentation (non-critical)\n* Repeat the motivation for why the empirical distribution is bucketed before applying MMG in Section 4.2.A. So far, it is only mentioned in passing in the contributions list of Section 1. \n* Reference Algorithm 5 in Section 4.2 or add an import statement to Algorithms 1/2. Otherwise, it is not clear what Merge(T2) is supposed to refer, what the difference between Merge and MMG*Merge is, etc.\n* Potentially use two different words for \"buckets of MMG\" and \"buckets of the quantized histogram\". Maybe \"buckets\" and \"quantization bins\"?\n* Make the first two italicized research questions in Section 1 consistent. It currently looks as if they had different assumptions: \"two continuous distributions with infinite support\" vs \"two distributions\" and \"if we obtain a stream of n samples\" vs \"number of samples n\".\n\n### Typos etc.\n* Typo \"WasseSRstein\" in Section 1\n* Missing number after \"We choose the bucket size to be []\" in Appendix G.2 \n* Missing word in \"Mergeable Sublinear Representation of Distributions\" paragraph of Section 1: \"summary of a distribution from the data stream [THAT] can address the [...]\"", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QQyg5xqaE6", "reviewer": "Reviewer_DJUY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper makes a strong theoretical contribution to sublinear distance estimation by unifying discrete and continuous settings and providing explicit error bounds. However, its practical generality remains limited: the framework targets only univariate cases and is evaluated on simple datasets with simple models consisting of logistic and linear regressions. These experiments confirm theoretical soundness but offer limited guidance for practical use. Showing even small-scale or conceptual examples that connect the framework to real-world AI workflows would make the paper substantially more appealing to applied researchers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Pros:\nThe proposed framework can be considered more general than prior approaches, at least in a theoretical sense. It unifies discrete and continuous settings, extends the tail assumptions from sub-Gaussian to sub-Weibull distributions, and supports multiple distance metrics under a single mergeable structure.\nFinally, the paper provides explicit theoretical error bounds for the proposed mergeable sublinear summaries, which is an important and often overlooked aspect in prior work. Understanding and bounding the approximation error is crucial when summaries are merged, since small local inaccuracies can compound during aggregation. This paper fills that gap by establishing provable error guarantees for both sub-Gaussian and sub-Weibull distributions, thereby strengthening the theoretical foundation of mergeable summary methods.\nCons:\nThe practical generality of the proposed framework is limited. While the theoretical formulation is elegant, it only applies to univariate distributions over ℝ in practice. Most real-world datasets are inherently multivariate, and the paper does not discuss how the proposed methods could extend to higher-dimensional settings. As a result, some readers may find it difficult to see how this framework could be applied beyond simple one-dimensional cases.\n\nFurthermore, this limitation is reflected in the experimental design. While the theoretical contributions of the paper are well established and do not necessarily require extensive experimentation, the work provides limited illustrative examples that could help AI researchers see how the proposed framework might be applied in practical machine learning contexts. The experimental evaluation focuses only on simple datasets such as ACS Income and MNIST, using basic linear and logistic regression models. These settings are sufficient to validate theoretical correctness but offer little insight into how the framework could inform or enhance real-world ML practice, where datasets are more complex and model architectures far richer.", "audience_yn": "Yes", "audience_explanation": "The paper addresses a meaningful and fundamental problem. Efficiently representing probability distributions with reduced computational and memory costs has broad theoretical and practical implications.", "requested_changes": "While the theoretical side of the paper is already well grounded and does not require extensive experimentation, the work would benefit from showing how the framework could connect to practical ML scenarios. Even a few illustrative hints—such as potential use cases or small-scale examples demonstrating integration with existing AI pipelines—would make the contribution more compelling and accessible to applied researchers.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)