# private_statistical_estimation_of_many_quantiles__4a00aa07.pdf

Private Statistical Estimation of Many Quantiles

Cl ement Lalanne 1 Aur elien Garivier 2 R emi Gribonval 1

This work studies the estimation of many statistical quantiles under differential privacy. More precisely, given a distribution and access to i.i.d. samples from it, we study the estimation of the inverse of its cumulative distribution function (the quantile function) at specific points. For instance, this task is of key importance in private data generation. We present two different approaches. The first one consists in privately estimating the empirical quantiles of the samples and using this result as an estimator of the quantiles of the distribution. In particular, we study the statistical properties of the recently published algorithm introduced by (Kaplan et al., 2022) that privately estimates the quantiles recursively. The second approach is to use techniques of density estimation in order to uniformly estimate the quantile function on an interval. In particular, we show that there is a tradeoff between the two methods. When we want to estimate many quantiles, it is better to estimate the density rather than estimating the quantile function at specific points.

1. Introduction

Computing statistics from real users data leads to new challenges, notably privacy concerns. Indeed, it is now well documented that the release of statistics computed on them can, without further caution, have disastrous repercussions (Narayanan & Shmatikov, 2006; Backstrom et al., 2007; Fredrikson et al., 2015; Dinur & Nissim, 2003; Homer et al., 2008; Loukides et al., 2010; Narayanan & Shmatikov, 2008; Sweeney, 2000; Wagner & Eckhoff, 2018; Sweeney, 2002). In order to solve this problem, differential privacy (DP) (Dwork et al., 2006b) has become the gold standard in privacy protection. It adds a layer of randomness in the esti-

1Univ Lyon, Ens L, UCBL, CNRS, Inria, LIP, F-69342, LYON Cedex 07, France 2Univ. Lyon, ENS de Lyon, UMPA UMR 5669, 46 all ee d Italie, F-69364 Lyon cedex 07. Correspondence to: Cl ement Lalanne <clement.lalanne@ens-lyon.fr>.

Proceedings of the 40 th International Conference on Machine Learning, Honolulu, Hawaii, USA. PMLR 202, 2023. Copyright 2023 by the author(s).

mator (i.e. the estimator does not only build on X1, . . . , Xn but also on another source of randomness) in order to hide each user s data influence. It is notably used by the US Census Bureau (Abowd, 2018), Google (Erlingsson et al., 2014), Apple (Thakurta et al., 2017) and Microsoft (Ding et al., 2017) among others. This notion is properly defined in Section 2, but for now it is only important to view it as a constraint on the estimators that ensures that the observation of the estimator only leaks little information on the individual samples on which it is built on.

Any probability distribution P on [0, 1] is fully characterized by its cumulative distribution function (CDF) defined by

FP(t) := P ( , t] , t R .

The central topic of this article is the quantile function (QF), F 1 P , defined as the generalized inverse of FP:

F 1 P (p) = inf t R | p FP(t) , p [0, 1] ,

with the convention inf = + . When P is absolutely continuous w.r.t. Lebesgue s measure with a density that is bounded away from 0, FP and F 1 P are bijective and are inverse from one another.

A well-known result is that, under mild hypotheses on P, if U U([0, 1]) (U follows a uniform distribution on [0, 1]), then F 1 P (U) P (Devroye, 1986). In other words, knowing F 1 P allows to generate data with distribution P. It makes the estimation of F 1 P a key component in data generation. Indeed, privately learning the quantile function would then allow generating infinitely many new coherent samples at no extra cost on privacy.

Given X1, . . . , Xn i.i.d. P, this article studies the private estimation of F 1 P (pj) from these samples at prescribed values {p1, . . . , pm} (0, 1). Without privacy and under mild hypotheses on the distribution, it is well-known (Van der Vaart, 1998) that for each p (0, 1), the quantity X(E(np)) is a good estimator of F 1 P (p), where X(1), . . . , X(n) are the order statistic of X1, . . . , Xn (i.e. a permutation of the observations such that X(1) X(2) X(n)) and E(x) denotes the largest integer smaller or equal to x. The quantity X(E(np)) is called the empirical (as opposed to statistical) quantile of the dataset (X1, . . . , Xn) (as opposed to the distribution P) of order p.

Private Statistical Estimation of Many Quantiles

While the computation of private empirical quantiles has led to a rich literature, much less is known on the statistical properties of the resulting algorithms seen as estimators of the statistical quantiles of an underlying distribution, compared to more traditional ways of estimating a distribution.

1.1. Related work

Early approaches for solving the private empirical quantile computation used the Laplace mechanism (Dwork et al., 2006a;b) but the high sensitivity of the quantile query made it of poor utility (see Section 2 for a quick introduction to differential privacy, including the Laplace mechanism and the notion of sensitity). Smoothed sensitivity-based approaches followed (Nissim et al., 2007) and managed to achieve greatly improved utility.

The current state of the art for the computation of a single empirical private quantile (Smith, 2011) is an instantiation of the so-called exponential mechanism (Mc Sherry & Talwar, 2007) with a specific utility function (see Section 2) that we will denote QExp (for exponential quantile) in the rest of this article. It is implemented in many DP software libraries (Allen; IBM).

For the computation of multiple empirical private quantiles, the problem gets more complicated. Indeed, with differential privacy, every access to the dataset has to be accounted for in the overall privacy budget. Luckily, and part of the reasons why differential privacy became so popular in the first place, composition theorems (Dwork et al., 2006b; Kairouz et al., 2015; Dong et al., 2019; 2020; Abadi et al., 2016) give general rules for characterizing the privacy budget of an algorithm depending on the privacy budgets of its subroutines. It is hence possible to estimate multiple empirical quantiles privately by separately estimating each empirical quantile privately (using the techniques presented above) and by updating the overall privacy budget with composition theorems. The algorithm Ind Exp (see Section 2) builds on this framework. However, recent research has shown that such approaches are suboptimal. For instance, (Gillenwater et al., 2021) presented an algorithm (Joint Exp) based on the exponential mechanism again, with a utility function tailored for the joint computation of multiple private empirical quantiles directly. Joint Exp became the state of the art for about a year. It can be seen as a generalization of QExp, and the associated clever sampling algorithm is interesting in itself. Yet, more recently, (Kaplan et al., 2022) demonstrated that an ingenious use of a composition theorem (as opposed to a more straightforward direct independent application) yields a simple recursive computation using QExp that achieves the best empirical performance to date. We will refer to their algorithm as Rec Exp (for recursive exponential). Furthermore, contrary to Joint Exp, Rec Exp is endowed with strong utility guarantees (Kaplan et al., 2022) in terms of

the quality of estimation of the empirical quantiles.

In terms of statistical utility of the above-mentioned algorithms (i.e. when using the computed private empirical quantiles as statistical estimators of the statistical quantiles of the underlying distribution), under mild hypotheses, QExp is asymptotically normal (Smith, 2011; Asi & Duchi, 2020) and Joint Exp is consistent (Lalanne et al., 2022).

1.2. Contributions

The main contribution of this paper is to obtain concentration properties for Rec Exp as a private estimator of multiple statistical quantiles (see Theorem 3.5) of a distribution. In order to do so, we adopt a proof framework that controls both the order statistic of X1, . . . , Xn relatively to the statistical quantiles (see Lemma 3.1), and the minimum gap in the order statistic, which is defined as mini X(i+1) X(i), and with the convention X(0) = 0 and X(n+1) = 1 (see Lemma 3.2). Indeed, this last quantity is of key interest in order to leverage the empirical utility provided by (Kaplan et al., 2022). This framework also gives us concentration results for QExp when used to estimate multiple statistical quantiles (see Corollary 3.4). In particular, our results show that when m (the number of statistical quantiles to estimate) is large, Rec Exp has a much better statistical utility (both in term of proved statistical upper bounds and of experimental behavior) for a given privacy budget than the simple composition of QExp.

