Differentially Private Quantiles with Smaller Error
Authors: Jacob Imola
Fabrizio Boninsegna
Hannah Keller
Anders Aamand
Amrita Roy Chowdhury
Rasmus Pagh
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
quantile estimation
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: A new mechanism with more precise private quantile estimation in most realistic parameter ranges

Abstract: In the approximate quantiles problem, the goal is to output $m$ quantile estimates, the ranks of which are as close as possible to $m$ given quantiles $0 \leq q_1 \leq\dots \leq q_m \leq 1$. 
We present a mechanism for approximate quantiles that satisfies $\varepsilon$-differential privacy for a dataset of $n$ real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by $\psi$.
As long as the minimum gap between quantiles is sufficiently large, $|q_i-q_{i-1}|\geq \Omega\left(\frac{m\log(m)\log(\psi)}{n\varepsilon}\right)$ for all $i$, the maximum rank error of our mechanism is $O\left(\frac{\log(\psi) + \log^2(m)}{\varepsilon}\right)$ with high probability.
Previously, the best known algorithm under pure DP was due to Kaplan, Schnapp, and Stemmer (ICML '22), who achieved a bound of $O\left(\frac{\log(\psi)\log^2(m) + \log^3(m)}{\varepsilon}\right)$. 
Our improvement stems from the use of continual counting techniques which allows the quantiles to be randomized in a correlated manner.
We also present an $(\varepsilon,\delta)$-differentially private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when $\delta$ is sufficiently close to zero.
We provide experimental evaluation  which confirms that our mechanism performs favorably compared to prior work in practice, in particular when the number of quantiles $m$ is large.

Differentially Private Quantiles with Smaller Error
Jacob Imola
Fabrizio Boninsegna University of Padova Italy fabrizio, www.ssnnggnnnd...nn........ unipd.is
BARC, University of Copenhagen Denmark ciim@di.ku.de
Hannah Keller
Anders Aamand
Amrita Roy Chowdhury
Aarhus University
University of Copenhagen
University of Michigan, Ann Arbor
Denmark
Denmark aa@di ku.
United States of America aroyc@umich. edu
hkellerdcs. au. au. .k
Rasmus Pagh
BARC, University of Copenhagen Denmark paghêdi ku.dk dk
Abstract
In the approximate quantiles problem, the goal is to output quantile estimates, the ranks of which are as close as possible to m given quantiles
91 I 9m 1. We present mechanism for approximate quantiles that satisfies e-differential privacy for a dataset of n real numbers where the ratio between the distance between the closest pair of points and the size of the domain is bounded by vb. As long as the minimum gap between quantiles is sufficiently m log(m)) log(+) ne
large, 14: 4-11 2 Ω
for all i, the maximum rank error of
our mechanism is O Hog (m))
with high probability. Previously, the best known algorithm under pure DP was due Kaplan, Schnapp, and Stemmer (ICML '22), who achieved bound of O (log(()) log (m))+og" (m)) Our improvement
stems from the use of continual counting techniques which allows the quantiles to be randomized in correlated manner. We also present (s, diffffrrreny private mechanism that relaxes the gap assumption without affecting the error bound, improving on existing methods when 5 is sufficiently close to zero. We provide experimental evaluation which confirms that our mechanism performs favorably compared prior work in practice, in particular when the number of quantiles m is large.
Introduction
Quantiles are a fundamental statistic of distributions with broad applications in data analysis. In this paper, we consider the estimation of multiple quantiles under differential privacy. Given dataset X of n real numbers and quantiles 0 < Qi <... < qm < 1 the goal is to output estimates ž Am such that the fraction data points less than 2; approximately qi- We measure the error by the difference between the rank of 2; in X and the optimal rank q.n. For the ease of exposition, we first consider the case where elements of X are integers in {l..... 6} and the error probability bounded by 1/b. In particular, the ratio &p between the closest pair of points and the domain size is bounded
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

by b. Past mechanisms fall into two categories based on the type of privacy guarantee achieved. For pure e-differential privacy, the best known bound on maximum rank error of O (log(b) log log"(m)/e)
due to Kaplan, Schnapp, and Stemmer [18]. On the other hand, work on approximate differential privacy has largely focused on controlling how the етrоr grows with the domain size b g 3 17 I
These results reduce the dependence on down to log" (b)) but introduce log( ( factors for small
values of 6, for example when log(1/ /6) > (bg(b) log"(m) (m). the bound on rank error exceeds that of methods guaranteeing pure differential privacy.
Our goal is two-fold: to improve the rank error of private quantile estimates both under pure differential privacy, and under (e, -diiferrrel privacy with small values of 6. To this end, we make the following contributions.
We present mechanism that satisfies e-differential privacy for any quantiles satisfying a mild gap assumption: specifically, that [g: q-11 2 2 m log(m) log(0) for all i. This condition depends only on the (public) queried quantiles- if they do not meet this assumption the protocol can be safely halted without accessing any private data. For quantiles meeting the assumption,
ne
with high probability, our mechanism achieves a maximum rank error of O [oog(b) (m)
saving a factor ((min(log(() ((mm over past purely private mechanisms.
We also present an (e, 8) -diifferretial private mechanism that relaxes the gap assumption to be independent of b without affecting the error bound. Notably, our error guarantee remains free of any dependence on ò; the parameter 5 only appears in the assumption on the gap between quantiles.
For both the mechanisms, our improvement stems from the use of continual counting techniques to randomize the quantiles in a correlated manner. We provide an experimental evaluation on real- world datasets which validates our theoretical results. The improvement is most pronounced when the number of quantiles m. is large, particularly under the substitute adjacency. In this setting, our mechanism improves the accuracy compared to [18] by factor of when estimating 200 quantiles with n = 500, 000, s = 1, and ò = 10-16,
1.1 Relation to Past Work
The problem of quantile estimation is closely related to the problem of learning cumulative distribu- tions (CDFs) and threshold functions 714 Learning of threshold functions is usually studied in the statistical setting where data is sampled i...d. from some real-valued distribution. For worst-case distributions the problem has sample complexity that grows with the support size, so in particular we need to assume that the support is finite or that the distribution can be (privately) discretized without introducing too much error. Feldman and Xiao 14] established sample complexity lower bound of (log b) for the quantile estimation problem under pure differential privacy. Bun, Nissim, Stemmer, and Vadhan 77] demonstrated a lower bound of 2 b) for the same task under (e, -differrenta privacy, and mechanism with nearly matching dependence on 6 was developed in a series of papers [ 3 [7 [.]. We note that these results focus on b and do not have an optimal dependence on the privacy parameter 8. For example, the algorithm of Cohen, Lyu, Nelson, Sarlós, and Stem- mer [T]] has sample complexity (and error) proportional to Ö(log" b). which is optimal, but this bound is multiplied by log"(1/5), For extremely large data domains, [ can therefore outperform our algorithm; however, for domain sizes encountered in practice, the higher dependence on 5 will likely outweigh this improvement. Our mechanism for approximate DP yields error independent of 8 and therefore outperforms existing mechanisms when is small. With a slightly worse dependence on 6. Kaplan, Ligett, Mansour, Naor, and Stemmer [17] achieved an error proportional to (1)8). Earlier work g had a weaker dependence on and 8.
The problem of estimating m quantiles under pure differential privacy has been explored by Gillen- water, Joseph, and Kulesza [15] as well as Kaplan, Schnapp. and Stemmer [88. The latter proposed
an algorithm with error O (mogg ). In the uniform quantile setting, where quantiles are evenly spaced, they improved this bound by a factor Olog m)) Their approach is inspired by the work of Bun, Nissim, Stemmer, and Vadhan 77. solving the problem of single quantiles using the exponential mechanism instead of an interior point algorithm. The problem solved recursively
by approximating the middle quantile gm and recursing on the dataset relevant for the first and
2

---

Privacy Guarantee
Minimum Gap
Notes
(e. D/-iifferetta Privacy Corolary 5.2
aklegtee looth)
Saves a (1mmin()gg))) kug (mn)) factor over
(c,6). Differremii Privacy, Corollary 5.3
independens unlike prior work [1
Table I: Summary of our theoretical results. We consider both add/remove and substitute adjacency.
Our privacy analysis is tighter for the latter.
second half of the quantiles, respectively. If the quantiles satisfy our maximum gap assumption, then our algorithm enjoys lower error by a min(log' (mn), (om)) factor when b 2 m. one is willing to relax to approximate DP, we can significantly reduce the gap assumption for the same error. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be (log(6) (log()) + log(m) m) log 5 )); ; this is still less than [18] when _ < b. usually the case for larger data domains. The properties of the algorithm of [8]] in the statistical setting was investigated by Lalanne, Garivier, and Gribonval [1]]. They also considered an algorithm based on randomized quantiles, but it relies on strong assumptions on the smoothness of the distribution.
Differentially private quantiles has received attention under different problem formulations. Some work takes the error function to be the absolute difference between the estimate and the true quan- instead of the rank error. This gives rise to a fundamentally different problem, and
tile 12 22 distribution assumptions are typically needed to ensure good utility. The problem has also been considered in streaming (2) and under local differential privacy [12 []] though the different natures of these problems prevents the techniques from carrying over.
Our Approach. Similar to 18 we also solve the problem by splitting it into m subproblems, referred to as "slices". Each slice is a contiguous subsequences of the sorted input data X {ax (==)ii......i that is, each slice must consist of the elements z((),.. ..... (()) for two indices < j. However, instead of using divide-and con-uu,,, we take a different approach we propose a way to choose random slices around the quantiles using techniques from continual counting [3] Assuming the quantiles are sufficiently spaced, each quantile can be approximated by applying the exponential mechanism to a subset of points around the quantile. The total mechanism then consists of two steps: (1) splitting the dataset into disjoint subsets around the quantiles using private continual counting, and (2) applying the exponential mechanism to each disjoint subproblem. The main technical challenge is that modifying one data point can modify the data contained in many of the subsets. To circumvent this issue, we must add correlated noise to each quantile before forming the subsets, which has the effect of hiding the modifications created in all the slices by the change in a single data point. Our privacy analysis introduces novel mapping for adjacent datasets X and X': by carefully aligning the noise introduced via continual counting, we ensure that at least m 1 slices remain identical. This gives approximate differential privacy (since the mapping is not exact), but the resulting ó parameter can be made extremely small given sufficient spacing between quantiles. We can then achieve pure differential privacy by mixing in uniformly random output with very small probability. Although slicing has also been used in prior work [II]. we are the first to apply continual counting in this context and achieve utility guarantees that are independent of 6.
Limitations. Our algorithms introduce a quantile gap assumption not present in prior work. However, as long the number of quantiles is not too large, this assumption is often met- mat-data analysts often care about a limited number of summary statistics (e.g.. 10%, 20%. ..., 90%). A particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation. For approximate DP, our gap assumption is milder, at O me (log(b) + log(m) log "h ")) - is usually significantly less than in practice, and for the realistic parameters tested in our experiments, the required gap was < 0.005. However, other techniques may be preferable when the quantiles are closer than the gap. We believe that a tighter analysis may relax the gap assumptions.
2 Background
Our setup is identical to that of Kaplan Schnapp, and Stemmer [8]. That is, we consider a dataset X {I:he=l...m where I; E [o, C. IR. We say a dataset X has minimum separation g if
3

---

mingzy [ z, Unless explicitly specified, without loss of generality we assume that a 0, g = since any general case can be reduced to this setting via linear transformation of the input. Our results can be translated the general case by replacing b with & --a Given set Q of m quantiles 0 < 41 <
Im the quantile estimation problem is privately identify Z = (21,.... 2m) E 61 such that for every E [m] we have rankx (2,) ~ [q.n.] We consider
the following error metric:
E (Q, max (z)) Lq:n|] =E[m]
This error metric has an intuitive interpretation as the difference between the estimate's rank and the desired rank, and is the more often considered in the DP literature [18 [5 7]. For convenience, we let r, = [q.ra] denote the rank associated with each quantile. We denote by 2()) the ith smallest element of X (i.c., the sorted order of the dataset).
Differential Privacy. We consider two notions of adjacency our privacy setup. Two datasets X' are add/remove adjacent if X' = X U {z} or X = X' U {z} for point z. We say X, X are substitute adjacent if [X] = (X'). and |XAX| S 2. Thus, X' may be obtained from X by changing one point from X. Differential privacy is then defined as:
Definition 2.1. A mechanism M(X) [0, (0 + y satisfies (e,8)-dij) dddffferrett privacy under the add/remove (resp. substitute) adjacency for all datasets X, X' which are add/remove (resp. substitute) adjacent and all S C y, we have
E Pr(M(X') E +
In our results, we explicitly specify which adjacency definition is used. While the two notions are equivalent up to factor of privacy parameters, our bounds for substitute adjacency are slightly tighter and not directly implied by those for add/remove adjacency.
3 Proposed Algorithm: SliceQuantiles
We begin with an intuitive overview our algorithm, followed by the full technical details. For ease of exposition, we focus here on add/remove adjacency and defer substitution adjacency to Section
3.1 Technical Overview
At high level, our private quantiles algorithm SliceQuantiles applies a private quant-le algorithm SingleQuantile to slices of the input dataset, which are contiguous subsequences of the sorted dataset. To ensure the accuracy of the overall scheme, they must meet the two conditions:
Each slice must be sufficiently large because the accuracy of SingleQuantile is typically mean- ingful only when there is enough input data.
The slices must be centered around the desired rank rt. i.e. consist of data with rank approxi- mately ri.
Following the criteria outlined above, one might attempt use slices Si. Sm, where each slice is defined as S; Z(r.-h)..... (+(r+++)) for some sufficiently large integer h and estimate quantile q. by applying SingleQuantile to S.. However, as noted in prior work [[] 7 this does not have satisfying privacy parameter. Consider an adjacent dataset X', where new point with rank s, T's))
added. This produces change in each slice S,, S,,..,, St,, where is the smallest index such that 8 S rt - h. The naive approach would be to use composition to analyze the quantile release, causing the error increase by factor of (mly
Instead, we make a more fine-grained analysis based on the following observation: for i > t the slice pairs {S,, ) are shifted by exactly 1, i.c.,. S, x/ ((r.- ... ,
+r++h+1) Our goal is to hide
'This is easy to enforce, minimum separation always be created by adding small amount of noise each data point (or by adding 1 to point i). Importantly, if the data not separated. affects only the utility guarantces our algorithms not their privacy guarantees.
n
For now, assume the slices do not overlap we address this issue later.

---

Algorithm SliceQuantiles
1: Input: X, f1,,,..... Pm (1) 62), v. [0.0]
2: Set h = --
3: Require: Pl...., Im E Goodmm..th
4: F1,....P
+ CC,, (ri, (ri,...,, .m.) 5: Flip a coin with heads probability Y
D Post-process the noisy ranks to integers.
6: if is heads i & Goodm, then
7: Sample ....... 2m i.d.d from [0, b]
8: return 21 Fm
9: end if
10: for
1 to do S, + (F. hj......... (F.
Get the perturbed slice
12: 2, SingleQuantile, 10. (S.)
13: end for
return 2m
this by randomly perturbing the ranks to noisy values iy such that it is nearly as likely to observe r, = Us + es, for any possible integers Ui,..., Um. and any "shifting" values 61,..., em satisfying
0 ist
c i>t
for given index < S m and a {-1,1}. We will refer vector of this form as a contiguous vector. Such perturbations are the central object of study in the problem of differentially private continual counting [13 TO 4, which provide the following guarantee (proof is in Appendix (A).
Lemma 3.1. There exists randomized algorithm CC2 z - T such that for all vectors r, E Td and e E (,1,0,1)" of the form in Eq. ( we have
(r( = i] s ef Pr(CC.(r) = =iee)
and (2) for all B > 0, Pr [|r CC.(r)ll 2 3 3lg((m) log( 2m )/e] s B.
Consequently, we can S = IT(F.-))..... .)..... ((F+ Our privacy analysis may then proceed as follows. Let S -i.... Syn denote the slices when X' used instead of X. Now, fix any observed noisy ranks fi.....ff generated from X. By the continual counting property (Eq, (2). when using X', it almost likely observe Fı ......, F' + Em, where e Em the shifting vector such that , Sm and S...., S' differ in at most one slice. This setup allows us to analyze the final release SingleQuantile(S.)) incurring the privacy cost of applying SingleQuantile only once. Interestingly, the privacy analysis when X" is formed by removing point from is more subtle and leads asymmetric privacy parameters. We discuss this in detail in Section
SingleQuantile(S.. using parallel composition
that is,
follows: first, perturb the target ranks ri, ri....,Tm Fm by adding correlated noise generated via continual counting; then, for each slice S, = -)) (FF+t)) apply the SingleQuantile mechanism obtain the output 2i....; 2m.
In summary, the main steps of SliceQuantiles
3.2 Implementation Details
Outlined in Algorithm] I, SliceQuantiles is provided with the following parameters: (1) (w, e an bound (to be set later) and privacy budget for CC; (2) (6, 62). the minimum list size (to be later) and privacy budget for SingleQuantile; (3) probability 7 of outputting a random value which assume for now is O, and (4) data domain bounds [0, b). We can instantiate the algorithm with any SingleQuantile that satisfies DD-
A technical challenge arises after sampling the vector i = (fi,.... Fm)): there is guarantee that the generated slices would be non-overlapping, which would invalidate our privacy analysis P We
3 As a simple counter- example, suppose the F; all ended up equal. Then, every slice could potentially change for an adjacent dataset, and the privacy parameter could be high me.
5

---

address this as follows. We define the following set for notational convenience:
Goodm,n.4 {f Fm)) E TTh - 2 - > 24 for i = 1,..., m - 1. n
The set Goodm, ...A consists of noisy vectors with sufficient space around each i; to ensure that the slices do not intersect. We eliminate the risk of overlap by checking that the sampled noise belongs to mo,d (Line and if not we release random output from (0, b)th (corresponding to a failure). To ensure that failure is rare, we require the input ranks r to belong to Goodm,n w+h where is the maximum error introduced by CC (Line 3). which is the precise requirement for the quantile gaps.
A practical improvement proposed in 18 is to adaptively clip the output range of the SingleQuantile algorithm. Our algorithm is able to support this as well as follows. Instead of estimating each 2, using independent calls to SingleQuantile as in Line 12] first compute 2m/2 for the middle quantile by running SingleQuantile with the entire data domain [0, bj. Then, compute 2m/4 using SingleQuantile with data domain restricted to [0, 2m/2], and compute 23m/4 /4 using SingleQuantile with data domain restricted to | b]. Output all quantiles by recursing in a similar binary fashion. The privacy analysis of SliceQuantiles can be modified in straightforward way to handle these adaptive releases, and in practice, when SingleQuantile is c.g. the exponential mechanism, the utility of SingleQuantile improves by restricting the set of possible outputs.
4 Privacy Analysis
We begin by explaining our analysis under approximate differential privacy, and later show how to convert this to guarantee under pure differential privacy. The proofs for results in this section appear in Appendix B
Technical Challenge. Our first attempt at a privacy proof might proceed as follows: observe that any E Goodm.n.h may be mapped to corresponding F' E Goodm...h such that (1) the difference vector e P-rP r' is contiguous vector, and (2) the corresponding slices Si....,S and . Sy differ in only one index j. and only by a single substitution within that slice. We would then hope to establish (e, diffferrett privacy by arguing the following: (1) noisy vector sampled by CC belongs to Goodm. with probability at least 1 - 8; (2) CC is capable of hiding any binary shift vector of the prescribed form; and (3) single application of (c, -ddiffrrrnt privacy suffices, since only one slice differs between the adjacent datasets.
Unfortunately, there is a flaw in this argument: if many vectors i are mapped to the same F', it becomes difficult to compare the resulting sum over duplicated F' values to a sum over all i Good mo A prior work 77] was able to show that there exists mapping sending at most two distinct values of r to single F'. However, this has a significant limitation: even a multiplicative factor of blows up the privacy parameter to 2 making it impossible to establish any guarantee with a privacy parameter smaller than (2). (Note that we cannot make use of privacy amplification by subsampling [8] 21] without incurring a large sampling error on quantiles.)
Key Idea. A key novelty of our technical proof is propose more refined mapping that mitigates the issue above. Specifically, our mapping injectively maps each i E Goodm...h to corresponding I' in a slightly larger set. Our mapping depends on whether X is smaller or larger than X'. When X' = X O } (i.e., an addition), we observe that the mapping above is, in fact, an injection. The difficulty arises only in the case of removal. Nevertheless, when X X' U {I.). we show that it is possible to construct an injection that ensures at most two slices among Si...., Sm and S Sy differ, each only by a substitution. Formally, we prove the following in Appendix [.]]]
Lemma 4.1. Let X, X' denote two adjacent datasets such that X' is smaller than X by exactly one point. Then, there exists a function F- (f): Goodm,,,h - Goodm,n,k-1 such that
F- is injective.
For 1 S m, the dataset slices S, = D)j.-K)y..... (F)++h) and St = = -........ (F satisfy Σm (s, 2, where drub is the number of substitutions of points needed to make S; and Si equal.
(-( F + er, where oF is binary vector of the form ezli] -1 2 5] for an index 5 < m ++ 1.

---

Similarly, if X' is larger than X by exactly one point, then there exists a corresponding function F* (F) m.,hh + Goodm,n+1. with the same properties, except that e₁ satisfies eşli] = 1 z for an index 1 S S m + 1, and the sum of substitution distances is bounded by 1 instead of 2.
The fact that F+ and F- map to slightly different sets than Goodm.n.t is not an important detail; our proof accounts for it by requiring the gap between the input ranks be 1 higher.
As a result, to analyze privacy under add/remove adjacency, we incur the privacy cost of CC once and of SingleQuantile at most twice, yielding total privacy parameter of + 25g. Due to the asymmetry of our mapping when a point is being added or removed, privacy under substitute adjacency is slightly better since substitution is both an addition and removal operation. Formally.
Theorem 4.2. Under add/remove adjacency, SliceQuantiles with 7 = 0, 3log(m) (0g(2m/))) and
5).
any h 2 1, satisfies (51 + 282, 8) differrentia privacy. Under substitute adjacency, SliceQuantiles satisfies (2E1 + 3E2, 8 + se +26a) ) privacy.
The proof is provided in Appendix B.2
Notice that privacy holds for any h 2 1; but our utility results, which we will show later, require h to be sufficiently large.
Conversion to Pure Differential Privacy. Observe that ō plays limited role in Theorem namely it affects only the minimum gap separating the ranks of interest. When the rank gaps (and the data size) are sufficiently large, 8 can be made small enough be absorbed into the terms. To do this, we prove a reduction from (e, --approxiea differential privacy to s-pure differential privacy, which holds when d < D the inverse of the size of the output range.
Lemma 4.3. If mechanism A(X) with discrete output range y satisfies (e,5) -ddifferrntti privacy with
8|2 (c- 1j S 1, then the mechanism Á(X), which outputs a random sample from y with probability
and outputs A(X) otherwise, satisfies (e, O)...
To apply the lemma to SliceQuantiles, we need to discretize the output domain to [6]T (for example, by rounding to the nearest integers). This introduces a maximum error of in the quantile estimates, which is negligible when the dataset has minimum gap of 1. A pure differential privacy guarantee is then corollary of Lemma 4.3 and Theorem 4.2 with 8 = >(f11-1)
6m
Corollary 4.4. Under add/remove adjacency, SliceQuantis with > 0 and
3log(m)
(mlogb b log (2m((69-1)
E1
and with estimates rounded to [ail...,, Lamb satisfies E + 2 differreniall privacy. Under sub-
stitute adjacency, Algorithm / with w (log(m) (mlog b + log 2miee
-1) + E1 + 282) satisfies
28, + pure differential privacy.
For most parameter settings, w will dominated by the m log 6 log(m) term. To satisfy the condition
r E Goodm,n, uh it is necessary to have n 2 m² log log(m)) For instance, when Ej = E2 = 1, b = 232 and m 100, then w Ra 65, 000, the minimum gap is 2w = 130, 000, and the total amount of data required is 1.3 x 107. While the minimum gap between quantiles maybe too large for some datasets, our algorithm offers asymptotic utility improvements over the best-known pure differential privacy algorithms when this assumption is met. We expand on this in the next section.
5 Utility Analysis
SliceQuantiles may be implemented with any private algorithm SingleQuantile for estimating single quantile of dataset. We introduce a general notion of accuracy for SingleQuantile in order derive general error bound.
Definition 5.1. An algorithm SingleQuantile( X) is an (a, (, algorithm for mediun estimation if, for all datasets X E (0, b)"h of size n 2 f, with probability at least - 33, SingleQuantile( (X) returns median estimate with rank error rankx (z)) S a.
7

---

For our purposes, it is sufficient to only require SingleQuantile to return median estimate, since the median of the slice S, is the element with the desired rank i; in X. In its general form, our utility guarantee is as follows:
Theorem 5.1. Suppose SliceQuantiles is run with an (ax, ( algorithm SingleQuantile for single quantile estimation. Then, for any input ranks "......Tu Tm such that they are in Good w-t for T(E 1),21, conditioned on Line not failing, the returned estimates satisfy Errx (Q, 2) S log m log( ( with probability 3.
O
E2
We prove this theorem Appendix C Next, we specialize this utility theorem in both the pure and approximate DP settings, and compare them to the best-known algorithms.
5.1 Utility Guarantee under Pure Differential Privacy
Under pure DP, we may implement SingleQuantile as the exponential mechanism with privacy parameter E2 and utility given by the negative rank enror. We show in Appendix [ that this is
(h, 2h + 1) algorithm for median estimation with = the following immediate corollary (for simplicity, we state it using add/remove adjaceney).
[log(2b/00] for any 8 E (0, 1). This gives 52
Corollary 5.2. Suppose SliceQuantiles run with set as Covollary 4.4 SingleQuantile set be the exponential mechanism and i t= 2 2 log logg(2bm//)) (2bm/B)
+ 1. Then, the algorithm satisfies e-differential privacy with & E1 + 282, and with probability at least 1 - 3 7, achieves an error bound
of E (Q, Z) S O log(b) + log log(m/9)) for any input quantiles with gap
6m log(b) log(m)
8
S1R
0 (mg(m) log log(mm(e - 11/72)
In contrast, the state-of-the-art algorithm under pure differential privacy attains error O log log 8) (mm)
bogblog" log"
18 When log(b) > log(m)² error improved by a factor of log(m)?. When log(m) < log(b) < log(m)), the factor is log(b). This represents an improvement factor of (iinloo(b)) log( }m) when b > m. Note that this improvement comes with a mild constraint: it requires the minimum gap between quantiles to be least S2(" m log(b) log(m)
5n
Nevertheless, the case of equally spaced quantiles remains a well-studied and important problem. In
this setting, 18 provide an improved analysis of their algorithm, achieving error of O log Ing(mm)
log(m/8 8) log(m))
Our algorithm still offer an improvement by a factor of log(m) for the case b > m.
Note that meet the required quantile gap, it must hold that 2 amm² log b log m
5.2 Finding Quantiles Under Approximate Differential Privacy
Under approximate differential privacy, quantile estimation algorithms with more favourable depen- dence on b are known. Specifically, as shown in [II), there exists an (8, 6DD algorithm which is (6. f, log"" (b)) algorithm for median estimation with 1000 log" (6) log(3) ) This algorithm may be used to answer general threshold queries, or the fraction of data below query point E [o, bj, of a dataset of size n, and provides error that scales with log" (b) instead log(b). We provide the full details of these results in Appendix C When translated to quantile estimation, this threshold
query-based method can answer any set of quantiles with error O (b) log" (lg"(log" (6)/85). We note that there is no dependence
in this bound.
Though the factor of 1000 above is probably far from tight, even the log² (1/8) factor incurred by the algorithm can be quite large, and result in higher error despite the improved log" (b) dependence on the domain size. To avoid incurring log(1 (1/8) terms, we instantiate the (e, 6) version of SliceQuantiles with the exponential mechanism to obtain:
Corollary 5.3. Suppose SliceQuantiles is run with w set as in Theorem 4.2 SingleQuantile set to 1. Then, the algorithm
be the exponential mechanism, with ? and e 2 [2 3llgg(2m,,) /
22
satisfies (E, -ifffferrntt privacy with E1 + 2 and with probability at least 1 - 3 8.
8

---

S 0 (og( log(mm) log( %
achieves an error bound of Errx (Q, 6 (log(m) mm) log(2m/6)
for any input quantiles with
4log(2bmm/)
gap
+
fimt
62m
Observe that whenever log m log( ( < log b, the gap is actually asymptotically less than the normal- ized error bound. This means the gap requirement can be removed entirely by merging any quantiles too close, and this will only increase the error term by constant factor.
Compared with the previous error guarantee, the guarantee in Corollary 5.3 is in fact lower whenever log(t) < log2(t) (f) log" (b) and log(m) is sufficiently small compared to (og(1/5), which is often true for practical choices of the parameters. For instance, log" (b) rarely exceeds 4 even for very large domains, while log(b) is typically below 64, and log (1,5) often reaches into the thousands for typical choices of Furthermore, the hidden constant factor the former algorithm not known to be under 1000, while in our case it is roughly 10. These factors underscore the superior practical performance of our approach.
Experiments
For our experiments (code is open- " we use variant of the k-ary tree CC mechanism introduced in [ with two-sided geometric noise, and SingleQuantile implemented as the exponential mechanism [8] 20 Similarly to Kaplan et al. [8] we construct two real-valued datasets by adding small Gaussian noise to the AdultAge and Adul tHours datasets [ both datasets, corresponding to ages and hours worked per week, exist on the interval [0, 100]; we use this as our data domain. Unlike their approach, however, multiset ranks), resulting in approximately n = 500,000 entries. This allows us to analyze a large number of quantiles without needing to resort merging techniques. Concretely, the gap assumption for our parameters is 0.005, so up to 200 equally-spaced quantiles could be answered. The distribution of these datasets are detailed in Appendix E To ensure minimum spacing of 1/n between data points, we add i/n to the ith element in the sorted dataset. For each m E {10, 20, 20...., 200). we randomly sample quantiles from the of 250 uniformly spaced quantiles {i/251 : = I..... 250). and run experiments on both datasets. This sampling procedure is performed independently for each experiment, ensuring that the reported results represent an average over both good and bad instantiations of the problem. We evaluate the mechanism under both substitute and add/remove adjacency, using = and 10-16 < A/2 as the privacy parameters. Additional experiments with varying privacy budgets are presented in Appendix E The y-axis in our results reports the average maximum rank error, with 95% confidence intervals computed via bootstrapping over 200 experiments. Results are shown in Figure | the first two plots (from the left) correspond to substitute adjacency, while the remaining plots correspond add/remove adjacency.
scale the dataset by duplicating each data point 12 times (preserving
Baseline Algorithms. Our primary baseline is Approximate Quantiles (18). which abbreviate to AQ. Experiments in that reference demonstrate improved utility over the AppindExp algorithm [15]. hence do not include AppindExp in our comparisons. AQ satisfies both pure and approximate DP, with the approximate DP analysis leveraging an improved analysis of the exponential mechanism under eere-coonenttateed DP
6 99. As we using approximate DP for our experiments, privacy analyses of AQ as comparison baselines. We also compare to the histogram-based method of [19] because its error much higher due making linear approximations of the data distribution, we put these plots in Appendix
include
Implementation details of SliceQuantiles. Our empirical results indicate that the most effective strategy for allocating the privacy budget between CC and SingleQuantile is to divide it equally,
assigning half to each mechanism. To compute the size of the slice, we use h = 2 log mmm
We used numerical optimization of the Chernoff bound to compute the smallest possible value of the parameter w bounding the CC mechanism with failure 8, beyond the asymptotic expression given in
according to Theorem C.1 with 3 = 0.05 and //- = b-a = 100n as [a, b] = [o. 100] and g g
Lemma 3.1 The details of this optimization appear in Appendix [ This reduced the quantile gap assumption and maximized the number of quantiles that SliceQuantiles is able to answer.
htngs//githbbbommmyyyyysaaaaabbp quantils

---

SiicQuanlles
Approximate Guantles
Approximate Quaniles Pure
working hours
working
Max Fank Error
200
100
200
Number of Quandies (m)
Figure 1: Experiments on AdultAge and AdultHours datasets. The datasets contain approximately 5- 10 data points, Each experiment was run 200 times, with each run using a random sample from a set of 250 uniformly spaced quantiles. Plots and are for substitute adjacency, while and d correspond to add/remove adjacency. Approximate Quantiles in the above figure refers the algorithm (AQ) from [18] The privacy settings (1, (1,10-16) 1110010)-DPPP JDD for SliceQuantiles and AQ, and (1, O)-DP for AQ with pure DP guarantee [8].
Results. We plot the three algorithms in Figure | The plots indicate that SliceQuantiles performs better than AQ, with notable advantage under substitute adjacency. This in line with our theoretical argument on tighter bound under this adjacency (Theorem 4.2 Consistent with our prior observations, AQ under approximate differential privacy performs worse than AQ with pure differential privacy, due our lower choice of 8. Because its utility guarantee is independent of 8, SliceQuantiles is able to circumvent this issue.
Conclusion
In this paper, we have proposed new mechanisms for approximating multiple quantiles on dataset, satisfying both and (e, 6) differential privacy. As long as the minimum gap between the queried quantiles is sufficiently large, the mechanisms achieve error with better dependence on the number of quantiles and than prior work. Our experimental results demonstrate that these mechanisms outperform prior work in practice, in particular when the number of quantiles large. interesting question for future directions is to explore if more careful analysis could reduce the minimum gap requirement or if other practical mechanisms for differentially private quantiles could further improve accuracy of computing many quantiles privately in practice.
Acknowledgments
Anders Aamand and Rasmus Pagh were supported by the VILLUM Foundation grant 54451.
Jacob Imola and Rasmus Pagh were supported by Data Science Distinguished Investigator grant from Novo Nordisk Fonden
Fabrizio Boninsegna was supported in part by the MUR PRIN 20174LF3T8 AHeAD project, and by MUR PNRR CN00000013 National Center for HPC, Big Data and Quantum Computing.
The research described in this paper has also received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC) and the Danish Independent Research Council under Grant-II DFF. 2064-000168 (YOSO).
References
[1] Anders Aamand, Fabrizio Boninsegna, Abigail Gentle, Jacob Imola, and Rasmus Pagh. Lightweight protocols for distributed private quantile estimation. arXiv preprint arXiv:2502.02990. 2025.
[2] Daniel Alabi, Omri Ben-Eliezer and Anamay Chaturvedi. Bounded space differentially private quantiles. arXiv preprint arXiv:2201.03380. 2022.
10

---

[3] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Proceedings of the SIst Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 852 860, New York, NY, USA, 2019, Association for Computing Machinery. ISBN 9781450367059.
doi: 10. 10.1 00.1145/3311276.3316333 URL.
org/10 11111111111112 .31.22766.336666 3316312
[4] Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on your elders: Laplace vs Gaussian noise, arXiv preprint arXiv:2408.07000 2024.
[5] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https///oi..or///O0 wwt..//////002222///X32222
[6] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, exten- sions, and lower bounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptogra- phy 14th International Conference, TCC 2016-B, Beijing, China, October 31 November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635-658 2016. doi: 00.1007998--36622 -36002--344-411 24. URL httph: / //tp:://do... 0tt.:iioor/11.100000000 978-3-662- 53-41-4-444444
[7] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 2015 IEEE 56th Anmual Symposium on Foundations of Computer Science (FOCS), FOCS '15, page 634-649, USA, 2015. IEEE Computer Society. ISBN 978 7771846388918 doi: N0.1109/FOCS.2015 20. URL httpp:///dd
org/10 10. 1109/FOCS. 2015.
[8] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 74-86, New York, NY, USA, 2018. Association doi: (1814//318745.31188
for Computing Machinery. ISBN 9781450355599 https: :tobps///do// org//i..org//.. wttgg//..111///1111 /111/1188//11.... 318888
URL
[9] Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pages 421-457. PMLR, 2021. URL http:://proceeding.. mlr. wtw.mml....../..mmmm wwwpprrsssssse. v133///ee22e111 cesar21a html
[10] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur. 2::2::2:::122:244 2011. doi: 10. 10.1 141524443221.2044444 URL https://doi. http:///ooooorrg//// org/10. 1144/ 2043626
[11] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. In Proceedings of the 55th Annual ACM Symposium
Theory of Computing, STOC 2023, page 472-482 482, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 978 9781450399135, doi: 10.1145/ 3564246.3585148 URL https::/too:.ii (et/ddii.rgg/1// 10. 1145/35644444 3585148
[12] John C Duchi. Michael Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-20, 2018.
[13) Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. Leonard Schulman, editor, Proceedings of the 42nd ACM Symposium Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 715-724, ACM, 2010. doi: 00.1145/1806689.111 18067877 URL https://dos org/
10. 10.1145/1806683 1806787
[14] Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM Journal on Computing, 1466):740-1766 2015. doi: 10.1137/140991844 URL https://doi httg/10.1137/4409900

---

[15] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3713-3722. PMLR, 2021. /tt.
mlr. pprsss/v19//sseee htt.13////glleeateeeaao html
[16] Scidu Inusah and Tomasz Kozubowski. A discrete analogue of the laplace distribution. Journal of statistical planning and inference, 13603):1000-1102 2006.
[17] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap. In Proceedings of Thirty Third Conference Learning Theory (COLT), 2020.
[18] Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Pruceedings of Machine Learning Research, pages 10751-10761. PMLR, 2022. httt:tttpp/:poceeeeeee
mlr Litesssv162/kap////
html
[19] Clément Lalanne, Aurélien Garivier, and Rémi Gribonval. Private statistical estimation many quantiles. In International Conference Machine Learning, pages 13399-18418, PMLR, 2023.
[20] Adam D. Smith. Privacy-preserving statistical estimation with optimal convergence rates, In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 I, pages 81 313-882 822. ACM, 2011. doi: 10.1145/1993636.. 99144///999633.1999944. 10 1tt.:////...11199903333333 1993743
[21] Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. CoRR, awtpa//..../0// 2022. doi: 1044550/AAXXI.22200003577 /ttpss//:///ai org/
10. 20.48850/arxivv.22 2210. 00597
[22] Christos Tzamos, Emmanouil- Vasileios Vlatakis Saaakis-karagkounii, and Ilias Zadik. Optimal private median estimation under minimal distributional assumptions. Advances in Neural Information Processing Systems, 13:3301-3311, 2020.
12

---

A Details From Continual Counting
In summary, the binary tree mechanism [13 10] achieves E-DP when the input vector r changed
to r + e, where e is a contiguous 0/1 or 0/ 1-valued vector. The mechanism achieves this by constructing segment tree whose leaves are the intervals [0. 1). .......................... [m 1, m)) and sampling Laplace random variable T) for each node I of the tree. For T = [loga (m + 1)1, let I1... Ir denote the interval decomposition of [0, i). Then, the estimate for i. is given by ri Σ5=1 "11 rounded to the nearest integer (by convention, for integers k the number The correlated noise being added to each allows the total error to grow only logarithmically with m. The final rounding ensures that the noisy ranks are integer valued. The rounding is private due to post processing and it only incurs an additional rank error of at most 1/2
1/2 is rounded up k).
A.1 Proof of Lemma
We start with the following concentration lemma:
Corollary A.1 (From Corollary 2.9 of [1)). Suppose 7/a 's are independent random variables, where
each 7/s has Laplace distribution Lap(b:). Suppose Y E; "ha by max; b, and 8 E (0, 1). Ler
V = =max Eg by bw / (2/2))) Then Pr[[V] > UN 8ln(2/)))) <
Proof of Lemma 3.7 Define round RT + Tm to be the rounding function rounding each co- ordinate of vector s E IR'e to the nearest integer (rounding up in case of ties). Note that rs + z² = round(s)
whenever x E Zm. To prove the first guarantee, observe that since the binary tree mechanism is an additive noise mechanism (i.e. CC(r) = round(r NN), where A is a noisy vector) the privacy guarantee of the binary tree mechanism implies that
Pr[CC(r) = r] = Pr(round(r +N = r] < e Pr(round e +N) = r] e Pr|CC(r) = i e
To show utility, each coordinate of N is the sum of at most T independent Laplace random variables with variance / to each estimate. From Corollary A. we have that, with probability at least
1 1- 3/m, each estimate has error at most & 881((2m// (3) max (VT, vIn(2m/B) The claim fol-
lows by a union bound and analysing the asymptotic of 12 (3) max( (VT, (ln(2m33) [B} s
I [1l + /In(2m/B))
B Omitted Proofs From Section 4
B.1 Proof of Lemma 4.1
Proof. Suppose first that X' adds a point to X. This means that there is minimal index such that I(a) = o for all < s, and (((+1) = z(3) for all 2 s. We will define 1+ (i) = F + ep, where each coordinate of e; is defined by
0 A h S
e,
[1 F h
It is clear that this vector belongs to Goodm,,-41. and that Property (3) of the map is satisfied. To injectivity, observe that if F, r' are different, but mapped to the same output, then they must have different vectors e, e'. Furthermore, the coordinates of r. F' only differ by 1. These two things can s + for an index i* However, this will then produce eq- = 0 and e/. = 1, resulting in the i coordinates of F+ (f), F+ (F') to be h + and h + s + 2, respectively, making impossible for equality.
only happen f.- h and P/.
Finally, Property (2) holds because the slices S,, Sy will disagree only if F3 E [s - h, 8 + h). and the sum of substitution distances is 1.
In the case that X' removes a point from X, then τiz) = 2/1 for all < s and z(z) = - for all i 2 8. We define the map F F-(F) (f) = + ep. where each coordinate of es is instead defined by
i= 1 h i> 1A h
4 -=1-1
13

---

Again, Property (3) and membership in Goodm,n,A is immediate. To argue injectivity, observe that if r. F' are different, but mapped the same output, then they must have different vectors e'. This is only possible if Fr. -1 h = 8 and 7/-- -1 - h = 8 for some index i" > 1. However, this then implies that 61- c = O, resulting in F (fr-) f.. and F (1)+-)) = P -1 and forcing the maps to still have different outputs F (f:--1) + F (P--).
Property (2) follows because the slices St, S disagree only in potentially locations; namely the index i" where a E [it- h P;- + hJ (if it exists), and the index j" which is the minimum index such that a < F3- h. Each disagreement adds one the substitution distance, and thus the total sum is at most 2.
Note that at first glance, it may appear though the case where X' removes point from X could be solved analogously to the case where X' adds a point, defining e; as:
F -1 7.
e
> s.
However, this choice would not lead to injective mapping. In particular, set - h and F%- = s + for an index i", which are different, but mapped to the same output. Specifically, this will produce e₁- 0 and e/-- = 11, resulting in F (f:-) + h F F (P).).
B.2 Proof of Theorem 4.2
Proof. We will first prove add/remove privacy.
Let A(X) denote SliceQuantiles run on input X, and let A(X, denote the algorithm conditioned on the noisy ranks f = (fi..... Pm). Let F+ F denote the maps guaranteed by Lemma 4.1 We
will first assume that X' is larger than X, and thus we will use F* in the following, For any output set Z, we have
Pr[A(X) E -|=
Σ Pr(A(X,F) PT(CC(( = Fi]
FEZm
<Pr(CC(r) & Good
Σ
Pr[A(X,F) E P)
iEGood
< 8 +
Pr[A(X,F) E Pr F]
iEGood
8
Σ
e Pr [A(X, (+(XFF((F) (F)) 2] E Pr(CC(r) F+]
meGoodm...k
< + e5tt02
Σ
Pr[A(X', F) Pr|CC(r) = =
FEGood 1T S + tct Pr(A((') E 2],
where the third line follows from Lemma 3.1 which shows Pr[[|r Fl1c0 > w| < 6. and by the
assumption that E Goodm. 1 the fourth follows from Properties (2) and (3) of Lemma 4.1
along with Lemma 3.1 and the fifth follows from Property (1) of Lemma 4.1 When X' is smaller
14

---

than X, then we use the map F and we obtain
Pr(A(X) E 2 = Σ F) e Pr(CC(()) =
FEZm
- Pr(CC((r) & Goodm.n-1.kg
Σ
Pr(A(X,F) E Pr(((((( =
FeGood 1,411
S6+
Σ
Pr(A(X, P] =
iEGood 1.1+1
S +
20 Pr (F((, E Pr(CC(() = F FT(T)
PEGood
< 58+e0 < 212222
Pr[A(X, F) E 2)Pr(CC(()
REGOodm,n-IA
< < 2
Pr(A(X') e Z],
where the deductions are the same, and the only change is the final parameter is + 28 as the constant is higher.
To prove substitution privacy, we may simply use the fact that for two neighboring datasets X, X,X' there is dataset X₃ such that X₃ may be obtained from either X, X by removing a point. Thus, from what we' ve already shown, the pair X, Xı satisfies (#1 + 252, 6)-DP, while X,, XX' satisfies (E1 + E2, DP. By group privacy, have final guarantee of (2e1 + 352, 8 + 22
B.3 Proof of Lemma
Proof. By the (EP guarantee, the probability observing any y E y may be bounded by Pr(A(X) = v) S e Pr(A(X') = y| +
Now, we have
1
Pr[A(X) = v) = = -) - = v) + 7
<1 - (E Pr[A(X') = vl + +6 ? |
=e (U-))(PHA(X) v)) + +7
1 31
8(1 7) + 7(1 5
1
e Pr(A(X') = v) + +8( - 7) + +1(11 - c²)
|
1
Se P=((A(( = vl +8+ 711 e²)
|
= =e PP((((())) = v).
C Omitted Details From Section
5
C.1 Proof of Theorem 5.1
Proof. By union bound, conditioned on Line not failing, with probability least 3, the returned quantiles 21...., 2m will satisfy |rankx (2x) R:l < a. By Lemma 3.1 each i; satisfies
|r Flloo 3lgg(m) log( with probability least 1 33. The bound follows from the triangle inequality.
C.2 Details Exponential Mechanism
Assuming that each point lies [a, b). the exponential mechanism samples point E [a, with probability exp(- E (q. 2))-here will assume the quantile g 1/2 for the median. This can
15

---

be implemented by sampling an interval 4. = ((ee))) with 2(0) and 2(++1) = b, with probability proportional to exp (-å kl)) [xl. and then releasing value uniformly sampled from the selected interval (see Appendix in [8]
The utility of the exponential mechanism for median estimation is as follows:
Theorem C.1. Given a dataset X E (a, bj* with minimum gap g > 0, parameters (0, 1) and & 0, let 1
b-a Then, the exponential mechanism a (h, 2h, 5) algorithm for median estimation
for h log
2xb D
Proof. It is sufficient to suppose the dataset has size 2h, and bound the probability of sampling
in the interval (a, 2[1)] and (z(22), b]. Let I {[a, (1)] ((2))........................... [2(2h)) 6]} be the set of intervals sampled by the exponential mechanism. The probability the sample z lies in the interval
[a, (())) is
e -2"((()) - a)
Pr(2 [0,
ΣE=1 e
2h
211 (I(1)) 1(--))
g
as Ee fli bli (1()) - x(--1)) 2 (1(1+1) R(n) 2 g. By our choice of h, this probability is at 1==1= most g. The same upper bound can be found for the other extreme interval (z(28): b). and the result follows from union bound.
C.3 Details on Threshold Queries
We discuss how the existing work threshold queries may be used to answer quantiles. These algorithms actually work by solving a much simpler interior point problem, where the goal on an input dataset X, is to simply return point such that F(1) S S I(n)- For small enough dataset, the interior point algorithm can also provide a median estimate with low error.
Lemma C.2. (Adapted from Theorem 3.7 of (T7]): There exists (e, 8)-DP algorithm Aint which |X| log(}) 8log" [X]) algorithm for median estimation.
a 300 log" log(3) 1000 log
This demonstrates that it is possible to instantiate SingleQuantile with better dependence on b, though the best-known constant factor of 1000 means it is not practical improvement.
The interior point algorithm may be used to answer threshold queries, which are queries of the form (x) a ._rankx x (z), with the following guarantee:
Lemma C.3. (Adaptive from Theorem 3.9 of (ITV): There exists an (s, algorithm which, with
probability B3 can answer any threshold queries (x(:) with error 0 log" (b) log( log
Using binary search, this algorithm may be used to answer any set of Q quantiles to within error O log" (b) log( 102
5n
D Better Computation of the Maximum Error for Continual Counting
In this section, we describe the procedure used to compute the maximum absolute error of the continual counting mechanism used in our experiments. The analysis relies on applying Chernoff bound to the mechanism and subsequently determining numerically the value that minimizes the error.
The mechanism under consideration is a variant of the approach developed in [4], which makes use of k-ary tree structure introduce correlated noise. Our modification lies in sampling the noise from a discrete Laplace distribution. Let & > O. the work in 4 provides guidelines for choosing l in order minimize the worst-case variance, and let T flog, (m + 1)] denote the depth of the tree.
The noise at each node of the tree is 7) DL(b) where 6 = The probability mass function of the discrete Laplace distribution given by
b blcl
Pr ly = x] Do
+
16

---

courding contribtiin
800
Mrsimum
000
400
10
10
10
Della (5)
The plot illustrates the minimum gap on the input ranks that is required to achieve (1, dd-differential privacy. Two distinct contributions are visible: the slice contribution and the continual counting contribution. The slice contribution corresponds the minimum slice size required to ensure that all SingleQuantile instances succeed with probability least 0.95. Importantly, this term is independent of 8. In contrast, the continual counting contribution grows as decreases. The computation considers 100 quantiles and add/remove privacy.
Figure 2:
Each continual counting noise Zi for i E [m], is the sum of at most T discrete Laplace noises. Using a Chernoff bound, we get for any A > 0
Pr||Z] 2 8] < 2e AE (o,))
where (A) is the moment generating function of 17 which sampled from DL( (sce [16]
(1 b)2
M2( (1 e1--->b)(( e^6)
By using union bound over mn continual counting noises we obtain
Pr
max iE
Z 2 3 S 2me N
Given O, finding (0, - log b) (so that the moment generating function is positive) such that minimum cannot be solved analytically. Our linear search uses 100 different À in [10-6, 6, logg()) 0.99] with an equal space and for each computes E())
E(A) log(2m/8 + T log (A))
the minimum error then released.
D.1 Relation Between d and Minimum Gap
To apply Sli lliieuuunniees it is necessary that the input ranks are "i....,T' E Good w--h- Thus, the minimum gap between ranks must be mingz; Ir. rry > 2(w + h). While can be computed using Theorem C.I is computed following the procedure illustrated in the previous section. Figure 2 shows the minimum gap required, 2(w + h), for different values of 6. The results consider the case of add/remove privacy, and m 100 (number of quantiles).
E Additional Experimental Material
In this section we give further experimental results. In Figure 3 the density and the cumulative distribution of the two datasets are depicted. The distributions are shown after data pre-processing, which accounts for data augmentation to increase the minimum gap among ranks, the insertion of low variance Gaussian noise to ensure uniqueness of the data points, and translation, thus the addition of i/n (where n is the size of the augmented dataset) to each point Z(z) so to guarantee that minzzj [c; - 2,5 2 1/n. This last features allows set g = 1/n when computing the slicing parameter using Theorem C.I
17

---

age data
working hours data
0.035
0.175
0,030
0.8
0.8
Cumulative Probabiltty
Cumulative Probability
Frequency (PDF)
0.025
Froquency (equencyy(P (PDF)
0.125
0.8
-0.6
0.015
0.075
0.4
0.010
0.050
0.0
0.000
0.000
20
40
80
20
40
100
age
working hours
Figure Histogram representation and cumulative distribution of AdultAge and Adul after pre- processing (data augmentation, Gaussian noise addition, translation).
As baseline, include the histogram density estimator algorithm, denoted Hist, introduced in [9]. This algorithm employs a differentially private estimate of the cumulative distribution function, obtained injecting Laplace noise into histogram representation of the dataset, to compute quantiles. Although the algorithm is conceptually simple, it requires the bin size to be determined in advance, which directly influences the utility of the resulting estimates. Given that the dataset bounds are known, achieving uniform bin sizes reduces to selecting the number of bins. In these experiments, we consider three configurations for the number of bins: 2 and N.
N.
We run the same experiments with additional privacy budget e 0.5 and ε = 5, to study the behavior in the small and high privacy regime. Figure depictt these experiments. showing that, if the data set is sufficiently large, SliceQuantiles achieves smaller error than AQ from [8]. In contrast, the performance of Hist varies depending on the chosen number of bins, yet it consistently exhibits an error that is approximately one order of magnitude higher.
18

---

StieQuendiees
Approsimate Quarties
Aporoximato Quardles Pure
Hist 1/10 N bins
Hist 1/2 bins
HisL biss
working hours
age
working hours
Max 10"
10"
Number Quandiles (m))
(a) Experiments with (0.5, 10 10-16)-DDD DDP for SliceQuantiles and AQ, while (0.5, D)DD for AQ with pure DP accounting and Hist. Such small privacy budget requires large minimum gap between ranks, thus, augmented the dataset 24 times obtaining 1172208 data points. Plots and b are for substitute adjacency, while e and correspond add/remove adjacency.
StieQvarrlee
Approsimate Quartiees
Aporoximate Quarties Pure
Hist 1/10 N bins
Hist 1/2 N aims
Hist N tins
working hours
age
working hours
Ennrr
hd"
Number Quantiles (m)
(b) Experiments with (1, 10 (1,10-10)-DP -DD for SliceQuantiles and AQ, while (1, 0)-DP for AQ with pure DP account- ing and Hist. For these privacy hudget we have to increase the dataset 12 times obtaining 586104 data points. Plots and b are for substitute adjacency, while and d correspond to add/remove adjacency.
SlccQuamiles
Approximate Guantiles
Aporoximate Quantles Pure
Hist 1/10 Nibins
Hist 1/2 bins
Hist bins
age
working hours
age
working hours
Max Enoor
150
60
160
200
Number Quandiles
(c) Experiments with (5, 10 1111-11---D- DD for SliceQuantiles and AQ, while (5, D)-D for AQ with pure DP account- ing and Hist. This privacy budget allows small minimum gap between ranks, thus, allowing us increase the dataset only 6 times obtaining 293052 data points. Plots and b are for substitute adjacency, while and d correspond to add/remove adjacency.
Figure 4: Comparison of SliceQuantiles, AQ and Hist.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We only mention claims and contributions in the abstract and introduction, which we prove or argue for in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss those limitations of our work that we are aware of in the introduc-
tion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
20

---

Answer: [Yes]
Justification: For each theoretical result (privacy and utility),, we provide proofs. They are partially in the appendix and correct to the best of our knowledge.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our experimental results can be reproduced by executing the code provided together with the submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
21

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the scripts we used run experiments and a README file describing how to run them.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
public/guides/ Soaadd/se//oeeSuumbaaiiiiooiooi
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/cccpublcccguuuddeeeoo Cotee//ddeeeSbmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide a paragraph for each experimental evaluation section, where describe the exact setting we are in.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The paper provides 95% confidence intervals for all experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
22

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments are not compute-intensive intensive and were run locally on a laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We believe that we conform with the NeurIPS Code of Ethics, as none of our work poses ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper presents foundational work whose goal to advance the field of Machine Learning. There many potential indirect societal consequences of work, none which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
23

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: In this work, we do not release any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The datasets used for the experiments in section 6 are properly referred to.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We do release any new assets in this work.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
25

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy hatt::///eeerrssssce////ffferers for what should or should not be described.
26


Reviews:
[{"review_id": "u8G3C8UwwH", "reviewer": "Reviewer_v3P9", "summary": "This paper proposes a novel differentially private algorithm for the quantile estimation problem, improving upon prior utility guarantees. Specifically, the authors reduce the approximation error from the previous $O(\\log(b)\\log^2(m)/\\epsilon)$ to $O((\\log(b)+\\log^2(m))/\\epsilon)$. However, to achieve this improvement, the algorithm additionally assumes that the queried quantiles satisfy a spacing condition:\n$|q_i-q_{i+1}|\\geq\\Omega(m\\log(m)\\log(b)/n\\epsilon)$. In the case of $(\\epsilon,\\delta)$-differential privacy, this constraint is relaxed to\n$|q_i-q_{i+1}|\\geq\\Omega(\\log(m)\\log(m/\\delta)+\\log(b)/n\\epsilon)$ while maintaining the same utility bound. The paper also presents experimental results on the AdultAge and AdultHours datasets, demonstrating improved performance over previous approaches.\n\nA key technical contribution is the use of a sliced quantile approach, in which the dataset is partitioned (via noisy boundaries) into disjoint slices, and a single-quantile mechanism is applied independently within each slice. The disjointness of slices enables strong utility guarantees through statistical independence.", "questions": "In the experiments section, could the authors provide a more detailed analysis of how the algorithm performs under varying values of the privacy parameters $\\epsilon$ and $\\delta$? This would help assess robustness across different privacy regimes.", "limitations": "This is a theoretical work, and I do not see any apparent negative societal impacts.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1.The paper is clearly structured and well written.\n\n2.The utility improvement from $O(\\log(b)\\log^2(m)/\\epsilon)$ to $O((\\log(b)+\\log^2(m))/\\epsilon)$ is substantial and well motivated.\n\n3.The theoretical analysis is sound.\n\n4.Experimental results show meaningful gains over existing methods.\n\nWeaknesses\n\n1.The core idea of slicing queries into independent subproblems is conceptually simple and may be seen as a straightforward extension.\n\n2.The spacing assumption imposed on the quantiles lacks sufficient justification or motivation, and its relationship to prior work is underexplored.", "was_revised": true, "final_justification": "The authors' detailed response answered my questions. Since my rating is positive, I will keep my rating.", "rebuttal": "Thanks for your questions and your consideration of our paper. We structured our rebuttal by first providing a common response, followed by answers to specific questions.\n\n## Common Response\n\n### Justification\nOur algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10\\%, 20\\%, ..., 90\\%). \nA particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section).  For approximate DP, our gap assumption is relatively mild, at $O(\\frac{1}{n \\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$---both terms are typically significantly less than $n$ in practice. \nFor equally-spaced quantiles, this means that $\\Omega(\\frac{n}{\\log n \\log(n/\\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\\varepsilon, b, m, \\delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\\frac{1}{n \\varepsilon} m \\log(b) \\log (m))$, but remains manageable as long as  $\\frac{m}{n} \\ll \\varepsilon \\log (b) \\log(m)$. This still permits answering $\\Omega(\\sqrt{\\frac{n \\varepsilon}{\\log(b) \\log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.\n\n### Comparison to prior work\n The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a $\\min(\\log^2(m), \\log(b))$ factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\\frac{1}{\\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$; this is still less than Kaplan (2022) when $\\frac{1}{\\delta} \\ll b$, usually the case for larger data domains.\nFor extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\\frac{1}{n \\varepsilon} \\log^*b \\log^2(\\frac{1}{\\delta})$. However, for domain sizes encountered in practice, the $\\log^2(\\frac{1}{\\delta})$ will likely outweigh this improvement. \nWe will add the above discussion in a revised version.\n\n## Answering Specific Questions\n> The core idea of slicing queries into independent subproblems is conceptually simple and may be seen as a straightforward extension.\n\nNote that the queries are *not* treated as independent subproblems, as this is not private (full discussion in Section 3.1). Instead, our algorithm adds correlated noise to shift each quantile, and the privacy analysis only goes through on this global structure.\n\n> The spacing assumption imposed on the quantiles lacks sufficient justification or motivation, and its relationship to prior work is underexplored.\n\nPlease refer to our common response for more discussion on this. We will add this clarification in a revised version.\n\n> In the experiments section, could the authors provide a more detailed analysis of how the algorithm performs under varying values of the privacy parameters  and ? This would help assess robustness across different privacy regimes.\n\n $\\delta$ does not affect the utility of the mechanism, but only the initial assumption, i.e. the smaller the $\\delta$ the larger the quantile gap must be. \nWe include some additional results for more values of $\\varepsilon$. The observation is similar to the results provided in the main paper – our algorithm outperforms Kaplan et al. by a factor 2 and a factor 1.3 under substitution privacy for $\\varepsilon = 0.5$ and $\\varepsilon= 5$, respectively."}, {"review_id": "3cjcuh4njz", "reviewer": "Reviewer_Ky2d", "summary": "This paper improved error bound in the problem of estimating multiple quantiles of a dataset under DP over prior methods. The authors introduce the SliceQuantiles mechanism, which offers both pure ε-DP and approximate (ε, δ)-DP guarantees. Their central innovation lies in leveraging continual counting techniques to inject correlated noise into the rank estimates of quantiles, enabling more efficient privacy composition.", "questions": "Could the authors provide a clearer and earlier definition of what constitutes a \"slice\" and explain explicitly why a slice corresponds to a subproblem in their framework?\n\nThe proposed setting relies on a minimal gap between quantiles, but verifying that this condition holds may be non-trivial. Can the authors provide guidance or practical procedures for how one might check or enforce this minimal gap in realistic applications? Also, what is the motivation behind the rank error metric?\n\nThe performance deteriorates for larger $b$ and depend on minimal gap. How does $b$ and gap interacts? It appear to me that a larger minimal gap leads to a larger $b$.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\nThe paper presents a theoretically sound improvement over prior work, eliminating a factor in the error bound.\n\nThe use of continual counting for quantile estimation is original in this context.\n\nWeaknesses:\n\nThis paper is difficult to follow and understand in several key aspects. For example, the concept of a \"slice\" is introduced at line 75 as “m subproblems, referred to as ‘slices’.” This term is referenced multiple times before line 124, where it is only hinted that a slice contains a subset of the dataset $X$. A more concrete definition appears at line 130, where a slice is described as some subset of $X$ determined by a sufficiently large $h$; however, it is not made clear what constitutes a \"sufficiently large\" $h$. From that point onward, slices are treated as subsets of $X$ in various contexts, but it remains unclear why a slice corresponds to a subproblem in the proposed methodology.\n\nAdditionally, in line 185, the Technical Challenge section attempts to explain the difficulty of establishing the differential privacy condition by describing a failed approach. However, the exposition of this failed attempt is unclear, and it does not effectively elucidate the core technical challenge faced by the authors.\n\nWhile supported by prior literature, the problem formulation appears artificial and narrow. The paper focuses on controlling the rank error under the condition that queried quantiles are separated by a minimal gap. Although it is reasonable that rank error becomes unavoidable when quantiles are too close, the authors do not provide sufficient justification for the practical relevance of this setting, especially given that verifying the minimal quantile gap condition may be non-trivial in practice which narrow down the applications by a lot.", "was_revised": true, "final_justification": "The authors have clarified the connection of this work with prior work and have addressed the assumption regarding the minimum gap. The main concern remains the clarity of the presentation and the lack of clearer definitions for key concepts (e.g., “slices”). I assume these issues can be addressed in the final version.", "rebuttal": "Thanks for your questions and your consideration of our paper. We structured our rebuttal by first providing a common response, followed by answers to specific questions.\n\n## Common Response\n\n### Justification\nOur algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10\\%, 20\\%, ..., 90\\%). \nA particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section).  For approximate DP, our gap assumption is relatively mild, at $O(\\frac{1}{n \\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$---both terms are typically significantly less than $n$ in practice. \nFor equally-spaced quantiles, this means that $\\Omega(\\frac{n}{\\log n \\log(n/\\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\\varepsilon, b, m, \\delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\\frac{1}{n \\varepsilon} m \\log(b) \\log (m))$, but remains manageable as long as  $\\frac{m}{n} \\ll \\varepsilon \\log (b) \\log(m)$. This still permits answering $\\Omega(\\sqrt{\\frac{n \\varepsilon}{\\log(b) \\log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.\n\n### Comparison to prior work\n The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a \\min\\{log^2(m), \\log(b)\\} factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\\frac{1}{\\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$; this is still less than Kaplan (2022) when $\\frac{1}{\\delta} \\ll b$, usually the case for larger data domains.\nFor extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\\frac{1}{n \\varepsilon} \\log^*b \\log^2(\\frac{1}{\\delta})$. However, for domain sizes encountered in practice, the $\\log^2(\\frac{1}{\\delta})$ will likely outweigh this improvement. \nWe will add the above discussion in a revised version.\n\n## Answering Specific Questions\n> the Technical Challenge section attempts to explain the difficulty of establishing the differential privacy condition by describing a failed approach. However, the exposition of this failed attempt is unclear, and it does not effectively elucidate the core technical challenge faced by the authors.\n\n Briefly, our algorithm works by sorting the dataset and taking a contiguous subset of data around the desired quantile. We refer to each contiguous subset of data as a “slice”, and this is what is used to form a private estimate of the quantile. The intuition behind this approach is that the data points that are closest to the queried quantile should be used to privately estimate the quantile as accurately as possible.\n\nThe technical challenge of this approach is that, perhaps surprisingly, the above procedure is not private because modifying one data point can modify the data contained in many slices (see lines 126-134 for an example). To circumvent this issue, we add correlated noise to each quantile before forming the slices which has the effect of *hiding* the modifications created in all the slices by the change in a single data point. We will clarify this in a revised version.\n\n> Could the authors provide a clearer and earlier definition of what constitutes a \"slice\" and explain explicitly why a slice corresponds to a subproblem in their framework?\n\nIn summary, a part of the definition can be found in line 124 where we say that a slice is “a contiguous subsequence of the sorted input data”. Additionally, the slice must be centered on a specific rank. We will make sure to introduce this concept earlier in the paper and to define it properly.\n\n> The proposed setting relies on a minimal gap between quantiles, but verifying that this condition holds may be non-trivial. Can the authors provide guidance or practical procedures for how one might check or enforce this minimal gap in realistic applications? Also, what is the motivation behind the rank error metric?\n\nWe stress that the minimal gap assumption is an assumption about the quantiles being queried and can be easily checked by computing the differences between consecutive quantiles (which is publicly known). In particular, it does not rely on any assumption about the data. See the common response for a discussion of the gap assumption.\nThe rank error metric is natural since it measures how far off an approximate quantile is from having the desired number of data points on each side. We note that under differential privacy it is impossible in general to achieve approximation of the value of a quantile because the value does not have small sensitivity. However, assuming that the data distribution is reasonably smooth, a small rank error implies a small error in value, too. For these reasons, rank error is the most common error measure for private quantile estimates and is the standard metric used in existing literature, e.g:\n\n*Gillenwater, Jennifer et al. “Differentially Private Quantiles.” ArXiv abs/2102.08244 (2021): n. pag.*\n\n*Kaplan, H., Schnapp, S. &amp; Stemmer, U.. (2022). Differentially Private Approximate Quantiles. Proceedings of the 39th International Conference on Machine Learning.*\n\n*Bassily, Raef, and Adam Smith. \"Local, private, efficient protocols for succinct histograms.\" Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015.*\n\n> The performance deteriorates for larger $b$  and depend on minimal gap. How does $b$ and gap interacts? It appear to me that a larger minimal gap leads to a larger $b$.\n\nExisting lower bounds show that the rank error must grow with $b$, both under pure and approximate differential privacy. The gap we need between quantiles is proportional to $\\log(b)$. Since the gap is inversely proportional to the number of data points $n$, the value of $n$ needed to answer a given set of quantile queries grows proportionally with $\\log(b)$."}, {"review_id": "LvB9Xe6vFL", "reviewer": "Reviewer_SjbT", "summary": "This paper introduces SliceQuantiles, a new mechanism for privacy preserving quantile approximation. While the existing works, in $\\epsilon$ $\\delta$ DP are optimal in logb, the proposed method improves over the state-of-the-art in reducing the complexity of $\\delta$ term (error independent of $\\delta$). In pure DP setting, the proposed method saves min(logb, log^2m) factor. The improvement is achieved by combining continual counting techniques with the exponential mechanism. Using Adult data set, the authors demonstrate that the proposed SliceQuantiles outperform AQ.", "questions": "Please see W1 - W3", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "S1.  The use of continual counting to correlate quantile noise is clever. The main idea is sound and clearly presented.\n\nS2. The paper provides rigorous theoretical proofs for both privacy and utility guarantees under add/remove model for approximate/pure DP. (Didn't check the proofs in detail)\n\nS3. Using scaled Adult dataset, authors demonstrated the high accuracy of the proposed algorithm. \n\nW1. For clarity: please consider to i) add input dataset in algorithm 1, ii) add ticks in Figure 1, iii) compare with AppindExp (reference 12), and iv) include approximate quantile literatures in the streaming model such as `Differentially private linear sketches: Efficient implementations and applications`, `Improved utility analysis of private countsketch`, and `Bounded space differentially private quantiles`.\n\nW2. Need more discussions or experiment on the query time complexity (perhaps appendix).\n\nW3. What happens to the utility guarantee under substitute model?", "was_revised": true, "final_justification": "Having reviewed the authors’ response for all reviewers, I have decided to maintain my positive score.", "rebuttal": "Thanks for your interest in our paper! We would like to answer your specific questions.\n\n> For clarity: please consider to i) add input dataset in algorithm 1, ii) add ticks in Figure 1, iii) compare with AppindExp (reference 12), and iv) include approximate quantile literatures in the streaming model such as Differentially private linear sketches: Efficient implementations and applications, Improved utility analysis of private countsketch, and Bounded space differentially private quantiles.\n\nThanks for this suggestion and we will incorporate them in the revised version. We chose to compare with Kaplan et al as our baseline since it is the state-of-the-art private quantile estimation algorithm in the central model and outperforms [12] (as validated via experiments in their paper).\n\n> Need more discussions or experiment on the query time complexity (perhaps appendix).\n\nThe running time of the algorithm is $O(n \\log n)$, it is dominated by the time taken to sort the dataset. Experimentally, we were able to run our algorithm with 200 quantiles and 500,000 data points in under a second.\n\n> What happens to the utility guarantee under substitute model?\n\nAs the utility of our algorithm does not depend on $\\delta$, the utility guarantee under substitution analysis is affected only by a factor of 2 in the privacy budget $\\varepsilon$ (Corollary 5.2, 5.3 with privacy budget given in Corollary 4.4)."}, {"review_id": "ySHXqjQkNY", "reviewer": "Reviewer_TKv1", "summary": "The paper presents a novel mechanism for computing approximate quantiles under $\\epsilon$-differential privacy (DP) and $(\\epsilon, \\delta)$-DP, achieving improved error bounds compared to prior work, notably Kaplan et al. (ICML '22). The authors leverage continual counting techniques to reduce the maximum rank error, particularly when the number of quantiles $m$ is large. The paper also includes experimental validation, showing practical improvements.", "questions": "1. Minimum Gap Requirement:\n   The minimum gap assumption, $\\left|q_i - q_{i-1}\\right| \\geq \\Omega\\left(\\frac{m \\log(m) \\log(b)}{n \\varepsilon}\\right)$, is a critical condition for the $\\varepsilon$-DP mechanism but differs in nature from Kaplan et al.'s requirement, which pertains to the spacing of data points. Here, the constraint is on the quantiles’ orders, which may limit applicability in certain scenarios. Could the authors elaborate on the implications of this assumption compared to Kaplan et al.'s, particularly regarding its impact on practical settings and datasets where quantiles may be closely spaced?\n\n2. Clarity of Presentation:\n   The exposition of the proposed solution could be improved for better accessibility. I suggest adding a sentence clarifying that, under suitable assumptions, $x_{(nq_i)}$ can be approximated by applying a location algorithm (e.g., a private median algorithm) to a subset of points around the quantile. The approach can be described as decoupling into two steps: (1) splitting the dataset into disjoint subsets around the quantiles using private continual counting algorithms, and (2) applying a location algorithm to each subset. This would provide a clearer high-level intuition for the SliceQuantiles algorithm.\n\n3. Potential Bias in Location Algorithm:\n   The method relies on estimating the location of data slices around quantiles. If the location algorithm used in SingleQuantile is not a median estimator (e.g., a mean estimator), this could introduce bias in the quantile estimates, unlike Kaplan et al.'s approach, which may be more robust in certain cases. Could the authors comment on whether this is a concern and how the choice of location algorithm affects bias, particularly for non-median estimators?\n\n4. Empirical CDF/Quantile Function Plots:\n   To better understand the practical improvements and potential biases, I recommend including plots of the empirical cumulative distribution functions or quantile functions for the datasets used in the experiments. These plots would help readers assess the distributions where the proposed method outperforms Kaplan et al. and whether the generic location algorithm in the $(\\varepsilon, \\delta)$-DP setting introduces bias, especially when the quantile function has high curvature.\n\n5. Literature:\n   The paper references Lalanne et al. (2023), noting that their algorithm relies on strong smoothness assumptions for randomized quantiles. I believe this refers to their histogram estimator for density, used as a plug-in for the quantile function. While Lalanne et al.'s approach requires regularity assumptions, the current paper assumes a minimum gap of 1 between data points, which is a form of regularity under which it should be possible to study histogram estimators. I suggest including a naive baseline similar to Lalanne et al.'s histogram estimator in the experiments, acknowledging the challenge of choosing the bandwidth parameter. This would provide a more comprehensive comparison and highlight the trade-offs of different assumptions.\n\n6. Notation and Clarity Issues:\n   - In line 124, the ordered statistics notation ($x_{(i)}$) is used without prior introduction, which could confuse readers unfamiliar with the convention. I recommend defining this notation explicitly.\n   - In Equation (1), the use of $d$ for a quantity in $\\{-1, 1\\}$ is potentially misleading, as $d$ is commonly used to denote dimension. Consider using a different symbol to avoid confusion.\n   - In Lemma 3.1, the equation appears to have a typo: it should likely be $\\Pr[\\mathrm{CC}(\\mathbf{r}) = \\tilde{\\mathbf{r}}] \\leq e^\\varepsilon \\Pr[\\mathrm{CC}(\\mathbf{r} + \\mathbf{e}) = \\tilde{\\mathbf{r}}]$ instead of comparing $\\mathrm{CC}(\\mathbf{r})$ to itself. Additionally, in the following line, $\\tilde{\\mathbf{r}}$ should be replaced with $\\mathrm{CC}(\\mathbf{r})$ for consistency.\n   - In lines 154–156, the bounds for applying SingleQuantile are unclear. Initially, it seems the algorithm uses the upper and lower data points as interval bounds, which could raise privacy concerns. However, it later appears that the bounds are the entire base interval $(a, b)$. Clarifying this and discussing how the domain reduction strategy compares to Kaplan et al.'s tree-based approach would improve understanding.\n   - In Lemma 4.1, the use of $F^+$ and $F^-$ for the rectifying functions is confusing, as these symbols are often associated with CDFs or quantile functions in this context. Consider alternative notation to avoid ambiguity.\n\n7. Scalability and Limitations:\n   The minimum gap requirement scaling as $\\frac{m}{n \\varepsilon}$ for $\\varepsilon$-DP makes the results less applicable in the high-quantiles regime. For $(\\varepsilon, \\delta)$-DP, the linear scaling of $\\delta$ with $m$ int the $\\delta$ part might be concerning, and the claim of utility bounds being independent of $\\delta$ suggests this dependence may be hidden in the gap assumptions. Could the authors clarify how this dependence is managed and discuss the practicality of the gap assumptions in high-quantiles scenarios?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Improved Error Bounds: The proposed mechanism achieves a maximum rank error of $O\\left(\\frac{\\log(b) + \\log^2(m)}{\\epsilon}\\right)$ for $\\epsilon$-DP, improving over Kaplan et al.'s $O\\left(\\frac{\\log(b)\\log^2(m)}{\\epsilon}\\right)$ by a factor of $\\Omega\\left(\\min(\\log(b), \\log^2(m))\\right)$. This is a meaningful theoretical advancement, especially for large $m$.\n- Novel Approach: The use of continual counting to randomize quantiles in a correlated manner is innovative and distinguishes this work from prior divide-and-conquer strategies.\n- Experimental Validation: The experiments confirm the theoretical improvements, showing a factor of 2 improvement in accuracy over Kaplan et al. when estimating 200 quantiles with $\\epsilon=1$ and $\\delta=10^{-16}$ under substitute adjacency.\n- $(\\epsilon, \\delta)$-DP Mechanism: The relaxation of the gap assumption in the $(\\epsilon, \\delta)$-DP mechanism, with error independent of $\\delta$, is a notable contribution, particularly when $\\delta$ is small. I have questions on this part that are detailed below.\n\nWeaknesses:\nSee my questions below.", "was_revised": true, "final_justification": "After reading the author’s response, I’ve decided to keep my positive rating of the article.", "rebuttal": "Thanks for your questions and your valuable feedback. We structured our rebuttal by first providing a common response, followed by answers to specific questions.\n\n## Common Response\n\n### Justification\nOur algorithms are designed to produce very accurate estimates for $m$ input quantiles, where $m$ is sufficiently small compared to $n$. This setting is practical and common—data analysts often care about a limited number of summary statistics (e.g., 10\\%, 20\\%, ..., 90\\%). \nA particularly important case is when the quantiles are equally spaced, which is closely tied to the problem of CDF estimation, the subject of a long line of research (see related work section).  For approximate DP, our gap assumption is relatively mild, at $O(\\frac{1}{n \\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$---both terms are typically significantly less than $n$ in practice. \nFor equally-spaced quantiles, this means that $\\Omega(\\frac{n}{\\log n \\log(n/\\delta)})$ quantiles can be answered. For example, with $n = 500,000$ and reasonable choices of $\\varepsilon, b, m, \\delta$, this gap assumption worked out to less than 0.005 in our experiments, meaning that up to 200 equally-spaced quantiles could be answered. For pure DP, our gap assumption grows slightly as $O(\\frac{1}{n \\varepsilon} m \\log(b) \\log (m))$, but remains manageable as long as  $\\frac{m}{n} \\ll \\varepsilon \\log (b) \\log(m)$. This still permits answering $\\Omega(\\sqrt{\\frac{n \\varepsilon}{\\log(b) \\log(n)}})$ equally-spaced quantiles. Finally, note that our gap assumption can be eliminated altogether by merging overly close quantiles into a single representative quantile; this will then add the required gap to the error instead.\n\n### Comparison to prior work\n The main comparison algorithms are that of Kaplan (2022) and Cohen (2023). For data domains which are not extremely large (such as $b = 2^{64})$, the algorithm of Kaplan (2022) is the prior state-of-the-art: it satisfies pure DP and makes no assumption on the quantile gap. However, if the quantiles have the spacing of the prior paragraph (for pure DP), then our algorithm enjoys lower error by a \\min\\{log^2(m), \\log(b)\\} factor. If one is willing to relax to approximate DP, our algorithm still has the lower error, and the gap assumption is significantly reduced. By combining quantiles, the gap assumption can be eliminated entirely, and the error will be $O(\\frac{1}{\\varepsilon}(\\log(b) + \\log(m) \\log \\frac{m}{\\delta}))$; this is still less than Kaplan (2022) when $\\frac{1}{\\delta} \\ll b$, usually the case for larger data domains.\nFor extremely large data domains, the algorithm of Cohen (2023) can start to outperform our algorithm using more advanced techniques than the exponential mechanism. Specifically, their algorithm can be used to answer any quantiles with error $\\frac{1}{n \\varepsilon} \\log^*b \\log^2(\\frac{1}{\\delta})$. However, for domain sizes encountered in practice, the $\\log^2(\\frac{1}{\\delta})$ will likely outweigh this improvement. \nWe will add the above discussion in a revised version.\n\n## Answering Specific Questions\n> 1. Minimum Gap Requirement: ...\n\nWe stress that our gap quantile assumption refers to spacing between the input (queried) quantiles, and does not refer to any part of the data itself. Kaplan et al. make an assumption that each point in the dataset itself is separated from the others by a small gap, and enforce this in practice by adding a small amount of random noise to each point. We also do this. For a full discussion of our quantile gap assumption, see the common response.\n\n> 2. Clarity of Presentation: ...\n\nWe thank the reviewer for the suggestion and we agree that this approach will enhance the intuition around our algorithm. We will clarify this in a revised version.  \n\n> 3. Potential Bias in Location Algorithm: ...\n\nThe location algorithm can be thought of as an *interior point* algorithm which aims at returning any data point inside a given range. Any pure DP interior point algorithm can be used as a building block of SliceQuantiles. However, it is necessary to carefully compute the length $2h$ of the slices so that no interior points algorithm fails. The choice of using the exponential mechanism to estimate the median of each slice was driven by two factors: it matches in utility a lower bound of $\\Omega(\\log b)$ for the interior problem under pure DP [1], and it solves it with high probability thus allowing to set $h = \\Omega(\\log(b) + \\log(m))$. Nevertheless, any pure DP interior point mechanism that achieves rank error $O(h)$ with high probability in $m$ can be used.\n\n[1]: *Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions.*\n\n> 4. Empirical CDF/Quantile Function Plots: ...\n\nWe agree that adding plots of the dataset CDFs will be interesting to include. While our theoretical analysis applies to any interior point algorithm, experimentally we always apply the exponential mechanism, even for approximate DP; thus, we do not expect a significant difference in the empirical bias of our algorithm vs. that of Kaplan et al. We will consider adding plots of this in a later version.\n\n> 5. Literature: ...\n\nThank you for raising these points, which we will discuss more thoroughly in the revision. As pointed out earlier, our gap assumption is an assumption about the query, not the data. The assumption of having a minimum gap of 1 in the data is made for simplicity and convenience to be able to state clear results that are directly comparable between the cases of discrete and continuous domains. The assumption can be enforced whp. by scaling the data and adding random noise to data values, but this makes the utility guarantee more complicated to state.\n\nConcerning a comparison to Lalanne et al. (2023) we agree that it would be a good idea to include it as a baseline. Theoretically speaking, their method is vulnerable to situations in which the distribution of values is concentrated (or concentrated around a few values) in which case even the non-private histogram may not contain enough information to output good quantile estimates.\n\n> 6. Notation and Clarity Issues:\n\nThank you for pointing out these issues, we will make sure to fix them.\n\n\n> 7. Scalability and Limitations:\n\nWe show that approximate DP allows us to achieve the same error as we were able to show for pure DP with a weaker gap assumption than was required for pure DP, since the quantile gap requirement scales with $\\log(m/\\delta)$. Therefore, increasing $\\delta$ will decrease the quantile gap required for good utility and make our results more applicable in higher-quantile regimes. It is correct that the utility bounds are independent of $\\delta$, and $\\delta$ only affects the gap assumption. See our common response for a full discussion of this interaction."}]

Author rebuttal:

Meta-review: The paper provides new pure and approximate DP versions of a new method for estimating multiple quantiles by applying techniques from the continual counting literature. 

Reviewers appreciated the novelty of the paper's methods and improved error guarantees. The most pressing recurring concern was over clarity, though this was at least partially addressed through author-reviewer discussions. The authors should make sure to revisit these discussions and use them to clarify the final version of the paper.
Decision: Accept (poster)