Lightweight Protocols for Distributed Private Quantile Estimation
Authors: Anders Aamand
Fabrizio Boninsegna
Abigail Gentle
Jacob Imola
Rasmus Pagh
Venue: ICML 2025 spotlightposter (2025)
Keywords: local differential privacy
adaptive algorithms
quantiles
shuffle model
Primary area: social_aspects->privacy
TL;DR: By using a private noisy binary search, we achieve quantile estimates under local differential privacy using a number of users that grows with the log of the domain size whereas prior non-adaptive methods use a larger (log-squared) number of users.

Abstract: Distributed data analysis is a large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. 
We consider two \emph{adaptive} algorithms for estimating one quantile (e.g.~the median) when each user holds a single data point lying in a domain $[B]$ that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle-DP). 
In the adaptive setting we present an $\varepsilon$-LDP algorithm which can estimate any quantile within error $\alpha$ only requiring $O(\frac{\log B}{\varepsilon^2\alpha^2})$ users, and an $(\varepsilon,\delta)$-shuffle DP algorithm requiring only $\widetilde{O}((\frac{1}{\varepsilon^2}+\frac{1}{\alpha^2})\log B)$ users. Prior (nonadaptive) algorithms require more users by several logarithmic factors in $B$. We further provide a matching lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-$\varepsilon$ regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.

Lightweight Protocols for Distributed Private Quantile Estimation
Anders Aamand Fabrizio Boninsegna 2
A Abigail Gentle Jacob Imola' Rasmus Pagh
Abstract
leading approach federated computations with formal pri- vacy guarantees is to use differential privacy (DP) (Dwork et al., 2006) which limits the amount of information that can be inferred about a given user's 's input by selecting the output from a suitable probability distribution defined by the inputs. A particularly simple and appealing setup is local differential privacy (LDP), in which each user individ- ually sends the output of a differentially private algorithm to central "analyzer", who in turn uses all the user out- puts to approximate function of the inputs. Though LDP is not the only approach to federated computations with differential privacy, it has been influential. For example, LDP has been used in industrial deployments of differen- tial privacy (Cormode et al., 2018; Erlingsson et al., 2014; Differential Privacy Team, 2017), and there a rich theory showing both upper and lower bounds the privacy-utility trade-offs that are possible under LDP. When giving pri- vacy guarantees under LDP it is common to consider pure differential privacy since it is known that any non-adaptive protocol satisfying approximate differential privacy can be converted into an equivalent one satisfying pure differential privacy (Bun et al., 2019). An interesting aspect of LDP algorithms is that they can be used as building blocks of more sophisticated algorithms offering better privacy utility trade-offs (with stronger trust assumptions), for example in the shuffle model (Bittau et al., 2017; Cheu et al., 2018; Erlingsson et al., 2019).
Distributed data analysis is large and growing field driven by a massive proliferation of user devices, and by privacy concerns surrounding the centralised storage of data. We consider two adaptive algorithms for estimating one quantile (e.g. the median) when each user holds a sin- gle data point lying in a domain [B] that can be queried once through a private mechanism; one under local differential privacy (LDP) and another for shuffle differential privacy (shuffle- DP). In the adaptive setting we present an s- LDP algorithm which can estimate any quan- tile within error a only requiring ( and an (c, 8)-shuffle DP algorithm requiring only Ō( + + log B) users. Prior (nonadaptive) algorithms require more users by several logarith- mic factors in B. We further provide a match- ing lower bound for adaptive protocols, showing that our LDP algorithm is optimal in the low-z regime. Additionally, we establish lower bounds against non-adaptive protocols which paired with our understanding of the adaptive case, proves a fundamental separation between these models.
log B cta' users,
1. Introduction
Quantile Estimation In this paper we study the problem of quantile estimation under local differential privacy con- straints. Specifically, we consider the setting of dataset X of datapoints æ Fr [B] == {1, .1. B), where B is an integer parameter. We note that some works on quantile esti estimation consider another setting where the input points are real numbers, e.g., from [0, 1]. but this requires assump- tions on the data distribution - in Appendix H, we will discuss how our algorithms can be brought to work in the continuous setting under mild assumptions on the distribu- tion of the input data. Given the dataset X, we define the empirical CDF Fx
A strong trend in recent years has been towards federated computations (Kairouz et al., 2021) in which algorithms are run on a distributed dataset rather than by collecting data and performing the computation in a centralized manner. This trend is motivated by the wish to protect individuals' data, as well organizations' wish steer clear of liability issues stemming from collecting and handling private data. The
'BARC and Department of Computer Science, Univer- sity of Copenhagen. Denmark 'Department of Information En- gineering, University of Padova, Italy 'School of Computer Science, University of Sydney. Australia. Correspondence to: Anders Aamand <aa@ ku.ku, Abigail Gentle <abi- gwwtleeesddneyy...ee.
[B] - [0, 1] by
Jacob Imola <jaim @ di ku. Fabrizio Boninsegna <fabrizio. <fabrizio.boninsegnn. @
(i) = 1 e [m]
22 S i1}
(I)
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
that is, Fx (i) is the fraction of elements in the dataset that are smaller than or equal to i. Given g E (0,1) we would

---