We then compare the statistical utility of Rec Exp to the one of a quantile function built on a simple histogram estimator of the density of P. Since this estimator is a functional estimator that estimates all the quantiles in an interval, its statistical utility (see Theorem 4.4) obviously has no dependence on m, whereas the utility of Rec Exp has one. We show that for high values of m the histogram estimator has a better utility than Rec Exp for a given privacy budget. This theoretical result is confirmed numerically (see Section 5). For reasonable values of m however, our work consolidates the fact that Rec Exp is a powerful private estimator, both to estimate empirical quantiles of a dataset (Kaplan et al., 2022) and to estimate the statistical quantiles of a distribution (this work). Furthermore, a simple comparison of the upper bounds (Theorem 3.5 and Theorem 4.4) can serve as a guideline to decide whether to choose Rec Exp or an histogram estimator.

2. Background

This section presents technical details about differential privacy and private empirical quantiles computation.

Private Statistical Estimation of Many Quantiles

2.1. Differential Privacy

A randomized algorithm A that takes as input a dataset (X1, . . . , Xn) (where each Xi lives in some data space, and the size n can be variable) is ϵ-differentially private (ϵ-DP) (Dwork et al., 2006a;b; Dwork & Roth, 2014), where ϵ > 0 is a privacy budget, if for any measurable S in the output space of A and any neighboring datasets (X1, . . . , Xn) (X 1, . . . , X n ) (given some neighboring relation ) we have

P A(X1, . . . , Xn) S eϵ P A(X 1, . . . , X n ) S

where the randomness is taken w.r.t. A.

Differential privacy ensures that it is hard to distinguish between two neighboring datasets when observing the output of A. The neighboring relation has an impact on the concrete consequences of such a privacy guarantee. A usual goal is to make it hard to tell if a specific user contributed to the dataset. This is typically associated with an addition/removal neighboring relation: (X1, . . . , Xn) (X 1, . . . , X n ) if (X 1, . . . , X n ) can be obtained from (X1, . . . , Xn) by adding/removing a single element, up to a permutation. Another choice is the replacement neighboring relation: (X1, . . . , Xn) (X 1, . . . , X n ) if (X 1, . . . , X n ) can be obtained from (X1, . . . , Xn) up to a permutation by replacing a single entry.

There are multiple standard ways to design an algorithm that is differentially private. We focus on the ones that will be useful for this article.

Given a deterministic function f mapping a dataset to a quantity in Rd, the sensitivity of f is

f := sup (X1,...,Xn) (X 1,...,X n )

f(X1, . . . , Xn)

f(X 1, . . . , X n ) 1 .

Given a dataset (X1, . . . , Xn), the Laplace mechanism returns f(X1, . . . , Xn) + f

ϵ Lap(Id) where Lap(Id) refers to a random vector of dimension d with independent components that follow a centered Laplace distribution of parameter 1. This mechanism is ϵ-DP (Dwork & Roth, 2014).

If the private mechanism has to output in a general space O equipped with a reference σ-finite measure µ, one can exploit the exponential mechanism (Mc Sherry & Talwar, 2007) to design it. Given a utility function u that takes as input a dataset (X1, . . . , Xn) and a candidate output o O and returns u (X1, . . . , Xn), o R, which is supposed to measure how well o fits the result of a certain operation that we want to do on (X1, . . . , Xn) (with the convention that the higher the better), the sensitivity of u is

u := sup o O,(X1,...,Xn) (X 1,...,X n )

u (X1, . . . , Xn), o

u (X 1, . . . , X n ), o .

Given a dataset (X1, . . . , Xn), the exponential mechanism returns a sample o on O of which the distribution of probability has a density w.r.t. µ that is proportional to

e ϵ 2 u u (X1,...,Xn),o . It is ϵ-DP (Mc Sherry & Talwar, 2007).

Finally, a simple composition property (Dwork et al., 2006b) states that if A1, . . . , Ak are ϵ-DP, (A1, . . . , Ak) is kϵ-DP.

2.2. Private empirical quantile estimation

This subsection details the algorithms evoked in Section 1.1 that will be of interest for this article.

QExp. Given n points X1, . . . , Xn [0, 1] and p (0, 1), the QExp mechanism, introduced by (Smith, 2011), is an instantiation of the exponential mechanism w.r.t. µ the Lebesgue s measure on [0, 1], with utility function u QExp such that, for any q [0, 1],

u QExp (X1, . . . , Xn), q := |{i|Xi < q}| E(np) ,

where for a set, | | represents its cardinality. The sensitivity of u QExp is 1 for both of the above-mentioned neighboring relations. As the density of QExp is constant on all the intervals of the form (X(i), X(i+1)), a sampling algorithm for QExp is to first sample an interval (which can be done by sampling a point in a finite space) and then to uniformly sample a point in this interval. This algorithm has complexity O(n) if the points are sorted and O(n log n) otherwise. Its utility (as measured by a so-called empirical error ) is controlled, cf (Kaplan et al., 2022) Lemma A.1. This is summarized as follows

Fact 2.1 (Empirical Error of QExp). Consider fixed real numbers X1, . . . , Xn [0, 1] that satisfy mini X(i+1) X(i) > 0 with the convention X(0) = 0 and X(n+1) = 1. Denote q the (random) output of QExp on this dataset, for the estimation of a single empirical quantile of order p, and E := i|Xi < q E(np) ,

the empirical error of QExp. For any β (0, 1), we have

Let us mention that in this article, we use the term Fact to refer to results that are directly borrowed from the existing literature in order to clearly identify them. In particular, it is not correlated with the technicality of the result.

Ind Exp. Given p1, . . . , pm (0, 1), Ind Exp privately estimates the empirical quantiles of order p1, . . . , pm by evaluating each quantile independently using QExp and the simple composition property. Each quantile is estimated

Private Statistical Estimation of Many Quantiles

with a privacy budget of ϵ m. The complexity is O(mn) if the points are sorted, O(mn + n log n) otherwise.

Rec Exp. Introduced by (Kaplan et al., 2022), Rec Exp is based on the following idea : Suppose that we already have a private estimate, qi, of the empirical quantile of order pi for a given i. Estimating the empirical quantiles of orders pj > pi should be possible by only looking at the data points that are bigger than qi, and similarly for the empirical quantiles of orders pj < pi. Representing this process as a tree, the addition or removal of an element in the dataset only affects at most one child of each node and at most one node per level of depth in the tree. The perlevel composition of mechanisms comes for free in terms of privacy budget, hence only the tree depth matters for composition. By choosing a certain order on the quantiles to estimate, this depth can be bounded by log2 m + 1. More details can be found in the original article (Kaplan et al., 2022).

When using QExp with privacy budget ϵ log2 m+1 for estimating the individual empirical quantiles, Rec Exp is ϵ-DP with the addition/removal neighborhing relation. This remains valid with the replacement relation if we replace ϵ by ϵ/2, as the replacement relation can be seen as a twosteps addition/removal relation. Rec Exp has a complexity of O(n log m) if the points are sorted and O(n log(nm)) otherwise. The following control of its empirical error is adapted from (Kaplan et al., 2022) Theorem 3.3.

Fact 2.2 (Empirical Error of Rec Exp). Consider fixed real numbers X1, . . . , Xn [0, 1] that satisfy mini X(i+1) X(i) > 0 with the convention X(0) = 0 and X(n+1) = 1. Denote (q1, . . . , qm) the (random) return of Rec Exp on this dataset, for the estimation of m empirical quantiles of orders (p1, . . . , pm), and

{i|Xi < qj} E(npj) ,

the empirical error of Rec Exp. For any β (0, 1), we have

E 2(log2 m + 1)2 ln 1

+ ln(m) + ln 1 β

3. Statistical utility of Exp

Fact 2.1 and Fact 2.2 control how well QExp, Ind Exp and Rec Exp privately estimates empirical quantiles of a given dataset. However, they do not tell how well those algorithms behave when the dataset is drawn from some probability distribution and the algorithm output is used to estimate the statistical quantiles of this distribution. This is precisely the objective of this section, where we notably highlight the fact

that the utility of Rec Exp scales much better with m (the number of quantiles to estimate) than previous algorithms for this task.

3.1. How to leverage Fact 2.1 and Fact 2.2

