Unbounded Differentially Private Quantile and Maximum Estimation
Authors: David Durfee
Venue: NeurIPS 2023 poster (2023)
Keywords: Differential privacy
Theory
Spars Vector Technique
Quantile

Abstract: In this work we consider the problem of differentially private computation of
quantiles for the data, especially the highest quantiles such as maximum, but
with an unbounded range for the dataset. We show that this can be done
efficiently through a simple invocation of $\texttt{AboveThreshold}$, a
subroutine that is iteratively called in the fundamental Sparse Vector
Technique, even when there is no upper bound on the data. In particular, we
show that this procedure can give more accurate and robust estimates on the
highest quantiles with applications towards clipping that is essential for
differentially private sum and mean estimation. In addition, we show how two
invocations can handle the fully unbounded data setting. Within our study, we
show that an improved analysis of $\texttt{AboveThreshold}$ can improve the
privacy guarantees for the widely used Sparse Vector Technique that is of
independent interest. We give a more general characterization of privacy loss
for $\texttt{AboveThreshold}$ which we immediately apply to our method for
improved privacy guarantees. Our algorithm only requires one $O(n)$ pass
through the data, which can be unsorted, and each subsequent query takes $O(1)$
time. We empirically compare our unbounded algorithm with the state-of-the-art
algorithms in the bounded setting. For inner quantiles, we find that our method
often performs better on non-synthetic datasets. For the maximal quantiles,
which we apply to differentially private sum computation, we find that our
method performs significantly better.

Unbounded Differentially Private Quantile and Maximum Estimation
David Durfee Anonym Inc. dav david@anonymcco.co com
Abstract
In this work we consider the problem of differentially private computation of quantiles for the data, especially the highest quantiles such maximum, but with an unbounded range for the dataset. We show that this can be done efficiently through a simple invocation of AboveThresholde a subroutine that iteratively called in the fundamental Sparse Vector Technique, even when there is no upper bound on the data. particular, we show that this procedure can give more accurate and robust estimates on the highest quantiles with applications towards clipping that is essential for differentially private sum and mean estimation. In ad- dition, we show how two invocations can handle the fully unbounded data setting. AboveThreshee
Within our study, we show that an improved analysis improve the privacy guarantees for the widely used Sparse Vector Technique that is of independent interest. We give a more general characterization of privacy loss for AboveThre Threshold which we immediately apply to method for improved privacy guarantees. Our algorithm only requires one O(n) pass through the data, which can be unsorted, and each subsequent query takes 0(1) time. We empiri- cally compare our unbounded algorithm with the state-of of-tthe-tttttttt algorithms the bounded setting. For inner quantiles, find that our method often performs better on non-synthetic datasets. For the maximal quantiles, which we apply differentially private sum computation, we find that our method performs significantly better.
can
Introduction
In statistics, quantiles are values that divide the data into specific proportions, such as median that divides the data half. Quantiles are a central statistical method for better understanding a dataset. However, releasing quantile values could leak information about specific individuals within a sensitive dataset. As a result, it becomes necessary to ensure that individual privacy is ensured within this computation. Differential privacy offers rigorous method for measuring the amount that one individual can change the output of a computation. Due it's rigorous guarantees, differential privacy has become the gold standard for measuring privacy. This measurement method then offers an inherent tradeoff between accuracy and privacy with outputs pure noise achieving perfect privacy. Thus, the goal of designing algorithms for differentially private quantile computation is to maximize accuracy for a given level of privacy.
There are variety of previous methods for computing given quantile of the dataset that will cover in Section 1.2, but each of these requires known bounds on the dataset. The most effective and practical method invokes the exponential mechanism Smith (2011). For computing multiple quantiles this method can be called iteratively. Follow-up work showed that it could be called recursively by splitting the dataset at each call to reduce the privacy cost of composition Kaplan et al. (2022). Further, a generalization can called efficiently in one shot Gillenwater et al. (2021).
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

1.1 Our contributions
In this work, we offer an alternative practical and accurate approach, Unbounded Quantile Esti- mation (UQE), that also invokes a well-known technique and can additionally be applied to the unbounded setting. While the commonly-used technique designs distribution to draw from that specific to the dataset, our method will simply perform noisy guess-and-check Initially we assume there is only a lower bound on the data, as non-negative data common in real world datasets with sensitive individual information. Our method will simply iteratively increase the candidate value by a small percentage and halt when the number of data points below the value exceeds the desired amount dictated by the given quantile. While the relative increase will be small each iteration, the exponential nature still implies that the candidate value will become massive within a reasonable number of iterations. As consequence, our algorithm can handle the unbounded setting where also show that two calls to this procedure can handle fully unbounded data. Computing multiple quantiles can be achieved by applying the recursive splitting framework from Kaplan et al. (2022).
Performing our guess-and- and-check procedure with differential privacy exactly fits AboveThreshold, a method that is iteratively called in the Sparse Vector Technique Dwork et al. (2009). We also take a deeper look at AboveThreshold and unsurprisingly show that similar to report noisy max algorithms, the noise addition can come from the Laplace, Gumbel or Exponential distributions. We further push this analysis to show that for monotonic queries, a common class of queries which we will also utilize in our methods, the privacy bounds for composition within the Sparse Vector Technique can be further improved. Given the widespread usage of this technique, we believe this result is of independent interest. Furthermore, we give more general characterization of query properties that can improve the privacy bounds of AboveThreshole We immediately utilize this characterization in our unbounded quantile estimation algorithm to improve privacy guarantees.
While the commonly used algorithms for quantile estimation can still apply incredibly loose bounds to ensure the data is contained within, this can have a substantial impact upon the accuracy for estimating the highest quantiles such as maximum. This leads to an especially important application for our algorithm, differentially private sum computation, which can thereby be used to compute mean as well. Performing this computation practically without assumptions upon the distribution often requires clipping the data and adding noise proportionally. Clipping too high adds too much noise, and clipping too low changes the sum of the data too much. The highest quantiles of the data used for clipping to optimize this tradeoff. The unbounded nature of our approach fundamentally allows us to estimate the highest quantiles more robustly and improve the accuracy of differentially private sum computation.
This improvement differentially private sum computation is further evidenced by our empirical evaluation, with significant improvements in accuracy. Our empericial comparison will be upon the same datasets from previous work in the bounded setting. We also compare private computation of the inner quantiles on these datasets. For synthetic datasets generated from uniform or guassian distributions, we see that the more structured approach of designing a distribution for the data from the exponential mechanism consistently performs better. However, for the real-world datasets, we see that our unstructured approach tends to perform better even within this bounded setting, By design our algorithm is less specific to the data, so alternative approach becomes advantageous when less is known about the structure and bounds of the data a priori. As such, for large-scale privacy systems that provide statistical analysis for wide variety of datasets, our methods will be more flexible to handle greater generality accurately.
1.2 Background literature
The primary algorithm for privately computing a given quantile, by which we compare our technique, applies the exponential mechanism with utility function based upon closeness to the true quantile Smith (2011). We will discuss this algorithm, which we denote as Exponential Mechanism Quantile (EMQ), in greater detail in Appendix A. This approach was then extended to computing multiple quantiles more cleverly by recursively splitting the data and establishing that only one partition of
Forr example, see Roth and Roughgarden (2010); Hardt and Rothblum (2010); Dwork al. (2015): Nissim al. (2016): Nissim and Stemmer (2018); Kaplan et al. (2020a.b); Hasidim et al. (2020); Bun et al. (2017): Bassily et al. (2018); Cummings et al. (2020); Ligett et al. (2017); Barthe et al. (2016a.b): Steinke and Ullman (2016): Cummings et al. (2015): Ullman (2015); Nandi and Bassily (2020); Shokri and Shmatikov (2015); Hsu et al (2013); Sajed and Sheffet (2019): Feldman and Steinke (2017); Blum et al (2015): Chen et al. (2016)
2

---

the dataset can change between neighbors thereby reducing the composition costs Kaplan et al. (2022). Additional fu work showed that generalization of the utility function multiple quantiles could be efficiently drawn upon in one shot Gillenwater et al. (2021). Another recent result examined this problem the streaming data setting and gave a method that only uses strongly sub-linear space complexity Alabi et al. (2022).
Quantile computation can also be achieved through CDF estimation Bun al. (2015); Kaplan et al. (2020a). However these techniques offer limited practicality as they rely upon several reductions and parameter tuning. Recursively splitting the data is also done for CDF estimation algorithms where the statistics from each split can be aggregated for quantile computation Dwork et al. (2010); Chan al. (2011). These techniques tend to be overkill for quantile estimation and thus suffer in accuracy comparatively.
We will also give improved privacy analysis of the Sparse Vector Technique which was originally introduced in Dwork et al. (2009). A more detailed analysis of the method can be found in Lyu et al. (2017). Additional recent work has shown that more information can be output from the method at no additional privacy cost Kaplan et al. (2021); Ding et al. (2023).
1.3 Organization
We provide the requisite notation and definitions in Section 2. In Section 3, we review the AboveThreshold algorithm from the literature and show that privacy analysis can be further improved. In Section 4, we provide our unbounded quantile estimation method. In Section 5, we test our method compared Appendix A, we consider the estimation of the highest quantiles which has immediate application to differentially private sum and mean estimation. Appendix B, we give further results on the AboveThreshen algorithm and provide the missing proofs from Section 3. In Appendix C, provide further variants and extensions our unbounded quantile estimation technique.
the previous techniques on synthetic and real world datasets. In
Preliminaries
We will let x,x' denote datasets in our data universe X.
Definition 2.1. Datasets x E X neighboring if most individual's data has been changed.
Note that we use the swap definition, but our analysis the Taeveohhesholleee agnostic to the definition of neighboring. Using this definition opposed to the add-subtract definition is necessary to apply the same experimental setup as in Gillenwater et al. (2021). Our differentially private quantile estimation will apply either and we will give the privacy guarantees we instead use the aud-subtract definition in Appendix C.2.
will be
Definition 2.2. function f X² R has sensitivity A if for any neighboring datasets If(x)
f(x) A
Definition 2.3. Dwork et al. (2006b,a) A mechanism M X is (i(e:))-diffrrnntially---- (DP) if for any neighboring datasets x.x & and S y: Pr[M(x) e S] < <PP(M(2') +.
We will primarily work with pure differential privacy in this work where 5 = 0. We will also be considering the composition properties of the Sparse Vector Technique, and the primary method for comparison will be Concentrated Differential Privacy that has become widely used in practice due to it's tighter and simpler advanced composition properties Bun and Steinke (2016). This definition instead based upon Reny divergence where for probability distributions P, P.Q over the same domain and a
P(z) Q(z)
(.(P)))) =
In 2-P
a
Definition 2.4. Bun and Steinke (2016) A mechanism M X y p-zero-comcentratedd differentially-privtte (zCDP) if for any neighboring datasets x,x' E X and all E (1.
(c(M())) pa.
3

