Bounded Space Differentially Private Quantiles
Authors: Daniel Alabi
Omri Ben-Eliezer
Anamay Chaturvedi
Venue: Accepted by TMLR ()

Abstract: Estimating the quantiles of a large dataset is a fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing private mechanisms for distribution-independent quantile computation require space at least linear in the input size $n$. In this work, we devise a differentially private algorithm for the quantile estimation problem, with strongly sublinear space complexity, in the one-shot and continual observation settings. Our basic mechanism estimates any $\alpha$-approximate quantile of a length-$n$ stream over a data universe $\mathcal{X}$ with probability $1-\beta$ using $O\left( \frac{\log (|\mathcal{X}|/\beta) \log (\alpha \epsilon n)}{\alpha \epsilon} \right)$ space while satisfying $\epsilon$-differential privacy at a single time point. Our approach builds upon deterministic streaming algorithms for non-private quantile estimation instantiating the exponential mechanism using a utility function defined on sketch items, while (privately) sampling from intervals defined by the sketch. We also present another algorithm based on histograms that is especially well-suited to the multiple quantiles case. We implement our algorithms and experimentally evaluate them on synthetic and real-world datasets. 

Published in Transactions on Machine Learning Research (06/2023)
Bounded Space Differentially Private Quantiles
Daniel Alabi Columbia University
alabid@cs.cokumbiic edu
Omri Ben-Eliezer
omrib@mit. edu
Massachusetts Institute of Technology
Anamay Chaturvedi
chaturvedi. www.httaoootttttteeeeeeeoo
Northeastern University
Reviewed on OpenReview: https: // openreview. net/ forun? id= si20D8VVuM
Abstract
Estimating the quantiles of large datasel. is fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing private mechanisms for distribution-indeeenden quantile computation require space at least lin- ear in the imput size n. In this work, we devise differentially private algorithm for the quantile estimation problem, with strongly sublinear space complexity, in the one-shot and continual observation settings. Our basic mechanism estimates any a-approximate quantile of length-n stream space while satisfying e-differential privacy at single time point. Our approach builds upon deterministic streaming algorithms for non-private quantile estimation instantiating the exponential mechanism using a utility function defined on sketch items, while (privately) sampling from intervals defined by the sketch. We also present another algorithm based on histograms that is especially well-suited the multiple quantiles case. We implement our algorithms and experimentally evaluate them synthetic and real-world datascts.
data universe X' with probability 1 1- using O [og((22/8)) log
ac
1 Introduction
Quantile estimation is fundamental subroutine in data analysis and statistics. For [0, 1J, the g-quantile of dataset of size n is the element ranked [qn] when the elements are sorted from smallest to largest. Computing a small number of quantiles in massive data set can serve as a quick and effective sketch of the "shape" of the data. Quantile estimation also serves an essential role in robust statistios, where data is generated from some distribution but contaminated by non-negligible fraction of outliers, i.e., "out of distribution" elements that may sometimes even be adversarial. For example, the median (50th percentile) of dataset is used robust estimator of the mean in such situations where the data may be contaminated. Location parameters can also be (robustly) estimated via truncation or winsorization, on quantile estimation as a subroutine (Tukey, 1960; Huber, 1964). Rank- nonparametric statistics can be used for hypothesis testing (e.g,, the Kruskal-Wall test statistic (Kruskal & Wallis, 1952)). Thus, designing quantile-based or based estimators, whether distributtionddeeeneent dependent or distributionnagnostiie is important many scenarios.
operation that relies
Maintaining the privacy of individual users or data items, or even of groups, is an essential prerequisite in many modern data analysis and management systems. Differential privacy (DP) is rigorous and now well-accepted definition of privacy for data analysis and machine learning. In particular, there is already a substantial amount of literature on differentially private quantile estimation (e.g., see (Nissim et al., 2007; Asi & Duchi, 2020; Gillenwater et al., 2021; Tzamos et al., 2020)).
Robust estimators also known be useful for accurate differentially private estimation; see, e.g., the work of Dwork and Lei (Dwork Lei, 2009) the context. of quantile estimation for the interquartile range and for medians.

---

Published in Transactions on Machine Learning Research (06/2023)
All previous work either makes certain distributional assumptions about the imput, or assumes the ability to access all input elements (thus virtually requiring a linear or worse space complexity). Such assumptions may be infeasible in many practical scenarios, where large scale databases have to quickly process streams of millions or billions data elements without clear a priori distributional characteristics. The field of streaming algorithuns aims to provide space-efficient algorithms for data analysis tasks such as these. These algorithms typically maintain good accuracy and fast running time while having space requirements that are substantially smaller than the size of the data. While distribution-agnostie quantile estimation is among the most fundamental problems in the streaming literature (Agarwal et al., 2013; Felber & Ostrovsky, 2017: Greenwald & Khanna, 2001; Hung & Ting, 2010; Karnin et al., 2016; Manku et al., 1999; Munro & Paterson, 1980; Shrivastava et al., 2004; Wang et al., 2013), no differentially private sublinear-space algorithms for the same lask are currently known. Thus, the following question, essentially posed by (Smith, 2011) and (Mir et al., 2011), naturally arises:
Can we design differentially privale quantile eslimalors that use space sublinear in the stream length, have efficient running time, provide high-enough utility, and do not rely on restrictive distributional assumptions?
It is well-known (Munro& & Paterson, 1980) that exact computation of quantiles cannot be done with sublincar space, even where there are no privacy considerations. Thus, one must. resort lo approximation. Specifically, for dataset of elements, an a-approzimate q quaantille is any element which has rank (q when sorting the clements from smallest to largest, and it is known that the space complexity of a-approximating quantiles is ((11/a (Munro& & Paterson, 1980). In our case, the general goal is to elficiently compute a-approxinate quantiles in a (pure or approximate) differentially private manner.
1.1 Our Contributions
We answer the above question affirmatively by providing theoretically proven algorithms with accompanying experimental validation for quantile estimation with DP guarantees. The algorithms are suitable for private computation of either a single quantile or multiple quantiles. Concretely, the main contributions are:
1.
We devise DPExpGK, differentially private sublinear-space algorithm for quantile estimation based on the exponential mechanism. In order to achieve sublinear space complexity, our algorithm carefully instantiates the exponential mechanism with the basic blocks being intervals from the Greenwald- Khanna (Greenwald & Khanna, 2001) data structure for non-private quantile estimation, rather than single elements. We prove general distributionnagnnstt utility bounds on our algorithm and show that the space complexity is logarithmic in n.
2.
We present DPHistGK, another difierentially private mechanism for quantile estimation, which applies the Laplace mechanism to a histogram, again using intervals of the GK-sketch as the basic building block. We theoretically demonstrate that DPHistGK may be useful in cases where one has prior knowledge the input.
We extend our results to the continual release setting, wherein we must maintain and output an estimate of the queried quantile an online manner as the data received and processed.
4.
We empirically validate our results by evaluating DPExpGK, analyzing and comparing various aspects of performance on weal-world and synthetic datasets.
2
Related Work
2.1 Quantile Approximation of Streams and Sketches
Approximation of quantiles in large data streams (without privacy guarantoes) is among the most well- investigated problems in the streaming literature (Wang al., 2013; Greenwald & Khanna, 2016; Xiang et al., 2020). A classical result of Munro and Paterson from 1980 (Munro & Paterson, 1980) shows that
2

---

Published in Transactions on Machine Learning Research (06/2023)
computing the median exactly with p passes over a stream requires (/n space, thus implying the need for approximation to obtain very efficient (that is, at most polylogarithmic) space complexity. Manku, Rajagopalan and Lindsay (Manku et al., 1999) built on ideas from (Munro & Paterson, 1980) to obtain a randomized algorithm with only ((11/) log" ) for a-approximating all quantilos; a deterministic variant of their approach with the same space complexity exists as well (Agarwal et al., 2013). The best known deterministic algorithm is that of Greenwald and Khanna (GK) (Greenwald & Khanna, 2001) on which we build on in this paper, with space complexity of O(a log(an)) to sketch all quantiles for n elements (up to rank approximation error of =om). A recent deterministic lower bound of Cormode and Veselý (Cormode & Vesely, 2020) (improving on (Hung & Ting, 2010)) shows that the GK algorithm is in fact optimal among deterministic ccomparison-based sketches.
Randomization and sampling help for streaming quantiles, and the space complexity becomes independent of n; an optimal space complexity of (((1/a) log log())3) was achieved by Karnin, Lang and Liberty (Karnin et al., 2016) (for failure probability B), concluding a scries of work on randomized algorithms (Agarwal al., 2013; Felber & Ostrovsky, 2017; Luo et al., 2016; Manku el al., 1999).
The problem of biased or relative error quantiles, where one is interested in increased approximation accuracy for very small or very large quantiles, has also been investigated (Cormode et al.; 2006); it would be interesting to devise efficient, differentially private algorithms for this problem.
Recall that our approach is based on the Greenwald Khanna deterministic all-quantiles sketch (Greenwald & Khanna, 2001). While some of the aforementioned randomized algorithms have a slightly better space complexity, differential privacy mechanisms are inherently randomized by themselves, and the analysis seems somewhat simpler and more intuitive when combined with deterministic sketch. This, of course, docs not rule out improved privale algorithms based on modern elficient randomized sketches (see Section 7).
2.2 Differential Privacy
Differentially private single quantile estimation: Works by Nissim, Raskhodníkova and Smith (Nis- sim et al., 2007) and Asi and Duchi (Asi & Duchi, 2020) improve the trade-off between accuracy and privacy by scaling the noise added for obfuscation in an instance-speeific manner for median estimation in the absence of distributional assumptions. Another work by Dwork and Lei (Dwork & Lei, 2009) uses "propose-test- release' paradigm to take advantage of local sensitivity; however, as observed in Gillenwater et al. (2021), in practice the error incurred by this method is relatively large as compared to other works like Tzamos et al. (2020). The work of Tzamos et al. (2020) achieves the optimal trade-oll between privacy and utility in the distributional setting, but again as observed by Gillenwater et al. (2021), with a time complexity of O(n*), this method does not scale well to large data sets
The work of Gillenwater al. (2021) shows how to optimize the division of the privacy budget to estimate quantiles in a time-efficient manner. For estimation of m quantiles, their time and space complexity are O(mm log(n) + m²n) and O(m2)), respectively. They do an extensive experimental analysis and find lower error compared to previous work. However, although they provide intuition for why their method should incur relatively low error, they do not achieve formal theoretical accuracy guarantees. Kaplan et al. (2022) improve upon the work of Gillenwater et al. (2021) for the multiple approximate quantiles problem by using a tree-based (recursive) approach to CDF eslimation. However, none of these works deal with quantile estimation in the sublinear space setting. Böhler & Kerschbaum (2020) solve the problem of estimating the joint median of two private data sets with time complexity sub-linear in the size of the data-universe and provide privacy guarantees for small data sets as well as limited group privacy guarantees unconditionally against polynomially bome-bounded adversaries.
Inherent privacy: Another line of work (Blocki et al., 2012; Smith et al., 2020; Choi et al., 2020) demon- strates that sketching algorithms for streaming problems might have inherent privacy guarantecs under minimal assumptions on the dataset in some cases. For such algorithms, relatively little noise needs to be added to preserve privacy unconditionally.
3

---

Published in Transactions on Machine Learning Research (06/2023)
3 Preliminaries and Notation
We now give standard differential privacy notation and formally describe the quantile ostimation problem. We also present the Siveewald-Khannng sketch guarantees in a suitable form.
3.1 Differential Privacy
Definition 3.1 (Differential Privacy (Dwork et al., 2006)). Let X - R. be a (randomized) mechanism. For any 2 0, 8 E [0, 1], Q satisfies (c, (f-))ffrreentii privacy if for any neighboring databases (that differ in one row) x ~ E X and any set 5 S.
PIQ(x) S E S] +
The probability is laken over the coin tosses of Q. We say that Q satisfies pure differential privacy (e-DP) if 8 = and approximate differential privacy ((e,8)-DP) if O. We can set e to be small constant (e.g.. between 0.01 and 2) but will require that 8 J. n=((1) be cryptographically small.
3.2 Quantile Approximation
In this subsection we make some definitions to for- malize our analysis.
Data set S' = 2,,
Definition 3.2. (Quantiles) Let there be totally ordered data universe X and input data stream X = (11,,),... (In, n)) (sometimes implicitly re- ferred to as X = (II,...,Za)) For (I,,1) E X, let val((x; i)) = x; and ix((z;,)) = EEe ((()),) zj < 22 or zj- = J..j < iH-- We abuse notation to say that for 01, U2 E X, v1 S v2 ix(e1) S ix(12). Then, the q-quantile of X is val(v) for v E X with ix(e) [qm]
1
233
2
3 4 5
Totally ordered domain X
We observe that in this setting value from the data universe can occur multiple times in set. To account for this we define range of ranks that any value can hold; this will be useful when reasoning about quantile approximation.
Figure 1: In the data set S of 8 elements, the true 0.5 quantile is the value 2, and the values 2,3, 4 and 5 are all acceptable 0.25-approximate answers. Noto that although is adjacent to 2 in the data universe X, it not an acceptable output.
Definition 3.3. (Rank and approximate quantiles) For x E X, we define Tmin(x) He X val(v) < 2)), (=) = [(v X val(e) S x) and rank(X, be the interval [Fmin(x), mmax [x)]. We say that æ E
d' is a-approximate g-quantile for X if rank(X, n [[qn] om, [qn] am) + 0.
Consider the following example see how these definitions play out in practice.
Example 3.4. Given the data set 2,,,,,,3,,,,66 6,5) (refer to figure 1), the 0.5 quantile 2, which we distinguish from the median, which would be the average of the elements ranked 4 and 5, i.e, 2.5 for this data set. A straightforward way to obtain quantiles is to sort the dataset and the pick the element at the [q n] position. This method only works in the offline (non-streaming' setting. For a-approximate 0.5 quantiles are 2, 3, 4 and 5. Note that 4, which does not occur in the data set, is still a valid response, but 1, which occurs in the data set and is even adjacent to the true 0.5 quantile 2 in the data universe X, is not a valid response.
0.25, the
We can now formalize the two versions of the problems that are dealt with in the literature on streaming quantile approximation. Let D be any distribution with random variable X D and CDF Fx R -+ (0. 1]. For any q E [0, 1], Q2 denotes the value such that Fx (x) 4-

---

Published in Transactions on Machine Learning Research (06/2023)
Definition 3.5 (Single Quantile). Given sample S= (Z1,... , in streaming fashion in arbitrary order, construct a data structure for computing the quantile @% such that for any E [0, with probability at least 1 3, 3, 10% Q a.
Definition 3.6 (All Quantiles). Given sample 5 = (I1,.... Fa) in a streaming fashion in arbitrary order, construct a data structure for computing the quantile 0% such that with probability at least 1 - 5, for all values of q E M where M C [0, 1]. @QD Q3 S a.
3.3 Non-private Quantile Streaming
In this subsection, provide formal guarantees needed for any sketch that our algorithms can build upon: Lemma 3.7. Given data stream Ti,..., of elements drawn from X, there erists a sketching algorithm that outputs list S(X) of s = O a log an) many tuples (V,, Ai) E (X x N) x N x N for i = 1.....& $ such that if X is the data mullii-se then:
1. rank(X, val(u:)) c EEssigi A: + Ejsighl-
9. + A; S 2am.
3. The first tuple is (minfx E x),1,0) and the last tuple is (maxfx 1),1,0).
4- The Vi are sorted in ascending order. Without loss of generality, the lower interval bounds Ejse and upper interval bounds A, + Ejgi are also sorted in increasing order.
From conditions 1 and 2 above, it follows that the GK sketch can be used to compute a-approximate quantiles by outputting the value ut- for the unique index 1 such that Σjsr S qn < A, + Σj Oj- More generally, any sketch which achieves the propertics outlined in Lemma 3.7 can be used in place of GK.
4 Differentially Private Algorithms
In this section we present our two DP mechanisms for quantile estimation. Throughout, we assume that a is a user-defined approximation parameter. The goal is to obtain a-approximate q g-quantiles.
The new algorithms we introduce are:
(1) DPExpGK (Algorithm 1): An exponential mechanism based 0e, algorithm for computing a single g-quantile. To solve the all-quantiles problem with approximation factor a, one run this algorithm iteratively with target quantile 0, a, 2a..... Doing so requires scaling the privacy parameter in cach call by an additional a factor which increases the space complexity by a factor of 1/a. We also give an optimized implementation (algorithm 8) of this algorithm in the appendix. We extend our results to the continual observation setting (Dwork et al., 2010; Chan et al., 2011).
(2) DPHistGK (Algorithm 2): A histogram based (c, 0)-DP algorithm (Algorithm 2) for the a-approximate all-quantiles problem. The privacy guarantee of this algorithm is unconditional, but there universal theoretical utility bound in the previous algorithm. However, in some cases the utility is provably better: for example, we show that if the data set is drawn from a normal distribution (with unknown mean and variance), we can avoid the quadractic 1/a² factor in the sample complexity that we incur when using DPExpGKGumb for the same all-quantiles task.
The rest of this section contains the descriptions of the two algorithms; we relegate all proofs to the appendix.
4.1 DPExpGKGumb: Exponential Mechanism Based Approach
We first establish how the exponential mechanism and the GK sketch may be used in conjunction to solve the single quantile problem. Concretely, the high level idca call the privacy preserving exponential mechanism with a score function derived from the GK sketch. The exponential mechanism is a fundamental privacy primitive which when given public set of choices and private score for each choice outputs choice
5

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm 1: DPExpCK: Exponential Mechanism DP Quantiles High Level Description
Data: (0), Z2..... .,))
Input: a (approximation parameter) q e [0, 1J (quantile parameters), 8n (sensitivity) S(X) {(v,,9 9r. (,), e [s]] GK(X,a)
Define score function
x( min - [gn]] y [m)n ( (x)))
(1)
where
fmin(() = max Σ gj : val(vi) < <x}
fmax (x) = min A +
Σ
91 val(e;) > x}
Execute the exponential mechanism with score function u(S(X), .), i.c. choose and output a single e E X with probability
exp 6 -))
28,,
that with high probability has a score close to optimal whilst preserving privacy. In the course constructing our algorithms, we have to resolve two problems; one, how usefully construct score function pass the exponential mechanism that the private value derived is good approximation to the q-quantile, and two, how to execute the exponential mechanism efficiently on the (possibly massive) data universe X. To resolve the first issue we devise the (not necessarily efficient.) routine Algorithm 1; and to resolve the second one, we run an essentially equivalent but far more efficient routine, Algorithm 8.
Constructing a score function: We recall that the GK sketch returns a short sequence of elements from the data set with a deterministic interval for their ranks and the promise that for any target quantile g E [o, 1], there some sketch element that lies within an units rank of [qn]. One technicality that we run into when trying construct score function on the data universe X' is that when a single value occurs with very high frequency in the data set, the ranks of the set of occurrences can span large interval in [0, n]. and there is no one rank we can ascribe to it so as to compare it with the target rank [gn]. This can be resolved by defining the score for any data domain value in terms of the distance of its respective rank interval Vmmin()), F'max(e (x)) (formalized in Definition B. from [qu]; elements whose intervals lie closer to the target have higher score than further away ones.
Efficiently exccuting the exponential mechanism: The exponential mechanism samples one of the public choices (in our case some element from the data universe X) with probability that increases with the quality of the choice according to the score function. In general every element can have a possibly different score and the efficiency of the exponential mechanism can vary widely depending on the context. In our setting, the succinetness of the GK sketch leads to a crucial observation: by defining the score function via the sketch, the data domain is partitioned into a relatively small number of sets such that the score function is constant on each partition. Concretely, for any two successive elements in the GK sketch, the range of values in the data universe that lie between them will have the same score according to our score function. We can hence first sample a partition from which to output value, and then choose a value from within that interval uniformly at random. To make our implementation even more efficient and easy to use, we also make use of the Gumbel-maz trick that allows us to iterate through the set of choices instead of storing them in memory
appendix B.1 and the expanded pseudocode in algorithm 8 for more detail.
On formalizing this outline we get the following formal guarantees for algorithm (please see appendix B.1 for a complete proof). .(.,-) denotes the l metric on

---

Published in Transactions on Machine Learning Research (06/2023)
Theorem 4.1.
Algorithm 1 is e-differentially private. Let &t be the value returned by Algorithm 1 when inilialized with targel quantile q. The Jollowing statements hold:
Algorithm can be implemented to run with space complecity O((1/a) log an), such that with prob- ability 1-8
d([qu], [fmin fmax I 2am 2(4am log(1
(2)
2. For n
24 //1/3 mi, Algorithm can be implemented to run with space complerity ((ae) (11()))13)))8 logn) such that with probability - B, is an a approzimate q q-quantile.
4.2 DPHistGK: Histogram Based Approach
For methods in this section, we assume that we have K disjoinl bins each of width w (e.g., a/2) partitioning the data universe. These bins used to construct histogram. Essentially, Algorithm 2 builds an empirical histogram based on the GK sketch, adds noise so that the bin values satisfy (c, D)-P, and converts this empirical histogram to an approximate empirical CDF, from which the quantiles can be approximately calculated. We demonstrate one use case of DPHistGK where the space complexity required improves upon the worst-case bound for DPExpGK, Theorem 4.1. While the histogram based mechanism does not have universal utility bounds in the spirit of the above theorem, the results this section serve one simple example where it may yield desirable accuracy while using less space.
Algorithm 2: DPHistGK: Computing DP Quantiles Bounded Space
Data: X (2), 22. ,,,,,
Input: a (approximation parameter), [0. 4] (quantile parameters), w Build summary sketch S(X) where
5(X) = {1, gi, A.) : i [+]] + (
/* cell labels a, and counts 4 =0
Initialize data-agnostic (empty) histogram Hist ((a,,)),.. with cell widths w for (0,.9t A,) E S(X) do
Insert da counts of v into histogram Hist
H = [+/+ initialize empty list
for (4) Hist do
é = max a + (0,((,2/e))
10
Append (ai, + 2) to H
c=c+à 11
12 = [q-n]
13
for (b, rank) e H do
14
if rank then
15
return b
/* return last element of 16 return H| 1]
*/
Suppose that we are given an i.i.d. sample S (X X2,..., Xn) such that for all E [n], X; of μ E Rd. The goal is to estimate DP quantiles of the distribution N( without knowledge of μ o², We will show how to estimate the quantiles assuming that o² is known. Note that it is easy to generalize the work to the case where o² is unknown as follows:
For any sample S drawn from i... from N(u, o² Taxa), the 1 confidence interval is
X +
21 21-8/2-
7

---

Published in Transactions on Machine Learning Research (06/2023)
where 21 is the 1 B/2 quantile of the standard normal distribution and X is the empirical mean. The length of this interval is fixed and equal 2021-8/2 O the confidence interval becomes x vn
vn log 1 In the case where o² is unknown, n-1 (X, - x)² is the sample variance (sample estimate of x²) and 1n-1,119/2 9/2 is the 1 8/2 quantile of the t-distribution with n 1 degrees of freedom. The length of the interval can be shown to be
vn
a_ in 1/1- where s²
20 kn 11-1,188/2 θ
1 log 3
where hn 1- O(1/n) is an appropriately chosen constant (see (Lehmann & Romano, 2005; Karwa & Vadhan, 2018; Keener, 2010) for more details and discussion). We can hence assume that 0² is known and proceed to show sample and space complexity bounds." 2
For any E (0, 1), we denote the g-quantile of the sample S (X,, .,, as Q3 and the q-quantile of the distribution as Qb. With this notation, for some / E (0, 1] and a > O, we wish to obtain a DP q-quantile Q' such that
PIIl% Q 2 a) S.
We shall proceed in threc-step approach: (1) Estimate a DP range of the population in sub-lincar space; (2) Use this range of the population to construct a DP histogram using the stream S; (3) Use the DP histogram to estimate one or more quantiles via the sub-linear data structure of Greenwald and Khanna. Our main formal result for algorithm can be summarized as follows (please see appendix B.2 for a complete proof).
Theorem 4.2. For the one-dimensional normal distribution N(,,o"), let S = (X1, (2,..., be a data stream through which we wish to oblain Q% a DP estimate of the q-quantile of the distribution.
For any q E (0,1) there erists an (e, 8DP algorithm such that, with probability at least 1 3, oblain 14% Q31 S a for any 0, B E (0, c, E (0, 1/n) and for stream length.
2 max {min (A,B),C) where
R
R oB
0 (
(coa log ) , -0=0
R
R2 0²00
log 1)
A == 0
log
B B
coa
coa 35
as long as μ E (-R, R) and using space of O(max (B 1 an))).
In the case where d = 1, by Theorem 4.2, there exists an (c, O)DD algorithm Q3 such that if E (-R, R) then using space of O &t 1 log am)) (with probability 1) as long as the stream length n is at least
of max { min {o(1)
R coaa
R 03
)
(
R coa 38
1
log 1 o²a² 3 1)}
R
log
log
1.
we get the guarantee that, for all B (0, > 0, P1112% - Q3 2 al S 3. Intuitively, this means that: (1) Space: We need less space to estimate any quantile with DP guarantees if the distribution is less concentrated (i.c., can be large) if we do not require high degree of accuracy for our queries (i.c., a can be large). (2) Stream Length: We need large stream length to estimate quantiles if we require high degree of accuracy (i.e., smaller B, 8, or do not have good public estimate of y (large R), or have small privacy parameters (small e, d), or have concentrated datasets (small σ).
5 Continual Observation
We now describe how our one-shot approach can be used as a black box to obtain a continual observation solution (Dwork et al., 2010; Chan et al., 2011). 1). In the absence of privacy, we recall that an a/ 2-2approxiimaee solution for the q-quantile problem on a stream of length n allows for an additive error of an/2 in the rank of any candidate quaantile solution. follows that if we append any arbitrary an/2-many elements to the end
2Qne could also estimate the variance in DP way and then prove complexity bounds.
8

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm 3: Continual Observation DP Quantiles
Data: Input stream X = (I,) for some n > Rmnin = Ω a²c
log n log [og a
privacy
parameter 6, approximation parameter a, target quantile y
failure probability 3 Let s
6" t O(oe/logn)
a² + a/2
+ logn ag
cp(s) Romin /* stores stream checkpoints Instantiate GK + GK(a")
Us +1 / holds a a-approximate qrquantile
*/
for stream element 2, E X do
$ 4-$+1
10
GK. Gnnierer((r.))
if [cp(s 1)] then
11
12
V, + DPEXpGK(GKS (GK, e" a", 8*) cp(s) cp(s +) a/2)
13
14
else
15
U/ - U--1
16
cp(s) t cp(s - 1)
of the stream, these new elements can lead an additional additive error of most an/2. This suggests that on releasing DP quantile estimate at any point the stream, we can avoid updating our q-quantile estimate for a proportionate number of additional elements whilst maintaining a (pproxxippooiiiatiion This is essentially the idea behind the flip number used in the study of adversarially robust streaming algorithms. At high level, the flip number is a measure of the number of times the output of an online algorithm changes by more than (1 + a) multiplicative factor (see (Ben-Eliezer et al., 2020) for more detail).
Building on this idea, we can show that we only need update our estimate after every additional a/2-fraction as many elements are added as were present at the previous estimate. the beginning of this process, i.c. when no stream elements have been processed, for the first few elements the pseudo-code) we will need to update our online estimate every time omit producing any estimate. However, after this short warm-up prefix of the stream, relatively small number of estimates serve (1 + a) appprooxieetee quantiles for every point in the remainder of the stream.
as described in
Accounting for the additional requirement. of privacy is now easy we merely need to privatize the estimate at each of the checkpoints, which are the points in the stream where the quantile estimate must be updated. For n elements in all there are O(logio -_m)) many such elements, which for a suitable choice of nmmin simplifies essentially to ((log)). In other words
that the privacy loss scales only with the logarithm of the length of the stream because of the relatively few checkpoints that occur. The formal statement is below, and we present complete proof in appendix B.3.
Theorem 5.1. Let c,a > O, E Z. For any 3 E (0, with probability 2 1 - B, Algorithm 9 maintains an a-approrimate q-quantile at every point in the data stream for 8 == S2
log 12 18). Furthermore,
a+e
Algorithm 8 satisfies e-DP and has space complerity 5 (21, log" n nlog (x1 logn
We conclude by mentioning that our continual observation solution incurs roughly a O(lgnn/a) overhead in the space complexity, which is line with classical works in differential privacy and adversarially robust strcaming (Ben-Eliezer et al., 2020; Dwork et al., 2010). Concurrently, Stemmer and Kaplan (Kaplan & Stemmer, 2021) developed notion of streaming sanitizers which yields a continual observation guarantee "for free". without incurring such overhead over the one-shot case.
9

---

Published in Transactions on Machine Learning Research (06/2023)
107
107
DPExpGKGumb DPExpPull
DPExpGKGumb
DuExpCKGumb
DPExpGKGumb
DPExpFul1
DPExpFul1
DPExpFul1
106
10
10-4
10-4
109
105
10
10
1
2
3
4
2
3
1
2
3
4
2
3
-105
-10
-105
-10
(a) Error vs. stream length for Uniform dis- tribution.
(c) Error vs. stream length for Normal dis- tribution.
(b)
Data structure sizes stream length for Uniform distribution.
(d) Data structure sizes stream length for Normal distribution.
V8.
Figure 2: DPExpGKGumb versus DPExpFull for uniform or normally distributed data, a =10-4, 1, 0.5
6 Experimental Evaluation
In this section, we experimentally evaluate our sublinear-space exponential-based mechanism, DPExpGKGumb. We study how well our algorithm performs in terms of accuracy and space usage. This section validates the theoretical results the prequel we find that the space complexity of the algorithm is indeed very small in practice, and that the accuracy is typically closely tied the approximation paramcter a. Our main baselines will be DPExpFul1, which applies the exponential mechanism the full data set without any sketching algorithms (see appendix C.1 for further implementation details), and the true quantile value. The truc quantile values are used to compute relative error, the absolute value of the difference between the estimated quantile and the true quantile, divided by the standard deviation of the data set. We graph the mean relative error over 100 trials the exponential mechanism per experiment, as well as the 80% confidence interval computed by taking the 10th and 90th percentile. We the target quantile to estimated to q 0.5 (the median) throughout as the relative error and the space usage generally do not to vary much with choice of q.
6.1 Synthetic data sets
In this subsection, compare our methods on synthetically generated datasets. We vary the parameters of the Stream Length n (the size of the input stream Ix),, the Approximation Parameter a (the approximation factor used by the internal GK sketch), and the Data Distribution. We generate data from uniform and Gaussian distributions; we use a uniform distribution in range [0, 1] (i.e., U(0, 1)) or a normal dist ion with mean 0 and variance (i.e., N(O, 1)), clipped to the interval [-10, 10).3.
We show results on space usage and relative error (both plotted mostly logarithmic scales) from non-DP estimates,
vary the parameters listed above.
In Figure 2, we vary the stream length n for an approximation factor of a 10-4, The streams are either normally or uniformly distributed. In Figures 2a and 2b, we compare DPExpGKGumb (space strongly sublinear in n) vs. DPExpFull (uses space of O(n)) in terms of space usage and accuracy. In general we find that although our method DPExpGKGumb incurs higher error, absolute terms remains quite small and the 95% confidence intervals tend to be adjacent for DPExpGKGumb and DPExpFull, However, there clear trend of exponential gap developing between their respective space usages which is natural consequence of the space complexity guarantee of the GK sketch. This holds for both distributions studied.
CClippigg is required for the exponential mochanism, it must operate never expect samples from N(0, 1) that outside [-10, 10] for any practical purpose; probability for any given sample satisfy this minuscule, about 10-21
bounded interval of values. In any case,
10

---

Published in Transactions on Machine Learning Research (06/2023)
DPExpGKGumb DPExpFull
DPExpGKGumb DPExpPul1
DPExpGXGumb DPExpFull
I DPExpGKGumb
DPExpFul1
10a
10
10
10-2
10a
10
10
10
10-5
5
10
6
10'
10a
1
2
3
4
1
4
1
2
3
4
1
2
4
-10
-105
-10
-10
Uniform distribu- tion: Error stream length
(a)
(b) Data structure sizes
(c)
Normal distribu- Error
(d) Data structure sizes vs. stream length
v8.
stream length
tion: length
stream
Figure 3: DPExpCKGumb versus DPExpFull for uniform or normally distributed data, a 10-1 1, 0.5
Uniform Normal
Uniform Normal
Uniform Normal
Uniform
0.0015
0.5
Normal
4. 10-4
0.4
0.001
0.3
2 1001
0.2
0.0005
0.1
0
3
2
3
0.1
0.5
5
0.1
0.5 1
5
-109
-10
(c) Approx. 10
factor
(d)
Approx.
factor
(a) Relative datastream size for a
(b) Relative datastream size for a
a= 10
10-4 6= 1, == 0.5
10-1 q 0.5
Figure 4: Relative error versus approximation factor.
In Figure 3, vary the stream length for relatively large approximation factor of 0.1. Here see that compared to the non-approxinate method we incur far higher error, although there is also concomitant increase in the space savings. This is not a typical use-case since the non-private error can itself be large, but we get a complete picture of how space usage and performance vary with this user-defined paramcter.
In Figures and 4d, we vary the approximation factor. In the small approximation setting we see the inverse tendency of accuracy with privacy which is characteristic of most DP algorithms. However, in the large approximation setting, there is no such clear drop in performance with more privacy. This motivates the question of determining the true interplay between the approximation factor and the private parameter 6, discussed further in Section 7.
Our algorithm performs well in practical settings where one wishes to estimate some quantity across all data items privately and using small space. For example, our results indicate that choosing an approximation factor of a 10-4 induces an error which is also of order about 10-4 for privately computing parameters chosen according uniform or normal distribution, all while saving orders of magnitude in the space complexity.
6.2 Real-World Datasets
We repeat our investigation of the utility and space complexity comparison between DPExpGKGumb and DPExpFull with the following real-world data sets (Dua & Graff, 2017): (1) Taxi Service Trajectory: A datasct from the UCI machine learning repository describing trajectorics performed by all 442 taxis (at
"The 80% CI for error incurred by DPExpFull entirely supported on point and drops off we log scale.
11

---

Published in Transactions on Machine Learning Research (06/2023)
107
1R-2
106
1F-2
1F-5
1E-5
DPExpFul1
106
DPExpPull
105
100
100
10-2
10a
10 10-2
103
10
10a
10-4
0.1
0.5 1
5
1E-2
1E-5 exact
0.1
0.5 1
1E-2 1E-5 exact
(a) Taxi data set: Error versus privacy parame- ter for DPExpGKGumb for approximation 10-2 and 10-3, and DPExpFul1.
(b) Taxi data sel: Space used by DPExpCKGumb for 10-2 and 10-s, and DPExpFull (ab- breviated "exact" for brevity).
(c) Gas sensor data
(d) Gas sensor data set: Space used by DPExpCKGumb for a 10 and 10-5, and DPExpFull (ab breviated "exact" for brevity).
set: Error versus privacy parameter for DPEXpGKGumb for approximation a 10-2 and 10-5, and DPExpPul1".
Figure 5: Taxi and Gas sensor data sets.
the time) in the city of Porto in Portugal (Moreira-Matiae et al., 2013). This dataset contains real-valued attributes with about 1.5 million instances. (2) Gas Sensor Dataset: A UCT repository dataset containing recordings of 16 chemical sensors exposed to varying concentrations of two gas mixtures (Fonollosa et al., 2015). The sensor measurements are acquired continuously during 12-hour time range and contains about 4 millions instances. We pick real-valued attribute from each dataset. (the TIMESTAMP and the first ETHYLENE CO gas sensor value, respectively) and calculate the median these datasets. The results are reported in Figures 5a and 5b, and Figures 5c and 5d respectively.
We see that the larger the approximation factor, the larger the space savings are with DPExpGK. Comparing DPExpFull to DPExpCK, we see space savings 2 times up to 1000 times as we vary the approximation factor. These results are consistent with our expectations that the space savings are inversely proportional to the allowed approximation factor.
7 Conclusion & Future Work
In this work, we presented sublinear-space and differentially private algorithms for approximately estimating quantiles in a datasct. Our solutions are two-part: one based on the exponential mechanism and efficiently implemented via the use of the Gumbel distribution; the other based on constructing histograms. Our algorithms are supplemented with theoretical utility guaranteos. Furthermore, we experimentally validate our methods both synthetic and real-world datasets. Our work leaves room for further exploration in various directions.
Interplay between a and e: The space complexity bounds we obtain are (up to lower order terms) in- versely linear a and in e. While it is either known or easy to show that such linear dependence in each of these parameters in itself is necessary, is not clear whether the l term in Theo- rem 4.1 can be replaced with, say, a + - Such an improvement, if possible, seems require substantially modifying the baseline Greenwald-Khame sketch adding randomness.
Alternative streaming baselines: We base mechanisms upon the GK-sketch, which is known to be space-optimal among deterministic streaming algorithms for quantile approximation. The use of a deterministic baseline simplifies the analysis and the overall solution, but better randomized streaming algorithms for the same problem are known to exist. What would be the benefit of working, e.g., with the (optimal among randomized algorithms) KLL-sketch (Karnin et al., 2016)?
Dependence in universe size: The dependence of our space complexity bounds in the size of the universe,
X, is logarithmic. Recent work of Kaplan et al. (Kaplan et al., 2020) (see also (Bun et al., 2015)) on
12

---

Published in Transactions on Machine Learning Research (06/2023)
the sample (not space) complexity of privately learning thresholds in dimension, fundamental problem at the intersection of learning theory and privacy, demonstrate bound polynomial in log" [2| on the sample complexity. As quantile estimation and threshold learning are closely related problems, this raises the question of whether techniques developed in the aforementioned papers can improve the dependence on | in our bounds.
Random order:
The results presented here (except for those about normally distributed data) all assume that the data stream is presented in worst case order, an assumption that may be too strong for some scenarios. Can improved bounds be proved when the data elements are chosen in advance but their order is chosen randomly? This can serve as a middle ground between the most general case (which we address this paper) and the case where data is assumed to be generated according to a certain distribution.
8 Acknowledgements
D.A. was supported by a Junior Fellowship from the Simons Foundation Society of Fellows, Cooperative Agreement CR20ADR0160001 with the U.S. Census Bureau, and a Fellowship from Meta AT. Most of this work was done while he was Ph.D. student at Harvard University. A.C. was supported in part by NSF CAREER grant 1750716.
References
Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Perturbation Techniques in Online Learning and Opti- mization, pp. 233 264. 2017. 23
Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. ACM Trans. Database Syst.,
2013. 2,
Hilal Asi and John C. Duchi. Near instance-optimality in differential privacy. CoRR, abs/ 2200200005000000 2020. 1,
Victor Balcer and Salil P. Vadhan. Differential privacy on finite computers. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume of LIPles, pp. 43:1-43:22 Schloss Dagstuhl Leibniz-Zentrun für Informatik, 2018. 23
Omri Ben-Fliezer, Rajesh Jayaram, David P. Woodruff, and Fylon Yogev. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACT-SICC Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pp. 88-80, 2020. 9
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Linndentrraus transform itself preserves differential privacy. In 53rd Annual IEEE Symposium Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 410-419. IEEE Computer Society, 2012. 3
Jonas Böhler and Florian Kerschbaum. Secure sublinear time differentially private median computation. In 27th Anvual Network and Distributed System Securily Symposium, NDSS 2020, San Diego, California, USA, February 23- 23-26, 2020, 2020.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In JEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 634-649, 2015. 12, 25
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1 26:24, 2011. 5,
Seung Geol Choi, Dana Pachman-Soled Mukul Kulkarni, and Arkady Yerukhimovich. Differentially-privaar multi-party sketching for large-scale statistics. Proc. Priv. Enhancing Technol, 2020(3):153 -141115-4444 2020. 3
13

---

Published in Transactions on Machine Learning Research (06/2023)
Graham Cormode and Pavel Veselý. A tight lower bound for comparison-based quantile summaries. In Symposium on Principles of Dotabase Systems,
Proceedings of the 39th ACM SIGMOD-SIGACT-S5 PODS'20, pp. 81 93, Association for Computing Machinery, 2020. 3
Graham Cormode, Zohar S. Karnin, Edo Liberty, Justin Thaler, and Pavel Veselý. Relative error stream- ing quantiles. In Proceedings of the 40th ACM Database Systems, P0 pp. 96 108. Association for Computing Machinery. 3
Symposium on Principles of
Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. Space- and time-efficient deter- ministic algorithms for biased quantiles over data streams. In Proceedings of the Twenly-Fiiie ACM Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Ilinois, USA, pp. 263-272, 2006. 3
SIGACT-SSGGODD-SGAAA
Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. 11
A. Dvoretzky, J. Kiefer, and J. Wollowitz. Asymptotie minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist., 27(3):642 669, 09 1956. doi: 10.1214/ aoms/1177728174. 24
Cynthia Dwork and Jing Lei. Differential privacy and robust statisties. In Proceedings of the 4 1ss Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009,
pp. 371-380, 2009. 3
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, pp. 265-284, 2006. 4, 26
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual ob- servation. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 715-724. ACM, 2010. 5, 8,
David Felber and Rafail Ostrovsky. A randomized online quantile summary in ((1//) log(1/c)) words.
Theory Comput., 13(1):1-17, 2017. 2,
Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. Reservoir computing compensates
slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical, 215:618 629, 2015. ISSN 0925-4005. 12
Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3713 3722. PMLR, 2021. 1,3
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD international conference Management of data, Santa Barbara, CA, USA, May 21-24, 2001, pp. 58 66, 2001. 2, 3, 17, 19
Michael Greenwald and Sanjeev Khanna. Power- conee-cons computation of ordcr-statistics over sensor net- works. In Proceedings of the Twenly-third ACM Database Systems, June 14-16, 2004, Paris, France, pp. 275 285, 2004. 25
SIGMOD-SSGARR Symposium on Principles of
Michael B. Greenwald and Sanjeev Khanna. Quantiles and equi-depth histograms over streams. In Data Stream Management Processing High-Speed Data Streams, pp. 45 45-86. 2016. 2
Peter Huber. Robust Estimation of a Location Parameter. The Annals of Mathemationl Statisties, 35(1):
73 101, 1964. doi: 10.1214/aomss 1177700732777772..
Regant Y. S. Hung and Hing- Hing-Fung Ting. An w(L/elog(L/e)) space lower bound for finding epsilon- approximate quantiles in a data stream. In Frontiers in Algorithmies, 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings, volume 6213 of Lecture Notes in Computer Science, pp. 89 100. Springer, 2010. 2,
14

---

Published in Transactions on Machine Learning Research (06/2023)
Haim Kaplan and Uri Stemmer. A note sanitizing streams with differential privacy, 2021. 9, 24
Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event /Graz, Austriaj, volume 125 of Proceedings of Machine Learning Research, pp. 2263-2285. PMLR, 2020. 12
Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In Pro- ceedings of the 39th International Conference on Machine Learning, Proccodings of Machine Learning Research, pp. 10751 10761. PMLR, 2022.
Zohar S. Karnin, Kevin Lang, and Edo Liberty. Optimal quantile approximation streams. In JEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 71 78, 2016. 2, 3,
Vishesh Karwa and Salil Vadhan. Finite Sample Differentially Private Confidence Intervals. In Anna R. Karlin (ed.), 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 44:1 44:9, 2018. 8, 25
R.W. Keener. Theoretical Statistics: Topics for Core Course. Springer Texts in Statistics. Springer New York, 2010. 8
William H. Kruskal and W. Allen Wallis. Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association, 57(20)):583 621, 1952. doi: 1L.100001621149..552...000
1
Erich L. Lehmann and Joseph P. Romano. Testing Statistical Hypotheses. Springer Texts in Statistics.
Springer New York, New York, NY, 3. edition, 2005. ISBN 9780387276052.
Ge Luo, Lu Wang, Ke Yi, and Graham Cormode. Quantiles over data streams: experimental comparisons, new analyses, and further improvements. VLDB J., 25(4):449-477 472, 2016. 3
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Random sampling techniques for space efficient online computation of order statistics of large datasets. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1-3, 1999, Philadelphia, Pennsylvania, USA, pp. 251 262, 1999. 2,
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 94 103, 2007. 20, 21
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the 30th ACM SICMOD-SICACCT-SICATI Symposium Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pp. 37 48, 2011. 2
Nya Mironov. On significance of the least significant bits for differential privacy. In the ACM Conference on Computer and Communications Securily, CCS'1, Raleigh, NC, USA, Oclober 16-18, 2012, pp. 650 661, 2012. 23
Luís Morcira-Matias, João Gama, Michel Ferreira, João Mendcs-Moreira, and Luís Damas. Predicting taxi- passenger demand using streaming data. IEEE Trans. Intell. Transp. Syst., 14(3):1393 1402, 2013. 12
J.I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315-323, 1980. ISSN 0304-3975. doi:
2,
Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, Son Diego, California, USA, June 11-13, 2007, pp. 75 84, 2007. 1,
15

---

Published in Transactions on Machine Learning Research (06/2023)
Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians and beyond: New aggregation techniques for sensor networks. In Proceedings of the 2nd International Conference Embedded Networked Sensor Systems, SenSys '04, pp. 239 249. Association for Computing Machinery, 2004. ISBN 1581138792. 2
Adam D. Smith. Privacy-preserving statistical estimation with optimal convergence rales. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pp. 813 822, 2011. 2, 21
Adam D. Smith, Shuang Song, and Abhradeep Thakurta. The Flajolct-Martin sketch itself preserves differ- ential privacy: Private counting with minimal space. In NewrIPS, 2020. 3
J. W. Tukey, A survey of sampling from contaminated distributions. Contributions to Probability and Statistics, pp. 448-485, 1960.
Christos Tzamos, Emmanouil- Vasileios Vlatakis Caaakikonnk,,,,,uuii,,,, and 1lias Zadik. Optimal private median estimation under minimal distributional assumptions. NeurIPS, 2020. 1,
Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pp. 347-450. 2017. 25
Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: experimental study, In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pp. 737 748, 2013. 2
Zhuolun Xiang, Bolin Ding, Xi He, and Jingren Zhou. Linear and range counting under metric-based local differential privacy. In IEEE International Symposium on Information Theory, ISIT 2020, pp. 908 913, 2020.
A Greenwald-Khamen Sketch
For completeness of our algorithmn' description, we specify the operations in the Creenwald- (GK) non-private sketch. Throughout, we will use mtt) to denote the number of elements encountered up to time & E E.. Some of the operations outlined here will be used a subroutines for the DP procedures.
A.1 The Sketch
Let X (2,, (n) be stream of items and S(X) be the resulting sketch with size sublinear in The GK sketch stores
S(X) (to, t1, "to.t,,..,,............. tw-1) Vi E s = (Us: Is; At).
where = (-mmmn(;))) Tmin (min((;-1) and A; = rmaz (v:) Tmin (vz). We reserve uo, Ux-1 be denole the smallest and largest elements seem in the stream X, respectively. We use S(X) to refer to the ith tuple in the sketch S(X). ic., for any S(X) t, = (v,, 0:, Ar).
Implicitly, the goal is to (implicitly) maintain bounds Tmin (v) and (maz(v) for every in S(X). Tmin (v) and (v) are the lower and upper bounds the rank of amongst all items in X, respectively. We can compute these bounds follows:
Tmin (v))= = === gj + A; Tmin (U:) = Σ gj.
15t
J51
As a result, Øi + A, is an upper bound on the number of items between 0/ and Uy. addition, D.
16

---

Published in Transactions on Machine Learning Research (06/2023)
The sketch is built in such way to guarantee (maximum) error of max + A.)/2 for approximately computing any quantile using the sketch.
We will also impose a tree structure over tuples in S(X) (mostly because of the merge procedure) as follows: the tree T(X) associated with (() has node V2 for each &, The parent of a node V is the node V, such that j the smallest index greater than with band((;) > band(4)).
(t)d(t4) the band of A time n and bandz(n) all tuples that had band value of All possible values of A are denoted as bands and it can take on values between
(0, 2 2an, i 2om. 2 2an - 1, 20m) corresponding to capacitios of (2am, on, .........,2 2,,4,211) .,,42.,8,4,21 1).
A.2 Quantile
Algorithm 4 computes the a-approximate q-quantile based on the sketch S(X) that has size that is sublinear in n.
The algorithm goes through all tuples and checks if the condition max(r T'mn (1i), Tmaz (1:) - -r < an is satisfied and return (i, 0;) as the representative approximate quantile. This algorithm will be used a subroutine for one or more of our differentially private algorithms.
Lemma A.1 (Proposition & Corollary 1 (Greenwald & Khanna, 2001)). If after receiving n items in the stream, the sketch S(X) satisfics the property max;(g; + A.) S 2em, then Algorithm 4 returns an a- approzimate q q-quantile.
Proof. The algorithm computes r= [qn]. Then the condition max(r - Tmin (2;), T'ma (m)a( -r S an clearly is (by definition) an a-approximate q-quantile. We still need to show that such always exists. First set e max;(g; + A2)/2. If  > n - e, then Tman (vy-1)= (maz((s-1)) (0s-1)== = n so that i = 8 - satisfies the property. When r S n e, then the algorithm chooses the smallest index j such that Imax (1₂) > r so that - Tmin (U)-1). This follows since if r- > (1))()))1) then mmaz(U)) = T'in (1/-1) + gg + A > Tmin (1)-1) 2e which contradicts the definition of
Algorithm 4: Quantile(S(X),, g, a): Computing a- a-Apprxxinatte Quantiles
Input: S(X), m, (approximation parameter)
Compute r = [qn]
for i 0, .......
do
(v,, 9: A.) S(
if max(r Tmin (Ui), Tmax (v:) - -r) S an then
return (i,
return
A.3 Insert
Algorithm 5 goes through a stream of items and inserts into the sketch. The algorithm calls a compress operator on the data structure every time that 0 mod 1 for any E [m].
Za
Algorithm inserts a particular item In into the data structure S(X). In the special case where on is a minimum or maximum, inserts the tuple L,,, at the beginming or end of S(X). Otherwise, it finds index such that 0 En e and then inserts the tuple (xn, 1, [2om]) into S(X) position i.
A.4 Compress
The Compress operation is an internal operation used for compressing (contiguous) tuples in S(X). The goal of this operation merge node and its descendants into either its right sibling or parent node. After merge, have to maintain the property that the tuple is not full. A tuple is full when gi + A > [2on].
17

---

Published in Transactions on Machine Learning Research (06/2023)
Algorithm 5: Inserting a stream of items into Summary Sketch
Data: 21, ... Fm.....
Input: S(X), (approximation parameter)
n =
for i= ,.,..,...... do
if 00 mod 2n then
L Compress(S(X).. Insert(S(X), a,; +
return S(X),
Algorithm 6: Insert(5(X),,,,,, Inserting into Summary Sketch
Data: En
Input: SXX), a (approximation parameter)
(Un, An) [0)
(Ug-1, 9s-1 -
if Fn < up then
Shift all positions in S(X) 1] to S(X)
[0 = (zm. 1,0)
else if In 1.-1 then
S(X)[s] = (In, 1,0)
else
for i= 5 8
1 do
10
(w, A,) = 5(X)
11
if u1-1 S In < vi then
Shift all positions ((X)(i..... - 1] to S(X)(i + +...8
12
13
((X)[i] (I 1, [2on])
14 return S(X), +1
Algorithm 7: Compressing the Sketch
Input: S(X), a (approximation parameter), n if then return
for
i 8- do
t = (v,, - [(
441 = (U1+1- A,-1) = S(X(ii+
Compute 9; the sum g-values tuple t, and its descendants if band((,) S band(1441) & (g) + +++ A,-1 20m) then Delete all descendants of t, and the tuple t; from sketch S(X)
Update 4+1 in S(X) to (1441, 0:+1, A+t1)
18

---

Published in Transactions on Machine Learning Research (06/2023)
By Proposition A.2, a node and its children will form contiguous segment. Let of be the sum of g-values of tuple 4 and all of its descendants. Then merging 4 and its descendants would update 441 in S(X) to (U++1. - 9i+1, A441) and delete &, and all of its descendants.
Proposition A.2 (Proposition in (Greenwald & Khanna, 2001)). For any node V, the set of all its descendants in the tree forms a contiguous segment in S(X).
A.5 Formal guarantee
We briefly recall the main guarantees of the GK sketch that we appeal to the main body of this work and provide a proof for the statements that are not reproduced from previous work.
Lemma 3.7. Given data stream Fiy...,Zn of elements drawn from X, there erists a sketching algorithm that outputs list S(X) of O 2 log an) many tuples (v,, 9t. A.) (X N) X X for I....,& 8 such that if X is the data multi-set then:
rank(X, val(u:)) c 1Ejsi9), + EEs
2. 9i + A; I 2am.
3. The first tuple is (min(x E X,, and the last tuple is (maxfı E X),1,0).
4. The vs are sorted in ascending order. Without loss of generality, the lower interval bounds Egg 9j and upper interval bounds A, + Ejs;hh 9j are also sorted in increasing order.
Proof. The first three statements are part of the GK sketch guarantee. For the third statement, i.e., to see that the u are sorted in ascending order, we see that the GK sketch construction ensures that val(u,) s val(1:41) for all Since an insertion operation always inserts a repeated value after all previous occurrences and the tuple order is always preserved, it follows that ix(rx) S ix(1:+1) as well, so in sum rank(X, s rank(X, 0441) In other words, the sort order in the GK sketch is stable.
The fact that the sequence Ejsrgj 9j is sorted in increasing order follows from the non-negativity of the 9 To ensure that A + Ejsr 95 are sorted in increasing order note that we always have that rank(X, < rank(X, 0++1) so that we can decrement A; and ensure that A, + Ejsigs I Ait1 + Ejsitt 9j without violating the guarantees of the GK sketch.
B Omitted proofs
We first recall and add some definitions that will require in the sequel.
Definition B.1. Let X ((11, 1),..,, (In, n)) (sometimes implicitly referred to as X = (#1, ..., x,)) be stream of elements drawn from some finite lotally ordered data universe X, i.e. x; E X for all i E [n].
1. Rank: Given a totally ordered finite data universe X, a data set X and a value x E X, let rankx = rank(X, = Evex 1ly S x].
2. For (I;, i) E X, let val((z,, 1)) = xy and ix((,,, i)) = EEsi)(((S,))) < x, or xj x..j < i))-
3. For vi, 02 E X, we say that en v U2 if ix(m) & ix(22).
4. The g-quantile of X is val(v) for v E X with ix(e) = [gr]].
5. For E X, we define (1) = 10 E X val(u) < 4H} (x)ax(x) 1(U E X val()) S x>] and
rank(X,x)) to be the interval [Fmin (x)
6. We say that x E X is an a-approximate ququnttlee for X if
- an, [qn] am] # 0.
With this notation, the data set is naturally identified as a multi-set of elements drawn from X. Definition B.2. Let (2) = { (E val(u;) < x and fmax (x) min(A, Ezsr val(u;) x}.
Note that for every X such that val xr, ix(u) E [frin (I),, (maz(() (x))
19

---

Published in Transactions on Machine Learning Research (06/2023)
B.1 Proofs of privacy and utility for DPExpGK
Outline: From Definition B.2 to Lemma B.5, we formalize how the GK sketch may be used to construct rank interval estimates for any data domain value. We then recall and apply the exponential mechanism with a score function derived from the GK sketch (Definition B.6 to Lemma B.9 and Algorithm 1), and derive the error guarantee Lemma B.11. We conclude this subsection with a detailed description of an efficient implementation of the exponential mechanism (Algorithm and Temma B.12), and summarize our final accuracy and space complexity guarantees in Theorem 4.1.
Remark B.3. We can add two additional tuples (-oo,0, 0) and 0,00,,0 to the sketch, which corresponds to respective rank intervals [0, 0) and [n+ 1, n, + 1). The bounds 9. + A, S 2an are preserved. This will ensure that the sets {i: val(u;) #t and {i: val())) > 2 for any X are always non-empty.
We formalize the rank interval estimation in a partition wise wise manner as below. Lemma B.4. Given GK sketch (v1, 91, AI)..... (Vs, Is: As), for every x X one of the following two cases holds:
1. Us for some i E [s] and == min Ui = tt.
Pmin (x) = =>9. 9j
iSi
Pmxx (2) -mminA
(Ai-
Σ dj = Di", val(oz=) > val(u:))
$56
2. x E (14-1, U;), i.c., > 4 and x < vs for some i E [s),
imin (x) = Σ 94
55
fmxx (I) A++1+ +
Σ
91
j54t1
Proof. Recall, by Remark B.3, that the first tuple and the last tuple are formal elements -oo and co, ensuring that every data universe element her explicitly occurs in the GK sketch lies between two values follow directly from Definition B.2 and the fact that the
that occur in the GK sketch. Both statements values occur in incrcasing order in the sketch (Lemma 3.7).
We bound the quality of the rank interval estimate [fuin (I), ) (m)) compared to the true rank interval (mmi(()), T Fiax (r)] as follows.
Lemma B.5. (x) - (m)) S 2an and (Tmax(x)) (x) - maxx(() S 2an.
Proof. Let i = argmax Ejsi Hs. Then by Definition of i", we have that val(E.) < x S val(o)+1). It follows that
[ix( ix(( C 1 Gj: Ar:4 + +1 + Σ gs
[ (2), Ar+41 - f (1:)
Since Tmin (x) [ix(u;.) ), (x)++)))) and g+++1 + Ae41 & 2om, it follows that [rmin (I) Pmin (x)) S 2on. The other inequality follows analogously.
Definition B.6 (Exponential Mechanism (McSherry & Talwar, 2007)). Let u S R R be an arbitrary score function with global sensitivity 6,, For any database summary d E s and privacy parameter > 0, R with probability x exp( ((a((())))) where 26,
the exponential mechanism E 8 + R outputs
6, max |u(S(X), u(S(X'), X~X',r
20

---

Published in Transactions on Machine Learning Research (06/2023)
The following statement formalizes the trade-off between the privacy parameter and the tightness of the tail bound on the score attained by the exponential mechanism.
Theorem B.7 (MeSherry & Talwar, 2007; Smith, 2011)). The exponential mechanism. (Definition B.6) satisfies diifferenttil pricacy. Further, the following tail bound on the utility (the score of the output element) holds:
P ( max ((axx( 28,(t + Ins) ) Set
rER
where is the size of the universe from which sampling from.
To run the exponential mechanism using our approximate rank interval estimates, we define a score function follows.
Definition B.8. Let d(::)) denote the & metric on Given a sketch S(X), we define a score function on X:
=(S(X), = min(ly - [qn : y E [fmin (x), f fax (x)) -d[[gn], [fmin (ar), (x)]
The magnitude of the noise that added the course of the exponential mechanism depends on the sensitivity of the score function, which we bound from above as follows.
Lemma B.9. For all n > 1/a, the sensitivity of u (t.e., du) is at most 4an + 2 units.
Proof- Fix any data set X' neighbouring X under swap DP and let [r'mn m)x be the rank ranges with respect to X' for values in X. Let [f'min (-), maxmmxx))) denote the confidence interval derived from the GK sketch S(X') for values in X.
Claim B.10. I'mia (z) minn (x) s 2, (Tmax(()) (x) r'max( S 2.
Proof. These bounds follow directly from the Definition of rmin and Tmaxi under swap DP at most two elements of the stream are changed which implies that the count of the sets defining these terms changes by at most unit cach for a total shift of units (in fact, this can be bounded by unit).
We now prove the scnsitivity bound.
u(S(X),x) - d[[gn], [fmin (x), fmaxx()) (z)])
< - d([mm] [rmin (x), mmax (z:]] + 2an
< - d([mm], [r'in (x), (=)(()))) + 2on +
S d([qn], [Pimn (x), maxx((()) (x))) + 4an
S u(S(X'), + 4an +
Swapping the positions of X and X', we get the reverse bound to complete the sensitivity analysis.
We can now derive a high probability bound on the utility that is achieved by Algorithm 1.
Lemma B.11. If a is the value returned DPExpGK then with probability 1 B,
d[[gn] [fmin (2), (max(())) 2an 2(4am + 2) log( log(1X2133) (2))
Proof. By construction, Algorithm 1 simply call the exponential mechanism with score function u(S())..), Since for any target q-quantile, [qn] lies in [0, n| it follows that there some i E such that [qn] (Ejsr Øj. A 41+1 Ejgr mz]. Tt follows that d( d[[gn], [rmin (val( (, rmax (.axx((val(22 (val(ve))) (vr))) & 2om
21

---

Published in Transactions on Machine Learning Research (06/2023)
and that hence max(u(S(X),x)) 2 -ann. If x² is the output of the exponential mechanism, then applying the utility tail bound we get that with probability 1 B,
(1S(X),2") 2 -2am 2(4an + 2) log(1>1/3)
By definition of u, the desired bound follows.
Algorithm 8: DPExpCKGumb: Implementing the Exponential Mechanism on S(X) using the Gumbel
Distribution (Optimized implementation of Algorithm 1)
Data: (#i, #2....
Input: e, a (approximation parameter), [0. (quantile parameters)
Build summary sketch S(X) and let = [S(X]]
Let (v,, 91, A.) (( for all i [s]
maxIndex = -1
Vaxualue = -oo
/* Iterating over tuple values i
Let ==
while <= 8 do
Fmin Ejsigs 9j
fmax = min(A;- + Ejso Jj val(v;)) > val(e:))
u, minfly [qn]] y E [fmino fmax]}
10
f = 2 5 f = f + Gumb(0, 1) if f > max Value then
11
12
13
maxIndex = (i, tuple)
14
maxValuc =
15
minnf Uy > 3
/* Iterating over intervals between tuples X((1-11, C X
16
Let i=1
17
while i <= s do
18
if X( is not empty then
19
finn = Ejs( 9j
20
Amax = A1+1 + Ejsi+13 95
U 1.j = -mmin (ly [qa]] : y E [fmin Pmax]).
21
22
log()>((;,,1, r2)1 54-11,
f = f + Gumb(00,1
23
if j > max Value then
24
25
maxIndex = (i, interval)
maxValuc =
27
i+i+1
28 if mazInder- = (i, tuple) for some i E 1,...,, then
29
return 0;
30 else if mazInder= (i, interval) for some i 1,..., s then
Pick E (1 Uz) uniformly at random
return
As discussed before, in general naive implementation of the exponential mochanism as in Algorithm 1 would in general be efficient. To resolve this issue, in Algorithm 8 take advantage of the partition of the data domain by the score function and the Gumbel-maz trick to implement the exponential mechanism without
22

---

Published in Transactions on Machine Learning Research (06/2023)
any higher-order overhead and return an a-approximate q quantile. This trick has become standard way to implement the exponential mechanism over intervals/tuples.
Lemma B.12. Algorithm 8 implements Algorithm the data universe X' with space complexity ((I((x)))
(where (XX is the GK sketch) and additional time complerity ((1(())) log [8())))
Proof. We see that it will suffice to show that Algorithm 8 executes the exponential mechanism with the same score function as Algorithm 1 to prove that it is valid implementation of the latter.
As noted in previous work (Abernethy et al., 2017), if Zi,..., .....,Zxx ZN are drawn ii.d. from standard Gumbel distribution, then
exp(fi) Vi E EjeNN exp(J;)
P J 11+2, 2:
max (ʃs + 2,} 2,} ]E[M]
We recall that when running the exponential mechanism on X, we want to sample the element z E X with probability x (xp(eu(S(X),x) To implement the exponential mechanism via. the identification with Gumbel argmax distribution above, we will simply compute the scores u(S(X), and let
u(S(X),
For x E X' such that x 02 for some E [s], Algorithm 8 directly computes the scores according to Definition B.8 and Lemma B.4; this is formalized by lines 5 to 15 in the pseudo code.
For I E X which lie strictly between the tuple values fo; : é E [s]], we proceed as follows. Fixing i, from Lemma B.4 we have that that for X(1;-1, 1, 0z) = for E X : x > 0;-1, < v;), the rank confidence interval estimate is the same, i.e. [Ejsi- 9j. Ai + E 9.1. It follows from Definition B.8 that for all such domain values the the score function value ((S(X),)) is equal; this is denoted u4-1, in the pscudo code. By summing the probabilities for sampling individual domain elements, it follows that the likelihood of the exponential mechanism outputting some value from the set A1; v2) is x (X(1;-1, u:) exp(ct:11x/2)) = exp(eu,-1,:/2+ Log(l (o; v)))). This is formalized by lines 16 to 27 in the pseudo code.
Finally, if some interval is selected, then by outputting elements chosen uniformly at random, we ensure that the likelihood of x ((;-1, u/) being output x [x(;; 1,))] 1x(]] exp(cut-1x/2 + (og((-((;;11,1 2))l exp(eu,_1.). Note that we do not need to account for ties in the Gumbel scores as the event f: - Zi = fy Zz for any j # i has measure 0. 5
To bound the space and time complexity; we note that by the guarantees of the GK sketch, the size of the sketch S(X) O((1/a) log an); we compute Gumbel scores by iterating over tuples and intervals of which there are at most ((((X))-many of each, each computation takes at most O(log [S(X)) time, and only the max score and index seen at any point is tracked in the course of the algorithm.
We can now state and prove main theorem in this section, proving utility bounds for a-approximating quantiles through DPExpGK with sublinear space.
Theorem 4.1. Algorithm 1 is e-differentially private. Let & be the value returned by Algorithm 1 when initialized with target quantile q. The following statements hold:
1. Algorithm can be implemented to run with space complexity O((1/a) log an), such that with prob- ability 1 1-8
d[[ga], [f (2), Fmax(())) < 2om 2(4am + 2) log()>1133)
(2)
2. For n
O >
24 1/333 a minin,. () Algorithm can be implemented to run with space complerity such that with probability 1 3, is an a approzimate q-quantile.
As is usual in the privacy literature, we assume that the sampling of the Gumb((, 1) distribution can be done finite- precision computers (Balcer & Vadhan, 2018). While the problem of formally dealing with rounding has not been settled in the privacy literature (Mironov, 2012), for any practical purpase it easily suffices store the output of the Gumbel distribution using few computer words.
23

---

Published in Transactions on Machine Learning Research (06/2023)
Our dependence in a, which for practical purposes is usually the most important term, is optimal. Recent subsequent work by Kaplan and Stemmer (Kaplan & Stemmer, 2021) shows how to improve the dependence in other parameters if approximate (rather than pure) differential privacy is allowed, or if the stream length is large enough.
Proof. The privacy guarantee of Algorithm follows from the privacy guarantee of the exponential mecha- nism and Lemma B.12. The accuracy bound in equation is simply a restatement of Lemma B.11, and the space complexity bounds follow from the GK sketch space complexity bound O (1 log angg....... To derive the second statement, we substitule mmin(e.1) for the approximation parameter a in equation 2 and gel 241zg(22123)
d([gn] [min ($), (max(()]]
2(4( min(e.1) ) 2) 1)g(((11133) 24 log( [2108
< 2 m 1)
24 log log()
om
on
4 1og //
12 log((11))3
3
c
on
on
12 3
3
an.
The space complexity bound now follows directly from the space complexity bound derived in Lemma B.12, the space complexity bound (((1/a) log on) for the GK sketch, and by substituting mr. for a. Sincve the approximation parameter must be greater than 1/n, we have that lo 733)
B.2 Proofs of privacy and utility for DPHistGK
In this section we prove Theorem 4.2, which we restate here for case of reference.
Theorem 4.2. For the one- meedimmnssionl normal distribution N(,, let S= X2....,, be a data stream through which we wish to obtain Q3, a DP estimate of the q-quantile of the distribution.
For any q E (0, 1), there erists 8)PP) algorithm such that, with probability at least 1 3, oblain 1Q% Q31 S a for any > 0, B (0, e], E (0, 1/n) and for stream length
n P max {min {A, B), C3. where
A A
R
log
R
B= 0 ( log
R
1
.
R² 02a2
log
1)
EGa
oB
38
as long as P E (-R, R, R) and using space of O(max ( 1 log an)).
Proof. For any stream (XI,...;_,,) we use the triangle inequality so that
Q2 Q31 s Q4 Q3 + 1Q3 Q31
(3)
< <a/2+ a/2.
(4)
Q31 a/2 follows with probability 1 1 3/2 by Corollary B.14 and 1Q3 - Q31 & a/2 follows with probability 1 - B/2 by Lemma B.15. The space complexity follows with probability 1 via the deterministic nature of the Greenwald-Khamn sketch.
J
Lemma B.13 IDvoretaky-Kieee--Wool Wolfowitz inequality (Dvoretzky et al., 1956)). For any n. E Z+, let
X1....,X, Xn be i..dd random variables with cumulative distribution function F so that F(x) is the prob- ability that a single random variable X is less than x. for any x E R. Let the corresponding empirical distribution function be F2(2) = + En 1[X, I x) for any x E R. Then for any y > O.
sup Fx (x) - F(x) > >)) s MER
24

---

Published in Transactions on Machine Learning Research (06/2023)
Corollary B.14. For any q (0, 1), let 2% be the q-quantile estimate for the distribution D and Q' be the q-quantile estimate for the sample. Then, 10% - Q'll S a/2 with probability 3/12 when 2 o² log 4/B.
2
1 27 4/8 and 7 a12. Lemma B.15. For any g (0, 1), a > O, 3 E (0, 1], e, (0, (0,1/n), there exists an (e, 8) diffferrennl private algorithm Q'' for computing the q-quantile such that
Proof. Follows by the DKW inequality (Lemmaa B.13) where 2
I0's Q33 a/2,
with probability 11-8 33 for stream length
n 2 O
min
(
R
log
R
o
( caa B8 1/)) )))
R
1 log
EOG
o3)
Furthermore, with probability 1, Q3's uses space of O(max R 1 log am)).
Proof. First, by the tail bounds of the Gaussian distribution (Claim B.17), we can obtain that for any i E [n]]
P[| > cj S 2e 2 /20? 1220?
that by the union bound,
P |X; - 1l 2 S 2ne - -2212r
which implics that for any 8 E (0, 1].
PMV XX; - nl S o 22og 4n/5 2 B/2,
which holds by our sample complexity (stream length) guarantees.
Next, let r [R/a]. 6 Divide |-R-o/2, / into 2r+1 bins of length at most each. Each bin B, should equal ((j 0.5)o, (j + 0.5)a] for any j E (-r,...., Next run the histogram learner of Lemma B.16 with per-bin accuracy parameter of a/K, high-probability parameter of 3/2, privacy parameters e, E (0, 1/n), and number of bins K = R|// + 1. We can do this because of our sample complexity (stream length) bounds. Then we obtain noisy estimates p.r......27 Pr with per-bin accuracy of a/K. Then any quantile estimate would have accuracy of (by summing noisy estimates for at most K bins).
Next, use these bins construct sketch (private by DP post-processing) based on the deterministic algorithms of (Greenwald & Khanna, 2004) to, with probability 1, obtain space of O(max R 1 log anJ). J
Lemma B.16 (Histogram Learner (Bun et al., 2015; Vadhan, 2017; Karwa & Vadhan, 2018)). For every K E NO {oo} and every collection of disjoint bins Bi...., Bx defined on the domain X. For any N, é E (0, 1/n),, > O, and 3 E (0, 1), there erists an (c, 6)D algorithm M X - BK such that for every distribution ID) on the domain X, if
1. X1,
X DJ PE = P(X; E BR] for any & E [K],
(øi..... PK) M(XI....... Xx).
n max min
log
2K 8 log 36 s 2 log 4 3 ea
}
1
B }
then (over the randommess of the dala XI,..., Xn and of M)
1. MX~D,M pal < a) > 1, 3, Plargmax, Pk 5] < np K 2 2/8, Note that this argument similar to the arguments Algorithm (Karwa Vadhan, 2018).
25

---

Published in Transactions on Machine Learning Research (06/2023)
3. Plargmax, Pk S np, + 2 eexp(-(en88) (max Pk)) if K 2/6.
Claim B.17 (Gaussian Tail Bound). Let Z be a random variable distributed according to standard normal distribution (with mean 0 and variance 1). For every > 0,
P|Z| > 11> < 2exp(-1211)
Lemma B.18. Algorillm 2 salisfies (e, O)-P).
Proof. For any i [n], any ilem x; can belong in at most one bin. Plus, the global sensitivity of the function that computes the empirical histogram 2, since changing single item change the contents of at most two bins.
As result, adding noise of Lap 2/c) to each bin satisfies D-D by Theorem B.19.
Theorem B.19 (Laplace Mechanism (Dwork et al., 2006)). Fix e >> 0 and any function f )mhh + R The Laplace mechanism outputs
f(y) + (I,...., Lk),,
Li,...,, LK Lap(O, /S) where GSy the global sensilivity of the function f. Purthermore, the mecha- nism salisfies (e, DDP
B.3 Extension to the Continual Observation setting
In this section we prove Theorem 5.1, which formalizes the privacy and utility guarantees of Algorithm in the continual observation setting. We start by making some definitions that will aid us in our analysis. Definition B.20. We make the following definitions:
1. Stream Prefix: Given an input data stream X = (II,..., we define the prefix up to the index s element of this stream X(1 : s] := (Z1....,Z.). Note that we can overload notation and treat X[1 s] as a data set by ignoring the order in which the elements arrive.
2. Checkpoint: A set S + 0 set of checkpoints for stream X if Vj SS, E value uy that is approxaapee g-quantile for X[1 :
We first observe that if we have an a/2 approximate quantile for a given data set, then that estimate remains at least an a-approximate quantile for slightly larger set as well.
Lemma B.21. If a E is an a/2-approzinaae q-quantile for a data set (for some q E [0, 1]), then a is an a-approzimate q- quontile for any data set X X such that |X s (1 + x
Proof. Since x an a/2-approximate q-quantile, we have that
(1 - a/2)|X|X S rank(x) s a/2)/
We then have that
rank(x)= = Σ 1355a) xx]
X
DEX'
Σ
1 2) +
Σ 1|
DE
VEX'
E1yss < Σ <3 Σ 1yy xz] +
Σ
1
VEX
yEX
vEX
(1- a110/22
Σ
1b53
(1X1 -x)
26

---

Published in Transactions on Machine Learning Research (06/2023)
+ (1- a010)/2)
Σ si (1 (1 a
yEX'
+ (1-a)XX|
Σ
1 5 (1+
yEX'
i.., x is also an a-approximate q-quantile for X', as required.
We show that the choice of checkpoints made in the pseudocode of algorithm 3 is valid per definition.
Lemma B.22. In Algorithm 8, the set {cp(s') s E [n]} forms a valid set of checkpoints for the data stream X. More concretely Us is an a/2-aoprorimmate q q-quantile for X[1 s].
Proof. First we bound the size of the set of checkpoints {cp(s') : o E [n]]]. Since a new checkpoint value is generated only when 8 2 (1 (=-))p)ps))) it follows that for any new checkpoint where cp(s') * cp(s' 1)), have cp(s') (1 + a/2)cp(s' where ax a/2, 8 and ex are the accuracy parameter, the failure probability, and the privale parameter that are passed in the calls to DPExpOK, respectively. It follows that there are at most & < log1+a/2 n2 log n checkpoints using the fact that for all x > -1, 1+x
1). Using Theorem 4.1, set the first checkpoint value to 24 |
x I log(1 + x) S x.
Since Vcp((s) the output DPExpGK given GK sketch with accuracy parameter a/2 and privacy parameter of
c" it follows that with probability 1 S* where 3 l rankx]us] E (1 a/2, + a/2)qn. We now apply the union bound over all private approximate quantile computations al checkpoints and are done. J
We now prove our main technical result..
Theorem 5.1. Let c,a > O, n E Z. For any 8 E (0, with probability 2 B, Algorithm 9 maintains an a-approzimate q-quantile at every point s in the data stream for s = S Algorithm 3 satisfies e-DP and has space complerity S ( (ate log" n log [x logn ag
log n 12 1B). Furthermore,
are
Proof. To see that Algorithm is e-DP, we observe that the output of this algorithm throughout the data stream can be sunmarized by its outputs at the checkpoints {cp(s) 8 E [w]} (the points in the stream at which a new checkpoint reached and a new value released are known publicly, so this suffices for privacy analysis). follows that there is a choice of c* 3logn
ae that gives us an cDP mechanism.
We now prove the accuracy guarantee. From the second statement of Theorem 4.1 we get that for points in 48 |X1/2 the stream s such that cp(s) 2 mi) i.c., the first checkpoint, the output vs will be an a/2-accurato quantile for X[1 cp(s)). Then, since [X[1 : s]] = s < (1 + a/2)cp(s) < (1 + a/2)] : cp(s)],, by Lemma B.21 follows that (an E (1 - a, + a)m,, i.c., vs is an a-approximate q-quantile for :].
C Additional Experiments
In this section, we include some additional experimental details and results.
Varying for DPExpGKGumb: Table 1, we vary and compare DPExpFull to DPExpGKGumb in terms of average absolute error and execution time (in seconds). We that DPExpGKGumb is significantly faster than DPExpFull in terms of average execution time. However, DPExpGKGumb incurs larger error because of the approximation factor of a 0.0001.
The last checkpoint might occur (1 + a/2mm. We may ignore checkpoints past
27

---

Published in Transactions on Machine Learning Research (06/2023)
c
DPExpFull (Error)
DPExpCKGumb (Error)
DPExpPull (Time)
DPExpCKGumb (Time)
0.1
0.0019796
0.002172
0.1330166
0.028163
0.5
0.0004581
0.0013467
0.13113595
0.02804
0.000249894
0.00127795
0.1335331
0.0284041
5
0.00007110
0.00151
0.1341164231
0.028285
Table 1: 0.0001, 10 U(0, 10). Time in Seconds.
Histogram-Based Algorithm: We also implemented the DPHistGK and tested by varying the bin width of the histogram. In general, we observe that DPExpGK has superior performance in terms of minimizing the error for any single quantile query. For example, we oblain averge absolute errors of at least 2.56 for bins and 3.001 for bins for q = 0.3 for DPHistGK. This suggests that we can rely on DPExpGK and its variants for gencral-purpose implementations with minimal crror. However, possible that certain parameter scttings (e.g.; bin width) for DPHistGK might yield better performance.
Continual Obscrvation Algorithm: We also implement the continual obscrvation algorithm that builds directly DPEXpGK. We fixed the first stream checkpoint to 10000. For 0.001 and stream length of = 100000 from UO0 10), we observe average absolute error of 0.00723 for (0.1, 0.5, 1,5) over 100 trials. For = 0.001 and stream length of n = 100000 from (5,, 1), we observe average absolute error of 0.00134. However, it is possible that the first few checkpoints might be an important parameter for the error of the sketch in the continual observation setting. We leave the full exploration of this question future work.
C.1 Full Space Quantile Computation
Without the bounded space requirement (i.e., space sublinear in the stream length), we can use the expo- nential mechanism with a score function that uses the entire stream values X. In that case, the sensitivity of the score function is at most 1. We use this one of the baselines for our experimental validation.
Lemma C.1. Given any insertion only stream
X= T2,, 201 In-1,
the sensitivity of the score function u. (under swap differential privacy) is at most 1. i.e., 5, S 1. The function u is defined as -Ilankk r where r is the approzimate [q n. rakk of the sketch and rank(X, X,e) is the runk of amongst all values in the stream X.
=
Proof. Let |X| = n. The score function becomes - -lrnnk(X,,) nel where ny = 1 nn. Consider two streams with only one element changed: X, X, denoting the element by zz- Then time S n, in the second stream x'y is inserted instead of zqz- In both cases, By changes by at most q (in the case of add-remove DP) and for swap DP, ng remains the same. And for any e, rank(X',e) would differ from rank(X,e) by most since the rank of any element can change by at most 1 after adding, deleting, in the stream. Furthermore, for any n 2 d, the rank of any will differ in X' by at most I replacing æd with I'd can displace the rank of any clement by at most 1. Also, the term ng will remain the same. (Note that in the add-remove privacy definition n, = [ nJ would change to either [g (n + 1)] or [q - 1)--
replacing an item
The "reverse triangle inequality" says that for any real numbers x and y, Jr yl 2 ||x|| - -eel- As result, -| (rank(,,))) ngl rrankXXX .e) nal $ raak(X', e) rank(X, e)l < for any
28


Reviews:
[{"review_id": "ln9gpUBrwu", "reviewer": "Reviewer_SR6t", "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": "Strengths: \n\nThe paper studies an interesting problem: DP quantile estimation with sublinear space complexity. The authors combine basic sketching algorithms with DP algorithms to solve this problem. Both of these add value to the DP machine learning community. The narrative of the first portion of the paper (up to section 4.1) is clear. \n\nWeaknesses:\n\n**Technical Soundness:**\nThe algorithm and analysis presented in section 4.2 seem to contradict some of the statements made earlier. E.g., \n- Page 5, before section 4.1, the authors motivate DPHistGK to solve the all-quantiles problem (the guarantee I expect here is something along the lines of $P[ \\text{quantile diff} < \\alpha, \\forall q ] \\le \\beta$). Yet, even under the normality assumption (given at end of page 7), the theoretical guarantee stated in Theorem 4.2 seems to suggest otherwise ($\\forall q, P[ \\text{quantile diff} < \\alpha ] \\le \\beta$). \n- The theoretical analysis in Section 4.2 doesn't quite type-check with the main setup developed in Section 3.2, since the normality assumption in Section 4.2 would assume that the data universe is not only unbounded but also not finite. \n\nThe complexity and utility analysis for Algorithm 2 is useful, but the assumptions are also strong (e.g., normality, known bound R etc). Presumably, under these specific assumptions, a simpler algorithm for estimating the quantile would be to first estimate the mean and variance of the underlying normal and derive the quantile value directly from the converted inverse CDF (there are efficient streaming algorithms for mean and variance estimation). How does this simple algorithm compare to the given DPHistGK in terms of utility (under the same privacy spending)? ", "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 DP quantile estimation under the sublinear space complexity constraint. \n\nTo address the research problem, the paper builds 2 lines of algorithms, both of which heavily rely on the Greenwald-Khanna algorithm for producing sketch intervals. \n\nThe first algorithm applies the exponential mechanism to privately select the appropriate interval in the GK output. The authors design a scoring function for the intervals to achieve this. The use of the Gumbel-max trick to further improve efficiency is natural. \n\nThe second algorithm builds a histogram based on GK intervals, derives an approximate empirical CDF, and releases privatized statistics with the Laplace mechanism. \n\nAuthors also extend their algorithms and analysis to the continual release setting and conduct basic numerical experiments with their developed algorithms. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Technical Soundness:**\nI am mainly concerned about the development and analysis of Algorithm 2, as I'm uncertain it's a good/reasonable algorithm for the all-quantiles problem as the authors have suggested. Specific questions\n- Under the assumptions in Theorem 4.2, do we get an \"all-quantiles\" guarantee as defined in 3.6? \n- For normal quantile estimation, how does Algorithm 2 DPHistGK compare to the simpler algorithm I describe above? \n- Could the authors give some examples to clarify why a general utility guarantee would not hold for DPHistGK? \n\n**Writing clarity:**\n- $Q_\\mathcal{D}^q$ in def'n 3.5 is undefined. \n- Page 6, the authors use the term \"confidence interval\" to describe the intervals returned from GK, where those intervals aren't really CIs in the frequentist statistics sense.\n- the distance function $d$ in eq (2) is undefined.\n", "broader_impact_concerns": "This work develops and analyzes algorithms for DP quantile estimation. In its current form, the work does not present any long-term ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TdCOV0bjTl", "reviewer": "Reviewer_89Xd", "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": "The paper is well-written. The design of the two algorithms is simple, so practitioners will find it easy to implement. The theoretical analysis is also sound. Overall, I think this is a cute paper.", "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 studies differentially private quantile estimation, with sublinear space complexity. It provides two algorithms in the one-shot setting: one relies on the exponential mechanism, and the other one relies on the histograms. The algorithms both instantiate the Greenwald-Khanna sketch for non-private quantile estimation as the basic building block, which is critical for achieving sublinear space complexity. The paper also provides a theoretical analysis of the space complexity for two algorithms. It then extends the one-shot algorithms to the continual release setting. Some experimental results are given to demonstrate the performance of the algorithms. \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have a few concerns and questions.\n1. It's not clear how to choose \\Delta_i in DPExpGK. Also, \\Delta_u is the sensitivity of the score function. Using the same notation \\Delta is confusing.\n2. I think the continual release algorithm is somewhat weak since we want \\alpha to be very small, then O(\\log_{1+\\alpha} n/n_min) would be very large. Can you elaborate on the role of n_min, and how you achieve O(\\log n/\\eps\\alpha)?\n3. The experiments only show the estimation of the median (q=0.5), I think it's worth adding more results for other choices of q. Moreover, it seems the choice of q does not affect the space complexity, but will it affect the accuracy?\n4. I'd suggest adding experiments for the continual release setting.\n5. Can DPHistGK extend to answer the empirical CDF?", "broader_impact_concerns": "It doesn't require a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DDAiddghwO", "reviewer": "Reviewer_B6tU", "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": "## What I liked:\n\n * The paper seems to introduce a problem at the intersection of two interesting areas.  \n\n * It provides what seems to be a general approach, with proven bounds.  \n\n\n\n## What I did not like:\n\n * The notation was very heavy, it seemed unnecessarily so at times.  For instance, d, S, and R are overloaded many times.  And some elements were not always explained in the main 12 pages.  For a couple of examples just in Definition 3.1:\n      - what are \"neighboring databases\"\n      - what are $S$ and $\\mathcal{R}$? \n\n   and notably \n      - $\\Delta_u$ in (Algorithm 1 & Thm 4.1) is only explained in the appendix (I think)\n      - And in Thm 4.1, what is S in Definition 3.1 in this context?\n\n  * Differential Privacy requires a proof :), but the core proofs are only in the appendix, and not even sketched in the first 12 pages.  I would emphasize putting proofs in the first 12 pages for the main result.  This, IMO, is more important than the algorithm focusing on data from a Normal distribution -- that requires a much stronger assumption on the data ... or Section 7.  \n\n  * The paper does not justify the specific focus on the GK sketch when there are many better sketches, and which I think can be treated as just a black box.  ", "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 studies the quantile estimation problem under a combination of small space (streaming) and differential privacy.  The goal is a combination of a summary (which could be maintained in a stream) that is size significantly less than the input size n (in their case roughly log(n)), and has a DP guarantee.  \nThe authors, nor this reviewer, are aware of any other work at this intersection.  Hence, the first algorithm and analysis for this is enough to publication in TMLR.  \n\nThe algorithm is quite simple:\n  * run a standard streaming quantile algorithm (the paper chooses the classic GK sketch)\n  * on a query apply the Laplacian mechanism to the answer.  \nWhat appears to be crucial (I had to dig into the appendix to figure this out -- I think I am interpreting it correctly) is that the sketch defines a region of values which satisfy the alpha-approximate quantile property.  The exponential DP mechanism then results in a value from a distribution that is:\n        (a) uniform over this region\n        (b) decays exponentially for values which deviate from this range.  \n\n\nThe paper also discussion extensions to:\n  * (1) how to apply this mechanism on all possible queries, not just *one* queried point.\n  * (2) how to improve bounds when the distribution is well-behaved (is known to be Normal)\n  * (3) how to ensure DP while data continues to stream in\n  * (4) some empirical studies.  \nThese are all straight-forward.  I have two small concerns:\n\nFor (1).  It queries at 1/alpha quantiles adjusting the error guarantees by a factor (1/alpha), and claims these values are enough.  However, I worry what happens if the jth sampled value is larger than the (j+1)th sampled value. Does that cause any issues?  (e.g., what happens if the returned 0.4 quantile is larger than the 0.45 quantile?)\n\nFor (4).  The error is measured in the value space, under relative error.  This is what DP cares about.  But streaming quantile summaries typically measure error in the estimates of the CDF.  e.g., if one asks for the 0.35 quantile, and the algorithm returns a value v, then the error is \n  |0.35 - CDF(@ v)|\nThat is, if the CDF at value v is 0.20 (there are only 20% of the value less than v), then the error is 0.15.  The example in Figure 1 shows that small changes in v [e.g., true value = 2.0 (CDF(v) = 0.5), approximate value 1.9999 (CDF(1.9999) = 0.125)].  This is not measured at all.  The way error is presented for DP can seemingly cause a very large discrepancy in this sense.  It may be ok, since it is perhaps the best one can do.  But it would be good to evaluate and explore.  \n  [Under the distributions the paper considers, I assume it won't be too bad since they are smooth.]\n\n\nI am also not sure why the paper features the old Greenwald-Khanna sketch.  Sure it is deterministic, but there are much better randomized one.  And since the exponential mechanism (and DP in general) is probabilistic, one can simply set probability of failure in each stage to beta/2, and use Union bound to get a total probability of failure beta.  ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": " * Theorem 4.1 & Algorithm 1 (the main result) should be:\n     - written with much more clear notation, so one could implement and trust the DP proof without digging through the appendix.  \n\n * The paper should be written to be able to use a generic quantile sketch, or explain why that cannot work.  The deterministic argument does not really make sense as pointed out in the last paragraph of Sec 2.1.  \n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers were in agreement that the final paper was satisfactory, and appreciate the revisions made by the authors, particularly with respect to generalizing the result.
Decision: Accept (poster)