Two difficulties arise when trying to control the statistical utility of QExp and Ind Exp based on Fact 2.1 and Fact 2.2.

First, the measure of performance (i.e. show mall the empirical error is) controls the deviation w.r.t. the empirical quantiles in terms of order :

{i|Xi < qj} E(npj) .

In fact, E(npj) npj has no link with FP a priori. In contrast, from a statistical point of view, the quantity of interest in the deviation w.r.t. the statistical quantiles (F 1 P (p1), . . . , F 1 P (pm)). We circumvent that difficulty with the following general purpose lemma :

Lemma 3.1 (Concentration of empirical quantiles). If X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π π R > 0 almost

surely, then for any p (0, 1) and γ > 0 such that γ < min F 1 X (p), 1 F 1 X (p) , we have

P sup k J |X(E(np)+k) F 1 X (p)| > γ

8p n + 2e γ2π 2

max E(np) + 1, E 1

. . . , min n E(np), E 1

The proof is postponed to Appendix A. The integer set J may be viewed as an error buffer : As long as an algorithm returns a point with an order error falling into J (compared to E(np)), the error on the statistical estimation will be small.

The second difficulty is the need to control the lower bound on the gaps . For many distributions, this quantity can be as small as we want, and the guarantees on the empirical error of QExp, Ind Exp and Rec Exp can be made as poor as we want (Lalanne et al., 2022). However, by imposing a simple condition on the density, the following lemma tells that the minimum gap in the order statistic is not too small .

Lemma 3.2 (Concentration of the gaps). Consider n 1 and X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t.

Private Statistical Estimation of Many Quantiles

Lebesgue s measure such that π R π π R > 0 almost surely. Denote i = X(i) X(i 1), 1 i n + 1, with the convention X(0) = 0 and X(n+1) = 1. For any γ > 0 such that γ < 1 4 π, we have

P n+1 min i=1 i > γ

The proof is postponed to Appendix B.

3.2. Statistical utility of QExp and Ind Exp

As a first step towards the analysis of Rec Exp, and in order to offer a point of comparison, we first build on the previous results to analyze statistical properties of QExp and Ind Exp.