---

We can translate DP into zCDP in the following way.
Proposition 1. Bun and Steinke (2016) If satisfies e e-DP then M satisfies _ -CDD
In our examination of AboveThreshole we will add different types of noise, similar to the report noisy max algorithms Ding et al. (2021). Accordingly, we will consider noise from the Laplace, Gum- bel and Exponential distributions where Lap(b) has PDF ptap(z;)) b), Gumbel(b) has PDF ( and Expo(b) has PDF ( ;;; b) where
1
PLap(z;b) b)= exp (-kz//b)
Pounbel exp 1-(z/b+e
2b
22 0
(x)
2<
We let Noise(b) denote noise addition from any of Lap(b), Gumbel(b), Expo(b). We will also utilize the definition of the exponential mechanism to analyze the addition of Gumbel noise.
Definition 2.5. McSherry and Talwar (2007) The Exponential Mechanism is a randomized mapping M X y such that
E y(x,))
Pr[M(x)= = y] oc exp
2A
where x y R has sensitivity A.
Improved Analysis for Sparse Vector Technique
In this section, review the AboveThreshold algorithm from the literature. To knowledge, this technique has only been used with Laplace noise in the literature. Unsurprisingly, we show that Gumbel and Exponential noise also be applied, with the former allowing for closed form expression of each output probability. We further show that for monotonic queries the privacy analysis of the Sparse Vector Technique, which iteratively applies AboveThresholle can be improved. All proofs are be pushed to Appendix B where we also give more general characterization of query properties that improve the privacy bounds of AboveThreshor
3.1 Above Threshold Algorithm
We first provide the algorithm for
where noise can be applied from any of the Laplace, Gumbel Exponential distributions.
Algorithm 1 AboveThreshold
Require: Input dataset x, stream of queries (ff X R3 with sensitivity A, and threshold T Set 7 = T Noise(A/E;)
2: for each query i do
Set Noise(A/Eg)
if f(x) v, 2 f then
5: Output T and halt
else
7: Output
end
9:
end for
We will also define common class of queries within the literature that is often seen to achieve factor 2 improvement in privacy bounds.
Definition 3.1. say that stream of queries {.f. R} with sensitivity monotonic if for any neighboring x E X we have either f((x) S f(lx) for all i f((x) f(x') for all

---

To our knowledge all previous derivations of AboveThreshold in the literature apply Lap noise which gives the following privacy guarantees.
Lemma 3.1 (Theorem and of Lyu et al. (2017)). If the noise addition Lap then Algorithm 1 (e1 + 2ep)-DP for general queries and is (ei + e2) for monotonic queries.
Given that Expo noise one-sided Lap noise, can often be applied for comparative algorithms such as this and report noisy max as well We will show this extension in the appendix for completeness.
Corollary 3.1. If the noise addition is Expo then Algorithm 1 (Eg + -PP for general queries and + e2) for monotonic queries.
While the proofs for Expo noise generally follow from the Lap noise proofs, it will require different techniques to show that Gumbel noise can be applied as well. In particular, utilize the known connection between adding Gumbel noise and the exponential mechanism.
Lemma 3.2. If the noise addition is Gumbel and & = e then Algorithm 1 queries and (E, + D2) for monotonic queries.
is (E: + 282)-DP for general
We defer the proof of this to the appendix. In all of our empirical evaluations we will use Expo noise in our calls to AboveThreshold because it has the lowest variance for the same parameter. While we strongly believe that Expo noise will be most accurate under the same noise parameters, we leave a more rigorous examination future work. We also note that this examination was implicitly done for report noisy max between Gumbel and Expo noise in McKenna and Sheldon (2020), where their algorithm equivalent to adding Expo noise Ding et al. (2021), and Expo noise was shown to be clearly superior.
3.2 Improved privacy analysis for Sparse Vector Technique
In this section, we further consider the iterative application of AboveThresholl which is known as the sparse vector technique. We show that for monotonic queries, analysis of sparse vector technique to oblain better utility for the same level of privacy. Our primary metric for measuring privacy through composition will be zCDP which we defined in Section 2 and has become commonly used particularly due to the composition properties. We further show in the appendix that our analysis also enjoys improvement under the standard definition of differential privacy, These improved properties immediately apply to our unbounded quantile estimation algorithm our queries will be monotonic.
improve the privacy
Theorem 1. the queries are monotonic, then for any noise addition Lap, Gumbel, Expo we have that Algorithm is require =z
- -CDD where -/2 Ez. If the noise addition is Gumbel then we further
Note that applying Proposition 1 will instead give & = Ei + 82. It will require further techniques to reduce this by / which will immediately allow for better utility with the same privacy guaranices. This bound also follows the intuilive factor of 2 improvement that is often expected for monotonic queries. The analysis will be achieved through providing range-bounded property, a definition that was introduced in Durfee and Rogers (2019). This definition is ideally suited to characterizing the privacy loss of selection algorithms,, by which we can view Threhhlre As such it will also enjoy the improved composition bounds upon the standard differential privacy definition shown in Dong al. (2020). This range bounded property was then unified with zCDP with improved privacy guarantees in Cesar and Rogers (2021).
We give a proof of this theorem along with further discussion in Appendix B.3. We will also give generalized characterization of when we can lake advantage of properties of the queries to tighten the privacy bounds in Above Threshlld We will immediately utilize this characterization to improve the privacy guarantees for our method in Appendix C.
4 Unbounded Quantile Estimation
In this section we give our method for unbounded quantile estimation. We focus upon the lower bounded setting which we view most applicable to real-world problems, where non-negative
5

---

data is incredibly common, particularly for datasets that contain information about individuals. This method can be symmetrically apply to upper bounded data, and in the appendix we will show how this approach can be extended to the fully unbounded setting.
For the quantile problem we will assume our data R". Given quantile q e [o. 1] and dataset x E R" the goal is to find & E R such that (x, E xxxx < t3] is as close to qn possible.
4.1 Unbounded quantile mechanim
The idea behind unbounded quantile estimation will be simple guess-and-check method that will just invoke AboveThreshon
In particula,, we will guess candidate valuest such that (x, E x|x, < r] is close to qn. We begin with the smallest candidate, recall that we assume lower bounded data here and generalize later, and iteratively increase by a small percentage. At each iteration we check if H x|x; < rif has exceeded gn, and terminate when it does, outputting the most recent candidate. In order to achieve this procedure privately, we will simply invoke AboveThreshold. We also discuss how this procedure can be achieved efficiently in Section 4.2.
Thus we give our algorithm here where the lower bound of the data, f, is our starting candidate and ß is the scale at which the threshold increases. Given that we want by a small percentage it must start as a positive value. As such we will essentially just shift the data such that the lower bound is instead 1. In all our experiments we set ß 1.001, so the increase is by 0.1% each iteration.
candidate value to increase
Algorithm 2 Unbounded quantile mechanism
Require:
Input dataset x, quantile q. lower bound f, and parameter B > 1 Run AboveThreshold with x, qn and f((x) (x, E xix; (+ < ( Output B + 1 where is the query that AhoveThreshold halted at
Given that our method simply calls AboveThreshold it will enjoy all the privacy guarantees from Section 3.1. Furthermore we will show that our queries are monotonic.
Lemma 4.1. For any sequence of thresholds {t R} let fi(x) Xx e x|x, till for all i. For any neighboring dataset under Definition 2, we have that (f] are monotonic queries with sensitivity 1.
Proof. Let xy be the value that differs between neighbors x, x' Define S,, = (x, E x/xx < f). We consider the case x x, and the other will follow symmetrically. For all thresholds f; (-00,xy) have x & S.n, and x A, so f((x) f(x'). For all thresholds t; (x/, o0) we have x, E Sya, and x/ E Sk so f(x) f(x'). Finally, for all thresholds E (x) we have X E SxA and x S. so fix)) f(x') + 1. Therefore, f(x) f(x') for all i, and the sensitivity is 1.
Note that for the swap definition of neighboring the threshold remains constant. We will discuss how to extend our algorithm and further improve the privacy bounds for the add-subtract definition of neighboring in the appendix.
4.2 Simple and scalable implementation
In this section we show how our call to AboveThreshold can be done with simple linear time pass through the data, and each subsequent query takes 0(1) time. While the running time could potentially be infinite, if we set B = 1.001, then after 50,000 iterations our threshold is already over 10a and thus highly likely to have halted. Unless the scale of the data is absurdly high or the value chosen converges to 1, our guess-and guess-and-checkk process will finish reasonably quickly."
In our initial pass through the data, for each data point x; we will find the index i such that B xx,, -+ B which can be done by simply computing (xog,(x,- - e+ 1)] as our lower bound ensures Xi - 1 121 1. Using a dictionary or similar data structure we can efficiently store (x, E xlβ' < X₃ 1+ 1 < Bit1) for each i with the default being 0. This preprocessing does not
"Note that the process also be terminated at any time without affecting the privacy guarantees.

---

require sorted data and takes O(n) arithmetic time, where we note that the previous algorithms also measure runtime arithmetically.
Finally, for each query we already have [x, E x|xz (+1 H. then we can add Kaz x1f8' < x, f+ 1 < J in O(1) time get [xy x/x, f+ B Inductively, each query will take O(1) time. We provide the code in the appendix for easier reproducibility.
4.3 Extension to multiple quantiles
The framework for computing multiple quantiles set up in Kaplan et al. (2022) is agnostic to the technique used for computing a single quantile. Their method will first compute the middle quantile and split the data according to the result. Through recursive application the number of levels of computation will be logarithmic. Furthermore, at each level we can see that most one partition of the data will differ between neighbors, allowing for instead a logarithmic number of compositions. As such our approach can easily be applied to this recursive splitting framework to achieve the same improvements in composition. This will require some minor updating of their proofs to the swap definition that we will do in the appendix.
Empirical Evaluation
In this section we empirically evaluate our approach compared to the previous approaches. We give further detail of the previous approaches, particularly EMQ, in Appendix A along with strong intuition upon why our approach will better handle maximal quantile estimation for data clipping. We first go over the datasets and settings used for experiments which will follow recent related work Gillenwater et al. (2021); Kaplan et al. (2022). Next we evaluate how accurately our method estimates quantiles for the different datasets in the bounded setting. Finally, will consider the application of computing differentially private sum, which also gives mean computation, and show how our algorithm allows for significantly more robust and accurate method when tight bounds are not known for the dataset.
5.1 Datasets
We borrow the same setup and datasets as Gillenwater et al. (2021); Kaplan et al. (2022). We test our algorithm compared to the state-of-the-art six different datasets. Two datasets will be synthetic. One draws 10,000 data points from the uniform distribution in the range 5, and the other draws 10,000 data points from the normal distribution with mean zero and standard deviation of five. Two datasets will come from Soumik (2019) with 11,123 data points, where one has book ratings and the other has book page counts. Two datasets will come from Dua and Graf (2019) with 48,842 data points, where one has the number of hours worked per week and the other has the age for different people. We provide histograms our datasets for better understanding Figure 1.
5.2 Quantile estimation experiments
For our quantile estimation experiments, for a given quantile q E [o, 1] we consider the error of outcome 0g from one of the private methods to be lo, -tyl where tę is the true quantile value. We use the in-built quantile function in the numpy library with the default settings to get the true quantile value. As in previous related works, we randomly sample 1000 datapoints from each dataset and run the quantile computation on each method. This process is then iterated upon 100 times and the error is averaged. We set = as in the previous works, which will require setting & = 1/2 for the call to AboveThreshold our method.
We will also tighten the ranges to the following, [-5.5] 5] for the uniform dataset, [-25, 25] for the normal dataset, [o, 10] for the ratings dataset, [o, 10000] for the pages dataset, [o, 100] for the hours dataset, and [0, 100] for the ages dataset. Given that EMQ suffers performance when many datapoints are equal we add small independent noise to our non-sythetic datasets. This noise will be from the normal distribution with standard deviation 0.001 for the ratings dataset and 0.1 for the other three that have integer values. Our method does not require the noise addition but we will use the perturbed dataset for fair comparison. True quantiles are still computed upon the original data. For the datasets with integer values we rounded each output to the nearest integer. For our method we set B = 1.001 for all datasets.
7

---

300
160
(a) Uniform
(b) Gaussian
(c) Book ratings
1603
14
200
1403
4000
(d) Book pages
(c) Census ages
Census hours
Figure 1: Histograms for each of our datasets.
For these experiments only compare method UQE and the previous method EMQ, using the implementations from Gillenwater et al. (2021). The other procedures, discussed in the appendix more generalized and thus for this specific setting do not perform nearly well which can be seen in the previous experiments Gillenwater et al. (2021); Kaplan et al. (2022), so we omit them consider estimating each quantile from 5% 95% 1%
from our results. For this experiment interval. In Figure 2 we plot the mean absolute error of each normalized by the mean absolute error of UQE to make for an easier visualization.
Uniformm data
Goussian cata
ratings data
Book
Age dota
Work hours datta
6.10
14
Figure 2: Plots of UQE = (mean absolute error UQE) / (mean absolute error UQE) and EMQ (mean absolute error EMQ) (mean absolute error UQE). Normalizing this way will make for an easier visualization. When EMQ is below UQE then it's 'ss error is lower, and when EMQ is above UQE then it's error is higher
As we can see Figure 2, EMQ consistently performs better on synthetic data, and UQE tends to performs better the non-synthetic data. This fits with our intuition that UQE will be best suited situations where the data is unstructured and less is known about the dataset beforehand because our guess- guess-and-chis anc-c methodology is designed to better handle ill- ill-behaving datasets.

---

5.3 Sum estimation experiments
As the primary application of our method we will also be considering differentially private sum computation, which can thereby compute mean as well. We will be using the following 2e-DP general procedure for computing the sum of non-negative data:
Let A = PrivateQuantileesseee lexx,, where PrivateQuantile is any differentially private computation algorithm and q 1. 2. Output Lap(A/c) + Σj= min(x,.4)
We further test this upon the non-synthetic datasets. For large-scale privacy systems that provide statistical analysis for wide variety of datasets, if we use PrivateQuantile that requires an upper bound then we ideally want this bound to be agnostic to the dataset. The is particularly true for sum computations upon groupby queries as the range and size can differ substantially amongst groups. As such, fix the range at [o, 10000] to encompass all the datasets. We will otherwise use the same general sctup as in Section 5.2.
We will measure the error of this procedure as the absolute error of the output and the true sum of the dataset. For each of the 100 iterations of choosing 1000 samples randomly from the full dataset, we also add Lap noise 100 times. Averaging over all these iterations gives our mean absolute error.
Privacy
Method
Ratings data
Pages data
Ages data
Work hours data
UQE
4.78021
4385.23 2077.16
103.05
180.48
=
EMQ
5.730.54
4324.382343.5
187.0633.5
339.0675.82
AT
8.75ps1
4377.45294000
293.11117.51
471.98
UQE 9.22o31
7102.343093.18
180.6127.0s
277 277.89,7.60
= 0.5
EMQ
6906.13 13713.36
7601.47 3963.52
678.22 1951.11
2131.80
AT
29.01
7491.97 4367.31
473.19238.19
582.58369.29
UQE
44.59
21916.376423.77
821.77
981.10219.66
8 0.1
EMQ
45861.792836.. 46
46552.092794.n
505.58.3228445.2
471 47185.5829437.2
AT
11351.7721
30830.492042..05
14490.06252a0
9928.1820159.17
Table 1: Mean absolute error for differentially private sum estimation. 'he standard deviation
over the 100 iterations is also provided for each in the subscript. UQE Our unbounded quantile estimation method. EMQ = The exponential mechanism based quantile estimation method. AT The aggregate tree method for quantile estimation. For our method we only use 0.99. For the others we use the best performance for E (0.95, 0.96, 0.97, 0.98, 0.99}.
We will run this procedure with E 10.1, 0.5, 13. Further we will use q = 0.99 always for our method, but give the absolute error for the best performing E {0.95, 0.96, 0.97, 0.98, 0. 0.99) for the other methods. It is important to note that this value would have to be chosen ahead of time, which would add more error to the other methods. The previous methods we consider here again the EMQ, but also the aggregate tree (AT) methods, were we use both the implementation along with generally best performing height (3) and branching factor (10) from Gillenwater et al. (2021). We also implemented the bounding technique using inner quartile range within Algorithm 1 of Smith (2011), but this performed notably worse than the others so we omitted the results from table.
As we can see Table 1, our method far more robust and accurate. Furthermore, for our method the choice of q remained constant and we can see that our results still stayed consistently accurate when e changed. Note that the noise added to the clipped sum is also scaled proportional e so the amount the error increased as e decreased for our method is what would be expected proportionally. Once again these findings are consistent with our intuition. Our technique is more robust to differing datasets and privacy parameters, and especially better performing for this important use case.
Recall that the sampled data had size 1000 so dividing accordingly can give the error on mean estimates. There a long line of literature on differentially private edge, all of these more complex algorithms either require assumptions upon the data distribution,
mean estimation." 3 To our knowl-
"See Kamath al. (2022) for extensive review of this literature

---

such as sub-Gaussian or bounded moments, or bounds upon the data range or related parameters. and most often require both. These results also focus upon proving strong theoretical guarantees of accuracy with respect to asymplotic sample complexity. We first note that our approach will provide better initial bounds upon the data as seen in our experiments, which directly improve the theoretical guarantees in the results that require data range. But also our focus here is upon practical methods that are agnostic to data distributions and more widely applicable to real-world data. Consequently, rigorous comparison among all of these methods would be untenable and outside the scope of this work.
5.4 Parameter tuning
We kept our & parameter fixed in all experiments for consistency but also to make our method data agnostic. However, our choice was aggressively small in order to achieve higher precision in the inner quantile estimation comparison in Section 5.2. This choice was still highly resilient to changes in e for sum experiments as we see our error only scaled proportional to the increase in noise. But for more significant decreases in & or in the data size, i.e. the conditions under which all private algorithms suffer substantial accuracy loss, this choice of could be too small. Those settings imply that the noise added is larger and the distance between queries and threshold shrinks, so our method is more likely to terminale earlier than desired. Smaller B values will then intensify this issue as the candidate values increase more slowly. For the clipping application, we generally think using value of B 1.01 would be more stable choice. In fact, replicating our empirical testing with this value actually improves our results in Table 1. Furthermore, increasing f will also reduce the number of queries and thus the computational cost. In general, we find that setting f E [1.01, 1.001] gives good performance with / = 1.01 as a default for computational efficiency. We leave to future work a more thorough analysis of this parameter to fully optimize setting it with relation to data size and privacy parameter. Additionally, all our methods and proofs only require an increasing sequence of candidate values and it's possible that other potential sequences would be even more effective. For example, if tight upper and lower bounds are known on the data, such as within the recursive computation of multiple quantiles, then it likely makes more sense to simply uniformly partition the interval and check in increasing order. But we leave more consideration upon this to future work as well.
Our choice o 0.99 in the differentially private sum experiments was also to maintain consistency with the choices for the previous method but also to keep variance of the estimates lower. This will create some negative bias as we then expect to clip the data. As we can see in our illustrative example Figure 3, the PDF will exponentially decrease once we pass the true quantile value, but will do so less sharply once all the queries have value n. Accordingly, setting q q= 1.0 would add slightly more variance to the estimation but initial testing showed improvement in error. However, if the user would prefer slightly higher variance to avoid negative bias, then setting the threshold at n or even n + 1/e, would make it far more likely that the process terminates with a value slightly above the maximum. This is particularly useful for heavy-tailed data, where clipping at the 99th percentile can have an out-sized impact on the bias.
Acknowledgments and Disclosure of Funding
We thank our collcagues Matthew Clegg, James Honaker, and Kenny Leftin for helpful discussions and feedback. We also thank anonymous reviewers for their helpful feedback.
References
Alabi, D., Ben-Eliezer, O., and Chaturvedi, A. (2022). Bounded space differentially private quantiles. arXiv preprint arXiv:2201.0333.
Barthe, G., Fong, N., Gaboardi, M., Grégoire, B., Hsu, J., and Strub, P.-Y. (2016a). Advanced proba- bilistic couplings for differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 55-67.
Barthe, G., Gaboardi, M., Grégoire, B., J., and Strub, P.-Y. (2016b). Proving differential privacy via probabilistic couplings. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 749-758.
10

---

Bassily, R., Thakkar, O., and Guha Thakurta, A. (2018). Model-agnostic private learning. Advances in Neural Information Processing Systems, 31.
Blum, A., Morgenstern, Sharma, A., and Smith, A. (2015). Privacy- public information for sequential games. In Proceedings of the 2015 Conference on Innovations Theoretical Computer Science, pages 173-180.
Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. (2015). Difterentially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 634-649. IEEE.
Bun, M. and Steinke, T. (2016). Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography. 14th International Conference, TCC 2016-B, Beijing, China, October 31-November 2016, Proceedings, Part pages 635-658. Springer.
Bun, M., Steinke, T,, and Ullman, J. (2017). Make up your mind: The price online queries in differential privacy. In Proceedings of the tiehty-eighth annual ACM-SIAM symposium discrete algorithms, pages 1306-1325. SIAM.
Cesar, M. and Rogers, (2021). Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Algorithmic Learning Theory, pages 421-457. PMLR.
Chan, T.-H. H., Shi, E., and Song, D. (2011). Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24.
Chen, Y., Machanavajjhala, A., Reiter, P., and Barrientos, A. F. (2016). Differentially private regression diagnostics. In ICDM, pages 81-90.
Cummings, R., Kearns, M., Roth, A., and Wu, Z. S. (2015). Privacy and truthful equilibrium selection for aggregative games. In Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings 11, pages 286-299. Springer.
Cummings, R., Krehbiel, S., Lut, Y., and Zhang, W. (2020). Privately detecting changes in unknown distributions. International Conference on Machine Learning, pages 2227-2237. PMLR.
Ding, Z., Kifer, D., Steinke, T., Wang. Y., Xiao, Y., Zhang, D., et al. (2021). The permute-and- mech- anism identical to report-noisy-max with exponential noise. arXiv preprint arXiv:2105.07260
Ding, Z., Wang, Y., Xiao, Y., Wang, G., Zhang, D., and Kifer, D. (2023). Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms. The VLDB Journal, 32(():23--4.
Dong. J., Durfee, D., and Rogers, R. (2020). Optimal differential privacy composition for exponential mechanisms. In International Conference on Machine Learning, pages 2597-2606. PMLR.
Dua, D. and Graf, C. (2019). Uci machine learning repository. In http///rchive.ee ics /uu. ml.
Durfee, D. and Rogers, R. M. (2019). Practical differentially private top-k selection with pay-what- you-get composition. Advances in Neural Information Processing Systems, 32.
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. L. (2015). Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117-126.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a). Our data, ourselves: Privacy via distributed noise generation. In Advances in CoypoolggyEUURCCYYYS 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 J--J 1, 2006. Proceedings 25, pages 486-503. Springer.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006b). 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 pages 365-284, Springer.
11

---

Dwork, C.. Naor, M., Pitassi, T., and Rothblum, G. N. (2010). Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715-724.
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. (2009). On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 381-390.
Feldman, V. and Steinke, T. (2017). Generalization for adaptively estimators via stable median. In Conference on learning theory, pages 728-757. PMLR.
Gillenwater, J.. Joseph, M., and Kulesza, A. (2021). Differentially private quantiles. In International Conference on Machine Learning, pages 3713-3722. PMLR.
Hardt, M. and Rothblum, G. N. (2010). A multiplicative weights mechanism for crivacy-preeervin data analysis. In 2010 IEEE 51st annual symposium on foundations of computer science, pages 61-70. IEEE.
Hasidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. (2020). Adversarially robust streaming algorithms via differential privacy. Advances in Neural Information Processing Systems, 33:147-158.
Hsu. J., Roth, A., and Ullman, J. (2013). Differential privacy for the analyst via private equilibrium computation. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing. pages 341-350.
Kamath, G., Mouzakis, A.. Singhal, V., Steinke, T., and Ullman, (2022). A private and computationally-effiieett estimator for unbounded gaussians. In Conference on Learning Theory, pages 544-572. PMLR.
Kaplan, H., Ligett, K., Mansour, Y., Naor, M., and Stemmer, (2020a). Privately learning thresholds: Closing the exponential gap. In Conference Learning Theory, pages 2263-2285, PMLR.
Kaplan, H., Mansour, Y., and Stemmer, U. (2021). The sparse vector technique, revisited. In Conference on Learning Theory, pages 2747-2776. PMLR.
Kaplan, H., Schnapp, S., and Stemmer, U. (2022). Differentially private approximate quantiles. In International Conference on Machine Learning, pages 10751-10761. PMLR.
Kaplan, H., Sharir, M., and Stemmer, U. (2020b). How to find a point in the convex hull privately. SoCG.
Ligett, K., Neel, S., Roth, A., Waggoner, B., and Wu, Z. (2017). Accuracy first: Selecting a differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 30.
Lyu, M., Su, D., and Li, N. (2017). Understanding the sparse vector technique for differential privacy. Proceedings of the VLDB Endowment, 10(6).
McKenna, R. and Sheldon, D. R. (2020). Permute-and-flig A new mechanism for differentially private selection. Advances in Neural Information Processing Systems, 33:193-200 203.
McSherry, F. and Talwar, K. (2007). Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 94-103. IEEE
Nandi, A. and Bassily, R. (2020). Privately answering classification queries in the agnostic pac model. In Algorithmic Learning Theory, pages 687-703. PMLR.
Nissim, K., Raskhodnikova, S., and Smith, A. (2007). Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pages 75-84.
Nissim, K. and Stemmer, U. (2018). Clustering algorithms for the centralized and local models. In Algorithmic Learning Theory, pages 619-653. PMLR.
12

---

Nissim, K., Stemmer, U., and Vadhan, S. (2016). Locating small cluster privately. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAAI Symposium on Principles of Database Systems, pages 413-427.
Roth, A. and Roughgarden, T. (2010). Interactive privacy via the median mechanism. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 765-774.
Sajed, T. and Sheffet, O. (2019). An optimal private stochastic-mab algorithm based on optimal private stopping rule. In International Conference on Machine Learning, pages 5579-5588. PMLR.
Shokri, R. and Shmatikov, (2015).
deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310-1321.
Smith, A. (2011). Privacy-preserving statistical estimation with optimal convergence rates. In
Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 813-822.
Soumik (2019). Goodreads- books dataset. In
goodreadsbooks. Steinke, T. and Ullman, J. (2016). Between pure and approximate differential privacy. "Journal of Privacy and Confidentiality.
Ullman, (2015). Private multiplicative weights beyond linear queries. In Proceedings of the 34th ACM SIGMOD-STGACT-SSCA Symposium on Principles of Database Systems, pages 303-312.
13

---

A Maximal Quantiles Estimation
In this section, we specifically consider applying our unbounded quantile estimation to computing the highest quantiles. This is commonly needed for clipping the dataset to privately compute the sum and mean, which we empirically test in Section 5.3. Our primary goal here is to build intuition upon why our approach fundamentally gives more accurate and robust estimations of the highest quantiles when only loose upper bounds on the data are known. We first give more details upon the previous methods, particularly the EMQ method. Then we give more detailed look at how these methods are negatively affected by loose upper bounds and why ours performs well in comparison.
A.1 Previous techniques
The most effective and practical previous method for quantile estimation, EMQ, builds a distribu- tion over an assumed bounded range [a. b] through an invocation the exponential mechanism. Assuming the data is sorted, it will partition the range based upon the data and select an interval X,1] with probability proportional to
clj qnl 2
(x/+1 - x1)
exp
where the intervals [a,x,] and [A,, b] are also considered. A uniformly random point is then drawn from within the selected interval. Note that this utility function is not monotonic and will not enjoy the same improved privacy bounds.
There are other approaches that recursively partition the data range while computing statistics each partition, then aggregate these statistics across logarithmic levels to reduce the noise for quantile computation Dwork et al. (2010); Chan et al. (2011). Another technique is to instead utilize the local sensitivity while maintaining privacy by using smoothing procedure that can also be used for computing quantiles Nissim et al. (2007). There is also a similar approach to ours within Chen et al. (2016) for bounding unbounded dataset that increases the bounds by factor of 2 each iteration but we will discuss in Section A.2 why this variant performs substantially worse.
A.2 Effeet of bounds upon maximum quantiles
As mentioned, EMQ will construct probability distribution over the range [a. b]. The corresponding PDF is unimodal step function of the intervals defined by the data with the peak interval [x,, xy+1 being such that j closest to gn. Note then that b >> xa then the probability of selecting [x,, b] increases dramatically. The exponential decay as the PDF moves away from the peak interval diminishes the impact of [x,, significantly n is far away from qn. However, for computing the highest quantiles, we want q close to by definition, and the looseness of the upper bound drastically effects the accuracy.
In contrast, as soon the candidate value for our method exceeds the true quantile value, each successive query will have an output of at least qn which is the threshold. The probability of continuing for Ā more queries then decreases in 2. For ease of comparison, we modify our Algorithm 2 such that in the last step, the oulput is drawn uniformly from [ 1*), assuming ( = for simplicity. This would then create continuous probability distribution that would similarly be a step function with each interval [Bi being a step.
For better intuition plot the approximate PDF of each in Figure 3. We use the Gumbel noise in the call to AboveThreshold to take advantage of the closed form expression in Lemma B.2 for easier PDF computation.
As we can see in Figure 3, the upper bound, increasing from 10 to 20 dramatically increases the probability of selecting point in [x,, b] which changes the normalization for the other intervals, significantly altering the PDF of EMQ. Given that our method unbounded, the PDF for UQE stays
'We expect à to most likely be small and this only adds a factor of B² additional error. Note that setting / too high. such as / = 2 which gives a similar algorithm to Chen et al. (2016), implies that even taking five additional queries will lead to value that is over 32 times too large.
14

---

Loose bounds
Tight bounds
USE PDF EMQ foF
0.30
0.4
Poloblty danske
Probabitty
0.33
0.2-
0.20
005
0.0
17.5
Figure 3: Illustrative example of how the approximate PDF of the previous method, EMQ is affected our unbounded method UQE A small amount of data was
by looser upper bounds compared drawn uniformly from [o, 10] and we set = 0.9, so accurate output would be about 9. The left and right side assumed range of [o, 20] and [o, 10] respectively for EMQ.
the same in both figures and sees the expected exponential decay once the candidate quantile passes the true quantile.
There are also alternative methods for bounding the data range by computing the interquartile range more accurately and scaling up. However these methods make strong assumptions upon the data distribution being close to the normal distribution as well as bounds upon the third moment Smith (2011). For worl-world datasets, the tails of the data can vary significantly, and scaling up in data-agnoo agnostic manner can often be similarly inaccurate. We also found this to be true in our experiments.
The smooth sensitivity framework will run into similar issues when q is closer to because fewer data points need be changed to push the quantile value to the upper bound. If this upper bound large, then the smooth local sensitivity will still be substantial. Aggregate tree methods are slightly more robust to loose upper bounds as they aren't partitioning specific to the data. However, for accurate estimates the partitioning of the range still requires the data be well-distributed across the evenly split partitions, which is significantly affected by loose upper bounds.
B Improved analysis for Sparse Vector Technique
In this section we complete the analysis for improving the privacy bounds for sparse vector technique with monotonic queries. We will first give a more generalized characterization of query properties by which can improve the privacy bounds for Above OboveThreshold While this characterization is more complex, we will immediately utilize it in Section C to improve the privacy bounds of our methods under an alternate common definition of neighboring. Additionally, the class of queries that we apply it to are not monotonic, so improvements can be made in multitude of settings. Next we will review the definition of range-bounded, a property of privacy mechanisms that can be used to improve composition bounds, and apply it to our setting. Finally we will utilize these results to show that the privacy analysis of the sparse vector technique can be improved more generally, but also specifically for monotonic queries.
B.1 Generalized characterization
We provide more general characterization for the privacy loss of AboveThreshold that is specific to the input stream of queries. This will be achieved by providing a one-sided privacy parameter for each pair of neighboring datasets where order matters. For given pair x, x,'', our goal will be to upper bound the output distribution of x by the output distribution x' up to an exponential factor of the one-sided privacy parameter. The specificity will reduce conciseness but it is for this reason that we will be able to further improve privacy analysis. This precise characterization will also help improve bounds for our method Section without requiring onerous analysis.
the parameter to the neighboring datasets
15

---

Definition B.1. For stream of queries (fi with sensitivity A, we define our one-sided privacy loss for neighboring data sets x, x as
<(x,x) x max ( Ae 82 A
maxx00,A(xx, -(((xx))))((())))))-))))))))))>) -(((x))_((x)))))
where 4x(xx)) max max(o, f(x) f((x)]
Given that definition is meant to encompass the one-sided privacy loss for AboveThreshold we will now prove that fact for Expo and Gumbel noise (and Lap follows equivalently to Expo). We first prove this conjecture for Expo noise.
Lemma B.1. For stream of queries (fi with sensitivity A, threshold T and neighboring data sets x,x', if we run Algorithm with Expo noise, then for any given outcome (1*=1, T3 we have
Pr ThboveeTTrrehholdx::f.777 =11 (xp(e(x,x')))' (AboveThressoll(xx.ffi (
Let Expo(A/e2) denote the noise drawn for query fi, and let Expo(A/e;) denote the noise drawn for the threshold. Further let Visk denote all v, such that S k. By construction, we have
Proof.
Pr [AboveThreesholdd:. = (_ Previs
max f(x) + ick
fe(x) +
will fix the randomness Vicks denoting vi such that k, for datasels x and x', and let maxick f(x) + and r' maxick f(x') + vi- It suffices then to show that for any fixed randomness Vict we have
Pryn [r < (x() vel
[ <T<+vv<// f((x') vx]
Let A, max(0, - suffices show that for every pair of draws v, v2. that satisfies
(f(x)) fxx))) and let = A1 and 1/2 = v2 + Ag- Vv, then the corresponding v', v'e are i) non-negative, ii) satisfy r' <T < fxxx) + v/2 and iii)
r} and A₃ = max(0, A
(v: A/Ei) (vx A/e)) exple(x, x P)xxoo A/E1) (1
We note that condition iii) does not require any scalar on the RHS as our change of variable is shift for each so the Jacobian of the mapping is the identity matrix with determinant of 1.
Condition i) follows from the fact that v. are non-negative because they're drawn from the exponential distribution, and A, A2 are non-negative by construction.
For condition ii), if T V'+v< fx(x) + V2 then T + v A < +xxx++15 + A, because A₂ 2 A, - -
must have z' < T A, by definition of A, Similarly, if
For condition iii) the PDF of the exponential distribution implics (v exp( ( and (rxpo A/ez) exp((22))ps.a Pexpo (V'2 A/e2)- Due to the fixing of ran- domness of Vicks we have that -I -IS maxx;e(((xx))) -(xx)) A; S Ag(x,x') from Definition B.1 and Ag S maxç0, x'xxxx)= -ff(x')) ((x()))(x))) which implies condition iii).
This proof then easily applies Lap as well. The proof for Gumbel will differ though as we no longer have similar closeness of PDF properties, but it will follow from the fact that give closed form expression for each probability.
Lemma B.2. Given dataset x, stream of queries (f and threshold T, for any outcome k1 T3 from running AboveThreshold with Gumbel noise and e E1 Ez. then
16

---

Pr ( -1
TT) exp( Σ exp( exp(1 Σ exp(xf(x))
exp (x)))
Proof. We add noise Gumbel(A/e) to all f((x) and the threshold T, and in order to output { T we must have that for the first k queries, the noisy value of fx) is the largest and the noisy threshold is the second largest. It is folklore in the literature that adding Gumbel noise (with the same noise parameter) and choosing the largest index equivalent to the exponential mechanism. This can also be extended to showing that adding Gumbel noise and choosing the top-k indices in order equivalent to the peeling exponential mechanism. The peeling exponential mechanism first selects the top index using the exponential mechanism and removes it from the candidate set, repeating iteratively until accumulating the top-k indices. formal proof of this folklore result is also provided in Lemma 4.2 of Durfee and Rogers (2019). Applying this result and the definition of the exponential mechanism gives the desired equality.
We then utilize this closed form expression to get our desired one-sided privacy bounds when using Gumbel noise.
Lemma B.3. For stream of queries (f} with sensitivity A, threshold T and neighboring data sets x,x', if we run Algorithm 1 with Gumbel noise with E E2, then for any outcome (1 _ we have
Pr [
exp(e(x, x [AboveThreesholdd.....77 {1(-1TT)
Proof. Let E = E2. From Lemma B.2 we know that
Pr [#ooetTrressolll((fff33 (1
TT)(5T) exp( (T) + Σx exp(5f((x)) exp($7) + E f(x))
(x())
Similar to the proof of Lemma B.1, we let A = max/0o, max (f(x') f((x)) and 42 = max/0 A +
- f((r)))(((()) We first want to show that
TTP(AT) exp(; + Σisl exp( f(x))
Tx Σnn exp( f(x())
Sea 14
(1)
exp(5T)
This inequality reduces to showing exp( ()) + fxp(xf(((())
f(x'(())))x) S (exp( ())+ -i= exp f f(x))).
This holds from the fact that exp( (T) S exp(eA, AA) exp( 7) because cA, / 2 and exp( à f(x')) S exp(eA, / A) exp(', 5, f(x)) for all by our definition of
fx(()
exp(ff((x'))
Sex 24
(2)
cxp(+T)+ E (xp($ff(x))
exp( (T) Σ exp( f((())
First we let A = max(0, maxest our desired inequality (2) by bounding the numerator with respect to A and the denominator with respect to A, We have exp( & fx())) exp(eA//A) ( by definition of N, Further exp({ S exp(eM//A) exp( f(x)) by definition N₁. so
f(x))) and &₂ = fx() fixx), and we will achieve
C + Σ exp( é exp( +)+ Σ exp( é f((x)) < e (exp(
f(())) A
A
[m] A
A
17

---

because /A/ 2 0. In order to show our desired inequality (2) it then suffices to show A 2 4, 4, By definition we know A₂ 2 Å + AZ. Furthermore, if 4 > A, then 4 fe(x))) - fi(x) -
which implies A A₂ 0, and we know A2 2 0 by construction.
Combining inequality (1) and (2) along with the fact that A, Ax(x,xx) from Definition B.1 completes the proof.
Now that we've bounded the one-sided privacy loss for neighboring datasets for each type of noise, this will immediately imply an overall privacy bound over all neighbors that utilizes this general characterization.
Corollary B.1. For stream of queries {fl with sensitivity and threshold Algorithm with Lap, Gumbel, or Expo noise is D-DP where
maxe(xxx) x-x
and for Gumbel noise we must have E Eg-
B.2
definition and properties
The definition of range-bounded was originally introduced in Durfee and Rogers (2019) to tighten the privacy bounds on the composition exponential mechanisms. The analysis was further extended in Dong et al. (2020) to give the optimal composition of range-bounded mechanisms. This definition was then unified with other definitions Cesar and Rogers (2021).
Definition B.2 (Durfee and Rogers (2019)). mechanism X y is b--unng-bounded if for any neighboring datasets x' e X and outcomes y, y' y:
Pr[M(x) = yl Pr [r(M(x)) y < Pr[M(x') = =
Pr[M(x)= = y
we have bounds upon this property that are stronger than those immediately implied by DP, then it was shown in Dong al. (2020) that substantial improvements be made in bounding the overall DP over the composition of these mechanisms. While these improvements can be applied to results here as well, focus upon the privacy bounds with respect to zCDP as it is much cleaner to work with in providing strong composition bounds. From the proof of Lemma 3.4 in Cesar and Rogers (2021) see that the range- bounded property can give significant improvement in xCDP properties compared to similar DP guarantees.
Proposition 2 (Cesar and Rogers (2021)). If mechanism M is is--range-buunde then it is -CDDP. 1
already set up to provide range-bounded properties of AboveThresholdd d. This will allow to give tighter guarantees on the range-boundedness which can be translated to better privacy composition bounds.
Our general characterization
Corollary B.2. For a stream of queries if and threshold T, Algorithm with Lap, Gumbel, or Expo noise is --raageee-ba bounded where
max x-xx
and for Gumbel noise we must have E Ez-
Proof. We can rewrite the inequality from Definition B.2 as equivalently
Pr [M(x) y1 Pr [M(x) s e [M(') y] Pr [M(x) y
Our claim then follows immediately by applying Lemma B.1 and Lemma B.3
18

---

B.3 Improved composition analysis of SVT
In this section we complete our analysis for improving the privacy bounds for sparse vector technique. While our generalized characterization was in more complex form, we simplify it here for general queries and monotonic queries. This will then match up the privacy guarantees that we gave in Section 3 for OboveThresholue
Lemma B.4. Given stream of queries (f with sensitivity A then for any neighboring datasets ((x,x)) E + Z8z. If the queries are monotonic then for any neighboring datasets e(x.x') S E2. and furthermore, e(x,x) + e(x',x & 2F2
Proof. By Definition 2.2 must always have 4x(x,x)) & A for any neighboring datasets. Fur- thermore, we must also have f((x)) - fx(x) 2 -A for any neighboring datasets. This implies x(x,x) & + 28g for any neighboring datasets.
Now assume the queries are monotonic, Without loss generality assume f(() 2 f(xx) for all k. Therefore xx)x,x))
and fxx' - fa(x) 2 -A, which implies (xxxx)s S &g. Similarly we have (n x) I but also fx(x) f((x) 2 O, which implies e(x'xx x)) S & + Eg. Combining these implics 6(x', x) + F2 and exx x) e(x,x') E1 + 28₂ for any neighboring datasets.
This lemma along with Corollary B.1 immediately imply Corollary 3.1 and Lemma 3.2
Proof of Theorem 1. From Lemma B.4 and Corollary B.2 we have that Algorithm is E + rangr- bounded. Applying Proposition then gives the zCDP guarantees.
The sparse vector technique is simply an itcrative call AboveThreshold and as such the privacy bounds will come from the composition. By analyzing the composition through zCDP which has become commonplace in the privacy community, we can immediately improve the privacy guarantees for monotonic queries in the sparse vector technique. Furthermore we can also improve the privacy guarantees under the standard definition using the improved composition bounds for bogge-bounded mechanisms from Dong et al. (2020).
We also note here that the generalized Sparse Vector Technique given in Lyu et al. (2017) only adds noise once to the threshold and only has to scale the noise to the number calls to AboveThreshold for the queries and not the threshold. Our analysis and Expo noise, but utilizing advanced composition properties will give far more accuracy. More specifically, the threshold and queries having noise proportional to vC/E, is preferable to all the queries having noise proportional to c/e, and only the threshold proportional to 1/e, where e is the number of calls to Above Threshold.
extend to give the same properties for Lap
B.4 Iterative exponential mechanism
It is folklore that the peeling exponential mechanism is equivalent to taking the top-k after adding Gumbel noise, as formally shown Lemma of Durfee and Rogers (2019). We show similar property here for AboveThreshold with Gumbel noise that it is equivalent to iteratively running the exponential mechanism.
Algorithm Iterative Exponential Mechanism
Require: Input dataset x, stream of queries {fi : - R3 with sensitivity A, and threshold T for each query i do
2: Run exponential mechanism with y (0.... where q(x, 0) = and q(x, j) = f((x) for all
j 1>0 0
3:
is selected then
Output and halt
5: else
Output
7: end
end for
19

---

Lemma B.5. ff
e/2 then Algorithm 1 with Gumbel noise gives the equivalent output
distribution Algorithm
Proof. We first define
exp 2xp fx ( T)+ Σ exp( (xx(())
Pk
By construction, the probability of Algorithm oulputting {1k-1, T3 is equal to pt. II p.). Furthermore, by our definition of we have
exp I)++ 2
exp(
& f(x))
28
23
Px
exp( 2o 7) + Ei=1 exp( 23 f(x))
Through telescoping cancellation
k-1 a
exp 23 T)
p.)
exp(
M) + Σ exp((x(()))
I=1
From Lemma B.2 then see that the oulput probabilities are equivalent.
C Additional unbounded quantile estimation results
In this section we first extend our method to the fully unbounded setting by simply making two calls AboveThreshold and essentially searching through both positive and negative numbers in each respective call. Next we show how our methods can also extend to the add-subtract definition of neighboring. Further, we'll apply our approach the framework set up in Kaplan al. (2022) for computing multiple quantiles and extend it to the swap definition.
C.1 Fully unbounded quantile estimation
Recall that our unbounded quantile estimation algorithm assumed that the data was lower bounded. then slowly increased that bound by a small percentage until the appropriate amount of data fell below the threshold for the given quantile. In order to extend to the fully unbounded setting, will simply first apply this guess and check method the positive numbers and then apply it to the negative numbers.
Algorithm 4 Fully unbounded quantile mechanism
Require: Input dataset x, a quantile q, and parameter / >
Run AboveThreshold with T qu and f(xx [x, E x(x
2: Run AboveThreshold with x, 7' (1 q)n and fíxx) = {x E x(xx - 1> -B'I
3: If the first AboveThresholl halts at k > then output B -1
If the second AboveThreshold halts k then output -Bk
5: Otherwise return 0
Note that the second call could equivalently be achieved by flipping the sign all the datapoints and again applying queries f(x) |x, x/x, + < B3)). Therefore all our privacy guarantees from Section 4 will still apply, but composing over two calls to Threhhld,,,,,, which the Sparse Vector Technique.
In the first call AboveThreshold we are assuming lower bound of 0, and searching the positive numbers. If it terminates immediately then it is likely that more than qth fraction of the data below We then symmetrically search through the negative numbers by assuming an upper bound of O. If this halts immediately then it is likely that the quantile is already near 0. We could also apply other variants of this, such as three total calls to get the maximum and minimum of the data if we wanted full data bounds.
20

---

Further note that computing the smallest quantiles will be challenging for our algorithm because it may take many queries get the appropriate threshold, but each query will have reasonable chance of lerminating if q is very small. To account for these queries in the lower-bounded setting, we can invert all the datapoints and instead search for quantile q on this transformed data, then invert our resulting estimate. We would also need to reduce our parameter a reasonable amount in this setting.
C.2 Extension to add-subtract neighbors
We also extend our results to the add-subtract definition of neighboring datasets. Definition C.1. Datasets x, E & are neighboring if one of them can be obtained from the other by adding removing individual's 's duta.
Under this definition we see that our threshold qn is no longer fixed, so we will instead set each query to be f((x) Hx, xlx, (+ f qn. Unfortunately this query will no longer be monotonic, so we will instead take advantage of our more general characterization in Section B.1 to further tighten the privacy bounds in this setting.
Lemma C.I. Given the stream of queries f(x) 1ix; E x|x, - +++ < B qn with sensitivity = 1, for any neighboring datasets x, under Definition C.1 and quantile q [o, 1] we have c(x,x" I max((1 q)8..qE. qei Ez).
Proof. Without loss of generality, assume that x has one more individuals data, so x E R" and x' E Rn-1 Let g(x) I[x x|x, e+ 1 (')). By construction
must have g(x) gxx))))))))))))))))) (0. 1 because x has an additional datapoint. Furthermore, because the thresholds are increasing, then g(x) gxx) 1 for all k. Similarly if gx(x) ga(x) = then
(xxx) (xx)
(xx) gxx)= = 0 for all i < k. We further see that f(x) - [(xx) = g(x) - (00gg(())))) - for all i.
First consider the so (x,xx) = and also (x(x,x) (fx(x) ((xx))f(xx)) O, so e(x, x') S qE1 Similarly, we have Ax(x' x) = and xx(xxx) - (f((x) fx(x)) q. s0 x) qE2
when ga (x) -g(x)=
We therefore have gxxx) gxx) 0 for all <
Next consider the case when (xx) ge(x') 1. Therefore we have Ax(x,x) s q and also fa(x') - f((x) q--1 which implies Ax(x,x') (ff(xx)) fx))) I 1. so (xxxx) S gei + + Similarly, we have that xx) S 9, and thus As(x', (f((x) - f((x)) 0, so exx x) S (1 - 9)a
Combining these bounds gives our desired result.
With these improved bounds we can then show that our methods also extend to the add-subtract definition of neighboring with tighter privacy guarantees.
Corollary C.1. If we run Algorithm 2 with E for quantile q under Definition C.1 then it is (qE, eDD..
Proof. Combining Lemma C.1 and Corollary B.1 immediately imply the desired result
C.3 Extension to multiple quantile estimation
As previously established, the framework in Kaplan et al. (2022) is agnostic to the single quantile estimation method. However their proof is for the add-subtract neighbors, although they note that can be extended easily to the swap neighbors. We also discuss here how can be extended for completeness.
For the swap neighboring definition, each level of the recursive partitioning scheme either two partitions differ under the add-subtract definition, or one partition differs under the swap definition. Applying their framework to our algorithm, we will instead compute all the thresholds advance of the splitting. Accordingly these thresholds will remain fixed. If the thresholds are fixed then can actually further improve our privacy bounds for the add-subtract definition. Once again we will use more general characterization from Section B.1.
21

---

Lemma C.2. Given the stream of queries f((x) Hxj - P with sensitivity A = 1, for any neighboring datasets x, under Definition C.1 have [xx, x') & ma
Proof. Without loss of generality, assume that has one more individuals data, x E R" and x' E R By construction we must have f(x) f(x))) E {0. 13 because x has an additional datapoint. Furthermore, because the thresholds are increasing, if fa(x) f((x) = then fi() f((x') 0 for all j k. Thus the case f((x) fx(x') = 0 easy.
Instead consider fx(x) fx(x²) = 1. We know (xxxx)) = 0 so (x -f())) = so e(x,x), & &g. Further we must have Ax x) and 45(x'
&
Combining these implies exx'xx & maxle,, 52) for any neighboring datasets.
Applying these bounds we see that applying the framework of Kaplan et al. (2022) to the swap definition either leads to composition of (& +2)-DP for the swap definition two compositions of max(f;, f2) for the add-subtract definition at each level. Setting & & we then have that the privacy cost of computing m quantiles with this framework will be equivalent log(m 1)
compositions of (e, + E2)
D Implementation code
For ease of implementation, we provide simple python code method with access to the respective Noise generator of the users choosing. In our experiments we used exponential noise from the numpy library.
def unboundedQuant iil (data, 1, b, 9, eps_1 eps_2)
d defcu (int) for in data: i math, 1x (x-xxxt))b) // d[i] +=
q cur, = 0,
(data) noise (1/eps_1)
while True: cur += d[i]
i +=
if cur noise(1/eps.. t:
break return b
22


Reviews:
[{"review_id": "O9bnrHLVsA", "reviewer": "Reviewer_Qz1m", "summary": "The paper considers the problem of computing the quantile q of a dataset with differential privacy. The prior standard technique for this problem was the exponential mechanism with the loss of an output T being the difference between the number of examples less than T and qn. An issue with the exponential mechanism (and most mechanisms for quantile estimation) is that it requires the user to bound the range of possible values in the dataset. The authors propose an alternate algorithm which does not require a prior bound, and takes advantage of the AboveThreshold algorithm. They propose using the AboveThreshold on queries of the form \"how many examples in the dataset are less than T?\", where T is exponentially increasing, and return the value T that AboveThreshold reports has more than qn elements less than T. As part of the analysis, the authors give an improved analysis of AboveThreshold, showing it has improved privacy guarantees for monotonic queries when using Exponential or Gumbel noise; previously, this was shown for Laplace noise. The Exponential distribution has lower variance, so this allows them to get a lower-variance estimate without sacrificing privacy. The authors perform experiments to compare to the exponential mechanism, as well as the aggregate tree method. On synthetic datasets, the exponential mechanism performs slightly better, but otherwise the authors' result is better for quantile estimation. For sum estimation, when using parameters agnostic to the dataset, the authors' algorithm by far outperforms the baselines, due to not relying on a good prior range estimate.", "questions": "Intuitively it seems like smaller beta is more likely to underestimate the quantile and larger beta is more likely to overestimate, is this correct? Also, for e.g. a bimodal dataset such as the Gaussian mixture 0.5 * N(0, 1) + 0.5 * N(Delta, 1), Delta >> 1, for estimating the 75th percentile, how would you expect UQE to compare to EMQ? (with a good or bad range estimate)", "limitations": "Yes, in the appendix the authors discuss the main limitation/weakness. N/A on negative societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall I enjoyed reading the paper and feel it makes a substantial contribution to the field. Private quantile selection is an extremely important problem with a number of applications, including any setting where we wish to compute a private sum. The problem of needing a bounded range for these problems has always been a troublesome part of DP research and application, and having a seemingly robust approach that at least partially gets around this issue is thus of significant impact. The main idea in the paper is simple to describe, which makes it more likely to see adoption and further development in follow-up works, but at the same time requires new analyses to achieve competitive privacy-utility tradeoffs. Finally, I felt the paper was overall a pretty easy read, in part due to the elegance of the algorithmic ideas but also the quality and clarity of the writing.", "weaknesses": "I think the only major weakness is that one still needs to choose beta appropriately. The authors mention this in the discussion in Appendix D, but this discussion is somewhat incomplete. Still, I believe that beta is a much easier parameter for a practitioner to choose appropriately than the range of the dataset, especially since the experiments show beta is somewhat dataset-agnostic, so this is a minor weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoroughly reading our work, giving extensive and detailed feedback, and are very pleased to hear that they enjoyed doing so.\n\n\nAs the reviewer mentioned we largely left a more detailed examination of beta settings to future work, partly to demonstrate that a reasonable guess of beta without any prior would still perform very well. Since the reviewer has shown further interest, which we greatly appreciate, we will mention that the general rule of thumb we have been further considering is that beta should be inversely proportional to the data size and epsilon. This also relates to the reviewer's intuition (which is spot-on) but extends it further.  Larger beta, say $\\beta=1.1$, will also lead to fewer guesses close to the true quantile. In fact, even with $\\epsilon = \\infty$ we could still only expect to be within about 5% of the true quantile. However, for smaller datasets and small epsilon, i.e. the situation under which all differentially private algorithms struggle with accuracy, we could only hope to have coarser estimates and setting beta higher will avoid significant underestimation that the reviewer's intuition caught. We note that we did find our experiments to show further robustness with respect to beta as we re-ran them afterwards with $\\beta = 1.01$ and found similar (if not greater) improvements for the real world data. As such, we believe a good default setting would not require too much specificity and a simple heuristic function that sets beta inversely proportional to the data size and epsilon should suffice. But this still needs further development. For now a selection of $\\beta \\in [1.001, 1.01]$ seems to be a well-performing and reasonably robust default.\n\n\n\n\nResponse to questions:\n\n1. The reviewer is spot-on with their intuition that smaller beta more likely leads to underestimation and larger beta more likely leads to overestimation. \n\n2. This is a really interesting question and we've been developing some further intuition for the inner quantiles (but concrete theoretical claims appear extremely difficult). The general intuition we've found so far is that the more symmetric the data is in a \"small\" neighborhood around the quantile, the better EMQ performs comparatively. Most real world data does not have this symmetry hence our UQE performing better. For the example the reviewer gives, the significant distance between the Gaussians compared to the variance would mean we would expect the 75th percentile to be symmetric and EMQ to likely perform better. But with more overlap and differing variances this symmetry would disappear and our intuition is that UQE would often perform better."}, {"review_id": "5k8h83qv8l", "reviewer": "Reviewer_nQ9t", "summary": "The authors propose a differentially private algorithm for differentially private quantile estimation that can handle unbounded data setting. The authors revisited the AboveThreshold subroutine in Sparse Vector Technique and proved new privacy guarantee results. The authors can verify the asymptotic runtime complexity and demonstrate the utility through experiments. The method can have successful application to differentially private sum estimation. ", "questions": "1. You provide theoretical runtime complexity analysis. It would be of interest to compare the runtime in experiments to verify your asymptotic analysis. \n\n2. From a quick search, there seems to be little literature in quantile estimation that addresses the unbounded setting.  It would be great to highlight this by citing some papers that can handle unbounded data in Introduction/Related Work.  You briefly mentioned this in your contributions, saying “commonly used algorithms can apply loose bounds to ensure data is contained within” and analyzing their drawbacks, but no citation is included.", "limitations": "The proposed method works worse than the existing EMQ method for synthetic data. Can you offer any suggestions on how to improve your method’s accuracy for these well-behaving datasets?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality** The proposed method for finding private quantile is a creative use of an existing method for the application to a new domain. The authors proved new privacy results for the existing method.\n\n**Quality**  The method can solve the problem. The theoretical analysis can verify the privacy and complexity of the proposed method. The authors can demonstrate the accuracy of the method through numerical studies.\n\n**Clarity** The problem is well-defined and clearly stated. The method can be clearly understood.\n\n**Significance** The problem being solved is important and as verified by the experiment the proposed method can improve accuracy for real-world data . The new privacy analysis to the Sparse Vector Technique can be of independent interest.", "weaknesses": "The authors do not provide theoretical utility guarantee; though the experiment results look good.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review and give detailed feedback on our work.\n\nResponse to questions:\n\n1. We felt that verification of runtime asymptotics was less necessary given the simplicity of the code (see Section D.3 in the supplemental file), but agree that experimental runtime verification would be a good addition particularly for larger datasets.\n\n2. This is a great suggestion and we'll look for work that handles unbounded data for non-quantile algorithms. Our mention of applying \"loose bounds\" (line 61) was specifically with respect to quantile algorithms, and to our knowledge none of these works explicitly address this or consider the drawbacks. Instead the bounds are just assumed to be reasonably tight. Our intention with that statement (line 61) was to give credit to these works that technically they can handle unbounded data (in practice) by using incredibly loose bounds even though it's never actually stated in their work. But as seen in our results for maximal quantile estimation, even somewhat loose bounds can have significant drawbacks on accuracy.\n\n\nResponse to limitation question:\n\nThis is a really good question and we've been developing some further intuition for the inner quantiles (but concrete theoretical claims appear extremely difficult). The general intuition we've additionally found is that the more symmetric the data is in a \"small\" neighborhood around the quantile, the better EMQ performs comparatively. Most real world data does not have this symmetry hence our UQE performing better. This also implies that our UQE would perform better (and we have empirically verified) for synthetic data generated from the exponential distribution or poisson distribution (with small parameter). We also note that this is for inner quantiles, and for the maximal quantiles (and loose upper bounds) our UQE also significantly outperforms EMQ on synthetic data. "}, {"review_id": "SjZEIxk5B5", "reviewer": "Reviewer_VnsR", "summary": "The paper tries to improve upon Sparse Vector Techniques for differential privacy to obtain better estimates of the maximum and quantiles.", "questions": "Please fix the proofs!\n\nIt is hard to tease out your contributions from the contributions section. Most of the contributions section belongs in the introduction. The contributions should be a succinct description of what _you_ contributed, not about where it can be used.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "The paper covers an important problem, finding a differentially private estimate of the max. This  is often needed in one of the most common aggregations, i.e. sums, to clip and set a sensitivity.\n\n It promises less noise for the same privacy through an improvement to the sparse vector technique. \n\nI would be interested in reading it again if the proofs were correct. However,...", "weaknesses": "I unfortunately cannot trust the results in the paper due to bad proofs.\n\nThe proof for Lemma B.1 is incorrect though the conclusion may not be. For example, the statement in Line 557 of the supplement is incorrect. The statement says you will get the same answer _with the exact same noise_. You’ve fixed the randomness and there is no remaining randomness for the probabilities. You end up using v’ \\neq v and v_k’ \\neq v_k later.\n\nFurthermore, injectivity of the mapping v, v_k -> v’, v_k’ is not enough to show that the probabilities P(AboveThreshold(x) = O) and P(AboveThreshold(x’) = O) are the same for some output O. For example x -> x/2 is an injective mapping from [0,1]. But for a uniform distribution, the probability of the image is ½, not 1. In this case, the mapping happens to be a shift, so the Jacobian of the map is the identity, which actually is enough since the determinant is 1. But the current proof is too much of a mess to know if I can trust the theoretical claims in the paper.\n\nPlease fix the reference in Lemma 3.1. The Thm 4, 5 in the VLDB version are show that algorithms are _not_ DP.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for pointing out the incorrect reference (should be Thm 2 and 3 for the VLDB version) in Lemma 3.1. Our reference in line 618 is also for Lemma 3.4 in the arxiv version of Cesar and Rogers and needs to be updated. \n\nWe felt that the flow and clarity of the introduction was best achieved through our format but should have used \"Our techniques\" as that subsection header instead and apologize for the misnomer. For a concise review of our results/contributions, we point the reviewer to the abstract.\n\n$ $\n\n$\\textbf{Clarifying the notation confusion which led to the reviewer's main issue:}$\n\n\nWe apologize for the notational confusion in our proof of Lemma B.1 which led to the main issue for the reviewer. In line 557, when we fix the randomness of $\\nu_{i<k}$ this denotes all $\\nu_i$ such that $i<k$. Hence there is still randomness from $\\nu_k$ and $\\nu$, which is what the probabilities are over, and why we later have $\\nu \\neq \\nu'$ and $\\nu_k \\neq \\nu_k'$. We hoped this would be clear from context and strongly suggestive notation but will be sure to clarify in the future. We also invite the reviewer to see the proof of Claim 3.9 in The Algorithmic Foundations of Differential Privacy by Dwork and Roth for a similar style of proof (that inspired our approach) which may further help understanding.\n\n$\\textbf{Updating the proof with an easy addition that addresses an important technicality}$\n\nWe greatly appreciate the reviewer pointing out that our change in variable is a shift so the Jacobian is the identity matrix with determinant of 1, which is easily added but an important technicality. We'll be certain to anonymously acknowledge the reviewer for this contribution. We apologize for this oversight and can add this update and better organize the rest of the proof after line 557 as:\n\n$ $   \n\nLet $\\Delta_1 = \\max(0, \\tau'-\\tau)$ and $\\Delta_2 = \\max(0, \\Delta_1 - (f_k(x') - f_k(x)))$ and let $\\nu' = \\nu + \\Delta_1$ and $\\nu_k' = \\nu_k + \\Delta_2$. It suffices to show that for every pair of draws $\\nu, \\nu_k$ that satisfies $\\tau < T + \\nu < f_k(x) + \\nu_k$, then the corresponding $\\nu', \\nu_k'$ are (1) non-negative, (2) satisfy $\\tau' < T + \\nu' < f_k(x') + \\nu_k'$ and (3)\n\n$\np_{expo}(\\nu;\\Delta/\\epsilon_1) \\cdot p_{expo}(\\nu_k;\\Delta/\\epsilon_2) \\leq \\exp({\\epsilon}(x,x')) p_{expo}(\\nu';\\Delta/\\epsilon_1) \\cdot p_{expo}(\\nu_k';\\Delta/\\epsilon_2) \n$\n\nWe note that condition (3) does not require any other scalar on the RHS as our change of variable is a shift for each so the Jacobian of the mapping is the identity matrix with determinant of 1.\n\n\nCondition (1) follows from the fact that $\\nu,\\nu_k$ are non-negative because they're drawn from the exponential distribution, and $\\Delta_1, \\Delta_2$ are non-negative by construction. \n\nFor condition (2), if $\\tau < T + \\nu$ we must have $\\tau' < T + \\nu + \\Delta_1$ by definition of $\\Delta_1$. Similarly, if $T + \\nu < f_k(x) + \\nu_k$ then $T + \\nu + \\Delta_1 < f_k(x') + \\nu_k + \\Delta_2$ because $\\Delta_2 \\geq \\Delta_1 - (f_k(x') - f_k(x))$. \n\nFinally, for condition (3), the PDF of the exponential distribution implies $p_{expo}(\\nu;\\Delta/\\epsilon_1) \\leq \\exp(\\frac{\\epsilon_1 \\Delta_1}{\\Delta}) p_{expo}(\\nu';\\Delta/\\epsilon_1)$ and $p_{expo}(\\nu_k;\\Delta/\\epsilon_2) \\leq \\exp(\\frac{\\epsilon_2 \\Delta_2}{\\Delta}) p_{expo}(\\nu_k';\\Delta/\\epsilon_2)$. Due to the fixing of randomness of $\\nu_{i<k}$, we have that $\\tau' - \\tau \\leq \\max_{i < k} (f_i(x') - f_i(x))$ so $\\Delta_1 \\leq \\Delta_k(x,x')$ from Definition B.1 and $\\Delta_2 \\leq \\max (0, \\Delta_k(x,x') -(f_k(x') - f_k(x)))$ which implies condition (3). Q.E.D.\n\n$ $\n\n\n\n\nWe also mention in line 569 that this proof applies to Laplace noise. The only change is that condition (1) is no longer required as Laplace noise can be negative, and for condition (3) the inequalities hold identically for the laplace PDF.\n\n$ $\n\n$\\textbf{Preemptively giving other further proof details and updates for better clarity}$\n\n\nPreemptively we feel the reviewer will also want more detail for Lemma B.2 although it's an immediate application of Lemma 4.2 (which is a folklore result) from Durfee and Rogers once the notation is translated. Specifically, for their $M^k_{gumbel}$ defined on page 11 (of their arxiv version), we'll let the output set be $Y = (i : i \\leq k ) \\cup \\tau$ where $\\tau$ represents the threshold. Further, let $q(x, i) = f_i(x)$ and $q(x,\\tau) = T$. By construction the probability that ${M}_{gumbel}^\\ell(q(x)) = (k, \\tau)$, where $\\ell=2$, is equivalent to the probability of above threshold (with Gumbel noise) returning $(\\bot^{k-1},\\top)$. Even more specifically, both can be identically written in the integral form at the beginning of their proof of Lemma 4.2 (top of page 36 of their arxiv version) but translated to the outcome of $(k ,\\tau)$. If we then look at the last line of the proof of Lemma 4.2 (page 36 of their arxiv version) and plug in $\\epsilon_q$ defined earlier in their proof, we see that this lemma immediately implies our desired result.\n\n$ $\n\n\nUpon detailed re-examination of all our proofs we also discovered that Lemma B.3 needs minor changes. In particular, the relaxation in line 589 must be removed. This does not affect any of the results in the main body of our paper, and only requires we remove the second claim in Corollary C.1 which is not used anywhere else in our results. We apologize for our embarrassing sloppiness and thank the reviewer for forcing a thorough re-examination upon us to improve the clarity of our work. Updating the proof only requires re-setting $\\Delta_1 = \\max(0,\\Delta_1)$ and $\\Delta'_1 = \\max(0, \\Delta'_1)$, but otherwise follows the exact same logic. We also found a typo in the proof of Lemma C.1 at the beginning of line 720, which should read $\\Delta_k$ instead of $\\Delta_i$. We'll be more than happy to immediately provide the edited and more detailed proof of Lemma B.3 in this thread, but it would exceed the character limit in this response."}, {"review_id": "BZsPwMKJkm", "reviewer": "Reviewer_QwHj", "summary": "The paper considers the problem of differentially private computation of quantiles for the data. The core idea is to leverage the ‘AboveThreshold’ algorithm  as a subroutine to guess the desired item value such that the rank of the item value is about qn for target quantile q. Authors also discuss the application of this method for mean and sum estimation where the proposed algorithm can help clipping the item values.Experimental results indicate improvement for inner quantiles over Page, Age, Workhours dataset. ", "questions": "1) Can the algorithm improve to O(logN) pass over the data with something like exponential search? \n\n2) 1000 data points in the experiments are very small. Also maybe consider including some results on the query latency. For example the time to find the median.\n", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Quantile estimation is very important problem with real-world applications. This paper presents a straightforward application Abovethreshold differential privacy techniques. For applications, the simplicity in algorithms is greatly valued. The paper is well written and very accessible for the general audience.", "weaknesses": " One major concern is the requirement of O(n) passes through the dataset. With a large volume of data, n passes seem to be formidable. The experimental section can be strengthened by using more data points and considering query latency. \n\nRelated works on quantile approximation are missing.\n     Gillenwater, Jennifer, Matthew Joseph, and Alex Kulesza. \"Differentially private quantiles.\"  They present a DP-algorithm with exponential mechanism that estimates all m quantiles in $O(mnlog(n)+m^2n)$ time. Zhao, Fuheng, et al. \"Differentially private linear sketches: Efficient implementations and applications.\"  && Pagh, Rasmus, and Mikkel Thorup. \"Improved utility analysis of private countsketch.\" They present a DP-algorithm using count sketch to estimate all quantiles in one pass with gaussian mechanism.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and apologize for not stating the runtime of our result more clearly. To be very clear, our algorithm only requires ONE pass through the data, so the runtime is O(n) in the data size, and does not require sorted data. We point the reviewer to section 4.2 for more details and section D.3 in the supplementary material for the corresponding code which is quite simple.  Furthermore this pass through the data is easily parallelizable which allows it to scale even better for large datasets. If we also apply the splitting framework (see section 4.3) for multiple quantiles, then this will only require log(m) passes through the data taking O(log(m) n) time in the data size.\n\nWe definitely see how our wording was confusing, but we hope this should clear up most of the reviewer's questions and concerns. We also note that we do reference and discuss \"Differentially private quantiles\" from Gillenwater et al.  multiple times (and using 1000 data points was a result of copying their experimental setup). We did not include explicit runtime comparison, though as you can see ours will do better asymptotically in the data size. We also thank the reviewer for pointing out the missing countsketch references that we will be sure to add with discussion."}]

Author rebuttal:

Meta-review: Reviewers Qz1m, nQ9t, and QwHj are all in favor of accepting the paper, arguing that the proposed unbounded quantile mechanism is simple with interesting and novel analysis, applies standard DP mechanisms creatively, and that the underlying problem is important. On the other hand, reviewer VnsR argues that some proofs are incorrect.

My understanding is that the two concrete concerns raised by VnsR have been addressed by the authors. In particular, regarding line 557, I think it is clear that the authors are only fixing the values of $v_1, \dots, v_{k-1}$ and not $v$ or $v_k$. It also looks like the authors acknowledge the correction required in their change of variables (which does not affect the calculation, since the determinant of the Jacobian is 1). While I agree that these are important corrections, it seems like these are relatively minor errors that can be fixed in the camera ready. During the reviewer discussion period I asked if there were any further correctness concerns and reviewer VnsR did not respond.

With these corrections, I believe the paper is above the bar for NeurIPS.
Decision: Accept (poster)