Lightweight Protocols for Distributed Private Quantile Estimation
ideally like to output an approximate gth quantile of the dataset, that is, value m [B] such that Fx (m) is approx- imately equal to g. Such value may not always exist, for example if all 24 are equal. Instead, we measure the approx- imation guarantee in terms of a parameter a E (0, 1) and we are happy to report a value m such that q is contained in the interval [Fx (m) - a, (m(m= + 1) + a).
The algorithm queries one user at time (so each |4|] = 1) and proceeds for n rounds. In terms of communication and run time, our algorithm is efficient: each user communi- cates just 1 bit to the server, and each round has update time Ollog B). In addition, we show that the error of our pro- tocol is optimal up to constant factors under (sequentially- adaptive) LDP:
Theorem 1.2. Suppose that B is sufficiently large, S 2' and E < 1. Any sequentially adaptive LDP protocol solving 1.DPemp-med an [=:)]=; with probability at least 3/4 for any dataset of size n Z nn must have log B
Adaptive Local Differential Privacy In this paper we consider LDP algorithms that work in rounds, making adap- tive choices of what information should be released in each round. An adaptive LDP protocol involves n users indexed by ,,....,,,,, n, with user i holding data item I,, and an aggregator that coordinates the protocol. In round / the aggregator queries a set 4 S {I....,,I n of one or more users, asking them to run a differrntiallyy private mechanism Mr on their data. The output of M2(2;) is then sent to the aggregator for each E 1.. Protocols in this model can be adaptive in the sense that the choice of mechanism M, can depend
1
no 2 E²
Remark: The above theorem is stated for the median, but as we will see, the same lower bound holds for estimating any quantile q E (2a, 1 2a.). Note that for S or M 1 - a. there is trivial protocol that outputs either or B. Combined with the above observation for reduc- ing a general quantile to the median, our results therefore show that O log B is essentially the correct bound for quan- tile estimation under aqquentially-ddapiiv LDP in the high privacy regime.
the results of mechanisms in rounds 1....,t - 1. We consider sequentially adaptive protocols in which the query sets 11 I2.... are disjoint, such that the privacy guarantee for each user is simply determined by the privacy guarantee of the mechanism that was used for the LDP report on their data (if any). In contrast non-adaptive LDP protocols can be run in a single round. The private mechanism M, is predetermined and does not depend the outputs of M M,-1. It is often the case that all Mr are the same. Adaptive mechanisms often offer much improved utility/privacy tradeoffs compared to their non- adaptive counterparts (Acharya et al., 2022; Joseph et al., 2020) but they are harder to coordinate and thus less desir- able from a practical perspective.
Non-Adaptive Protocols Theorems 1.1 and 1.2 settle the optimal privacy/utility tradeoffs for adaptive LDP protocols in the high privacy regime. As we will discuss in Section 1.1, all non-adaptive mechanisms that we are aware of require polylog( (B) factor more users to solve LDP DDPemp-mede an, which can be significant as B is typically a large parameter such as 2d2, Our privacy/utilitty tradeoff in the adaptive case is therefore much better than for known non- adaptive pro- tocols, but as discussed, non-adaptive protocols are more practically appealing. A natural question is thus if the gap is inherent. We settle this question in the positive essen- tially showing that any non-adaptive protocol must incur an additional logarithmic factor in B in the number of users required for desired accuracy. Thus, non-adaptivity, while practically desirable, comes at a significant price in utility. Our result is as follows.
For quantile estimation, each user holds the datapoint r; E [B] and our goal is to estimate quantile, with error described as above, such that M₁ satisfies LDP. It is not hard to see that an algorithm for estimating the median, that is = 1/2, can be used to estimate any quantile of the dataset with only a constant factor increase of the approxi- mation guarantee. This is because we can reduce the general case to the median by introducing n additional, virtual users holding data, (1 9)n users each holding the value 1 and q users holding the value B (see Lemma B.1). Thus, for our algorithm we focus on estimating the median. We refer to this problem with desired accuracy a and LDP privacy parameter ε as LDPemp- i ( &x (see Sec- tion 2 for the formal definition). We derive a sequentially adaptive algorithm with the following guarantee:
Theorem 1.3. Suppose B is sufficiently large, B B-Q() < a S for a universal constant c, and & I log(i/a) Sup- pose that there exists a non-adaptive s-LDP algorithm solving
a,5) with probabil- ity at least 3 for any dataset of size n 2 nn- Then (o)
no = log(1/a)
Theorem 1.1. For all a E (0, }), and E 10, there exists a sequentially adaptive E-LDP protocol solving SePemp-meddannf ( a,E) with probability at least 1- 1
In particular, when a (1), the number of users must be M(lgg" B) whereas our previous theorems show that Oloo B) suffices for adaptive protocols. The authors be- lieve that the high logarithmic dependence on 1/a is an artifact of the proof.
B for any dataset with n 2 caa for a universal constant e.
B
2

---

Lightweight Protocols for Distributed Private Quantile Estimation
The Shuffle Model Shuffle differential privacy (shuffle- DP) (Bittau et al., 2017; Cheu et al., 2019) captures the idea that using a random permutation to shuffle large enough set of somewhat private user messages, thus making their origins indistinguishable, boosts the privacy guarantee for each user. More precisely, in shuffle-DP, each user applies a LDP protocol to their data and then sends the output to a trusted shuffler whose only task is to randomly permute the users data before forwarding it to a central data curator. The privacy boost achieved from shuffling was analysed in (Feld- man et al., 2021) (see Theorem G.4). To gain the privacy boost, the batch of users shuffled can not be too small. This makes fundamentally incompatible with highly adaptive protocols having n rounds of adaptivity, and each batch of size one. To bypass this, we consider protocols which run in bounded number of rounds, shuffling the users queried in each round, simultaneously obtaining both the benefits of adaptivity and the boosted privacy from shuffling.
1.1. Related Work
Differential Privacy Differential privacy is considered the gold standard in private data analysis due to its rigorous guar- antees, e.g., immunity to side information, and other useful properties (Dwork et al., 2006; Dwork & Roth, 2014). A number of mechanisms exist for releasing medians and gen- cral quantiles for centralized DP. First, one may instantiate mechanisms based on local sensitivity (Nissim et al., 2007; Dwork & Lei, 2009; Asi & Duchi, 2020). since quantiles often have low local sensitivity for many datasets. More re- cently, specialized mechanisms for medians (Tzamos et al., 2020; Drechsler et al., 2022; Aliakbarpour et al., 2024) and quantiles (Wilson et al., 2020; Gillenwater et al., 2021; Al- abi et al., 2023) have been proposed to obtain even lower error but they require certain mild assumptions on the dis- tribution of the data points. The case where data points can be arbitrary from some discrete domain [B], like for us, has been well studied in the central setting. The sequence of works, (Beimel et al., 2016; Bun et al., 2015; Kaplan et al., 2020; Cohen et al.. 2023) gradually reduced the number of users needed for accuracy a to Ô ( (1e log" (B) log (1/5) for (e, 8)-privacy. This almost matches the the 2 (B)) lower bound from (Alon et al., 2019). A corollary of this lower bound is that even with central DP, no algorithm can achieve (11) quantile error in the continuous setting regard- less of how many users there are.
We refer to the problem of estimating the median of n users within accuracy a using r adaptive rounds of shuffling under an (fxx) (a 0,,,,,,,, e, 6, r) (see Section 2 for formal definition). We provide protocol for this problem with r loga B and
(e, 5)-DP as feeuffllee----ee
(log B)- 0 (2= + )²)
Theorem 1.4. Letr log, B and a, a, < 1. There exists protocol for shuffle e-pp medi an(( a, e, d.r) in the sequentially interactive model which requires
Local Differential Privacy There is increasing interest in local differential privacy (LDP), where the central aggrega- tor is not trusted, and each user applies a DP mechanism to their data before broadcasting it. LDP mechanisms for many problems and accompanying lower bounds were shown in (Duchi et al., 2013). A ubiquitous LDP protocol that we will utilize is randomized response (See Lemma A. I), where answers a binary query are flipped with probability T=e7 R 1 E. For the median problem, an LDP algo- rithm was found in (Duchi al., 2018) under different loss function, the difference between the estimate and the median in the data domain. This loss function is subject to strong lower bounds (a linear dependence on the domain size). The most relevant work to our setting is the so-called hierarchical mechanism (Cormode et al., 2019).
1 2 )
n == ((
log B log(110) log log B 8
users, and succeeds with probability 1 - B. The protocol queries shuffled batches of n/ (og2(B) users.
We believe that the framework of combining shuffling with rounds of adaptivity might be of interest for many other problems. On the one hand, we could use non-adaptive protocol with shufffing, getting better dependence on e and o, but this would incur additional logarithmic factors in B. On the other hand, we could use sequentially adaptive algorithm like in Theorem 1.1, but then we lose the bene- fits of shuffling since each batch has size 1. Theorem 1.4 demonstrates that protocols having several adaptive rounds using shuffling of each batch, can provide the best of both worlds.
Hierarchical Mechanism The hierarchical mechanism uses the b-adic decomposition of the interval [o, B] (which is a b-ary tree of depth O(log,()) whose nodes at level correspond to intervals of length B). Each participant uniformly selects a level l at random and employs stan- dard frequency LDP oracles (Bassily & Smith, 2015; Wang et al., 2017) to disclose which node at level & their data belongs to. The central aggregator may then combine the frequency oracles at each level to answer any range query. A particular use of range queries with relative error a is for
Experiments In Section 5, we demonstrate that the al- gorithm in Theorem 1.1 performs favorably compared to known ada-adaetive mechanisms as well as a more naive noisy binary search mechanism.
3

---

Lightweight Protocols for Distributed Private Quantile Estimation
constructing an a-approximate CDF of the data set, which in turn be used to approximate every quantile within error a. Unfortunately, dividing the user data among levels worsens the dependence on (B). In Appendix D, we demonstrate that the hierarchical mechanism can be used to solve LDPstat cestat-meddiie median with n = O lug' In terms of the polynomial dependence on log B, there is still a multiplicative log B gap between this upper bound and the lower bound of Theorem 1.3 which would be very interesting to close.
2. Preliminaries
In local differential privacy, we assume that each of n users hold a data point in the discrete and ordered domain [B] = (., B3} for a positive integer B. Each user will communicate a central (untrusted) aggregator using a differentially private mechanism. We consider sequentially adaptive protocols: In round t the aggregator queries a set 4 S {1,...,,) n2 of one or more parties, asking them to run a differentially private mechanism M₁ on their data. The output of M2(r;)) is then sent to the aggregator for each E 4. In general, any sequentially adaptive protocol may be implemented by querying one new user over n rounds', Let us label the users 1, ...., n in the order in which the protocol queries them and denote the data of user by 2; E [B]. Also denote the the private mechanism that user i uses by M; and the output y4+ = (M,).))
g² ) users.
Shuffle Differential Privacy The central model of DP requires that data be collected non- privately by the curator, which results in extremely accurate protocols. On the other hand, in the local model users do not trust anyone, and the response to any query must be privatized before it is broadcast by the user. In shuffle-DP, each user applies a LDP protocol to their data and then sends the output trusted shuffter whose only task is to randomly permute the users data before forwarding it to central data curator. This places shuffling as a middle ground between these two models in terms of both trust and accuracy.
Given the outputs {ye where yi = Mz()), the data aggregator makes an estimate of the ęth quantile with post-processing function F:
my = F(y1....... Bn)-
We require that each M,, satisfy local differential privacy: Definition 2.1. We say M, satisfies (e, (c,5)) 5)-occl DP if for all xr, x' E [B], and all outputs y, we have
Understanding the separation between the local, shuffle, and central models of privacy, and therefore the trade-offss be- tween trust and accuracy, is of both theoretical, and practical interest. For survey of such separations, see (Cheu, 2021).
Pr[M,(x) = v| s e Pr[M.(x') y)-
We say that M, satisfies s-local DP if satisfies (e, 0)-DP.
Noisy Binary Search and Threshold Queries Consider an algorithm that sequentially picks threshold query m E =B]. then samples a user from the database X and receives the bit y = [ S m). Since Pr(y = 1] = Fx(m), finding an integer m such that (m) R g reduces to the noisy binary search problem. This search over a CDF with threshold query sample access, exactly mirrors searching over monotonically increase sequence of coins. Noisy binary search was introduced by (Karp& & Kleinberg, 2007) with a tight bound of (log( (a²), later improved by constant factors by (Gretta& & Price, 2024), which holds for the non-private median when samples are accessed via threshold queries in the statistical setting.
In the adaptive setting, we allow M; to depend on Vl, ...... Vi i.c.
y1 = V............. 1)--))
(2)
where each M, satisfies Definition 2.1 in Iy (for any fixed choice of yi...., 1i- In contrast, in a non-adaptive pro- tocol, each M, fixed in advance (and usually all M, are the same mechanism).
To measure the utility of my. use the quantile error. For given data set X = (.,) define Fx as in Equation 1. We say m, is an a-approximate quantile estimate on X if
Pr[[Fx (mg), (1) -a- a. + 0 2 B,
Structure of the Paper In Section 2, we introduce neces- sary preliminaries for our theoretical analyses. In Section 3, we provide overview of our main ideas and technical con-
where the above probability is over the randomness in my. We are typically interested in the high-probability setting, where 3 = B)
tributions. Section 4 is dedicated to proving Theorem 1.1. In Appendix F, we prove the lower bounds of Theorems 1.2 and 1.3. In Appendix G, we provide the proof of Theo- rem 1.4. Finally, in Section we present our experimental results.
Now, we formally define the LDP median problems in both the statistical and empirical settings:
Rounds which query multiple new users may he split into many rounds, each querying one user.

---

Lightweight Protocols for Distributed Private Quantile Estimation
(LDPstat- median)). In L.Dsstttmedd (,, D is unknown distribu- tion over [B]. Users I...., sample Ti,...,2H In according to D. Each user i outputs = .M, .. where the M,'s are e-LDP mechanisms. The goal is to output an m- = mi(y....., E [B] such that mn is an a-approximate median D.
Definition 2.2
& Kleinberg, 2007): Given an ordered set of B coins with unknown head probabilities {p.) such that pi S .... S PB. a target T E (0, 1), and an error a > O, our goal is to find any coin i such that
[es (T a) +0,
(3)
which intuitively means that the desired probability T lies between coin i and + 1 (up to error (:). We refer to coin satisfying the above property as (T, a)-good. At each round, we may query a coin with index j. and we receive the result of the flipped coin. This problem generalizes classic binary search, where for the query t. one would have p; = 0 for all S and p. for all > We will denote the gen- eral problem as Monot on i (N a) (omitting (p: }= when they are clear from context). The state-of-the- art algorithm for Monot oniccss is the Bayesian Screen- ing Search (BayeSs) due to (Gretta & Price, 2024). Their algorithm finds a (T, ---good coin using O log samples with high probability in B
Definition 2.3
(LDPemp-median), LDPemp-medi an [ax))=1,, a,,), E). there are users I...., (where the ordering is chosen by the pro- tocol) with data points (x:)==1 E [B]". User outputs y/-
In
(t..,,-.....,.11 where the M,'s are E-LDP mechanisms. The goal is to output an in - -m(y),.... Vn.) E [B] such that mn is an a-approximate empirical median of {x, Mi
For shuffle DP, we assume that the protocol partitions the users {I,...,r) , into r disjoint subsets .,....,4, Ly and that each user i E It applies the same mechanism M, to their data I2 where Mr may be chosen adaptively based on (M,((:))sss(t-.ee, We assume that n. I - I is a uniformly random permutation for each & E [r]. Given the outputs (Be)ee(r) where, Yt- = (M)(()())) (in shuffled order), the data aggregator outputs
a²
To see how noisy binary search algorithms relate me- dian estimation under LDP, it is instructive to consider LDPstat srrsttt-mmeiin(2) n, E). Concretely, any sample x from D gives a coin flip with head probability p: Prz-d(ı (z I i] for any E [B]. It is a useful warmup problem, to show that one can solve ADPstat-medla Plugging in
mag- = F(yn,... .,))
using an algorithm for MonotonicNEs the algorithm of Gretta and Price gives an algorithm for LDP st -median(D, n, a,s) if 2 C. stant C. We show the precise details in Appendix C.
for a post-processing function F. We say that the pro- tocol satisfies (e, 6)-shuffte DP if for any t E [r]. any (x:) te)) (x))sez, differing only in a single coordinate, and any set S.
بे for con-
For LDP PoPemm-mede an, the situation is more complicated. A first idea is to reduce to the statistical setting by sampling users with replacement, thus sampling i.i.d from the empiri- cal distribution. However, in sequentially adaptive protocols, users may only be queried once but sampling with replace- ment may sample single user many times?, To resolve this issue, our main idea is to go through the users in a random order or equivalently sample users without replacement. Ideally, we would like to maintain the guarantees of algo- rithms for Monotont cNBS, but this problem assumes that the coin probabilities are unchanging over time. However,
Pi(lMi ES Se (r((M E
+ ES]+6.
Definition 2.4 (shuffle-emp-ie meddan)).. In a, e,
there are users 1, I, (where the ordering is chosen by the protocol) with data points (xx)%_ E [B] Using an (s, o--sufffle DP mechanism with r rounds of adaptivity, the goal is to output an m = m yr) E [B] such that i is an a-approximate empirical median of (=:)²_1-
In fact, they obtain stronger guarantees. For any a, T, their al- gorithm uses Cr.a (log B + O(log2/3 B log lo + log()))
3. Technical Contribution
In this section we give high-level discussion our technical contribution for designing algorithms and proving lower bounds. For simplicity, we focus on the high privacy setting E $&1. 1.
where Cr. = e
((1-T) for sufficiently small a. Moreover, by information theoretic lower bounds, any algorithm must use Cr.y log B coin flips.
a²
"If we allow for multiple queries to the same user, we can indeed reduce to the statistical setting by sampling users with replacement. However, some users would then be sampled up to O(log n/ log log n)) times and to maintain e s-LPP, their reports would have to be made more noisy, thereby increasing the number a-approximate median. Thus, even
3. Adaptive LDP Median Estimation via Noisy Binary Search (Theorem 1.1)
of users needed to get allowing for users to he queried multiple times, it is unclear how to get optimal bounds via algorithms for Monotonni CNBS.
At the heart of our LDP median protocol of Theorem 1.1 is an algorithm for the noisy binary search problem from (Karp
5

---

Lightweight Protocols for Distributed Private Quantile Estimation
when sampling without replacement, the empirical CDF of the remaining users, and thus the coin probabilities, change over time. Our main technical contribution is two-fold. We first show that throughout the process, no coin probability is altered too much.
different gth quantiles from each other, even from a "hard"
family of distributions. Our hard family of distributions will be close in statistical distance, but still has different ęth quantiles:
i = g - 2a 4a 1 20
Lemma 3.1. Let si,...., In E [B] and let yi = T((() where : [n]] - [n] is a random permutation. For 0 S t n and j E [B), we define p)} = [tcisnly.SiH Suppose that
Ps(1)
i i= B
i == B,
n-1
n 2 Clogs B
a² for a sufficiently large constant C. Then with high probability in B, we have for all 0 1 S n/2 and all
for B E (2..... B-2). . If i'ss chosen uniformly at random, then our LDP distinguishing mechanism will be able to de- liver log( B) bits of information (measured with the mutual information), by Fano's ' inequality. However, there is an upper bound on the amount of mutual information possible with an LDP protocol, as first established in (Duchi et al., 2013) and this leads to our desired result.
j E [B] that Ip} -Pj-p" P)] S a.
Then, we show that the algorithm by Gretta and Price in fact also solves an adversarial version of Monotoni which we denote AdvMonoton: cNBS. Here, in each round, if coin j is selected to be flipped, an adversary may instead flip coin with bias p such that 1p, pl I ca: for some The goal is to return (T, a(1 + c))-good coin. A formal definition can be found in Definition E.1. Our result, which may be of independent interest is as follows.
To get a lower bound in the empirical setting, we observe that a low-error algorithm for empirical quantile estimation can be applied also get low-error in the statistical setting by just applying it on the data sampled from D. The approxi- mation guarantee follows from the fact that we have enough users that the empirical q-quantile of the samples is an a/2 approximation to the true q-quantile of the distribution D.
Theorem 3.2. Let < a S 1 and suppose c S 1. There exists an algorithm for AdvMonot oww.onnn/nn/nnncc a, c) which uses O1 (lozz)) coin flips and returns (1/2, a(1 +
c))-good with high probability in B.
Lower Bound for Non-Adaptive Protocols (Theorem 1.3) It turns out more challenging to obtain lower bound for non-interactive protocols. Our proof is via reduction to the problem of privately learning CDF under non-interactive LDP with e--error below a. For small and a, it is known (Edmonds et al., 2020) that any such algorithm re- log* B quires 0 (1/o) users".
Now by Lemma 3.1, as we sample users without replace- ment, the CDF of the remaining users never changes by more than a at any point. In particular, for the data 2, of newly sampled user and threshold / E [B], the probability of observing one when applying randomized response to ( I i] never varies by more than oe. Denoting this probability ps, we are exactly in a position to apply Theo- rem 3.2 to conclude that 0 ( (1/2, 2ax) good coin. But this translates exactly to being an aaprrxxipoo median.
B users suffices to find a
Our reduction works as follows: Given a non-interactive e-LDP algorithm for median estimation which succeeds with probability 2/3, we first boost this success proba- bility to 1 - a² with Olog 1/a) independent repetitions and the median trick. The privacy of this protocol is thus
The proof of Lemma 3.1 and Theorem 3.2 can be found in Section 4 and Appendix E.
e = O(s log(1/a)). Second, assuming access to such an algorithm succeeding with high probability, we design a con-interactive CDF approximation algorithm as follows. First, we add 2n dummy users n of which are and n of which are 1. We run the LDP median estimation algo- rithm this new set of users and by selecting how many dummy users to include from the left and from the right, we can use their responses to estimate any quantile with error probability 01 = 0(a) with probability 1 - -(a²). Union bounding over the equally spread O(1/a) quantiles a, 2a,..., [1/a] -a, we obtain a CDF estimation algorithm which has error Oi with probability 1 - O(a). In particular, the expected error of this con-interactive protocol is ((a). Now the lower bound from (Edmonds et al., 2020) kicks in
3.2. Lower bounds for Adaptive and Non-Adaptive Median Estimation (Theorems 1.2 and 1.3)
We next describe the main ideas for the lower bounds of The- orems 1.2 and 1.3, full proofs can be found in Appendix F.
Lower Bound for Adaptive Protocols (Theorem 1.2) In fact, we provide lower bound for the general quantile estimation problem, demonstrating that all quantiles (not too close to the 0 or 1) are as hard as the median. To prove this lower bound, we first prove lower bound in the statistical setting of Definition 2.2 and then reduce to the empirical setting of Definition 2.3. Our building block for the statistical lower bound is the framework in (Duchi et al., 2013), which uses the fact that a protocol attaining low error on the quantile problem, can distinguish distributions with
'In fact, their bound is 2(log B), but it is relatively simple to check that their proof extends to general s, a S 1 with mild assumptions on these parameters.
6

---

Lightweight Protocols for Distributed Private Quantile Estimation
which in turn gives the lower bound for median estimation, with the log" log((1//) (1/o) stemming from the fact that we have to apply their lower bound with E O(s log(1/a)).
c++1 (x((==) 0 is exactly 2n-1
Y Thus,
Y
Yo
E[X (X,)ssd) 2n i
Yi
2n - i
2n
3.3. Shuffle DP for Median Estimation (Theorem 1.4)
Y;
Yo
X;
Our core contribution with Theorem 1.4 is to demonstrate explicit trade-off's that exist when considering trust models and rounds of adaptivity. While adaptive algorithms that query ((1) users per round are extremely sample efficient, they remain fundamentally incompatible with the shuffle model. We introduce protocols that exchange the benefits of faster learning for larger groups amenable shuffling, and show that such protocols can compete in practical parameter regimes.
2n
2n
Moreover, writing Y/+1 = Yi - b where b E {0, 1] for a given < n, we have
Y
[1141 1011-X,l== (2n (2n 1)
if = 0, and
2n - - Y (2n (2 -i 1)
[x++1 X,|
Karp & Kleinberg (2007) introduced naive "binary search with repetitions" algorithm as a baseline. This algorithm follows the natural approach of a standard binary search: query the midpoint, then recurse on either the left or right half of the array. However, since queries are noisy, each point must be queried a logarithmic number of times to achieve accuracy and failure probability B".
if b = 1. Now, Y, is exactly the number of zeros among the
2n i values qii + 1)....: : π (2n), so trivially 0 Y; S
2n i. It follows that for n. in either of the cases b (0,
1
X - X,I S 2n - i-
Building on the "near-optimal" analysis of (Feldman et al., 2021), we prove a shuffle-DD upper bound in Theorem 1.4 on the sample complexity of this "binary search with repeti- tions" algorithm with only r = log, rounds of adaptivity. Sampling batches of n/r users at each round we shuffle their private outputs, to learn one of the pivots up to curacy a and failure probability 3/r. Union bounding over all r steps ensures we return an a-approximate quantile with probability 1 - B.
72
Finally, X, = 0, so we may apply Azuma's inequality (Theorem A.2 of Appendix A) with an appropriate rescaling of the X,'s to obtain that
-t-n
Pr
max ISSn
[
2
< exxp
2
as desired.
The full proof of Theorem 1.4 can be found in Appendix G.
It is now easy to obtain Lemma 3.1.
4. Median Estimation with Adaptive LDP
Proof of Lemma 3.1. Suppose without loss of generality
that n = 2n' is even. Fix j E B and define h; = [., S j] and e, = (z()) = [w S jl for E [n]. Let Y₁ = K[t < i Y.
In this section we prove Lemma 3.1 and Theorem 1.1, post- poning the proof of Theorem 3.2 to Appendix E. We start with the following technical lemma.
2n G. 0}/- Then p = n-ク. so plugging into Lemma 4.1,
we find that,
Lemma 4.1. Let by,..., bnn E {0, 1}, (1...., (.....2m] 2m}
{1...., 2m} random permutation, and q; bR(s) for 1 <
Pr
lp² 109-17 p31 a DStSR
max
2 exp
-a2n
1 < 2n. Les Y; = | E [2n] \ [i] Cj = 0}}, and X; =
Ya, For any t 2 O.
2n- ; 2n
< exp
(=Clog B
S 2B-
Pr max
X,| 2
2 < 2 2exp
Choosing C sufficiently large and union bounding over all E [B], the result follows.
IsiSD
Proof. We first note that (X:) forms a martingale. To see this, first observe that
Finally, assuming Theorem 3.2, we can prove our main theorem Theorem 1.1.
Y, Y 1 (X,)ssd = Y; 2n
Proof of Theorem 1.1. We pick random permutation i [n]] - [n] and define yt = (x()). the input of user (()). For j E [B] and t < n, we define of Kktssnlu and
Indeed, conditioning on (X,)ssh, the probability that
n-t
7

---

Tter S e/2 follows from second degree observing that Lightweight Protocols for Distributed Private Quantile Estimation
Φb 0. Thus the map j + of is the empirical CDF of the users Ut+1.-.., Un-
DpBaye5S
DpNaiveNBS
Hierarchical Mechanism
0.04
0.57
1.0
1.0
Our algorithm uses the algorithm of Theorem 3.2 to solve AdvMonotoni (tw.oooooooiiNNs(11112 CNBS az/8, 1) with the adversarial to be described shortly. To do so, whenever the algorithm calls for flipping a coin j at step i, we sample a new user (T(() and apply randomized response to the variable [ S j]. retaining the bit with probabil- ity Ites and flipping it otherwise, to get a variable zj. By standard properties of randomized response, this protocol satisfies the e-LDP requirement. Moreover, the probability Ite (1
Curuuaative Distribbution
0.8-
0.8
Success rate
probabilities {-]),=1 B
0.6
0.4
0.2
0.2
10
10" privacy budget
0.0
0.2
0.4
error
(a) Pareto like data with
2500 and B
4
pf that 2j = 1 is y qj
and
DpBaye55
DpNaiveNBS
lnj 1/2| = \ e e 1
c|1-1 4
Rual
1.0
10*
(4)
1+ EF
0.8
Cumalatuu Distribuutoo
0.8
where we have written of = -1/-2++ + Xz. Using that n >
Success
0.7
0.6
2a0 > leg it follows from Lemma 3.1, that lo - 0ن1 -
at, a/5 for all t S n/2 and 0 و S B with high probability in B. Thus,
0.4
0.6
0.2
0.5
Ip' 291 103 2g1(e= 1)
Co
10a
16
10
164
0.0
0.1
0.2
1 e
10
number of coins B
where the bound c'-1
(b) Uniform data with 2500 and
Taylor expansion of the maps f I+e
Figure I. Plots la compare the three algorithms on the Pareto-like dataset: the left plot shows the success rate for Osest 0.04 across E [0.1, 5). and the right plot shows the c.d.f. of the absolute error for 0.57. Plots 1b compare DpBayeSS and DpNa MpNaiveNNs on a uniform datasct with rate for different coin domains B for Cves 0.04, and the right plot shows the c.d.f. of the absolute error for B 10 The error bars on the left plots are standard deviation, computed as the sample average over 200 trials. The decrease in accuracy observed in Figure 1b at B = 10 is likely attributable to random generation of more challenging dataset.
(())) = 1/2 and (e())= < O.
It now follows from Theorem 3.2, that using the noisy feed- back from at most n/2 of the users, the algorithm finds an (1/2, ae }-good coin j" with high probability in B. In par- ticular DJ- S 1 + a5 and pf. 2 1 Qz, It thus follows from equation (4) that L.. S 1/2++0 a and +1 2 1/2 - a. Therefore j* + 1 is an a-approximate median of { 1m
1: the left plot shows the success
completing the proof.
5. Experiments
We compared three mechanisms for median estimation in the empirical setting: DpNaiveNBS (binary search with randomized response). Hierarchical Mechani sm from (Cormode et al., 2019), which serves the state of the art for non-adaptive protocols, and our sequentially adaptive algorithm, DpBayeSs, introduced in Theorem 1.1 (Algo- rithm 4 in Appendix illustraaes the pseudocode). Further details of the implementation, extensive experimental analy- sis, and experimental results for our algorithm in the shuffle model appear in Appendix I. Experiments were conducted on data generated from two distributions: a Pareto distribu- tion over [B), often used to model quantities like income and population (Arnold, 2014), and uniform distribution over random interval [7. r] with 1 < 7 S < B, ensuring that the position of the median is not straightforward.
coin is returned with Otest = 0.04, and the absolute quantile error, Fxx (m) - Fx (m)). where m is the returned median. We run each algorithm 200 times and computed the standard deviation of the success rate as the sample average of Bernoulli random variable.
In Figure la, we plot the success rate of the three privacy mechanisms for fixed B = 49, and n = 2500, with a vary- ing from 0.1 to 5, for the synthetic Pareto-like dataset. We also plot the cumulative distribution of the absolute quantile error, showing the distribution of the quantile error over 200 trials, for æ 0.57. These parameter settings are typical values encountered in real applications; we test many more parameter values in Appendix I with similar results. The plots illustrate that DpBayeSS always achieves far higher success rate than the other two mechanisms, and is statisti- cally significant as the confidence intervals are far from over- lapping. Correspondingly, the CDF of the absolute quan-
We evaluated the mechanisms using two metrics: the success rate, computed as the fraction of times a (}) (tea) ) -good
8

---

Lightweight Protocols for Distributed Private Quantile Estimation
tile error shows this value is much lower for DpBayess. Also, observe that the number of users is insufficient to obtain meaningful median using the fierarchical Mechanism, which aligns with our theoretical predictions.
was supported in part by the Big-Mobility project by the University of Padova under the Uni-Impresa call, by the MUR PRIN 20174LF3T8 AHeAD project, and by MUR PNRR CN00000013 National Center for HPC, Big Data and Quantum Computing.
In Figure 1b, we plot the succes rate of DpBayess and DeNaiveNBS with a fixed privacy budget 5 over vary- ing domain sizes B from 10a 10 using the uniform distribution data set with 2500 users. We also plot the CDF of absolute quantile enror for large domain of B 10 We observe again that DpBayeSS achieves superior perfor- mance in all the values of B tested. Due to implementa- tion constraints, Hierarchical Mechan sm was not tested on this dataset, but results in Figure la indicate its error generally higher than binary search-based methods. Our code is freely available
Impact Statement
This paper presents work whose goal is to advance the field of Private Machine Learning. There many potential social consequences to collecting user data, even privately, none of which we feel must be specified here.
6. Conclusion
Our starting observation is that approximating a quantile with limited information is essentially a noisy binary search. Based on this we introduced novel adaptive local dif- ferentially private algorithm for estimating a quantile in both statistical and empirical settings. We have shown that this algorithm, which uses private implementation of the Bayesian Screening Search of Gretta & Price (2024), is opti- mal up to constant factors. In proving this, we demonstrated that the original algorithm is robust to a limited form of adversarial noise addition, which may of independent interest.
As adaptivity be expensive, also proposed shuffle- DP mechanism that uses fewer rounds of communication by "batching" users and shuffling their private responses. We showed that this approach is competitive in practical parameter regimes and evaluated the effectiveness of these approaches through experiments on synthetic data designed mimic real-world scenarios.
Several open questions remain. Absent privacy constraints in the statistical setting, one can estimate the median with O(1/a²) samples (trivially, in the empirical setting, one simply outputs the median of the data set), so finding a protocol that converges to this as E + oo is of particular theoretical interest.
Acknowledgements
Aamand, Pagh, and Imola carried out this work at Basic Algorithms Research Copenhagen (BARC), which was sup- ported by the VILLUM Foundation grant 54451. Pagh and Imola were supported by Data Science Distinguished In- vestigator grant from the Novo Nordisk Fonden. Boninsegna
'https:/ //ght://///thbb com/ Soot//nnsenaaber/Onee ile_.
est imat i ion with_adapp adapt we__DD

---

Lightweight Protocols for Distributed Private Quantile Estimation
References
Bun, M., Nelson, J., and Stemmer, U. Heavy hitters and the structure of local privacy. ACM Trans. Algorithms, 15(4): 51:1-51:40, 2019, doi: 10. 145/334442.
Acharya, J., Canonne, C. L., Tyagi, H., and Sun, Z. The role of interactivity in structured estimation. In Confer- ence on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 1328-1355. PMLR, 2022. URL https: pttpsttss:/proceeeee ngo mlr. prres// v178/achazya222 htmml...........................
Cheu, A. Differential privacy in the shuffle model: A sur- vey of separations. CoRR, abs/2107. 2021. URL
https: wttp://.wwrr.aaa...eeeaea
Cheu, A., Smith, A. D., Ullman, J. R., Zeber, D., and Zhilyaex, M. Distributed differential privacy via mixnets. CoRR, abs/1808 01394, 2018.
Alabi, D., Ben-Eliezer, O., and Chaturvedi, A. Bounded space differentially private quantiles. Trans. Mach. Learn. Res., 2023.
Cheu, A., Smith, A. D., Ullman, R., Zeber, D., and Zhilyaev, M. Distributed differential privacy via shuffling, In Ishai, Y. and Rijmen, V. (eds.), Advances in Cryptol- ogy EUROCRYPT 2019 38th Annual International Conference on the Theory and Applications of Crypto- graphic Techniques, volume 1 11476 of Lecture Notes in Computer Science, pp. 375-403. Springer, 2019. doi: 10. 10.1007/978-3 10119988---3-111-- 17653-2.13.
Aliakbarpour, M., Silver, R., Steinke, T., and Ullman, J. R. Differentially private medians and interior points for non- pathological data. In Guruswami, V. (ed.), 15th Inno- vations in Theoretical Computer Science Conference, ITCS, volume 287 of LIPIcs, pp. 3:1-3:21, 2024, doi: 10.4230/LIPIcs.ITO
Alon, N., Livni, R., Malliaris, M., and Moran, S. Private PAC learning implies finite littlestone dimension. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 552-860. ACM, 2019. doi: N0.11445/3113276.33163
Cohen, E... Lyu, X.. Nelson, J., Sarlós, T., and Stemmer, U. Optimal differentially private learning of thresholds and quasi-concave optimization. In Saha, B. and Serve- dio, R. A. (eds.), Proceedings the the 55th Annual ACM Symposium Theory of Computing, STOC, pp. 4824 ACM, 2023. doi: 10.1145/3564246.3888 148.
Amold, B. C. Pareto distribution. Wiley StatsRef: Statis- tics Reference Online, pp. 1-10, 2014. doi: 10.1002/ 9781 1881118410 111441144 100.p
Cormode, G., Jha, S., Kulkarni, T., Li, N., Srivastava, D., and Wang, T. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference Management of Data, SIGMOD '18, pp. 1655-16555 Association for Computing Machinery, 2018. ISBN 9781450347037, doi: 10.1145/183371333111
Asi, H. and Duchi, C. Near cestance-optimalin dif- ferential privacy. CoRR, abs/2005. 2020. URL https: / //ariiiivv..///a///aaa////aaavva org/ hbtg//bs//20 211/2200.......
Bassily, R. and Smith, A. D. Local, private, efficient pro- tocols for succinct histograms. In Servedio, R. A. and Rubinfeld, R. (eds.), Proceedings of the Forty-Seventh Anmual ACM on Symposium on Theory of Computing, STOC, pp. 127-135. ACM, 2015. doi: 10.1 10.1145/2746539, 2746632.
Cormode, G., Kulkarni, T., and Srivastava, D. Answer- ing range queries under local differential privacy. Proc. VLDB Endow, 12(10): 126-1138, 2019, doi: 10.14778/ 0539490.3339496 URL http: //wt::::/wwww... vldb. org/ htddd//ol1//p111. 12 1 corooooddeddddee
Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure approximate differential privacy. Theory Comput., 12(1):1-61, 2016. doi: 10.4086/TOC. 2016. V012A001
Cormode, G., Maddock, S., and Maple, C. Frequency esti- mation under local differential privacy. Proc. VLDB En- dow, 14(1 (4216:::0062055, 2021. doi: 10.14778/3476249. 3476261.
Bittau, A., Erlingsson, Ú. Maniatis, P., Mironov, I., Raghu- nathan, A., Lie, D., Rudominer, M., Kode, U., Tinnés, J., and Seefeld, B. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, pp. 441-459. ACM, 2017. doi: 10. 00.1145//132747733332666
Differential Privacy Team. Learning with privacy at scale., 2017. Apple Machine Learning Research.
Drechsler, J., Globus-Harme I., Mcmillan, A., Sarathy, J., and Smith, A. Nonparametric differentially private confi- dence intervals for the median. Journal of Survey Statis- tics and Methodology, 10(3):04-829, 06 2022. ISSN 2325-0984. doi: 10. 10.1093//samm/smcc01..
Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. Differen- tially private release and learning of threshold functions. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pp. 634 649, USA, 2015. IEEE Computer Society. ISBN 9781 467381918, doi: 10. 109/FOCS.SOOO 2015.455.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy and statistical minimax rates. In 54th Annual IEEE Symposium on Foundations of Computer Science,
10

---

Lightweight Protocols for Distributed Private Quantile Estimation
FOCS, pp. 429-438. IEEE Computer Society, 2013. doi: 10.1 (09/FFCCS2003.533.
Gillenwater, J., Joseph, M., and Kulesza, A. Differen- tially private quantiles. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Confer- ence on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Ma- chine Learning Research, pp. 3713-3722. PMLR, 2021. URL http::/proceeddigg lttpgggs.ll.....ss.... www.ppeess/v13.... g giLlenwater2a. html.
Duchi, J. C., Jordan, M. I., and and, M. J. W. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 118 201. 2018. doi:
Dwork, C. and Lei, J. Differential privacy and robust statis- tics. In Mitzenmacher, M. (ed.), Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, pp. 371-380. ACM, 2009. doi: 10.1 155/1464444 1536466.
Gretta, L. and Price, E. Sharp noisy binary search with monotonic probabilities. In Bringmann, K., Grohe, M., Puppis, G., and Svensson, O. (eds.), 51st Interna- tional Colloquium on Automata, Languages, and Pro- gramming, ICALP 2024, July 8-12, 2024, Tallinn, Es- tonia, volume 297 of LIPlcs, pp. 75:1-75:19. Schloss Dagstuhl Leibniz-Zentrruu für Informatik, 2024. doi: 10. 0042200LIPICS.ICALP.2004
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 1-07, 2014. doi: 10.1561/0400000042.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. D. Calibrating noise sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC, volume 3876 of Lecture Notes in Computer Science, pp. 265-284. Springer, 2006. doi: 10.1007/1
Joseph, M., Mao, J., and Roth, A. Exponential separations in local differential privacy. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 515- 527. SIAM, 2020. doi: 10.1137/1.78166119975999
14.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K. A., Charles, Z., Cor- mode, G., Cummings, R., D' D'Oliveira, R. G. L., Eichner, H., Rouayheb, S. E.,, Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Har- chaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi. M. Javidi, T., Joshi, G., Khodak, M.. Konečný, J., Korolova, A., Koushanfar, F., Koyejo. S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi, H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song. W., Stich, S. U., Sun, Z., Suresh, A. T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, H., and Zhao, S. Advances and open prob- lems in federated learning. Found. Trends Mach. Learn., 14(1-2):1-210 2021. doi: 10.1561/220000008
Edmonds, A., Nikolov, A., and Ullman, J. R. The power of factorization mechanisms in local and central differential privacy. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy. J. (eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 425-438. ACM, 2020. doi: 10. (0.144//357713.3384299
Erlingsson, Ú. Pihur, V., and Korolova, A. RAPPOR: randomized aggregatable crivacy-presevingg ordinal re- sponse. In Proceedings of the 2014 ACM SIGSAC Con- ference on Computer and Communications Security. pp. 1054-1061, ACM, 2014. doi: 10. 10.1145/2660020 00.1145/2660026726666444 26603448.
Erlingsson, Ú. Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM- SIAM Sym- posium on Discrete Algorithums, SODA, pp- 1468-2479 SIAM, 2019. doi: 10.
Kaplan, H., Ligett, K., Mansour, Y., Naor, M., and Stemmer, U. Privately learning thresholds: Closing the exponential gap. In Conference Learning Theory, COLT 2020, vol- ume 125 of Proceedings of Machine Learning Research, pp. 2263-2285. PMLR, 2020.
Fan, X., Grama, I., and Liu, Q. Hoeffding's inequality for supermartingales. Stochastic Processes and their Applications, 122(10)33545-355 2012. ISSN 0304-
Karp, R. M. and Kleinberg, R. Noisy binary search and its applications. In Proceedings of the Eighteenth Annual ACM- SIAM Symposium on Discrete Algorithums, SODA, pp. 881-890, 2007.
4149. doi: 10. n..1016/.spa.20112.60
Feldman, V., McMillan, A., and Talwar, K. Hiding among the clones: A simple and nearly optimal analysis of pri- vacy amplification by shuffling. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 954 964.. JEEE, 2021. doi: 10.1109/FOC552999 2021. 1000660
Nissim, K., Raskhodnikova, S., and Smith, A. D. Smooth sensitivity and sampling in private data analysis. In John- son, D. S. and Feige, U. (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp- 74. ACM, 2007. doi: 10.1 001114/5579999 1250803.

---

Lightweight Protocols for Distributed Private Quantile Estimation
Tzamos, C., Vlatakis-Gkaragkounn E. V., and Zadik, I. Optimal private median estimation under minimal distributional assumptions. In Larochelle, H., Ranzato, M.. Hadsell, R., Balcan, M.. and Lin, H. (eds.), Ad- vances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. 2020. URL https:/ prrtps://prcot
210144chaaf2ccaal09441111bbbbbb -bb.bbatttttbbbb--catt.c....... html.
Wainwright, M. Basic tail and concentration bounds, pp- 21-57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Wang, T., Blocki, J., Li, N., and Jha, S. Locally differentially private protocols for frequency estima- tion. In Kirda, E. and Ristenpart, T. (eds.), 26th USENIX Security Symposium, USENIX Security 2017,
pp. 729-745. USENIX Association, 2017. URL
https: www.:uusiwi..ooooooeeeeeee.. usen hteeikceecrrttyytttteciccl------ -essionss/ sssss/// presentation/vang- tianhao.
Warner, S. L. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the Amer- ican Statistical Association, 60(30)):63-9,, 1965. ISSN
01621459, 1537274X.
Wilson, R. J., Zhang, C. Y., Lam, W., Desfontaines, D., Limmons-Marengo, D., and Gipson, B. Differentially private SQL with bounded user contribution. Proc. Priv. Enhancing Technol., 2020(2)230-255, 2020. doi: 10.
2478/POPETS-2020-000
12

---

Lightweight Protocols for Distributed Private Quantile Estimation
A. Additional Definitions
Lemma A.1 (Binary Randomized Response (Warner, 1965; Dwork et al., 2006)), For a binary input a {0, 1}, and privacy parameter E, the following protocol M + {0,1} satisfies E-LDP:
M(x)
J, w.p. e
(1 11-I, otherwise.
Azuma's inequality We will use the following version of Azuma's 's inequality which bounds the maximum deviation of martingale (Xe)20 at any time = 0,....... See Theorem 2.1 in (Fan et al., 2012) for stronger and more general bound.
Theorem A.2 (Azuma's inequality). Lei (Xi) be martingale such that Xo = 0 and Xi+1 XiI S 1 for all 0 < < n
For any 2
Pr max S
[ f| S
exp
2n
Bernstein's Inequality use the following variant of Bernstein's ' Inequality in the proof Theorem 1.4, see Wainwright (2019, Proposition 2.10) for a detailed overview.
Theorem A.3 (Bernstein's Inequality). Let {X+)==1 be independent random variables that are bounded almost surely by 1.
Let 0² E Var[X,] be the average variance. We then have,
Pr
Σ
n
X;
1
Ex
n
> a S exp
-na²
2 + 2a 3
n
71
B. Reduction the Median
Consider the simple case where we are given an algorithm A which returns the median of n samples in the most natural sense, by returning the n/22thh index of their sorted representation. Without changing this algorithm we can have it return any arbitrary index by adding elements to the beginning or the end of this sorted array. For example, adding two elements to the beginning of the array will create new array with n' n + elements where the n' /2'th index will the (n/2 1) index of the original array. The padding argument below formalizes this notion, demonstrating that any algorithm for an a-approximation of the median can be used to obtain 2o-approximation of any quantile.
Lemma B.1 (Padding Argument). Any a-approximation algorithm for the median, with E (0, 2). can be used to construct a 20-approximation for any quantile T E (0, 1).
Proof. Consider a dataset D = {xI,... Inf where each element is such that I; E (I,...,,,, Let M be an algorithm for the a-approximation of the median then for m = A(D) we have by definition
Prp(r m]
2
+ and Pro(r m m
a.
(5)
where Pro(æ= < m] Eren(rSml and [x S m] is an indicator function. Consider now padded dataset Dp DU (1)()-)) U [B}T*, where {a} indicates the multi-set containing the a element x times 6 The new empirical cumulative distribution the data set for y E (1,.... B 1).is
(1 - T)n + Ene Le S
1-T
Prpp S
+ Pro[I S vl.
Drl
2 2
as we have Dpl = 2n. Thus
Prp(# & y) = 2Pr xr Σ 1
(6)
The application of A to the padded data set Dp returns a-approximate median A(Dr). Therefore, for (I...., B 1}. from Equation and Equation 5 it follows that
Pro(r: & mrl < T + 2a and
Pro(# S mp +1 2a.
Notice that mp # B, as Prople (a < B = 1 < iff a 2.
This concludes the proof.
We consider (1 - r) and rm integers.
13

---

Lightweight Protocols for Distributed Private Quantile Estimation
C. Statistical Private Median Estimation
In this section, we will provide an algorithm for LDPstat DePstat-mediant using the state-of-the-art algorithm for MonotonicNte eNBS. We prove the following:
Theorem C.1. Let E (0. 1) and = 0. Suppose that the number of users n 2 C C (#
for sufficiently large
constant C. Then there exists an algorithm solving LDPstat-mediange n. E) with high probability in B.
In this section, we prove Theorem C.I. For this, we recall the following result which is corollary of the main result in (Gretta& & Price, 2024). Recall the definition of an (2) a) -godd coin in (3).
Theorem C.2 ((Gretta & Price, 2024)). For any a (0, 4), there exists an algorithm for MonotonicNBs(T: oi) which uses O log B coin flips and outputs an (3) a) -good coin with high probability in B.
a
Proof of Theorem C.I. For i E [B], we define qi = =ドs; Pli] with the convention that = 0. Thus j + qj is the CDF of DD Consider sampling X ~ 'D and let Y be the random variable obtained by applying randomized response to the indicator variable [X S.] retaining the bit with probability Iter and flipping it otherwise. Then Pr[Y = =1] = P where e¹ Py qi 1405 (1 - 9j) 14er " Then,
e +1
4 = Pj
(8)
e
+1
e
We use the the algorithm in Theorem C.2 to solve Monotoni CNBS To do so, whenever the algorithm calls for flipping coin j. we sample a new user X D and apply randomized response to the variable Y = X j.. By standard properties of randomized responze, this protocol satisfies the s-LDP requirement. Moreover, by Theorem C.2, the algorithm finds an [ -good coin j with high probability in B. In particular
2: e(+1) when the inputs are the unknown {pr)
a
[ and +1++1 2 1 + It thus follows from Equation (8) that qz- S 1/2 + a and 9z-+1 2 1/2 P. S 1 + a eI Therefore jr is an a-approximate median of D completing the proof.
In the high privacy regime, i.e. for < 1, the sample complexity of Theorem C.1 becomes n = Ω lower bound up to a constant factor. 00
[log B sta²
matching our
D. The Hierarchical Mechanism
The algorithm was presented in (Cormode et al., 2019) and can be used to approximately answer general range queries. It comes in several variants but here will show how it can be used to reconstruct the CDF of a distribution D on [B] within b eererroo & under e-LDP in a non-adaptive fashion using O( (log B)3
users sampled i.i.d from D with high probability in B.
sin2
In particular, this implies that it can solve CePPstat-mdiian an (in fact approximate any quantile) within the same sample complexity with high probability in B.
The main idea is to construct b-ary tree of depth (llg((B) on [B]. For the below, we will assume that B is power of 2 and that b- 2 (although for the experiments, we use different constant b). The nodes on level i (where level 0 is the root) corresponds to the 2' dyadic intervals of B. Namely, in the binary representation of elements of B, there is an interval corresponding to each prefix of length i in the binary representation. The non-adaptive protocol we will consider is as follows. The n samples Z1. Fn ~ D are partitioned into batches of size k := n/ (log B + 1), one for each level& f = 0, ........ log B of the binary tree. Namely, for
O,.... log B, define S (Ix++1, ........,.. (x(++1)) A user i with kf 1 i S k(E + 1) writes one-hot encoding of which node they belong to on level é and uses randomized response each of the 2 bits of retaining them with probability Tf and flipping them with probability I+e This is the message y, they send to the central server. This is the unary encoding mechanism; see (Cormode et al., 2019) for more sophisticated solutions, that require less communication but nonetheless have the same approximation errors. The combined algorithm is denoted Hi Hierarchical. Mechanisms.
Analysis sketch of Hierarchical Mechanism We here analyse the performance of Hierarchical Mechanism for approximating the CDF Fo(1) of D at any point i E [B]. We assume that = S 1. Denote by I = (1...., i and let I = J U U...U U T, be the unique partition of into & log B dyadic intervals such that for each a, at most one of
14

---

Lightweight Protocols for Distributed Private Quantile Estimation
Algorithm 1 BayeSS main steps
Input: (zi...i,....m a E (0, 2 log L + BayesLearnaa (B, (=t)=.....//..a))
R - (.)) [for = 0(1)
return TestCoins(Rt, (4ijn/441....m///
the intervals have length 2 For a sample z ~ D, denote by > = Pr(a E 15] such that A E==E== d, is exactly equal to Fi) Let .,....,f le be the levels the tree corresponding to I,...,,4. For S t, the bit corresponding to 15 of the randomized response vectors obtained from St, constitute k i.i.d random {0, 1} variables xi, .....,,'' X each attaining the value I with probability Ite + Ite Namely, they can attain the value exactly the sample is in I (which happens with probability Xy) and the bit is retained, or the sample is not in 1 (which happens with probability Ay) but the bit
Ave
(1-Az)
is flipped. For 1,..., k, define
e +1 ( x; 1+e
Y
1-
so that [[ >//k. Since e < 1, have |Y!| C/(sk) for some universal constant C. Define,
k
X
Y
/=1==1
which sum of th independent (but not necessarily i.i.d) random variables. Then B[X] X, and it follows from Hoeffding's 's inequality that
20 2exp
a²82k
Pr[[X - Xa 2|
S 2
2exp
kt(2C/ (k{2)/(kE))3/
2C
Since / < log B, it follows that if k = O(log B)2 ((=* is sufficiently large, then
Pr||X X 2 a < B
for any desired constant y. In particular, it suffices to have k O(log ()²/(= users at each level of the to approximate the CDF with high probability within under c-LDP. Since n k(log B 1), the claim the sample complexity follows.
E. Proof of Theorem 3.2
The goal of this section to prove Theorem 3.2. We first define the adversarial setting.
Definition E.1. Let 0 < a < and a positive integer. Let po..... PB E [0, 1] be unknowns with 0= Po S ... S PB 1. In AdwMonot i CNBS(T, at c), for e > 0, our goal is to identify an (r, aI + c)) -good coin (defined in Equation 3). To do so. we may iteratively pick indices i B. Then an adversary selects a probability p. such that lč. -0--p pPl S co, and we observe the outcome of coin flip with heads probability p..
We show that the Bayess algorithm (Bayess abbreviates Bayesian Screening Search) from (Gretta & Price, 2Algo rithm 3) solves the Advonotooii cNBS(T, c) problem returning the (r, + c))-good coin with high probability in B using O( ((1-)) log coin flips. We actually prove a stronger theorem which immediately implies Theorem 3.2.
a²
Theorem E.2. Suppose that < and < min(f, (r, -T}. There exists an algorithm (Gretta & Price. 2024) for ddvMonotooicNBs((r a. c) which uses C..a (log B + O(log//3 log B + log })) coin flpp? and returns (T, + -godd coin with probability at least 1 B.
Namelyy Cr. is the information capacity of the Binary Asymmetric Channel (BAC) with crossover probabilities (7 (7+ - a). Concretely, Cr = max, ((1 4)(7 a) + 4 + a)) - (1 () a) - qff(r + a) with H being the binary entropy function, and Cra = @( ((1(-1)) for a S min(r, 1-177 7).
15

---

Lightweight Protocols for Distributed Private Quantile Estimation
Note that Theorem 3.2 follows directly from Theorem E.2 by setting -1/2 and 8 B-^ for any constant A. With this, the proof of Theorem 1.1 is complete.
Before we delve into the proof of Theorem E.2, let us first describe the idea behind Bayess, described shortly in Algorithm
1. At a high level Bayess proceeds in two steps allocating portion of the coin flips for each step. The first step is a Bayes learner algorithm, called BayesLearn It starts by assigning a uniform prior w([:) to each coin interval 7, = [ + +] for any E [B - II. then takes the 7-quantile interval under the posterior w (I.), selects a coin from this interval, flips it, and updates each (I+) according to the result of the coin flip and the error a. This procedure is repeated iteratively. The sampled intervals are collected in a multiset L, with the guarantee that, after O intervals in I. contains (T, o--good coin with high probability in B (referred to as good intervals). In the second step, this property is used to narrow the set of possible coins (11/)), ensuring that it contains at least one (T, a:)-good coin. Each coin in the candidate set can be individually tested, up to error a, with high probability using O yaz log( R coin flips.
(1++) log log
coin flips, 7-fraction of
C+.a
It is easy challenge in proving Theorem E.2, is analyzing the first part of the algorithm, BayesLearn, in the adversarial setting. The authors in (Gretta & Price, 2024) used stopping time argument to analyze Bayes They defined potential function L with an initial negative value, constructed so that a positive potential implies finding at least y fraction of good intervals. The stochastic process describing the evolution of the potential {#;)==... is then modeled with a submartingale that can be used to bound, using Azuma's inequality, the probability that the process crosses zero after sufficient number of iterations. We prove that we can use the same argument for the case of adversarial probabilities we allow the potential catch approximate good intervals, namely intervals containing (T, a(1 + +c)) c))-good coin.
that in the adversarial setting, the coins be tested up error a(1 + c) in the second step. Our main
New Potential Let {e...., r be the set of (r, (1, + c))-good intervals. Let a be the maximum i E [B - 1] such that P. S T. Let L be the list of intervals visited in BayesLearn. We define the potential function as
(wc L) == logg w(a) + 12C,, (H E L : x E -
-
where w(a) is the Bayesian posterior weight associated the best interval and Cr,a is concrete function of 7 and a. Notice that positive potential implies Hz E L|x E [(,r]]] > 7/L/. hence indicating the presence of y fraction (T, a(1 + -ooog intervals in L. The following Lemma generalises Lemma 7 of (Gretta & Price, 2024) and allows the construction of submartingale.
Lemma E.3 (Adaptation of Lemma 7 in (Gretta & Price, 2024) for adversarial probabilities). For e S 1 and a S min(T, 1 Th the expected variation of the potential is
E E Fely1 yel 2 (1 12,)
(9)
where (Ji...., W)) are the results of the coin toss up to + 1-th sample, and Cr,a θ ((=((()) (I(I_r)
Proof. The proof for the adversarial setting, which allows an adversary to alter the head coin probability at each iteration up to co,, while preserving their order, closely resembles the proof of Lemma 7 in (Gretta & Price, 2024), which addresses the case of fixed coin probabilities. We will go through the steps of the proof highlighting the main differences. An implementation of BayesLearn for empirical quantile estimation, where each user is used at most once, can be found in Algorithm 2.
Let's define the capacity of the (r,a)-BAC (Binary Asymmetric Channel) as
Cr,a = max H( - (T - a) + q(( + a)) - (1 H)H - -
4
9 = arg max H ((1 (1 a) + + + a)) (1- (L=z)l((= a) zH1 + a),
where (p) is the binary entropy. Let's define the multiplicative Bayes weights dz,g : {0.1) x {0, 1} + R. they indicates the multiplicative effect of a flip resulting x (1=Heads, 0=Tails) on the density of an interval on side y (I=Right, 0=Left) of
16

---

Lightweight Protocols for Distributed Private Quantile Estimation
Algorithm 2 BayesLearn for empirical quantile estimation, from Algorithm 2 in (Gretta & Price, 2024)
function Get_nnteraa
2: return min E [B] s.t. ( 2 q with W(x) EiE(I,....)) w(i)
3: end function
4: function RouncInteervalloooiniii w,4)
5: return if (-(1)1)
((3) < else 141 with W(x) = Die w(i)
6: end function
7: function BayesLearn B, a,
8: w1 + uniform((1 1))
9:
- arg max, =(( - - (1-x) -r))) -
-
10: I + O [Multiset)
11:
for E [M] do
Ji - GelinteervalPPoomnuntttteddeo,,
G RoundInterval W, 4) {Gets the coin from the selected interval)
14:
I. - [ú)
15:
ai {uu)==I,... (Sample user]
16:
faxtR=l.... + f= \ {ær} (Remove the user from the dataset}
17:
Yi - [ S c4] {Flip the coin)
(x)
i E {1, (s.
18:
(i+1(x) +
d - Wi(is 1)) + (...((W(())) 1) if = j: (
if E ( + +l...., B
end for
20:
return L (Return multiset of intervals]
21:
end function
the flipped coin.
1 T - a
dop0 =
1 - T (2g - 1)a
1- +
do.
T (2g 1) 1)
T T a
d1,0
+ (2q 1)a
T a
d1.1 + (2q 1)a
We will mainly use the results from Lemma in (Gretta Price, 2024) that states that
C, = (r + at) log, d1,0 + (1 - T a) log, do.0:
(10)
Cr, =
log, d1,1 + (1 T a) log, do,1,
(11)
with the fact that d1,0 2 do and d1,1 S do,1. Recall the potential function: let (e....,r) be the set of (7, (r, ()) good intervals. Let be the maximum i [B 1] such that pt r. Let L be the list of intervals visited in Bayealearn.
Let je be the interval chosen t-th round, and let be the index of the coin flipped. Let pL, pt (we will discard the coin subscript) the probability of the selected coin at time t. We split the potential in two addend
12CT.a E L|æ E re. -l)
(12)
logz w(a)
(13)
The main difference with the proof in (Gretta Price, 2024) is that a good coin is defined on the initial probabilities hei.he.....B but at the t-th iteration we only have access to coin with probability {p:)= However, they are concentrated around a, lp p'1 co for S
17

---

Lightweight Protocols for Distributed Private Quantile Estimation
Bad Queries: Consider je $ re. If je r, then p¹ + (1 + c)a. As have that Ip* pl1 car also have p² p- ca 2 - + c)a ca r + a. The expected change in the weights is
E E|log, (a) log, wy (a)] = pz log2 d1,0 + (1 - p²) log, do,0 2 C,
Where the last inequality comes from the fact that the expression is minimized as p¹ + and Equation 10. Consider now je < L. then p' (1+ c)a, which means p² - p² + ca S (1+ c)a + ca = 7 - a. then
Bloog (a) logg wy wr(aa] = p' log2 d1,1 + -1-1p') log2 do,1 Cr,a+
where we reach the minimum Cr.a when p' = a, due to Equation 11. As jt & [e the change in Equation 12 is -Y- 1--2,,,,a Therefore, on bad queries the expected change in is at least (1 - 12y)
Good Queries: Let's consider the expected change in Equation 13 when jt E [e. r). Consider the case where jt o a, then the expected change is either
y' log2 d1.o + (1 11-pp loga do,0 if a is on the left of jr. so p² 2 - 1¹ 2 T COE
p' logg d1,1 + (1 - p²) log2 do,1 if a is on the right of j.. so pd < + p' S co
The first expression increasing in p' while the second is decreasing, therefore the expected change least
min {(T cax) log, d + (1 - r + ca) log, do.o: (T + ca) logg d1, + (1 - ccx) log2 do,
(14)
Let's consider the first argument of the previous expression
(r ca) logz d1,0 + (1 - T + loga do.0 = (r + a) log2 d1,0 + (1 - - - a)) loga do.o - a(1 + c)ogg d1,0 - logz do,0)
CT.a - a(1 + c) (log, d1.0 - log2 do.0)
(as d1.0 2 do.0)
20
2 Cr 20( d1,0 logz do.0)
(as 1
2 Cr 2(6 log 2)C
2 -1CCr.a
where in the first inequality we used the fact that $ 1 + (1 + c)a S 2a, while in the second inequality we used Lemma 10 and Lemma 13 in (Gretta & Price, 2024), valid for a 2 minn 1 r). Analogously, for the second argument of Equation 14 we get (r + cax) logg d1,1 + (1 - - -co)loog, do,1 = (T aa) d1, + (1 - J + ax) logg do.1 - (1 + e)a (log, do, loga d1,1)
20
2 -111
where the inequality follows by an analogous computation. Therefore, the change of the weights when jr + a is in expectation at least -11C when c E [0, and a I 1/2 min(r, 1 T). Let's consider now the case where je = a, the expected change is
p' logz(di, okk di,
k)) (1 p²) logg (do.ok do (1-1(1-A)) k)-
(15)
for some l: E [0, 1]. We have two cases: l: S q or k > q. When S the coin flipped is a then p² < t and so p < r + co.
in (Gretta & Price, 2024) was shown that in this case Equation 15 is decreasing in p², then the minimum is
(r cn.) logg(d1,ok: + (1 k)) + (1 T - ca.) (dgz(da.kk k + do - k))
if S
(16)
Conversely, when k > q the coin flipped is a and then p² 2 r so p¹ 2 r - ca. this case the expression (15) is increasing in p' so the minimum is
(r - ea:) logg(d1,0d + (1, - k)) + (1 - + ca) log,(do,k + do (1)))) R))
if >
(17)
In (Gretta& & Price, 2024) the authors demonstrated that the minimum obtained when k {0, 1}. Therefore, for k = >>> q we have Equation 17 while for k = 0 < g we have instead Equation 16, which means that the minimum is
min ((T - ca)) log, d1,0 + (1 - r + cor) log, do ; (7 + ca)) log, d1,1 + (1 - - ca.) log, do.1)
18

---

Lightweight Protocols for Distributed Private Quantile Estimation
which is at least -11C as demonstrated for the case ji * To conclude, the expected change in Equation 12 is least
12Cr,a - 7), then the overall expected change for the potential is least 12Cr,a -7) -1C (1 11-11 1-12 Cr, cocnluding the proof.
The previous Lemma is the building block for the analysis of Bayes aea rn, as it allows the construction of a submartingale (Yi)==,,.. with Y D:+1- gt. for g = (1 12y)Cr,a that can be used to bound the probability to have a y fraction of good intervals, hence positive potential. The analysis then follows directly from (Gretta & Price, 2024) with the distinction that the algorithm now with high probability in B returns a (T, a1 + -))-good coin, so proving Theorem E.2. Since the proof is identical (see Lemma 6 and Theorem 1 of (Gretta & Price, 2024)), we omit it. However, in order to make this paper self-contained, we will show simple proof of Theorem 3.2 (which is much less general than Theorem E.2), We restate the theorem here.
Theorem E.4. Let 0 < S and suppose S There exists an algorithm for AdvMonotonicNBss( which
uses
O
log B coin flips and returns an (1/2, at1 + e))-good with high probability in B.
Proof. Let & be the potential function in Lemma E.3 in the case T = 1/2. Given Lemma E.3, by choosing 9 (1-127)C1/2. equal to the lower bound of the lemma, we have that [Yi) for Y(+1 = $ p++1 gt. , a submartingale
E| 11, Vt] = E[ 1 1y1................... Vol gl = =B[0,+ 1
x Ny+Ye Yv 2 Y. y1
2g
The difference of the martingale sequence (Y+1 Yel is
1++1 Y/ - logg w (a) logg we wx(aa] + 1/,1 + S |log2 w++1(a)
logg wx(a)) + O(a²),
by triangle inequality and C1/2,a = O(a²) for a E 1041 due to Lemma 10 (Gretta & Price, 2024). The remaining term
log (c) log (a)] S max log d1,0, log ) S O(a) for Lemma 13 (Gretta & Price, 2024), thus |Y - Yil S (ax). We can use Azuma's inequality to bound the probability of having a negative potential
Pr|B.+1 S 0 = Pr[0.+1 gt - 1 S gt +11
= Pr[Ye+1 - Yo S -gt [1
(gt + 11)²
< exp
for gl 2 -1.
1. 0(22)
Note that + = - log( - 1). Therefore, picking T = =0 log any desired constant 0. Thus,
sufficiently large, we get that (gT+0,)² T-0la") 2 > Alog B for
Pr(0 S0 < B
On the other hand, note that if T O, then
ΦT+1
0 < 12C1/2,a
< <1 [e,
order the intervals in L in sorted order according to their indices i of the corresponding coins. By picking subset S of every (1/7)th of them, we are ensured that one of them will be good (conditional on the high probability event 47+1 >> 0). For each interval in S, we can test whether it is (1/2, a11 + -goog with high probability using O [) coin flips of each of the coins at its endpoints. Therefore, we successfully determine an (L/2,a(1 + e))-good coin with high probability in B. If we pick 7 1/13, the total number of coins flipped is
and so, y fraction of the intervals in L are (1/2, c)) el)-goodd Now
+ |5
log B = 0
log B
+ 0
log B
= o
log B a
a²
9
a2
where the final bound uses that g = (1-11) (1-112
= 1 C1/2, =))2). This completes the proof.
19

---

Lightweight Protocols for Distributed Private Quantile Estimation
F. Lower Bounds
In this section, we give the proof our lower bounds: Theorem 1.2 for adaptive mechanisms, and Theorem 1.3 for non- adaptive mechanisms. Since an algorithm for the median problem implies an algorithm for a general quantile by inserting dummy elements, we will correspondingly show a lower bound for the general quantile problem, demonstrating that all quantiles (not too close the minimum or maximum) and -attempp-uantiiii ile with the additional parameter y to describe the corresponding generalizations.
hard as the median. We use the notation LDPst -quantuuttttt
E.1. Adaptive Mechanisms
In the statistical setting, our building block will be the lower bound framework in (Duchi al., 2013), which turns the estimation problem into distinguishing problems. In our setting, it means that if mechanism attains low error on the quantile problem, then it is good at distinguishing distributions with different qth quantiles from each other, even from a "hard" family of distributions. Our hard family of distributions will be close in statistical distance, but still have different gth quantiles:
2a
Pa(i) = 4a
i = 3
1-9- q
2a
B,
for 3 E log(B) B3 bits of information (measured with the mutual information), by Fano's 's inequality. However, there is an upper bound on the amount of mutual information possible with an LDP protocol, as first established in (Duchi et al., 2013). This gives us the following bound:
If 22..
2].
is chosen uniformly at random, then our LDP distinguishing mechanism will be able to deliver
Theorem F.1. Let B 4, a < f. E 1, and q E (2a, 1 2a). Suppose there a sequentially interactive s-LDP algorithm that for any distribution DD solves LDPstat aDPstat-quantiii e(D, n, a, e, 9) with probability at least 2 Then
log B
n 2 Ω
2a
(MI...., Mn) be a sequentially interactive E-LDP protocol which solves LDDstat-qqantt uDDstatt-qunttleeD.. E, with probability 2 1/2, i.e., for a distribution D and n samples 21,..., Zn from D, it outputs an estimate m M.. (n) which is an a-approximation the median of D with probability at least 1/2. Consider the following collection of distributions {Pp} sE(B)) indexed by parameter {l,..., B - 1}, with probability mass functions defined by
Proof. Let M
2a
= 0
Ps(1)
4a
B
q 2x
i= = B - 1.
Let 8 be uniformly at random from {1...., B 1--1 -1. and generate n samples T1,..., Tr from Pg.. Let 3/ M,(3;, -i,..., V4-1) be the e-differentially private output of user generated in the manner of in the manner of (2). Finally, let m.- = Fly....., Vn) be the estimated median output by our protocol. By Fano's inequality,
1(3 ((3:v1.. .i....,,,,. ..)) 2 H(3*) H1 8*1)+
Prrma-- + 337 logz( B - 1)
> logg (B) - 11 log(B (B - (B)-
log,(B).
where / denotes the mutual information and H denotes the binary entropy.
However, using the fact that our mechanism e-LDP, we can use the upper bound from (Duchi et al., 2013) on the mutual information between (y1...., , }n and 9*. According to their bound (see the calculations following Corollary of (Duchi
20

---

Lightweight Protocols for Distributed Private Quantile Estimation
al., 2013)) for all e < 1, have
T(8" , Un)) S 4(c - 1 n
Σ
[Pg 1arPPpriie 1av..
B²
Note that the total variation distance between Pg and Par for Pp + 3 is 4a. It follows that,
I(3" ;......,nn - no
Combining inequalities, we see that log(B) < 1024=2a²n which implics that n = 2 lox go ) as desired.
To adapt this to the empirical setting, observe that any algorithm for the empirical problem can be used to solve the statistical problem by sampling, and then applying the empirical algorithm.
Theorem F22 Let B 2 4, a < 2.2 and q E (2a, 1 - 2a). If S min(1, a Vlog B), then any sequentially interactive E-LDP algorithm that solves LDDemp-quantile((::)).) 0,E,9) with probability requires 92 ( 2a
Proof. We will first show any algorithm .M which solves 1 E, with probability å can be used to solve L.DPstatquaant e 20x, e, with probability 3. The algorithm will simply apply M to the sampled dataset {-I,..., In J==1 from D. Using Hoeffding's bound, together with the fact that 2 2 the qth quantile F(g) of the sampled dataset will have quantile error at most a from the true qth quantile of D with probability at least 3 Thus, the correctness guarantee of M carries over, with success probability at least & by the union bound.
Using the above reduction, we are able to show lower bound of 2 2 efa so long as these log( 1024"*
2 a²
is satisfied.
Theorem 1.2 follows directly from Theorem F.2. These lower bounds establish that our algorithm in Theorem 1.1 tight in the (1) regime.
F.2 Non-Adaptive Mechanisms
In order to prove non-adaptive lower bound of Theorem 1.3, we will apply a lower bound for learning a cumulative distribution function from (Edmonds et al., 2020). The CDF learning problem is defined as follows:
Definition F3. Given a dataset X {z1, ....,..,... } [B], let (1) denote its c.d.f. (given by Fx(()= + 1 7). In the LDPemp-cdff (z; ) e) problem, the task is to output a function F under e-LDP which approximates the c.d.f. up to error alpha at all points; i.e.
E B|| Fx loel S a.
Observe the above definition considers the expected error, which different from applying Definitions 2.3 or 2.2 with constant probability of failure. We change to expectation because it is the setting considered by (Edmonds et al., 2020), but may casily convert between the two types of guarantees (since the maximum c.d.f. error is 1, we only need failure probability of a to obtain a bound on the expectation).
lower bound on n for learning a c.d.f. was shown in (Edmonds et al., 2020) for < 1:
Theorem E44 (Theorem 23 in (Edmonds et al., 2020)) There exists a constant C such that, for all a sufficiently small, and all م..z any e-LDP algorithm which solves (DPemp-cdf((z;)) a,E)
(B) Clog(2B)
< 1 and B satisfying z2 log(1/9) (1/a)² a2
requires
(B) c2 log(1/a)
2 Ω
In particular, it is sufficient to satisfy Theorem E.4 when a 2 B (21(1) and S are constants typically significantly less than B.
which is a mild assumptions as a, [og[1/a)>
Vlog
To apply this theorem, we prove a reduction from LDPemp-quantiin for constant to LDPemp-cdE. The c.d.f. may be solved to accuracy a by computing the a, 2a........................ a quantiles. With correct padding, we may use our
21

---

Lightweight Protocols for Distributed Private Quantile Estimation
uDPemp--uanttii ill le algorithm answer any of these quantiles. To answer all 1 quantiles, our reduction uses non- adaptivity in a crucial way: it only necessary collect responses once, add in the proper amount of responses for padded elements, and then post-process them into response. By boosting the accuracy of the quantile with log(2) runs, each quantile estimate will have success probability at least 1 - a². We may then apply a union bound to obtain a bound on the expected error on all quantiles (giving the desired c.d.f. error).
Lemma F.5. Suppose there is a non-adaptive algorithm solving L.Demp-quame i (e((x)) a, e, with probubility T for all datasets of size n Z no- Then, there is a non-adaptive algorithm solving LDPemp (aif(()))= a(1+)) 22 log with probability 1 for any datasets of size n. 2 14g
3
Proof: WLOG, we may assume that S 2. Suppose we are given dataset {z1 1--1 We will first show how to estimate 3 and error .. We may do this by adding padded elements to the dataset. any quantile of with success probability at least {
Specifically, if q < g', then adding z=9n padded Bs to the dataset will ensure that the qth quantile will match the q'th quantile of the original dataset. If < q. then adding '-4 n padded is to the dataset will ensure the gth quantile will match the q th quantile of the original dataset. Observe that quantile error of a in the padded dataset corresponds to quantile error in the original dataset. q
Next, observe that computing the quantiles {a, 2a, ..... . 1- a with error a gives a 2a c.d.f. estimation. We will simulate running the above procedure on all 1 quantiles by collecting the responses 11 -M((xr),.... (I, In = (M.xn), and then may post-process
rf = r!
(B) for + S i S n + 7. the response to obtain an estimate of any q'th quantile with error at most a This crucially uses the fact that the M are non-interactive, as any state shared between the M, could not be simulated for all runs at once.
g- By picking the correct padded elements,
q'
Each of the above estimated quantiles has error a with probability least - We may boost the success probability by q 1 times and taking the median quantile estimate; by Chernoff's bound, running the above procedure independently 2 log(( a
we are guaranteed that each quantile estimate is at most e from the true o' quantile with probability a². By the union bound all quantile estimates will have error a with success probability least a, and the expected c.d.f, error at most - (1 a < a(1 + )). Finally, the privacy parameter is 2s log( ) by simple composition.
Theorem F.4 and Lemma F.5 together give us lower bound on the median error under LDP:
Theorem F.6. For any constant E (0.1, 0.9), any a sufficiently small, e < log(1/a)) and B such that a 2 B-1(1)
and E <
Blug Togll/a)z, any e-LDP algorithm which solves LDPquantile seeeaanteeeeee(((ee -mp(( a,e, q) with probability at least?
requires
(B) n n2 Ω =2a2 log( log(1/a)))
Theorem 1.3 follows directly from this result.
G. Naive Shuffle-DP binary Search for the Median
This section is dedicated to proving Theorem 1.4.
The naive binary search with errors algorithm Algorithm 3 tests each coin up to a-accuracy and a 3/gog B failure probability, such that a simple union bound over all log B steps of binary searching will yield an (a, -aacuuraeee estimate. This algorithm is suboptimal up to logarithmic factors, although there are indications that its strong constant factors can make up the difference in some parameter regimes (Karp & Kleinberg, 2007; Gretta & Price, 2024). The simple fact that this algorithm runs in deterministic number of rounds, with a deterministic number of samples per round, allows for a straightforward application of amplification by shuffling (Feldman et al., 2021), something we could not achieve with the fully adaptive Bayesian updates algorithm.
Algorithm 3 provides the functional details of this algorithm, which we analyze below to find the necessary sample complexity for desired accuracy a and failure probability 3. The shuffler is not included in the pseudocode, as it has no effect on the accuracy of the algorithm. To compute the final sample complexity, it will be most important to prove how accurately we can learn the bias of one coin at each step of the algorithm. We give a tight characterisation in Lemmas G.I and G.2
22

---

Lightweight Protocols for Distributed Private Quantile Estimation
We consider both statistical error, where samples are assumed be drawn from some unknown distribution with mean p. and interested in an estimate p which is close to that true mean, and the empirical setting where make no assumption on the distribution of the samples, and are interested in how close our estimate p is to the "best-case" sample
mean
Ei=1 Zi--
Lemma G.1 (Sample complexity of learning one coin to its statistical mean.). Given samples {2, from Bernoulli random variable X with mean p received through a binary randomized response channel M such that yi ~ M(x;), we can T- In order to learn an (a,, -estimate of p. Pr[lő pl > oj < 8 it suffices to use
1e++1 estimate P = o Ei=1 1/s
samples where,
(200--)) 220(1 Pp a²
2(e +1
n S
a2(ee - 1)3 4ate -1] log(1/3).
+
In other words, the sample complexity of learning one coin its statistical mean with constant failure probability is pl _ when 2 1.
0 x= - when < 1, or O
Proof. Given Bernoulli random variable x with mean p. and binary randomized response channel M (see Lemma A.1) the distribution induced by applying M to is:
y = M(x) Bern (- e +
o T (1
p)
1
e Bern
6 +5 p+ 1+ x+1)
+1
The variance of this distribution is
+ 6 6
e e
0² = Var(y)
= e +
E ++1p)
e +1 e +1
e +1+ (
6 -1)
2
ec
p(1-10 - p)
(e + 1)2
We then proceed by simple rearranging, substitution, and application of Bernstein's 's inequality Theorem A.3.
1 E
e
- e
1
Pr [10 pl > a] Pr
yj
E [v]
> a
6
Pr
e 1
1
Σ
n
V/
EE [w]
> a
71
1=1
1 n
Pr
11 Σ
E
[w]
>
( c++1
1=1
n212
B < exp
(Bernstein's Inequality)
20t
+
21
3
20
2
n <
log(1/3)
12
31
2p(1
p)
2e
2(e +1) +
+
3a(e - -1) log(1/3).
(Substituting and 2²)
a
1)2 022(6-
Lemma G.2 (Sample complexity of learning one coin to its sample mean.). Given samples { where each x; E E(0,1) 1). and private outputs y; MMxx), the true sample mean is n Ei= Z4. Denote the sample mean the collected private outputs Y Σn yi- Our estimator of the sample mean will be similar to the statistical case, where P = e - In order to learn an (a, -)-tstmeee of P it is sufficient to use n samples such that
2et
2(e + +1)
<
+
3a log(1/8).
a²(c" 112
23

---

Lightweight Protocols for Distributed Private Quantile Estimation
Therefore, the sample complexity of learning the sample mean with constant failure probubility O ( when or O (ater) when 1. It is pleasing to note that this recovers the sample complexity of learning in the statistical case, up to the additive sampling ervor.
The key difference will be the variance of in this case which Proof. The proof will proceed similarly to the statistical case.
is
8² = (=)) =
= (ee 1)2²
The derivation then proceeds as in the statistical case.
Pr| - Pl > a| = Pr
Y
P > a
e
e
6
e +
Pr
Y
E Y
oF -1 1
>
e
-1
e -
c
Pr
(Y
E [Y])
> a
Pr
Y E M
>
t- a cf 2541
- nt²
S exp
(Bernstein's 's Inequality)
2x +
20
2
5
log(1/3)
122
2
2(c + +)
3a(e - 1) log(1/3).
(Substituting and σ²)
a2(6 - 1)2
With this we can now formally state the sample complexity of naive binary search for the median under local differential privacy. We will focus on the empirical case for this result.
Theorem G.3 (Naive Binary Search for the Median under Local Differential Privacy). The naive algorithm described by Karp& & Kleinberg (2007), under the constraints of e-local differential privacy, has sample complexity
2
+ 2(e + +1) 3a(e -1] log( (B) log
log B B
n
a=(e - 1)2
We can therefore say that for 1, the naive approach has sample complexity O log sample complexity
log [log 3
)) and for e 2 has
a
lug de
log
log B ))
Proof. Given n total users, let n' n/ /ogo((() B) and let B B/ log B),, apply Lemma G.2 with n', 8 to get sample complexity.
a2(e= 1)2 + 2(e + 1)
2et
log B B
n
3a(e log( B3) log
By union bound over all log B rounds of the binary search, the final estimate will be an (a, aaproxiiioo median.
As stated in the introduction, the primary motivation for this approach is that by dividing the algorithm into few deterministic stages, with many samples tested at each stage, we can hope apply amplification by shuffling (Feldman al., 2021). We state the amplification by shuffling result here, and a subsequent lemma that will be useful our analysis.
Theorem G.4 (Feldman, McMillan, and Talwar (2021, Theorem 3.1)). For any domain X, let M : M X.x... ......MM-.1 XX + y for t [n] be sequence of randomizers such that Me(yha-1.)) E clooo DP; and let be the algorithm that given
24

---

Lightweight Protocols for Distributed Private Quantile Estimation
tuple of messages, oulputs uniformly random permutation of said messages. Then for any å E (0, 1] such that EL S log (oloū(2/8) S y is is (e, 5)-P, where
))
1+8 c -1
C looooo//// (4/(4/) E 71
E $ log
+
E +1
n
This implies the following useful lemma, Lemma G.5 (Amplification by shuffling). Fix any E (0, 1], & E (0, 1]. and n such that e > 16/log(4/5)/m Then, for
=2n
EL log
80 log(440)
Shuffling the messages of n users using the same e LDD randomizer satisfies (c, 8)-suffeee differential privacy.
Proof. For e, å and ez as above we have < EL. S log 16log(275)
Applying Theorem G.4, we get (6', difffeerent
privacy for
c 1+8
e' < log
SE
eci. + 1
v 80
80 log (4/8)
<e/8
Proving the lemma.
We can prove Theorem 1.4.
Theorem G.6 (Restatement of Theorem 1.4). Let log, B. There exists a protocol for shuffle-emp- -eedi -median e, 6, with success probubility 1 B provided that
n n
(12 log BogB, By log(1/6) log 3
log B
The protocol has logg B rounds of adaptivity and queries shuffled batches of n/ logg(() users.
Proof of Theorem 1.4. Take the sample complexity achieved Theorem G.3, and note that we in the >>> regime as we will be applying taking εy E Ollogn) n.). We therefore have
( log a
log B
n =
log
8
We apply Lemma G.5 while noting that at each stage we shuffle n'' = n/ log(() (B) users. Setting EL = log so log (B) (0g(4/8) and rearranging gives that for each step of the binary search have enough users to accurately learn the CDF of the remaining suffix of users within error a/2 with probability B/ log B. Union bounding over all log B steps of the binary search, we conclude that with probability - 3, every step succeeds. This gives sample complexity.
2nn
n= =
(Log B aE
log(L/0) log 8
log B
but we are not finished. We have handle the multiple restrictions on parameter regimes
o 0 log B aE
log B
log B log B log (1/5)
1og(1/5) log
2 max
3
a2
22
25

---

Lightweight Protocols for Distributed Private Quantile Estimation
Algorithm 3 Shuffled Noisy Binary Search for quantile estimation.
function (RRg(X)
2: return X w.p. e*+1 otherwise -X
3: end function
4: function Shuffled Noisy Binary Search([a]] B, T,E)
5: X + x(f;;)= {Random permutation of the users)
6: z' + log 80 log(4/8)
7: r + flog B) (Number rounds}
8:
s + n/r] (Batch size}
9:
L t-1 1
10:
R B
11:
for -1,2..... do
12:
m + L + +(R L)
13:
Sj + X (((--1)s41 {Sample one batch}
14:
{-) 0
15:
for k = ., do
16:
yk t [S S ml {Query}
IK RRd (Apply Randomized Response with e'}
{+ E Uk
end for
20:
p+ e ---15
f < T then
22:
L m +1
23:
else
24:
R - m
25:
end if
26:
end for
return m
end function
The right hand side of this inequality comes from restrictions present in Lemmas 3.1 and G.5 on n and e respectively, the latter comes from using n' n/ lBg(B) in the restriction on E. trivial solution be take 1/(aE) and replace it with 1/ min (a² {),, which gives
+ ( log B 1og(1/5) log log B
n = o
8
This result has improved dependence in and and could be preferable from communication perspective. Rounds of adaptivity are restricting factor in distributed learning, and our goal was to understand the trade offs possible under privacy constraints. It is of practical interest to know whether the constraint on n Lemma G.5 can be improved from n = Ω (log(1/ (o)(()))/e²) to Ω (log(1/)//)) This, in combination with a strengthening of Lemma 3.1 to have a linear dependence on a, would allow the analysis to go through with only a (/s))) dependence.
H. A Note on the Continuous Case
If we replace the discrete domain [B] with continuous one, say [0, 1], it is generally impossible to obtain quantile error o(1) using finite number of samples under LDP. This follows from our lower bounds by discretizing [0, 1] into [B] buckets and letting + cc. In fact, this is general issue for quantile or range estimation problems in DP (even beyond the local model), which is why related work studies the discrete setting (Beimel et al., 2016; Bun et al., 2015; Kaplan et al., 2020; Cormode al., 2019). On more positive note, if we impose mild guarantees on the family of possible distributions the
26

---

Lightweight Protocols for Distributed Private Quantile Estimation
Algorithm DPBayeSS for empirical quantile estimation with local differential privacy, from Algorithm 3 in (Gretta & Price, 2024)
1: function ReductionnoGammaa(1a1
B,,,,,,,,) B, z. a, M, {From Algorithm 2 with C-RR on each coin flip)
2: L + (PBayesLearn((z:)
3: R - [Get the q-qunntlles of L}
4: for [+|4] do
5: append 41) to R
6: end for
7: return Bertteee/eeeeeeeelllltttteeeee
8: end function
9: function (f B,
MB, +
logt
Hogg (B)-1
11:
MB.*
log( (B((B)++nng log( (B)-1
log (B)
12:
â 0.6
log B (Hyper-parameter obtained empirically in Section 1.1}
n
13:
R + ReductionToGamnss ((::))=t.....M,, B,
ing
if | > 13 then
R [1] + R+ [n] (Pad Rt with the extremes of the initial problem.
16:
E, 13) {Reducing R to fixed size |R| S 13] R ReductionToGamaeeiitmm. (= Mn, +M, R, E,
17:
return Apply WoisyBinan na narySearch with s-RR over the coins in R using dataset (xi) Jiri)ima Ma, + Mag l.... 10
find probability closest to
18:
else
19:
return Apply Nois NoisyBinarySearce with s-RR over the coins in R using dataset {ai +1.... to find probability closest to 1
20:
end if
21:
end function
samples can come from, our result has implications the continuous setting as well. For instance, if we assume that there are (known) numbers -o = yo < y1 <... < yB = oc such that in any interval [e, 11+1]. the emperical CDF increases by at most 2/2, then we can again obtain quantile error a with O 2a0 users using our algorithm and bucketing users in the same interval [ye, Vt+1). As the dependency on B the number of samples logarithmic, this might allow B be quite large, with correspondingly small quantile error a. We note that if the assumption on the CDF is incorrect, only the accuracy is affected while the algorithm remains private.
I. Experiments
All experiments were carried out using an Intel Xeon Processor W-2245 (8 cores, 3.9GHz), 128GB RAM, Ubuntu 20.04.3, and Python 3. We considered the success rate for an error a
1
success rate := Pr Fx < +
where Fx is the CDF of the sensitive dataset and m is the median released by the algorithm, and the absolute quantile error
error = (mx - Fx(m))
the main metrics for our evaluation. Each algorithm was executed 200 times compute the empirical cumulative distribution of the absolute quantile error. As error opted for the standard deviation of the sample average success rate, calculated as:
p(1 - p)
1
200
where
p =
Σ
Fm(m))
+a Fx + +1) 2
200
200
27

---

Lightweight Protocols for Distributed Private Quantile Estimation
Data Generation The income dataset was generated using a Pareto distribution p(a)) Z well studied distribution model income data (Amold, 2014). We generate
(2500, 5000, 7500) positive integers by sampling from the continuous Pareto distribution with shape ? 1.5 and multiplicative factor 2000 and then rounding them. For different coin domains [B] we clip the dataset to get integer values in [B]. To compare DpBayeSS and DpNaiveNBS across various coin domains [B] for a fixed privacy budget, we generated n = 2500 integers by sampling from a uniform distribution over a random interval within [B]. This approach avoids having the median around B /2, which would make the problem too straightforward.
Implementation Details once.
These mechanisms are run across the entire data set, which means that each user sampled
DpNaiveNBS a standard differentially private implementation of noisy binary search introduced in (Karp & Kleinberg, 2007), where each coin flip is privatized using randomized response with E privacy budget, which we call RR. It searches for the coin with probability closest to 1 using a standard binary search. To estimate a coin probability, it samples without replacement batches of size b = TTgg Toga BT then redistributes the remaining samples
2.
[logg B b by adding one sample to each batch starting from the first. Due to randomized response, any empirical probability ei+1 Pe = Σ Eeaatc RR (Ir I cl) is unbiased P.- e- (Pe 1 before confronting with 1 2-
DpBayeSS is implementation of Algorithm 3 in (Gretta & Price, 2024), with some minor changes (7 is set to 1/13 in line 11 of Algorithm 3). where each coin flip is privatized using randomized response. The algorithm runs at most two DpBayesTear (a differentially private implementation of Algorithm where each coin flip is privatized using randomized response) and further makes use of iveBBs on the remaining coins to get the one with head probability elosest z. The sample budget n is divided into M MR, Mn, for the two DpBayesLearn and Ms Ma for the DpNaiveNBS The split satisfies the following ratios suggested in (Gretta & Price, 2024) Mez
log B log log B
Ma
= log B, and Ma² log log B. Ms
Mg
BayesLearn is designed to take as an input for updating the weights during the Bayesian learning step (see Algorithm 2), hence it assumes a sufficiently large number of users. To reverse this approach, so using n as input, we empirically determine the minimum value of a achievable by the algorithm. For DpBayesLearn and E < 1 we showed that to get an error a we need to solve for an error ā us For a fixed n, the error cannot be smaller than 8
a 8c Mlgg for some constant > 0, therefore we have that ā 2 cv EVA
We analyze different values of c in the selection section in order to get value of e such that the algorithm, with à = =cy log better results. For completeness and full reproducibility we provide a pseudocode of our implementation in Algorithm
log B
n gives
Hierarchical Mechanis sm is built according to (Cormode et al., 2019). Essentially, we constructed tree with branching factor equal to 4 and at each level we store the 4-adic decomposition of [B]. For example, if B = 49 at the 451, [2 4 + 1,..., 3- 45], [3 48 + 1...,, 19],, while on the leaves are stored all the possible singletons. Each user selects a random level of the tree and reports its position using unary encoding (Wang et al., 2017: Cormode al., 2021). For this LDP protocol we used the public library at the following GitHub repository*. After filling the tree, we computed the whole cumulative distribution and released the coin with closest value to _
first level of the tree, composed by four nodes, is stored {[1,.... 4 [4 + 1,..., 2
'https://gi thutb com Samuel Maddock /ptree/ueeaa LDP
28

---

Lightweight Protocols for Distributed Private Quantile Estimation
0.02
Bus 0.06
C-0.50
c-1.50
0.7
0.6
0.8-
0.8
DpllayeSS 0.100
Dptayyed 2.311
Opsaye5S c-
Success
0.4
0.6
0.6
Dpllayess
Opaayc55
Dp5ayr55 c-1.16
0.3
Upsaya55 c=1.77
OpSayc55 c- 1-8
0.2-
Eydiayess, not 3.5
0.2
0.2
Dpdaya65
Dpíaayess 1.29
Cydleest axe
0.0
0.0
0.0
1.0
0.00
0.02
0.04
0.00
0.02
0.04
Constant
Emor
Erer
Success rate constant
Cumulative distribution of absolute error
(a) Experiments for 2500 and B
4
Sist 0.02
Ous 0.06
c=1.50
1.0
1.0
0.8
DpfasyeS 8.10
Dpilaye55 p.31
DpSayd53
0.6
0.8
Dpfayess 0.7.33
0.6-
Opsaya55 c-9.4
0.4
Dpaaye53
Opdayad5 cm1.37
Dp5aya55 c=1.88
0.2
0.2
Dpllaye5S 1.7.
Updaya66 c+2.00
0.0
EpinyeeS ept 1.5
0.0
0.0
0.00
0.04
0.02
Constant
Success rate vs. constant
Cumulative distribution of absolute crror
(b) Experiments for 5000 and B =
4
Figure 2. Experiments estimate the best constant compute Cuupdate CV
log B
I.1. Hyper-Paramette Selection
To determine the optimal parameter for updating DpBayesLearn given fixed number of users n, coins B, and varying privacy budgets e E (0.5, 1, 1.5), we conducted experiments using DpBayesS with different update parameters Olupdate
ev log These experiments were performed on two distinct datasets generated by sampling from Pareto distribution, the outcomes illustrated in Figure 2. By analyzing different Owe values and the error distribution across various privacy budgets, we observed that the algorithm performs poorly c 0.1. However, within the range [0.3, 0.7). the performance stabilizes and the precision decreases for e > 0.7. Therefore, effective range for the parameter is [0.3, 0.7). Based on this analysis, we chose to use = 0.6. We note that our analysis is tailored to the high-privacy regime; however, in practice, this constant also yields well well-performing algorithm for 5.
29

---

Lightweight Protocols for Distributed Private Quantile Estimation
DpBaye5S
DpNaiveNES
Betaye55
DcNavoNoS
0.03
0.05
0.50
10
1.0
0.45
1.-
Succers rats
0.40
0.35
0.5-
0.30
0.4
14-
0.4
62-
0.20
0.15
10a
10"
10'
10
107
10
10
10
5.0
0.25
0.30
6.15
0.30
025
0.66
6.55
6.6
5.15
020
025
636
335
arror
Success rate vs. coin domain size B
Cumulative distribution absolutc error
Experiments for 2500 and
0.5
DpBaye5S
DpNaiveNes
Obatt 0.03
Sioet 0.05
10*
10*
0.9
0.7
Success rate
0.8-
0.6
0.7
0.4
2.4
0.5
0.4
16a
10a
10a
10F
0.000 0.05 3.050 6.11 0.002 0.22
5.100
0.00
0.08
6.33
025
enor
emor
Success rate vs. coin domain size B
Cumulative distribution absolute error
(b) Experiments for n 2500 and
Figure 3. Experiments dataset obtained by sampling random integers random subset of [B].
1.2. Comparison Analysis
In Figure we run the three algorithms two Pareto like dataset with n = {2500, 7500} and = {49, with various privacy budgets = E [0.1, 5]. We observed how the adaptive mechanisms DpBayeSs and DpNaiveNBS veNBS outperform non adaptive mechanism such as Hierarchical Mechani sm. This superior performance is not surprising as the former algorithms are tailored specifically for median estimation. In contrast, Hi Hierarchical Mechanism constructs differential private data structure capable of answering any range queries with error of polylog( (B). From our results it is clear the DpBayeSS is more likely to return coin with low quantile eттоr than DpNai VeNBS, both for E < 1 and > 1. This result aligns with the findings in (Gretta & Price, 2024), where the authors conducted experiments demonstrating that Bayess can achieve the same error rate as NaiveNBs (algorithms without randomized response) using fewer coin flips and, consequently, fewer user samples.
We conducted further experiments evaluate the behavior of DpBayeSS and D ivNBS for different coin domains [B]. The dataset is obtained by sampling (103, 10 103, 10%). The main results are listed in Figure for two different privacy budgets (0.5, 1]. We observed that DpBayeSS is more stable than DpNa iveBBS for different coin domains, and offers good utility for realistic privacy budget and error (e.g. for Csest = 0.05, = 1, and n 2500, DpBayeSS returns a good median with probability higher than 0.8).
2500 integers uniformly from random interval in [B], for any B
30

---

Lightweight Protocols for Distributed Private Quantile Estimation
DiMeNcMEs--O Stafte
DENIAARES STOTI
Rua 0.000
5,00225
20.10
e0.5
1.0
1.0
64
6.
Succes
0.4
6:2
02
Boo
Ouy
1.21
6.2
SAC0000 1305
0.4
6:3
0.6-
0.5-
6-4
0.2
10
100
8:3 107
0.003
5201
6:302
0:33
0.0
6000 (E6S DOUE 0528
0.011
0.0025
22.10
3.224
3.2
3.5
1.0-
0.8-
S00000
6.2
0.2
02-
10P
0.0000 e01s 0,0000
8,0000
budget
Success rate vs. privacy budget
Cumulative distribution of absolute error
Figure 4. Experiments for = 10" and B = 48, with 5 = 10 for shuffle DP
L.3. Noisy Binary Search with Shuffling
When the number of users n is sufficiently large, noisy binary search with shuffling, as described in Section G, can be implemented. The implementation mirrors that DppaaieeNBs but the privacy budget εRR for randomizing the coin flip is determined हжर log ( Tog, B
+ ) achieve (e, oddifferrrtt privacy (DP) under shuffling, as established in Lemma G.5. Since ERR 2 0 is required, the user population must be sufficiently large to enable this amplification technique. In particular, for 8 = 10-8, s E {0.1, 1}. and B = 48, it is necessary to have greater than 2.5 107, 7.8. 10 and 1.3 10t, respectively, making a direct comparison with the previous experiments impossible. However, we note that the required number of users can significantly reduced in practice by employing tighter numerical upper bound for privacy amplification by shuffling (Feldman al., 2021).
We generated Pareto-like dataset (as described in the Data Generation section) with 10? and conducted experiments using Ā 10-8 and various privacy budgets & E [0.1,5]. Due to limited computational resources and the non optimal implementation of DpBayesSS and Hierarchical Mechanism, we restricted our comparison to DpNa i veNBS and its variant implemented with privacy amplification through shuffling. The results are shown in Figure 4. For small privacy budgets, shuffling- based amplification provides higher utility, whereas for e > 3, the performance of the algorithms converges and becomes comparable.
31

---

Lightweight Protocols for Distributed Private Quantile Estimation
Optaysts
GoHewwnds
Hiaractical Medhatam
2p0
Sphurddtt
Terurcticll Muchurtim
0.1
0.1
0.8
0:4
Seccos
0.2
0.2
6:3
0.0
0.0
40
10
30
10
30
6.
62
01
64
05
03
02
02
03
14
0.00
a 0.06
10.57
2088
2.2
1.0-
1.-
0.4
0.21
Day
0.64
0:6
0.6-
06-
10
307 privary budgett
207 prioary budget
0.2
02
05
02
02
03 cTsl
04
Success rate vs. privacy budget
Cumulative distribution of absolute
(a) Experiments for n 2500 and B
OpPlpe55
DoNewveoss
- Herraceec Medharti
Mesercoecal Muchartien
Rew
3.5
2.15
0.1
08
0.4
04
10
24
2.2
1.0
0.8
6.2
0.6
0.8-
02:
0.2
6:3
06.
10P
Dae 0.1
- 0.2
#2.15
1324
3.7
3.0
1.0
3.5
00000000 088
0.64
04.
0.2
02-
aão
privacy budget
Divccy budget
encer
Success rate vs. privacy budget
Cumulative distribution absolute error
(b) Experiments for 7500 and B = 4
Figure Comparison analysis.
32


Reviews:
[{"review_id": "wh3mcF5lXh", "reviewer": "Reviewer_RF3G", "summary": "The paper studies the problem of finding quantiles with constraints of differential privacy. More specifically, it studies shuffle and local differential privacy. \nThe authors proved that the algorithms have utility higher than any known algorithm for the problem and also proved that the local DP algorithm’s bounds are tight and it is impossible to improve it further.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your interest in our paper!", "claims_and_evidence": "The evidence sufficiently supports the claims.", "methods_and_evaluation_criteria": "Methods and evaluations are appropriate for the problem at hand.", "theoretical_claims": "The proofs presented in the paper are correct.", "experimental_designs_or_analyses": "The experimental design seems valid.", "relation_to_broader_scientific_literature": "The problem of estimating quantiles in differentially private way is well-studied in the literature since it is a common routine for may data analysis algorithms. \nLocal and shuffle differential privacy are also well-studied fields since they allow simplifying privacy guarantees of the systems using DP. \nHowever, getting high utility from this algorithms is often hard. \n\nUnfortunately, the LDP algorithms for quantile estimation were not studied enough, so I am really glad that this gap is getting closed.", "essential_references_not_discussed": "The paper doesn't lack any specific reference.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BiAAhx6Q1s", "reviewer": "Reviewer_HTT3", "summary": "This paper studies quantile estimation under local differential privacy. They are interested in the sequentially adaptive local model, where the aggregator queries each user only once, but in rounds where the set of users and the randomizer they are asked to use can depend on information learned in previous rounds.\n\nThey first argue via folklore tricks that estimating any quantile can be reduced to estimating the median with twice as many users. Hence, the main task is to estimate the median of either a distribution (where each user samples one example in an i.i.d. fashion from it), or of a dataset from a discrete domain B. They give a sequentially adaptive $\\epsilon$-DP $n$-round algorithm in the local model that outputs the $\\alpha$-approx median whp, as long as the number of users is $O(\\log B / \\alpha^2 \\epsilon^2)$. This is the main contribution of the paper and follows by using the noisy binary search primitive considered in prior work (Gretta and Price 2024) where you have a number of coins with monotonically increasing success probabilities, a target probability, and can flip coins, with the goal of finding a pair of successive coins containing the target probability. The statistical setting is a straightforward reduction to this problem, but the empirical setting is more challenging since you can't simply sample with replacement from the empirical distribution (since then you might see the same user multiple times- resulting in an algorithm that is not sequentially adaptive). The authors instead use sampling without replacement, along with randomly permuting the users, and argue via martingale-based techniques that for any threshold in $[B]$, and any $t > 0$, the probability that we draw one of the remaining $n-t$ users that are less than the threshold remains almost unchanged from what it was when $t=0$. They then argue that the techniques of Gretta and Price for the noisy binary search problem satisfy a robustness property;  they work even if we don't flip exactly the same coins, but rather ones with close probabilities. This is sufficient to solve the problem in the empirical setting.\n\nThey also show a matching lower bound for sequentially adaptive local model algorithms using Fano's inequality-based techniques of Duchi et al. They also appeal to a result of Edmonds, Nikolov, and Ullman to argue that this gives a separation from the non-adaptive local model, where there is a lower bound of $\\Omega(log^2 B / \\epsilon^2)$ for this problem (for constant $\\alpha$). They also give a result in the shuffle model that achieves better round complexity than the $n$-round local model protocol (with similar total number of users).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your interest in our paper and your valuable feedback!\n\n> The only one I was more unsure of was the shuffle model result, where I didn't fully understand the algorithm that they were using (the proof of Theorem 1.4 is rather vague on this point so fully specifying the algorithm would make it easier to verify).\n\nThanks for pointing this out. We agree that the writing surrounding the proof of theorem 1.4 can be improved. We will update the paper by describing the algorithm in detail and including pseudocode before proving the theorem in the appendix. To clarify, the algorithm randomly partitions the users into batches of size roughly $\\frac{1}{\\epsilon^2}+\\frac{1}{\\alpha^2}$. For a given threshold $t\\in [B]$, our analysis then shows that the shuffled randomized responses to whether the users are above or below $t$ suffice to determine the cdf at $t$ within additive $\\alpha$ with sufficiently high probability. Our algorithm thus uses $\\log_2(B)$ such batches to perform a binary search on $t$. This is similar to the algorithm given by Karp and Kleinberg [1] (section 1.2), but with extra care needed to ensure privacy. \n\n> Not essential, but Cohen et al. (STOC 2023) is the latest paper on quantile estimation/interior point in the central model that should be cited in the related work (where Kaplan et al. and others are mentioned) since it gets asymptotically tight bounds. Also I'd add in a more detailed exposition of work on adaptivity (and separations with non-adaptivity) in the local model (for e.g. Joseph Mao Neel Roth 2019, Joseph Mao Roth 2020, Daniely Feldman 2019, Acharya Canonne Sun Tyagi 22 for e.g.).\n\nThanks for drawing these to our attention. We will include a discussion of these in the paper. In particular, we agree that a more detailed exposition on adaptivity in LDP should be included. \n\n> instead of adversarial monotonic NBS I'd call the problem robust monotonic NBS (adversarial makes it sound like an adversary can choose coins maliciously).\n\nWe note that the algorithm for NBS works even in the case where an adversary can change coin probabilities maliciously (by at most some amount), hence the name. There is indeed no malicious adversary when we apply the NBS algorithm in our main protocol, but on the other hand, the changing coin probabilities have a complicated distribution. The strong adversarial assumption allows us to handle this, and it is unclear how to analyse our LDP protocol without such an assumption. \n\n>The indices in Lemma 3.1 and 4.1 are overloaded (i and j) which was confusing on first read. Also in Lemma 4.1 the set in the theorem statement should have c_j = 0 not c_i=0.\n\nThanks for making us aware of this, we will fix the $c_i$ typo and streamline the use of free variables in these lemmas. \n\n> in the proof of Lemma 3.1, the comment on conditioning on pi(1),...pi(i) is confusing because conditioning on X_js does not imply conditioning on pi(1)....pi(i) (but you don't need to condition on that part of the permutation for the argument to go through).\n\nThanks for this point. In our first writeup, we defined the martingale as a Doob martingale, wrt the random choices of $\\pi(1),...\\pi(2n)$, but you are right that with the current definition, we should just condition on $(X_j)_{j<i}$. We will update the paper.", "claims_and_evidence": "The claims seem correct and are largely well explained.", "methods_and_evaluation_criteria": "The primary results are theoretical and experiments are secondary considerations in the paper - however, they do consider experiments where they compare their method to two other more standard baseline algorithms, and run on datasets of different sizes, drawn from two types of distributions- pareto and uniform. They evaluate the absolute quantile error and success rate (the fraction of times a good quantile is released). They also choose reasonable $\\epsilon$ values in their evaluations. Overall, the experimental setup makes sense.", "theoretical_claims": "Yes, I checked all the proofs for correctness, and am convinced that the most significant results are correct. The only one I was more unsure of was the shuffle model result, where I didn't fully understand the algorithm that they were using (the proof of Theorem 1.4 is rather vague on this point so fully specifying the algorithm would make it easier to verify).", "experimental_designs_or_analyses": "Yes, see methods and evaluation criteria.", "relation_to_broader_scientific_literature": "Prior work has obtained non-adaptive algorithms for quantile estimation in the local model of differential privacy with suboptimal dependence on the domain size; this is the first work to get the correct dependence (leveraging adaptivity). This work fits in the larger literature on the local model of differential privacy (using tools in the model like randomized response and mutual information-based lower bonds), as well as the larger literature on private quantile estimation (extensively explored for the central model of differential privacy as well and a fundamental problem both theoretically and practically).", "essential_references_not_discussed": "Not essential, but Cohen et al. (STOC 2023) is the latest paper on quantile estimation/interior point in the central model that should be cited in the related work (where Kaplan et al. and others are mentioned) since it gets asymptotically tight bounds. Also I'd add in a more detailed exposition of work on adaptivity (and separations with non-adaptivity) in the local model (for e.g. Joseph Mao Neel Roth 2019, Joseph Mao Roth 2020, Daniely Feldman 2019, Acharya Canonne Sun Tyagi 22 for e.g.).", "other_strengths_and_weaknesses": "This paper cleverly uses existing tools, and has to jump through a number of technical hoops in order to get them to work for empirical quantile estimation (in the sequentially adaptive local model). Demonstrating the robustness of the Gretta-Price noisy binary search algorithm may be of independent interest.", "other_comments_or_suggestions": "1) instead of adversarial monotonic NBS I'd call the problem robust monotonic NBS (adversarial makes it sound like an adversary can choose coins maliciously).\n\n2) The indices in Lemma 3.1 and 4.1 are overloaded (i and j) which was confusing on first read. Also in Lemma 4.1 the set in the theorem statement should have c_j = 0 not c_i=0.\n\n3) in the proof of Lemma 3.1, the comment on conditioning on pi(1),...pi(i) is confusing because conditioning on X_js does not imply conditioning on pi(1)....pi(i) (but you don't need to condition on that part of the permutation for the argument to go through).", "questions_for_authors": "See questions on shuffle model in the 'theoretical claims' section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pI8miFJ4Yz", "reviewer": "Reviewer_EwQE", "summary": "This paper considers the estimation of quantiles under the LDP framework with bounded integral data. It derives a series of lower bounds under both shuffle-DP and LDP, and proposes an LDP algorithm in an adaptive setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your questions and your consideration of our paper\n\n>For random variables with infinitely many possible values (e.g., Poisson), does the proposed algorithm or framework still apply?\n\nWithout any assumptions on the distribution of the random variable, known lower bounds (as we discuss under related work) show that it is impossible to obtain any meaningful error guarantees, even in the central setting of DP. For concrete distributions (like Poisson with a reasonable bound on its rate, or even continuous distributions), one can usually apply our algorithm combined with bucketing as we discuss in Appendix H. The error guarantees will then depend on how much the CDF can change within a single bucket which in turn depends on the parameter space of the class of distributions. While it is interesting how well classes of infinite or continuous distributions can be discretized, this direction of work is somewhat orthogonal to ours.\n\n>Regarding footnote 1, I may be mistaken, but I believe some prior work considers privacy-preserving quantile estimation on a continuous interval (e.g., on ), such as [1] in CDP setting and [2] in the LDP setting. Could the authors clarify how these results relate to their work?\n\n[1] considers continuous distributions with the same error function as ours. However, related to our discussion in Appendix H, their results depend on a parameter $\\Delta$ that expresses how well the continuous distribution can be discretized into a finite set of intervals on which the CDF does not increase too quickly. [2] extends a line of work (see e.g., Duchi et al. [3]) aiming to minimize the average distance between the estimated median and the data points (and a more generalized form for other quantiles). Lower bounds in [3] show that this error must grow linearly with the range in which the true median lies. In our setting, without further assumptions on the data distribution, this would be linear in $B$. We additionally note that minimizing the distance in the domain between the estimated and true median must also have error $\\Omega(B)$, even under central DP. Indeed, if $n$ is odd and $(n+1)/2$ of the $x_i$’s are 0 and the remaining $(n-1)/2$ $x_i$’s are $B$, then the median is $0$, but changing the data of just a single user can change the median to $B$.\n\nOn the other hand, our work aims to minimise the *rank error* of the quantile and is not subject to these lower bound.\n\n\n[1] Lalanne, C., Garivier, A., & Gribonval, R. (2023). Private statistical estimation of many quantiles. In International Conference on Machine Learning (pp. 18399-18418). PMLR.\n\n[2] Liu, Y., Hu, Q., Ding, L., & Kong, L. (2023). Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning (pp. 21698-21714). PMLR.\n\n[3] Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182– 201, 2018.\n\n>The paper specifies a particular range for $\\epsilon$. For very large privacy budgets (i.e., $\\epsilon\\to \\infty$), will the results degrade or converge to the non-private results (as seen in [3] and [4])? In other words, do these bounds become consistent with classical results in the absence of privacy constraints?\n\nOur result states that $O((\\log B)/\\alpha^2)$ users suffice to find an $\\alpha$-approximate median under LDP with high probability in $B$ even for $\\epsilon=O(1)$.iThis matches known lower bounds even absent privacy constraints for statistical median estimation (when  requiring high probability in $B$). On the other hand if we just want success probability $2/3$, absent privacy constraints, $O(1/\\alpha^2)$ users suffice for statistical median estimation. It is an interesting open question to design a protocol with the correct convergence to $O(1/\\alpha^2)$ as $\\epsilon\\to \\infty$, but would likely require quite different techniques than the ones presented in our paper.\n\nIn the *empirical* setting, absent privacy constraints, an algorithm can simply output the median of the data set, so one should expect that as $\\epsilon\\to \\infty$ the required number of users would converge to $1$. Again, it is interesting to understand this convergence. In any case, we focus on the common choice of $\\epsilon=O(1)$.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "See the pros below.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Pros: Quantile estimation under LDP is a significant problem and the non-asymptotic results appear to be interesting.\n\nCons: The authors assume data are drawn from a bounded integral space (with finitely many values), which seems fairly restrictive and uncommon.", "other_comments_or_suggestions": "See the questions below.", "questions_for_authors": "1. For random variables with infinitely many possible values (e.g., Poisson), does the proposed algorithm or framework still apply?\n\n2. Regarding footnote 1, I may be mistaken, but I believe some prior work considers privacy-preserving quantile estimation on a continuous interval (e.g., on $[0,1]$), such as [1] in CDP setting and [2] in the LDP setting. Could the authors clarify how these results relate to their work?\n\n\n3. The paper specifies a particular range for $\\epsilon$. For very large privacy budgets (i.e., $\\epsilon \\to \\infty$), will the results degrade or converge to the non-private results (as seen in [3] and [4])? In other words, do these bounds become consistent with classical results in the absence of privacy constraints?\n\n\n[1] Lalanne, C., Garivier, A., & Gribonval, R. (2023). Private statistical estimation of many quantiles. In International Conference on Machine Learning (pp. 18399-18418). PMLR.\n\n[2] Liu, Y., Hu, Q., Ding, L., & Kong, L. (2023). Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning (pp. 21698-21714). PMLR.\n\n[3] Chen, L., Keilbar, G., & Wu, W. B. (2023). Recursive quantile estimation: Non-asymptotic confidence bounds. Journal of Machine Learning Research, 24(91), 1-25.\n\n[4] Howard, S. R., & Ramdas, A. (2022). Sequential estimation of quantiles with applications to A/B testing and best-arm identification. Bernoulli, 28(3), 1704-1728.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2ZPcrysD3t", "reviewer": "Reviewer_KDYn", "summary": "The authors study the problem of estimating quantiles under local differential privacy and under shuffle differential privacy, with applications in distributed and private quantiles estimation. \nTo do so, the paper presents new algorithms.\nThe article presents both upper and lower bounds for the problems at hand.\nFinally, the article compares experimentally the new methods that it introduces with already existing methods.\n\n## update after rebuttal \n\nAfter the rebuttal, I will maintain my original score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your questions and valuable feedback!\n\n> The structure of the paper makes it slightly difficult to follow, as the technical details of the algorithm are introduced quite late. This forces the reader to jump back and forth to understand how the challenge outlined in the introduction is actually addressed. Adding brief “how-to” explanations earlier could improve readability.\n\nWe will do our best to add more such explanations. Feel free to let us know if there was any part that was particularly confusing.\n\n\n>The definition of an approximate median in Definition 2.2 could be clarified. While it is defined for empirical distributions in the introduction, it is not explicitly extended to general distributions. A quick reminder of this concept in Definition 2.2 would be helpful.\n\nThanks for pointing this out. We will clarify in the paper.\n\n>The article would benefit from a brief conclusion summarizing key insights, highlighting open questions, and outlining possible directions for future work.\n\nThanks for the suggestion. We agree, and will include it in the next version of the paper.\n\n>The study focuses on \"quantile error,\" which measures how much probability mass the estimate is off by. However, in some applications, the primary concern is the uncertainty on the actual value (especially when the grid is a discretization of the real line and inherits a distance). Can the results be extended to this setting?\n\nOur results cannot be generalized to a domain-based error without making an assumption on the underlying data distribution. Lower bounds from [1] show that any median estimation protocol must have error that grows linearly with B when error is measured with the average distance from the estimate to each data point. Additionally note that minimizing the distance in the domain between the estimated and true median must also have error $\\Omega(B)$, even under central DP. Indeed, if $n$ is odd and $(n+1)/2$ of the $x_i$’s are 0 and the remaining $(n-1)/2$ $x_i$’s are $B$, then the median is $0$, but changing the data of just a single user can change the median to $B$. We expect that similar lower bounds would hold for other data-domain based error functions. \n\n\n[1] Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2018). Minimax Optimal Procedures for Locally Private Estimation. Journal of the American Statistical Association, 113(521), 182–201. https://doi.org/10.1080/01621459.2017.1389735\n\n>In Theorem 1.4, the condition $n=O(\\dots)$ suggests that the procedure works as long as there isn’t too much data. This seems counterintuitive, as one might expect more data to make the problem easier. Could you clarify this?\n\nThanks for pointing this out. The statement should be that only $n=O(\\dots)$ users are needed to get an $\\alpha$-approximate median. We will update the writing.\n\n>In the same theorem, why do $\\alpha$ and $\\epsilon$ appear to interact independently in the bound? Is this a consequence of the specific regime being considered?\n\nIn the following, we ignore logarithmic factors and focus on the polynomial dependence on $\\alpha$ and $\\epsilon$. In order to apply privacy amplification by shuffling (Lemma G.5), we have to pick the number of users in a batch $n’\\gg 1/\\epsilon^2$. With this many users, shuffle DP ensures that essentially each user in the batch answers threshold queries correctly with probability $>3/4$. With $>3/4$ probability of correct answers, it suffices to have $O(1/\\alpha^2)$ users in a batch to estimate the fraction of these users with $x_i$’s below a given threshold $t$ within $O(\\alpha)$. Additionally, there is another reason that the batch has to be this big, namely to ensure that the threshold query of the batch is within $O(\\alpha)$ of the threshold query of the full data set. Together, this gives sample complexity $O(1/\\alpha^2+1/\\epsilon^2)$. The additional logarithmic dependencies come from the fact that these events have to hold with less than constant error probability (since we union bound over $\\lg B$ steps of the binary search). Finally, we need $\\lg B$ times as many users, since there are $\\lg B$ steps to the binary search.\n\n>The paper states: “We are typically interested in the high-probability setting, where β=1/poly(B).” Is this because setting β=1/B would be equivalent to making a random guess? If so, adding a sentence to explain this, and clarifying that the polynomial must be greater than B for relevance, could be helpful.\n\nWe note that $\\beta$ is the \\emph{failure} probability. A random guess would thus give $\\beta=1-\\Theta(\\alpha)$, since the probability of guessing an $\\alpha$-approximate median is $\\Theta(\\alpha)$. Our algorithm guarantees that our median estimate is bad only with very low probability $1/poly(B)$, say $1/B^{10}$.", "claims_and_evidence": "The claims of the article are well-supported by clear proofs and empirical evaluation.", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense for the problem at hand.", "theoretical_claims": "I checked the proofs that are presented in the main body of the article, and I looked at the proof techniques that are used in the appendix. No issue was found, yet I did not check every single detail.", "experimental_designs_or_analyses": "I checked the soundness of the experiments that are presented in the main body of the article. I did not however check the correctness of the code that was provided by the authors.", "relation_to_broader_scientific_literature": "The authors link their work to prior literature and claim (with theoretical evidences) that their new algorithm improves prior state of the art by a polylogarithmic factor in the size of the set on which they work.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths : \n- The article is theoretically sound and overall well written.\n- The problem that is tackled is of interest for the community of privacy preserving machine learning.\n\nI overall have a positive opinion of the paper, so the following weaknesses are more in order to improve the paper than they are to point out reasons to reject it.\n\nWeaknesses : \n\n- The structure of the paper makes it slightly difficult to follow, as the technical details of the algorithm are introduced quite late. This forces the reader to jump back and forth to understand how the challenge outlined in the introduction is actually addressed. Adding brief “how-to” explanations earlier could improve readability.\n- The definition of an approximate median in Definition 2.2 could be clarified. While it is defined for empirical distributions in the introduction, it is not explicitly extended to general distributions. A quick reminder of this concept in Definition 2.2 would be helpful.\n- The article would benefit from a brief conclusion summarizing key insights, highlighting open questions, and outlining possible directions for future work.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. The study focuses on \"quantile error,\" which measures how much probability mass the estimate is off by. However, in some applications, the primary concern is the uncertainty on the actual value (especially when the grid is a discretization of the real line and inherits a distance). Can the results be extended to this setting?\n2. In Theorem 1.4, the condition n=O(…) suggests that the procedure works as long as there isn’t too much data. This seems counterintuitive, as one might expect more data to make the problem easier. Could you clarify this?\n3. In the same theorem, why do 𝛼 and 𝜖 appear to interact independently in the bound? Is this a consequence of the specific regime being considered?\n4. The paper states: “We are typically interested in the high-probability setting, where β=1/poly(B).” Is this because setting β=1/B would be equivalent to making a random guess? If so, adding a sentence to explain this, and clarifying that the polynomial must be greater than B for relevance, could be helpful.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviews on this paper are uniformly positive, and all advocate acceptance.  The paper addresses an important problem in the context of machine learning, of privately gathering information on the distribution of data, in the form of quantiles.  They show improved results for this task over prior work in the distributed/federated setting, under local and shuffle differential privacy.  The reviewers appreciated the technical depth and importance of the work.  Some minor concerns were addressed clearly during the rebuttal phase, which led to the reviewers increasing their appreciation of the contribution.  On this basis, the paper is (strongly) recommended for acceptance in ICML.
Decision: Accept (spotlight poster)