Theorem 3.3 (Statistical utility of QExp). Consider n 1 and X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π R π π R > 0 almost surely. Denote q the (random) result of QExp on (X1, . . . , Xn) for the estimation of the quantile of order p, where min(p, 1 p) > 2/n. For any γ (0, 2 min(p,1 p)

P |q F 1 π (p)| > γ 4n

32 + 4e γ2π 2

Sketch of proof. We fix a buffer size K and define QC (for quantile concentration) the event Any error of at most K points in the order statistic compared to X(E(np)) induces an error of at most γ on the statistical estimation of F 1 π (p) . The probability P (QCc) is controlled by Lemma 3.1. We fix a gap size > 0 and define the event G (for gaps) mini i , so that P (Gc) is controlled by Lemma 3.2. Then, we notice that

P |q F 1 π (p)| > γ

P |q F 1 π (p)| > γ QC, G + P (QCc) + P (Gc)

P E K + 1 QC, G + P (QCc) + P (Gc) ,

where E refers to the empirical error of QExp. Using

Fact 2.1 for a suited β controls P E K + 1 QC, G .

Tuning the values of K, and β concludes the proof.

The full proof can be found in Appendix C.

Applying this result to Ind Exp (ϵ becomes ϵ

m) together with a union bound gives the following result :

Corollary 3.4 (Statistical utility of Ind Exp). Consider n 1 and X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π R π π R > 0 al-

most surely. Denote q := (q1, . . . , qm) the (random) result of Ind Exp on (X1, . . . , Xn) for the estimation of the quantiles of orders p := (p1, . . . , pm), where mini[min(pi, 1

pi)] > 2/n. For each γ 0, 2 mini[min(pi,1 pi)]

P q F 1 π (p) > γ 4nm

+ 4me γ2π 2

where F 1 π (p) = (F 1 π (p1), . . . , F 1 π (pm)).

The proof is postponed to Appendix D.

So, there exist a polynomial expression P and two positive constants C1 and C2 depending only on the distribution such that, under mild hypotheses,

P q F 1 π (p) > γ

P(n, m) max e C1 ϵnγ

m , e C2γ2n .

We factorized the polynomial expression since it plays a minor role compared to the values in the exponential.

Statistical complexity. The term P(n, m)e C2γ2n simply comes from the concentration of the empirical quantiles around the statistical ones. It is independent of the private nature of the estimation. It is the price that one usually expects to pay without the privacy constraint.

Privacy overhead. The term P(n, m)e C1 ϵnγ

m can be called the privacy overhead. It is the price paid for using this specific private algorithm for the estimation. For Ind Exp, if we want it to be constant, ϵn has to roughly scale as m times a polynomial expression in log2 m. As we will see later in Theorem 3.5, Rec Exp behaves much better, with nϵ having to scale only as a polynomial expression in log2 m.

A privacy overhead of this type is not only an artifact due to a given algorithm (even if a suboptimal algorithm can make it worse), but in fact a constituent part of the private estimation problem, associated to a necessary price to pay, as captured by several works on generic lower bounds valid for all private estimators (Duchi et al., 2013; 2014; Acharya et al., 2021e; 2018; 2021a;c;d;b; Barnes et al., 2020a;b; 2019; Kamath et al., 2022; Butucea et al., 2019; Lalanne et al., 2023; Berrett & Butucea, 2019; Steinberger, 2023; Kroll, 2021).

3.3. Statistical properties of Rec Exp

With a similar proof technique as in the one of Theorem 3.3, the following result gives the statistical utility of Rec Exp :

Theorem 3.5 (Statistical utility of Rec Exp). Consider n 1 and X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π R π π R >

Private Statistical Estimation of Many Quantiles

0 almost surely. Denote q := (q1, . . . , qm) the result of Rec Exp on (X1, . . . , Xn) for the quantiles of orders p := (p1, . . . , pm), where mini[min(pi, 1 pi)] > 2/n. For any γ (0, 2 mini[min(pi,1 pi)]

π ) we have

P q F 1 π (p) > γ 4n

2e πme ϵnγπ 32 log2(2m)2

+ 4me γ2π 2

The proof is postponed to Appendix E.

As with Corollary 3.4, we can simplify this expression as

P q F 1 π (p) > γ

P(n, m) max e C1 ϵnγ (log2 m)2 , e C2γ2n ,

where P is a polynomial expression and C1 and C2 are constants, all depending only on the distribution.

Statistical complexity. On the one hand the statistical term of this expression, which is independent of ϵ, is the same as with Ind Exp. This is natural since the considered statistical estimation problem is unchanged, only the privacy mechanism employed to solve it under a DP constraint was changed.

Privacy overhead. On the other hand the privacy overhead P(n, m)e C1 ϵnγ (log2 m)2 is much smaller than the one of Ind Exp. The scaling of ϵn to reach a prescribed probability went from approximately linear in m to roughly a polynomial expression in log2 m.

In particular and to the best of our knowledge, this scaling in m places Rec Exp much ahead of its competitors (the algorithms that compute multiple private empirical quantiles) for the task of statistical estimation. Remark 3.6. All the results presented in this section require a uniform lower-bound on the density of the distribution from which the data is being sampled. Note that via some minor adaptations in the proofs, all the results can be adapted to the less restrictive hypothesis that the density is lower-bounded on a neighborhood of the statistical quantiles only.

4. Uniform estimation of the quantile function

Private quantile estimators often focus on estimating the quantile function at specific points p1, . . . , pm , which is probably motivated by a combination of practical considerations (algorithms to estimate and representing finitely many numbers are easier to design and manipulate than algorithms to estimate a function) and of intuitions about

privacy (estimating the whole quantile function could increase privacy risks compared to estimating it on specific points). It is however well-documented in the (non-private) statistical literature that, under regularity assumptions on the quantile function, it can also be approximated accurately from functional estimators, see e.g. (Gy orfi et al., 2002; Tsybakov, 2009).

Building on this, this section considers a simple private histogram estimator of the density (Wasserman & Zhou, 2010) in order to estimate the quantile function in functional infinite norm. This allows of course to estimate the quantile function at (p1, . . . , pm) for arbitrary m. As a natural consequence, we show that when m is very high, for a given privacy level Rec Exp has suboptimal utility guarantees and is beaten by the guarantees of the histogram estimator. Theorem 4.4 and Theorem 3.5 give a decision criterion (by comparing the upper bounds) to decide whether to use Rec Exp or a histogram estimator for the estimation problem.

4.1. Motivation: lower bounds for Ind Exp and Rec Exp

Lower-bounding the density of the exponential mechanism for u QExp gives a general lower-bound on its utility:

Lemma 4.1 (Utility of QExp; Lower Bound). Let X1, . . . , Xn [0, 1]. Denoting by q the result of QExp on (X1, . . . , Xn) for the quantile of order p, we have for any t [0, 1] and any positive γ (0, 1

P |q t| > γ 1

Note that this holds without any constraint relating p,n, or γ. The proof is postponed to Appendix F. As a consequence, if the points X1, . . . , Xn are randomized, the probability that QExp makes an error bigger than γ on the estimation of a quantile of the distribution is at least 1

2 . A direct consequence is that for any γ (0, 1

4], the statistical utility of Ind Exp has a is lower-bounded:

P q F 1 π (p) > γ 1

and the statistical utility of Rec Exp is also lower-bounded:

P q F 1 π (p) > γ 1

2e nϵ 2(log2 m+1) .

These are consequences of lower-bounds on the estimation error of the first statistical quantile estimated by each algorithm in its respective computation graph (with privacy level ϵ/m for Ind Exp; ϵ/(log2 m + 1) for Rec Exp).

In particular, for both algorithms, utility becomes arbitrarily bad when m increases. This is not a behavior that would be expected from any optimal algorithm. The rest of this section studies a better estimator for high values of m.

Private Statistical Estimation of Many Quantiles

4.2. Histogram density estimator

The histogram density estimator is a well-known estimator of the density of a distribution of probability. Despite its simplicity, a correct choice of the bin size can even make it minimax optimal for the class of Lipschitz densities.

Under differential privacy, this estimator was first adapted and studied by (Wasserman & Zhou, 2010). It is studied both in terms of integrated squared error and in Kolmogorov Smirnov distance. In the sequel, we need a control in infinite norm. We hence determine the histogram concentration properties for this metric.

Given a a bin size h > 0 that satisfies 1

h N, we partition [0, 1] in 1

h intervals of length h. The intervals of this partition are called the bins of the histogram. Given 1

h i.i.d. centered Laplace distributions of parametter 1, (Lb)b bins, we define ˆπhist, an estimator of the supposed density π of the distribution as: for each t [0, 1],

ˆπhist(t) := X

b bins 1b(t) 1

i=1 1b(Xi) + 2

The function that, given the bins of a histogram, counts the number of points that fall in each bin of the histogram has a sensitivity of 2 for the replacement neighboring relation. Indeed, replacing a point by another changes the counts of at most two (consecutive) bins by one. Hence, the construction of the Laplace mechanism ensures that ˆπhist is ϵ-DP.

Note that, as a common practice, we divided by n freely in terms of privacy budget in the construction of ˆπhist. This is possible because we work with the replacement neighboring relation. The size n of the datasets is fixed and is a constant of the problem.

The deviation between π and ˆπhist can be controlled.

Lemma 4.2 (Utility of ˆπhist; Density estimation). Consider X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π is L-Lipschitz for some positive constant L, and the private histogram density estimator ˆπhist with bin size h. For any γ > Lh, we have

P ˆπhist π > γ 1

he h2(γ Lh)2

The proof is postponed to Appendix G.

4.3. Application to quantile function estimation

In order to use ˆπhist as an estimator of the quantile function, we need to properly define a quantile function estimator associated with it. Indeed, even if ˆπhist estimates a density of probability, it does not necessary integrate to 1 and can even be negative at some locations. Given any integrable function

ˆπ on [0, 1], we define its generalized quantile function

F 1 ˆπ (p) = inf q [0, 1]| Z q

0 ˆπ p , p [0, 1] ,

with the convention inf = 1. Even if this quantity has no reason to behave as a quantile function, the following lemma tells that F 1 ˆπ is close to an existing quantile function when ˆπ is close to its corresponding density.

Lemma 4.3 (Inversion of density estimators). Consider a density π on [0, 1] w.r.t. Lebesgue s measure such that π π R > 0 almost surely. If ˆπ is an integrable function

that satisfies ˆπ π α, and if p [0, 1] is such that F 1 π (p) 2α

π , F 1 π (p) + α

(0, 1), then

F 1 π (p) F 1 ˆπ (p) 2α

The proof is in Appendix H.

A direct consequence of Lemma 4.2 and Lemma 4.3 is Theorem 4.4. It controls the deviation of the generalized quantile function based on ˆπhist to the true quantile function.

Theorem 4.4 (Utility of F 1 ˆπhist; Quantile function estimation).

Consider X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π is L-Lipschitz for some positive constant L and that π π R > 0 almost

surely, and h < π /(4L) such that 1

h N. Let F 1 ˆπhist be the quantile function estimator associated with the private histogram density estimator ˆπhist with bin size h. Consider γ0 (2Lh/π , 1/2), I := Fπ (γ0, 1 γ0) , and ,I the sup-norm of functions on the interval I. We have

P F 1 ˆπhist F 1 π ,I > γ

2 Lh 2 n; ,

whenever γ (2Lh/π , γ0).

The proof is postponed to Appendix I.

Analysis of Theorem 4.4. As with Theorem 3.3 and Theorem 3.5, the upper-bound provided by Theorem 4.4 can be split in two terms : The error that one usually expects without privacy constraint, 2

4 ( γπ 2 Lh)2n), and the

one that come from the private algorithm, 1

h exp( γπ hnϵ

The assumption γπ 2 > Lh ensures that the bin size h and the desired level of precision γ are compatible.

Private Statistical Estimation of Many Quantiles

101 102 103

100 Beta(0.5,0.5)

Ind Exp Rec Exp Hist

101 102 103

100 Beta(1, 3)

Ind Exp Rec Exp Hist

101 102 103

Ind Exp Rec Exp Hist

101 102 103

100 Beta(2, 5)

Ind Exp Rec Exp Hist

The vertical axis reads the error E ˆq F 1(p) where p = 1 4 + 1 2(m+1), . . . , 1

4 + m 2(m+1) for different values of m, n = 10000, ϵ = 0.1, ˆq is the private estimator, and E is estimated by Monte-Carlo averaging over 50 runs. The histogram is computed on 200 bins.

Figure 1. Numerical performance of the different private estimators

Computational aspects. ˆπhist is constant on each bin. Hence, it can be stored in a single array of size 1 h. If the data points are sorted, this array can be filled with a single pass over all data points and over the array. Then, given p1, . . . , pm (0, 1) sorted, estimating F 1 ˆπhist(p1), . . . , F 1 ˆπhist(pm) can be done with a single pass over p1, . . . , pm and over the array that stores ˆπhist. Indeed, it is done by integration of the array until the thresholds of the pi s are reached. The overall complexity of this procedure is O n + m + 1

h to which must be added O(n log n) if the data is not sorted and O(m log m) if the targeted quantiles pi are not sorted.

Comparison with Rec Exp. Comparing this histogrambased algorithm to Rec Exp is more difficult than comparing Rec Exp to Ind Exp. First of all, the results are qualitatively different. Indeed, Rec Exp estimates the quantile function on a finite number of points and the histogram estimator estimates it on an interval. The second result is stronger in the sense that when the estimation is done on an interval, it is done for any finite number of points in that interval. However, the error of Rec Exp for that finite number of points may be smaller than the one given by the histogram on the interval. Then, the histogram depends on a meta parametter h. With a priori information on the distribution, it can be tuned using Theorem 4.4. Aditionally, the hypothesis required are different : Theorem 3.5 does not require the density to be Lipschits contrary to Theorem 4.4. Finaly, we can observe that the histogram estimator is not affected by the lower bounds described in Section 4.1. Hence, when all the hypotheses are met, there will obviously always be a number m of targeted quantiles above which it is better to use histograms. The two algorithms are numerically compared in Section 5. Remark 4.5. Notice that the hypothesis of Lipschitzness of the density is only useful for the histogram estimators. In particular the guarantees of Rec Exp of Section 3 do not require such hypothesis. This section thus presented

a strict subclass of the problem on which Rec Exp may be suboptimal. Remark 4.6. We would like to highlight the fact that histograms are used as an illustration of the suboptimality of Rec Exp on some instances of the problem. In particular, it does not imply that they are the state of the art on such instances. It is very possible that other mechanisms perform well in such cases (Blocki et al., 2012; Alabi et al., 2022). In fact, provided that the inversion from the cumulative distribution function of the distribution to its quantile function is easy (which is typically the case when the density is uniformly lower-bounded), we expect that many private CDF estimators will behave similarly or better on these specific instances (Bun et al., 2015; Kaplan et al., 2020; Drechsler et al., 2022; Denisov et al., 2022; Henzinger & Upadhyay, 2022).

5. Numerical results

For the experiments, we benchmarked the different estimators on beta distributions, as they allow to easily tune the Lipschitz constants of the densities, which is important for characterizing the utility of the histogram estimator.

Figure 1 represents the performance of the estimator as a function of m. We estimate the quantiles of orders p = 1 4 + 1 2(m+1), . . . , 1

4 + m 2(m+1) since it allows us to stay in the regions where the density is not too small.

Ind Exp vs Rec Exp vs Histograms. Figure 1, confirms our claims about the scaling in m of Ind Exp and Rec Exp. Indeed, even if Ind Exp quickly becomes unusable, Rec Exp stays at a low error until really high values of m. The conclusions of Section 4.1 also seem to be verified : Even if Rec Exp performs well for small to intermediate values of m, there is always a certain value of m for which it becomes worse than the histogram estimator. This shift of regime occurs between m 10 for the distribution Beta(0.5, 0.5)

Private Statistical Estimation of Many Quantiles

and m 40 for the distribution Beta(2, 5).

Error of the histogram-based approach. The shape of the error for the histogram estimator is almost flat. Again, it is compatible with Theorem 4.4 : The control in infinite norm is well suited for the histograms.

Role of the Lipschitz constant. By crossing the shape of the beta distributions (see Appendix J) and Figure 1, a pattern becomes clear : The distributions on which the histogram estimator performs best (i.e. the distributions on which it becomes the best estimator for the lowest possible value of m) are the distributions with the smallest Lipschitz constant. This was expected since the guarantees of utility of Theorem 4.4 get poorer the higher this quantity is.

6. Conclusion

Privately estimating the (statistical) quantile function of a distribution has some interesting properties. For low to mid values of m, this article demonstrated that there is a real incentive in estimating it on a finite sample of m points. This was done by using algorithms recently introduced in order to estimate the empirical quantiles of a dataset. However, when the number m becomes too high, the previously-mentioned algorithms become suboptimal. It is then more effective to estimate the density with a histogram. Furthermore, the utility results are qualitatively stronger : The estimation is uniform over an interval, as opposed to pointwise on a finite set. Theorem 3.5 and Theorem 4.4 can be used to decide what method to choose.

An interesting question would be to know if it is possible to modify Rec Exp in such regimes in order to bridge the gap with histograms. Possibly by adapting the privacy budget to the depth in the computation tree.

Another interesting question would be to investigate the possible (minimax) optimality of the techniques of this article on restricted classes of distributions or regimes of m.

Acknowledgments

Aur elien Garivier acknowledges the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d Avenir (ANR-16-IDEX0005), and Chaire Seq ALO (ANR-20-CHIA-0020-01).

This project was supported in part by the Allegro Assai ANR project ANR-19-CHIA-0009.

Cl ement Lalanne would like to thank Adam D. Smith for the suggestion of important references.

Additionally, the authors would like top thank the anonymous reviewers for their suggestions and inputs that helped

to improve the current version of this article.

Abadi, M., Chu, A., Goodfellow, I. J., Mc Mahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Weippl, E. R., Katzenbeisser, S., Kruegel, C., Myers, A. C., and Halevi, S. (eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pp. 308 318. ACM, 2016. doi: 10.1145/2976749.2978318. URL https: //doi.org/10.1145/2976749.2978318.

Abowd, J. M. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2867 2867, 2018.

Acharya, J., Sun, Z., and Zhang, H. Differentially private testing of identity and closeness of discrete distributions. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, Neur IPS 2018, December 3-8, 2018, Montr eal, Canada, pp. 6879 6891, 2018. URL https://proceedings.neurips.cc/ paper/2018/hash/ 7de32147a4f1055bed9e4faf3485a84d Abstract.html.

Acharya, J., Canonne, C., Singh, A. V., and Tyagi, H. Optimal rates for nonparametric density estimation under communication constraints. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 26754 26766. Curran Associates, Inc., 2021a. URL https://proceedings.neurips.cc/ paper files/paper/2021/file/ e1021d43911ca2c1845910d84f40aeae Paper.pdf.

Acharya, J., Canonne, C. L., Freitag, C., Sun, Z., and Tyagi, H. Inference under information constraints iii: Local privacy constraints. IEEE Journal on Selected Areas in Information Theory, 2(1):253 267, 2021b. doi: 10.1109/JSAIT.2021.3053569. URL https:// doi.org/10.1109/JSAIT.2021.3053569.

Acharya, J., Canonne, C. L., Mayekar, P., and Tyagi, H. Information-constrained optimization: can adaptive processing of gradients help? Co RR, abs/2104.00979, 2021c. URL https://arxiv.org/abs/2104.00979.

Private Statistical Estimation of Many Quantiles

Acharya, J., Canonne, C. L., Sun, Z., and Tyagi, H. Unified lower bounds for interactive high-dimensional estimation under information constraints. Co RR, abs/2010.06562, 2021d. URL https://arxiv.org/ abs/2010.06562.

Acharya, J., Sun, Z., and Zhang, H. Differentially private assouad, fano, and le cam. In Feldman, V., Ligett, K., and Sabato, S. (eds.), Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Research, pp. 48 78. PMLR, 2021e. URL http://proceedings.mlr.press/ v132/acharya21a.html.

Alabi, D., Ben-Eliezer, O., and Chaturvedi, A. Bounded space differentially private quantiles. Co RR, abs/2201.03380, 2022. URL https://arxiv.org/abs/2201.03380.

Allen, J. e. a. Smartnoise core differential privacy library. https://github.com/opendp/ smartnoise-core.

Asi, H. and Duchi, J. C. Near instance-optimality in differential privacy. Co RR, abs/2005.10630, 2020. URL https://arxiv.org/abs/2005.10630.

Backstrom, L., Dwork, C., and Kleinberg, J. M. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In Williamson, C. L., Zurko, M. E., Patel-Schneider, P. F., and Shenoy, P. J. (eds.), Proceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8-12, 2007, pp. 181 190. ACM, 2007. doi: 10.1145/1242572.1242598. URL https: //doi.org/10.1145/1242572.1242598.

Barnes, L. P., Han, Y., and Ozgur, A. Fisher information for distributed estimation under a blackboard communication protocol. In 2019 IEEE International Symposium on Information Theory (ISIT), pp. 2704 2708, 2019. doi: 10.1109/ISIT.2019.8849821.

Barnes, L. P., Chen, W.-N., and Ozgur, A. Fisher information under local differential privacy. IEEE Journal on Selected Areas in Information Theory, 1(3):645 659, 2020a. doi: 10.1109/JSAIT.2020.3039461. URL https:// doi.org/10.1109/JSAIT.2020.3039461.

Barnes, L. P., Han, Y., and Ozg ur, A. Lower bounds for learning distributions under communication constraints via fisher information. Journal of Machine Learning Research, 21:Paper No. 236, 30, 2020b. ISSN 1532-4435. URL https://jmlr.csail.mit.edu/ papers/volume21/19-737/19-737.pdf.

Berrett, T. and Butucea, C. Classification under local differential privacy, 2019. URL https://arxiv.org/ abs/1912.04629.

Blocki, J., Blum, A., Datta, A., and Sheffet, O. The johnsonlindenstrauss transform itself preserves differential privacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pp. 410 419. IEEE Computer Society, 2012. doi: 10.1109/FOCS.2012.67. URL https://doi.org/10.1109/FOCS.2012.67.

Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. P. Differentially private release and learning of threshold functions. In Guruswami, V. (ed.), IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 634 649. IEEE Computer Society, 2015. doi: 10.1109/FOCS.2015.45. URL https://doi.org/10.1109/FOCS.2015.45.

Butucea, C., Dubois, A., Kroll, M., and Saumard, A. Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids. Co RR, abs/1903.01927, 2019. URL http://arxiv.org/ abs/1903.01927.

Denisov, S., Mc Mahan, H. B., Rush, J., Smith, A. D., and Thakurta, A. G. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In Neur IPS, 2022. URL http://papers.nips.cc/ paper files/paper/2022/hash/ 271ec4d1a9ff5e6b81a6e21d38b1ba96Abstract-Conference.html.

Devroye, L. Non-Uniform Random Variate Generation. Springer, 1986. ISBN 978-1-4613-8645-2. doi: 10.1007/978-1-4613-8643-8. URL https:// doi.org/10.1007/978-1-4613-8643-8.

Ding, B., Kulkarni, J., and Yekhanin, S. Collecting telemetry data privately. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3571 3580, 2017. URL https://proceedings.neurips.cc/ paper/2017/hash/ 253614bbac999b38b5b60cae531c4969Abstract.html.

Dinur, I. and Nissim, K. Revealing information while preserving privacy. In Neven, F., Beeri, C., and Milo, T. (eds.), Proceedings of the Twenty-Second ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database

Private Statistical Estimation of Many Quantiles

Systems, June 9-12, 2003, San Diego, CA, USA, pp. 202 210. ACM, 2003. doi: 10.1145/773153.773173. URL https://doi.org/10.1145/773153.773173.

Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Co RR, abs/1905.02383, 2019. URL http: //arxiv.org/abs/1905.02383.

Dong, J., Durfee, D., and Rogers, R. Optimal differential privacy composition for exponential mechanisms. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 2597 2606. PMLR, 2020. URL http://proceedings.mlr.press/ v119/dong20a.html.

Drechsler, J., Globus-Harris, I., Mcmillan, A., Sarathy, J., and Smith, A. Nonparametric Differentially Private Confidence Intervals for the Median. Journal of Survey Statistics and Methodology, 10(3):804 829, 06 2022. ISSN 2325-0984. doi: 10.1093/jssam/smac021. URL https://doi.org/10.1093/jssam/smac021.

Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy and statistical minimax rates. In 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Allerton Park & Retreat Center, Monticello, IL, USA, October 2-4, 2013, pp. 1592. IEEE, 2013. doi: 10.1109/Allerton.2013.6736718. URL https: //doi.org/10.1109/Allerton.2013.6736718.

Duchi, J. C., Jordan, M. I., and Wainwright, M. J. Local privacy, data processing inequalities, and statistical minimax rates, 2014. URL https://arxiv.org/abs/ 1302.3203.

Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 407, 2014. doi: 10.1561/0400000042. URL https://doi.org/10.1561/0400000042.

Dwork, C., Kenthapadi, K., Mc Sherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In Vaudenay, S. (ed.), Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pp. 486 503. Springer, 2006a. doi: 10.1007/11761679\ 29. URL https://doi.org/10.1007/11761679 29.

Dwork, C., Mc Sherry, F., Nissim, K., and Smith, A. D. Calibrating noise to sensitivity in private data analysis. In Halevi, S. and Rabin, T. (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006,

New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pp. 265 284. Springer, 2006b. doi: 10.1007/11681878\ 14. URL https://doi.org/10.1007/11681878 14.

Erlingsson, U., Pihur, V., and Korolova, A. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In Ahn, G., Yung, M., and Li, N. (eds.), Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014, pp. 1054 1067. ACM, 2014. doi: 10.1145/2660267.2660348. URL https://doi.org/ 10.1145/2660267.2660348.

Fredrikson, M., Jha, S., and Ristenpart, T. Model inversion attacks that exploit confidence information and basic countermeasures. In Ray, I., Li, N., and Kruegel, C. (eds.), Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pp. 1322 1333. ACM, 2015. doi: 10.1145/2810103.2813677. URL https: //doi.org/10.1145/2810103.2813677.

Gillenwater, J., Joseph, M., and Kulesza, A. Differentially private quantiles. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 3713 3722. PMLR, 2021. URL http://proceedings.mlr.press/ v139/gillenwater21a.html.

Gy orfi, L., Kohler, M., Krzyzak, A., and Walk, H. A Distribution-Free Theory of Nonparametric Regression. Springer series in statistics. Springer, 2002. ISBN 9780-387-95441-7. doi: 10.1007/b97848. URL https: //doi.org/10.1007/b97848.

Henzinger, M. and Upadhyay, J. Constant matters: Finegrained complexity of differentially private continual observation using completely bounded norms. Co RR, abs/2202.11205, 2022. URL https://arxiv.org/ abs/2202.11205.

Homer, N., Szelinger, S., Redman, M., Duggan, D., Tembe, W., Muehling, J., Pearson, J. V., Stephan, D. A., Nelson, S. F., and Craig, D. W. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLo S Genet, 4 (8):e1000167, 2008.

IBM. Smartnoise core differential privacy library. https://github.com/IBM/differentialprivacy-library.

Kairouz, P., Oh, S., and Viswanath, P. The composition theorem for differential privacy. In Bach, F. R. and

Private Statistical Estimation of Many Quantiles

Blei, D. M. (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1376 1385. JMLR.org, 2015. URL http://proceedings.mlr.press/ v37/kairouz15.html.

Kamath, G., Liu, X., and Zhang, H. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In Chaudhuri, K., Jegelka, S., Song, L., Szepesv ari, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 10633 10660. PMLR, 2022. URL https://proceedings.mlr.press/v162/ kamath22a.html.

Kaplan, H., Ligett, K., Mansour, Y., Naor, M., and Stemmer, U. Privately learning thresholds: Closing the exponential gap. In Abernethy, J. D. and Agarwal, S. (eds.), Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pp. 2263 2285. PMLR, 2020. URL http://proceedings.mlr.press/ v125/kaplan20a.html.

Kaplan, H., Schnapp, S., and Stemmer, U. Differentially private approximate quantiles. In Chaudhuri, K., Jegelka, S., Song, L., Szepesv ari, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 10751 10761. PMLR, 2022. URL https://proceedings.mlr.press/v162/ kaplan22a.html.

Kroll, M. On density estimation at a fixed point under local differential privacy. Electronic Journal of Statistics, 15 (1):1783 1813, 2021. doi: 10.1214/21-EJS1830. URL https://doi.org/10.1214/21-EJS1830.

Lalanne, C., Gastaud, C., Grislain, N., Garivier, A., and Gribonval, R. Private quantiles estimation in the presence of atoms. Co RR, abs/2202.08969, 2022. URL https: //arxiv.org/abs/2202.08969.

Lalanne, C., Garivier, A., and Gribonval, R. On the Statistical Complexity of Estimation and Testing under Privacy Constraints. Transactions on Machine Learning Research Journal, April 2023. URL https://hal.science/ hal-03794374.

Loukides, G., Denny, J. C., and Malin, B. A. The disclosure of diagnosis codes can breach research participants privacy. J. Am. Medical Informatics Assoc., 17(3):322 327,

2010. doi: 10.1136/jamia.2009.002725. URL https: //doi.org/10.1136/jamia.2009.002725.

Mc Sherry, F. and Talwar, K. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 94 103. IEEE Computer Society, 2007. doi: 10.1109/FOCS.2007.41. URL https://doi.org/ 10.1109/FOCS.2007.41.

Narayanan, A. and Shmatikov, V. How to break anonymity of the netflix prize dataset. Co RR, abs/cs/0610105, 2006. URL http://arxiv.org/abs/cs/0610105.

Narayanan, A. and Shmatikov, V. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA, pp. 111 125. IEEE Computer Society, 2008. doi: 10.1109/SP.2008.33. URL https://doi.org/10.1109/SP.2008.33.

Nissim, K., Raskhodnikova, S., and Smith, A. D. Smooth sensitivity and sampling in private data analysis. In Johnson, D. S. and Feige, U. (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 75 84. ACM, 2007. doi: 10.1145/1250790.1250803. URL https://doi.org/ 10.1145/1250790.1250803.

Smith, A. D. Privacy-preserving statistical estimation with optimal convergence rates. In Fortnow, L. and Vadhan, S. P. (eds.), Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pp. 813 822. ACM, 2011. doi: 10.1145/1993636.1993743. URL https://doi.org/ 10.1145/1993636.1993743.

Steinberger, L. Efficiency in local differential privacy, 2023. URL https://arxiv.org/abs/2301.10600.

Sweeney, L. Simple demographics often identify people uniquely. Health (San Francisco), 671(2000):1 34, 2000.

Sweeney, L. k-anonymity: A model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl. Based Syst., 10(5):557 570, 2002. doi: 10.1142/ S0218488502001648. URL https://doi.org/ 10.1142/S0218488502001648.

Thakurta, A. G., Vyrros, A. H., Vaishampayan, U. S., Kapoor, G., Freudiger, J., Sridhar, V. R., and Davidson, D. Learning new words. Granted US Patents, 9594741, 2017.

Private Statistical Estimation of Many Quantiles

Tsybakov, A. B. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, 2009. ISBN 9780-387-79051-0. doi: 10.1007/b13794. URL https: //doi.org/10.1007/b13794.

Van der Vaart, A. W. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. doi: 10.1017/ CBO9780511802256.

Wagner, I. and Eckhoff, D. Technical privacy metrics: A systematic survey. ACM Comput. Surv., 51(3):57:1 57:38, 2018. doi: 10.1145/3168389. URL https: //doi.org/10.1145/3168389.

Wasserman, L. A. and Zhou, S. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375 389, 2010. doi: 10.1198/jasa.2009.tm08651. URL https:// doi.org/10.1198/jasa.2009.tm08651.

Private Statistical Estimation of Many Quantiles

A. Proof of Lemma 3.1

i=1 1(F 1 X (p)+γ,+ )(Xi) .

Let k { E(np) + 1, . . . , n E(np)}. We have the following event inclusion: X(E(np)+k) > F 1 X (p) + γ N n (E(np) + k) N n(1 p) k 1 .

N being a sum of independent Bernoulli random variables, we introduce η := 1 p γπ , a natural upper bound on the probability of success of each of these Bernoulli random variables. Hence, by multiplicative Chernoff bounds, whenever γπ η k+1

nη 0, which is equivalent to k nγπ 1,

P X(E(np)+k) > F 1 X (p) + γ P N nη 1 + γπ η k + 1

By going further and imposing that k + 1 1

2nγπ , we get

P X(E(np)+k) > F 1 X (p) + γ e nη

Finally, by noticing that η γπ η 2 / 2 + γπ 2η = γ2π 2

P X(E(np)+k) > F 1 X (p) + γ e γ2π 2

Now, looking at the other inequality, we define

i=1 1( ,F 1 X (p) γ)(Xi) .

Like previously, X(E(np)+k) < F 1 X (p) γ N E(np) + k N np + k 1 .

With the exact same techniques as previously, imposing the condition k 1 1

P X(E(np)+k) < F 1 X (p) γ e γ2π 2

Thus, under the various conditions specified for k, by union bound,

P |X(E(np)+k) F 1 X (p)| > γ e γ2π 2

8p n + e γ2π 2

Now define I := {k { E(np), . . . , n E(np)}||X(E(np)+k) F 1 X (p)| γ}. Notice that since X(1) X(2) X(n), I is an integer interval. Which means that if a I b I, then [a, b] Z I. As a consequence, if |X(E(np)+k) F 1 X (p)| γ for two integers k1 and k2, it is also the case for all the integers between them. By union bound, we get

P sup k J |X(E(np)+k) F 1 X (p)| > γ 2e γ2π 2

8p n + 2e γ2π 2

J := max E(np) + 1, E 1

+ 1 , . . . , min n E(np), E 1

Private Statistical Estimation of Many Quantiles

B. Proof of Lemma 3.2

The following fact is a direct consequence of Lemma 2.1 in Chapter 5 of (Devroye, 1986).

Fact B.1 (Concentration of the gaps for uniform samples). Let X1, . . . , Xn i.i.d. U([0, 1]), the uniform distribution on [0, 1]. Denoting 1 := X(1), 2 := X(2) X(1), . . . , n := X(n) X(n 1), and n+1 := 1 X(n), for any γ > 0 such that γ < 1 n+1,

P min i i > γ = (1 (n + 1)γ)n .

We give a proof here for completeness. The first step consists in characterizing the distribution of ( 1, . . . , n). Let h : Rn R be a positive Borelian function. By the transfer theorem, Z h( 1, . . . , n)d P( 1, . . . , n) = Z h(X(1), X(2) X(1), . . . , X(n) X(n 1))d P(X(1), . . . , X(n)) .

Furthermore, (X(1), . . . , X(n)) follows a uniform distribution on the set of n ordered points in [0, 1]. Hence, Z h( 1, . . . , n)d P( 1, . . . , n) = 1

Z h(X1, X2 X1, . . . , Xn Xn 1)10 X1 Xn 1d X1 . . . d Xn .

Finally, the variable swap δ1 = X1, δ2 = X2 X1, . . . , δn = Xn Xn1 that has a jacobian of 1, same as its inverse (both transformations are triangular matrices with only 1 s on the diagonal), gives that Z h( 1, . . . , n)d P( 1, . . . , n) = 1

Z h(δ1, . . . , δn)10 δ1,...,0 δn,Pn i=1 δi 1dδ1 . . . dδn .

The last equation means that ( 1, . . . , n) follows a uniform distribution on the simplex 0 1, . . . , n

1, Pn i=1 i 1 . The probability P (mini i > γ) may now be computed as

P min i i > γ = n! Z 1γ<δ1,...,γ<δn,Pn i=1 δi<1 γ10 δ1,...,0 δn,Pn i=1 δi 1dδ1 . . . dδn,

and by considering the variable swap δ i := δi γ 1 (n+1)γ (which is separable) of which the jacobian of the inverse is (1 (n + 1)γ)n,

P min i i > γ = n!(1 (n + 1)γ)n Z 10<δ 1,...,0<δ n,Pn i=1 δ i<1dδ 1 . . . dδ n = (1 (n + 1)γ)n .

This concludes the proof of Fact B.1. Now, X1, . . . , Xn i.i.d. Pπ where π is a density on [0, 1] w.r.t. Lebesgue s measure such that π R π π R > 0 almost surely. In particular, the data is not necessary uniform. By a coupling argument,

if U1, . . . , Un i.i.d. U([0, 1]), F 1 π (U1), . . . , F 1 π (Un) has the same distribution as (X1, . . . , Xn). We can furthermore notice that p, q (0, 1), ϵ > 0, , |p q| > ϵ = F 1 π (p) F 1 π (q) > ϵ

Indeed, the lower bound π π ensures that Fπ is a bijection and that so does its inverse. The upper bound π π ensures that Fπ cannot grow too fast, and thus that its inverse is not too flat. Formally,

a, b, |Fπ(b) Fπ(a)| =

In particular, it holds for b = F 1 π (p) and a = F 1 π (q).

Consequently, if 1 := U(1), 2 := U(2) U(1), . . . , n := U(n) U(n 1), and n+1 := 1 U(n),

P min i i > γ P min i i > πγ = (1 (n + 1) πγ)n .

Private Statistical Estimation of Many Quantiles

Finally, let us simplify this expression to a easy-to-handle one. If γ < n 2 π,

P min i i > γ

Furthermore, for any x (0, 1/2) and n 1, by the Taylor-Lagrange formula, there exist c x

n = en ln(1 x

2 1 (1+c)2 x2

And so, when n 1, 1 x

In definitive, when n 1 and γ < 1 4 π P min i i > γ

C. Proof of Theorem 3.3

For simplicity, let us assume that E 1 2nγπ

1 min (E(np) 1, n E(np)), which is for instance the case when

γ < 2 min(p,1 p)

π , which we suppose. Furthermore, suppose that 1

2nγπ 2, which is for instance the case when

n > 2/ min(p, 1 p) thank to the hypothesis on γ. By noting K := E 1 4nγπ

, Lemma 3.1 says that,

sup k { K,...,K} |X(E(np)+k) F 1 X (p)| > γ

8 max(p,(1 p)) n ,

We call QC (for quantile concentration) this last event. Let δ > 0 that satisfies δ < 1 4 π. We define the event G := mini i > δ n2 (for gaps). Lemma 3.2 ensures that

P (Gc) 1 e 4 πδ .

Conditionally to QC, denoting by q the output of QExp, |q F 1 π (p)| > γ = E K 1 K/2 whenever n 4/(γπ ). By also working conditionally to G, and in order to apply Fact 2.1, we look for a β > 0 such that

K/2 = 2 ln(n2) + ln 1

which gives

δ e ϵE 1 4 nγπ

Note that even if Fact 2.1 is stated for β (0, 1), its conclusion remains obviously true for β 1.

Finally, P |q F 1 π (p)| > γ P |q F 1 π (p)| > γ, QC, G + P (QCc) + P (Gc)

16 + 1 e 4 πδ + 4e γ2π 2

8 max(p,1 p) n,

and by fixing δ := n e 2

32 , because 1 e 4 πδ 8 πδ for any δ > 0,

P |q F 1 π (p)| > γ 4n

32 + 4e γ2π 2

8 max(p,(1 p)) n .

D. Proof of Corollary 3.4

Ind Exp is the application of m independent QExp procedures but with privacy parameter ϵ

m in each. A union bound on the events that check if each quantile is off by at least γ gives the result by Theorem 3.3.

Private Statistical Estimation of Many Quantiles

E. Proof of Theorem 3.5

For simplicity, let us assume that E 1 2nγπ

1 min (E(np1) 1, n E(npm)), which is for instance the case when

γ < 2 mini min(pi,1 pi)

π , which we suppose. Furthermore, suppose that 1

2nγπ 2 , which is for instance the case when

n > 2/ mini min(pi, 1 pi) thank to the hypothesis on γ. By noting K := E 1 4nγπ

, Lemma 3.1 says that for any

i {1, . . . , m},

sup k { K,...,K} |X(E(npi)+k) F 1 X (pi)| > γ

8Cp1,...,pm n ,

where Cp1,...,pm := maxi (max (pi, (1 pi))). We define the event QC (for quantile concentration),

sup k { K,...,K} |X(E(npi)+k) F 1 X (pi)| γ

By union bounds,

P (QCc) 4me γ2π 2

8Cp1,...,pm n .

Let δ > 0 that satisfies δ < 1 4 π. We define the event G := mini i > δ n2 (for gaps). Lemma 3.2 ensures that

P (Gc) 1 e 4 πδ .

Conditionally to QC, denoting by q the output of Rec Exp, q F 1 π (p) > γ = E K 1 K/2 whenever n 4/(γπ ). By also working conditionally to G, and in order to apply Fact 2.2, we look for a β > 0 such that

K/2 = 2(log2 m + 1)2 ln(n2) + ln 1

δ + ln m + ln 1 β

which gives

δ e ϵE 1 4 nγπ

4(log2 m+1)2 .

Note that even if Fact 2.2 is stated for β (0, 1), its conclusion remains obviously true for β 1.

Finally, P q F 1 π (p) > γ P q F 1 π (p) > γ, QC, G + P (QCc) + P (Gc)

δ e ϵnγπ 32(log2 m+1)2 + 1 e 4 πδ + 4me γ2π 2

8Cp1,...,pm n,

and by fixing δ := n em

2 π e ϵnγπ 32(log2 m+1)2 , we get that,

P q F 1 π (p) > γ 4n

2e πme ϵnγπ 32(log2 m+1)2 + 4me γ2π 2

8Cp1,...,pm n .

F. Proof of Lemma 4.1

By definition of u QExp we have n u QExp (X1, . . . , Xn), q 0 for any input, hence using that 0 γ 1/4 we get

P |q t| > γ =

[0,1]\[t γ,t+γ] e ϵ 2 u QExp (X1,...,Xn),q dq R

[0,1] e ϵ 2 u QExp (X1,...,Xn),q dq

[0,1]\[t γ,t+γ] e ϵ

Private Statistical Estimation of Many Quantiles

G. Proof of Lemma 4.2

Let us consider a specific bin of the histogram b. Let γ > 0. Denoting by ,b the infinite norm restrained to the support of b, which is a semi-norm, we have

P ˆπhist π ,b > γ = P

i=1 1b(Xi) + 2

where L Lap(1), a centered Laplace distribution of parameter 1. So,

P ˆπhist π ,b > γ = P

i=1 1b(Xi) π

triangular inequality P

i=1 1b(Xi) π

+ P 2 nhϵL > γ/2

Let us first control the first term. Since π is L Lipschitz, x b, π(x) 1

2 . So, when γ > Lh,

i=1 1b(Xi) π

i=1 1b(Xi) 1

Finally, notice that the family (1b(Xi))i is a family of i.i.d. Bernoulli random variables of probability of success R

b π. By Hoeffding s inequality,

i=1 1b(Xi) π

2e h2(γ Lh)2

The second term is controlled via a tail bound on the Laplace distribution as

P 2 nhϵL > γ/2 = P |L| > γnhϵ

So, if γ > Lh,

P ˆπhist π ,b > γ 2e h2(γ Lh)2

4 n + e γhnϵ

Finally, a union bound on all the bins gives that if γ > Lh,

P ˆπhist π > γ 2

he h2(γ Lh)2

H. Proof of Lemma 4.3

F 1 π (p) + α

! ˆπ π α Fπ

F 1 π (p) + α

π π Fπ F 1 π (p) + α

= Fπ F 1 π (p) = p .

Private Statistical Estimation of Many Quantiles

So, F 1 ˆπ (p) F 1 π (p) + α

Furthermore, for any t 2α

π , F 1 π (p) ,

Fˆπ F 1 π (p) t ˆπ π α Fπ F 1 π (p) t + α

π π Fπ F 1 π (p) tπ + α

< Fπ F 1 π (p) 2α

= Fπ F 1 π (p) α < p .

So, for any t 2α

π , F 1 π (p) ;

F 1 ˆπ (p) F 1 π (p) t ,

and finally,

F 1 ˆπ (p) F 1 π (p) 2α

I. Proof of Theorem 4.4

Given γ 2Lh

, γπ 2 2π Lh

2π = Lh. So, Lemma 4.2 applies and gives that

P ˆπhist π > γπ 2

Furthermore, I = Fπ ((γ0, 1 γ0). So,

p I, γ0 < F 1 π (p) < 1 γ0 .

In particular, when ˆπhist satisfies ˆπhist π γπ 2 , Lemma 4.3 applies and gives

p I, |F 1 ˆπhist(p) F 1 π (p)| γ .

This is equivalent to p I, F 1 ˆπhist(p) F 1 π (p) ,I γ .

P F 1 ˆπhist F 1 π ,I > γ 1

2 Lh 2 n; .

J. Distributions for the experiments

Private Statistical Estimation of Many Quantiles

0.00 0.25 0.50 0.75 1.00 x

Beta(0.5,0.5) Beta(2,5) Beta(1,3) Beta(2,2)

pdf : probability distribution function , is the density w.r.t. Lebesgue s measure.

Figure 2. Distributions used for the experiments