Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
Authors: Omri Ben-Eliezer
Dan Mikulincer
Ilias Zadik
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
convex floating body
high-dimensional probability
quantile estimation

Abstract: The last few years have seen a surge of work on high dimensional statistics under privacy constraints, mostly following two main lines of work: the "worst case" line, which does not make any distributional assumptions on the input data; and the "strong assumptions" line, which assumes that the data is generated from specific families, e.g., subgaussian distributions.
In this work we take a middle ground, obtaining new differentially private algorithms with polynomial sample complexity for estimating quantiles in high-dimensions, as well as estimating and sampling points of high Tukey depth, all working under very mild distributional assumptions. 

From the technical perspective, our work relies upon fundamental robustness results in the convex geometry literature, demonstrating how such results can be used in a private context. Our main object of interest is the (convex) floating body (FB), a notion going back to Archimedes, which is a robust and well studied high-dimensional analogue of the interquantile range of a distribution.  We show how one can privately, and with polynomially many samples, (a) output an approximate interior point of the FB -- e.g., "a typical user" in a high-dimensional database -- by leveraging the robustness of the Steiner point of the FB; and at the expense of polynomially many more samples, (b) produce an approximate uniform sample from the FB, by constructing a private noisy projection oracle.


Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
Omri Ben-Eliezer Department of Mathematics
Dan Mikulincer
Ilaas Zadik
Department of Mathematics
Department of Mathematics MIT Sradik@mit.om edu
MIT
MIT danmiku@mit.eom
omribemit.edu
Abstract
The last few years have seen surge of work on high dimensional statistics under privacy constraints, mostly following two main lines of work: the "worst case" line, which does not make any distributional assumptions "strong assumptions" line, which assumes that the data is generated from specific families, e-g., subgaussian distributions. In this work take middle ground, obtaining new differentially private algorithms with polynomial sample complexity for estimating quantiles in high-dimensions, points of high Tukey depth, all working under very mild distributional assumptions. From the technical perspective, our work relies upon fundamental robustness results in the convex geometry literature, demonstrating how such results can be used in private context. Our main object of interest is the (convex) floating body (FB), notion going back to Archimedes, which is robust and well studied high- dimensional analogue of the interquantile range. We show how one can privately, and with polynomially many samples. (a) output an approximate interior point of the FB e.g., "a typical user" in a high-dimensional database by leveraging the robustness of the Steiner point the FB; and at the expense polynomially many more samples, (b) produce an approximate uniform sample from the FB, by constructing private noisy projection oracle.
the input data; and the
well estimating and sampling
Introduction
Computing statistics of large, complex high-dimensional datasets under privacy constraints is fundamental challenge in modern data science. In this work, we study the sample complexity of several different tasks related estimating the quantiles of d-dimensional distribution D, from having sample access to it, under privacy constraints. Our first focus is on estimating quantiles of fixed marginals. For random vector E Rd the quantiles of X along direction O the quantiles the -one-dimensiona) marginal (X, 0). which we denote by Qg((X, 6)) for E [0. 1]. Our second focus on estimating a convex region called the floating body of dd-dimensional distribution, an analogue of the 1-dimensional interquantile range exhibiting rich mathematical properties, investigated over decades of research convex geometry and sharing connections with the work Archimedes (see, e.g., the survey [NSW19]). Formally, the g-flaating body of random vector X E Rd is given by
((.)))
(x(X)
n {ar Rd (x,0) < (x((x)))), 0E34-1
(I)
and in statistical language corresponds to the points of so-called Tukey-depth at least 1 - g [NSW19]] When clear from context, we also denote (D) the floating body of the random vector X D. See Figure I for simple demonstration of the floating body.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Support(X)
(o((x,0)
F(()
Figure 1: The floating body of a dataset X.
Similar to their I-dimensional analogues, the quantiles in high-dimensions are preferred to other descriptive statisties and location estimators due to their robustness properties [Hub81, MR97] and high breakdown points [DG07, Alo03, TP16]. As opposed to other statistics, marginal quantiles can be estimated under the mere minimal distributional assumption having non-trivial mass around the location of the quantiles (see e.g. [AMBI] 19, Lemma 3J). Moreover, the floating body can also be estimated in the Hausdorff distance for log-concave measures and stable laws [AR20].
Besides statistical guarantees, an essential property of an estimator in modern data science is to be private. For instance, many large healthcare datasets contain sensitive patient information [DE13, ZZZ+17, FLJ+ 14, YKÖ17] and it is crucial for an estimator to balance the trade-off between protecting the privacy of the input while producing accurate statistical results.
Differential privacy (DP) the leading notion quantifying privacy guarantees randomized algorithm over input dataset. In this work, we focus on algorithms satisfying pure DP guarantees. Given a parameter > 0, e-differential privacy guarantees that the probability of a given output cannot change more than multiplicative factor e" after the arbitrary change of the input data of one data item (e.g., a single user record in a large database). More generally, e-DP can be defined as
follows with respect the Hamming distance dæ (X, X') := Hi E [n] X1 * X(),, defined for two n-tuples of samples X (X1,..., X,), X' (Xi.... Xx,) E (Rdy).
Definition 1 (e-DP). A randomized algorithm A is e-differential private if for all subsets S E F of the output space (92, F) and n-tuples of samples X2 E (IR))", holds that
(A(())) S) S e (X, Xa) (A((2) E
While there has been lot of work differential privacy, it usually analyzes algorithms under worst-case assumptions. The most closely related to our work the line of research on privately outputting an interior point of the convex hull of input points in high dimensions for worst-case input [BMNS19, KMST20, SS21, KSS20J. Only recently there has been lot of statistical work analyzing differentially private estimators under distributional assumptions for various statistical tasks [BCS15, D1,18, BCSZ18b, KSSU19, KLSU19, SU19, ZKKW20, CKS20, TVG720, KSU20J. On the topic of the present work, [TVG720] established the exact trade-off between privacy and accuracy of median estimation in one dimension. One of the main motivations of the present work is to make first step towards understanding the high-dimensional counterparts of these privacy-accuracy tradeoffs, by proposing the floating body as natural estimate under privacy constraints in high dimensions. In particular, the convexity of the floating body allows us invoke powerful robustness theorems, originating from decades of research in convex geometry. It is this combination, of classical theorems with the modern framework of DP, which yields several new and non-trivial results.
1.1 Our Contributions
The minimal assumptions. It known that even in one dimension, private quantile estimation is impossible for arbitrary measures [TVGZ20]. Thus, some assumptions required. In this work make the following minimal assumptions on the underlying distribution.
Definition 2. We say that distribution D supported on Rd has g-adiissible law with parameters R Rmin, r, > 0, if, for every 0 E Sd-1 the following four conditions hold:
1. (X 0)) [ [-Rmaxs Rmax].

---

2. For some E R it holds that [Q,((X, 0)) - (c. (c. 2 Rmin-
3. The density fo of (X,0) exists and satisfies ft()) 2 L whenever & E [Q₂ 0))
7, ()) + r].
4. If (x are i.i.d. as D, then with high probability ||x I poly(n, d), for all i [n].
The set of all such distributions is denoted by Ag(maxx: Rmin, r; L).
We now expand further on the claimed "minimality" of the above assumptions. First, note that assumptions (1) and (3) are actually necessary for consistent private quantile estimation. This is an outcome of the tight lower bound for the one-dimensional case (see the main result of [TVGZ20D, where it is established that the minimal sample complexity
privately learn one quantile of distribution explodes to infinity whenever there is no bound on the possible quantile values (R = Rmaxx = oo) the distribution has mass around the quantile (T. 0). We highlight that the latter property (of having positive density around the quantile) is a requirement for optimal estimation rates (and a standard assumption) for even non-private miedimmnsioonll quantile estimation (c.g.. see [VdV00, Chs. 21, 25.3]). Now, assumption (2) is equivalent to the assumption that the floating body contains ball of radius Ruinn Again, if Rain O. the floating body has an empty interior, and the floating body's 's estimation becomes degenerate task. Finally, assumption (4) is very mild boundedness technical condition that our data is arbitrarily saaynomiall--boundde which almost does not hurt generality. For example, for the "heavy-tailed" Cauchy random vectors this assumption holds for the polynomial dn.
Private many-quantiles estimation. Let us introduce a useful convention: we identify a fixed vec- tor X = (Xi...., X..) E (z with random vector in RR chosen uniformly from ( In other words we identify a "sample" X with the empirical distribution over its d-dimensional coordinates. Now, in [AR20] it was established that for any symmetric log-concave measure D, if one has n i.i.d. samples X = (X1...., samples satisfies for Y ~ DD with probability at least 0.9,
E (R")) from D, then the empirical measure on the
(x. = sup (Qx((X Qg((X, BEga-1
(3)
for some n = O(d/a"). Here, and throughout the paper, Ô means we omit logarithmic factors, in all parameters. One can easily generalize the above result for any q-admissible law (as described in Definition 2) (see Supplementary material).
We now proceed with an observation. For any integer M > O, and for any subset of M directions, say that one wants estimate the q-quantiles of the distribution along each of the M directions. A simple "low-dimensional" approach would be as follows; one can take n samples and then take the empirical q-quantiles of the projection of the samples along each of the M directions. Using standard concentration results having Ó(1/a²) fresh samples per direction suffices for estimation in the corresponding direction, leading to the desired estimation guarantee with = Ó(M/a²) samples. We note that for each specific direction Ö(1/a²) samples are known to be necessary [TVGZ20, Proposition 3.7]. Comparing with the guarantee of [AR20] in (3) we are lead to an interesting high-dimensional statistical phenomenon: without privacy constraints, simultaneously estimating M > d marginal quantiles in high-dimensions requires less samples than the natural (but perhaps naive) approach of projecting the points and then calculating the empirical quantile on each direction.
Our first contribution is to reveal the private analogue of the above high- Consider the task now of private estimation of M quantiles, iee. of (V, 0t)), Y D for M different directions (0.) The "naive" approach would be, as before, to first project along the different directions, but then, instead of calculating the (non-private) empirical quantiles of the projected points, one would apply the optimal private algorithm of [TVGZ20] to each projection, separately. This would lead to the guarantee in (3) with sample complexity (assuming, for simplicity, here and throughout the contribution section all parameters besides M, &, a are constant)
phenomenon.
( M a
M
n =
+
4)
EQ
'The algorithm from [TVGZ20] is technically only designed for median estimation, but with the natural modifications the same algorithm and analysis can be straightforwarddy extended for q-quantele estimation.
3

---

Our first main result is an improved private rate for the estimation of M quantiles which appropriately privatizes the nigh-dimensional result of [AR20]. Theorem 3 (informal). There exists an e-differentially privale algorithm that draws
n == d
M EO1
samples from any admissible distribution Y DD and produces an estimate in that satisfies max 1Q, 0.)) - mu. S a with probability at least 0.9.
i=1....M M
Notice that the rate described in Theorem 3 is always at least as good the rate in (4), and that it is strictly better when M > d and & > a. This constitutes indeed a private analogue of the high-dimensional phenomenon mentioned above; privately estimating M >> d can require much less samples than simply projecting and applying the one-dimensional machinery.
Private interior point. Next, we attempt to privately produce point estimates of the floating body F2(Y) itself. Our first task is to output an interior point of F, (Y), relatively easy task without privacy concerns [AR20], with clear statistical motivation of outputting "typical datapoint" in high-dimensions. We show that with polynomial in d samples one can achieve such a guarantee with small error. There has been closely related (but not fully comparable) work on this task the worst case regime, which we discuss in depth in Section 1.2.
For our result we leverage the Steiner point of the floating body, denoted (Y), (see (7) for the definition). The Steiner point has been widely studied in the context of Lipschitz selection [BL00]. In the problem of Lipschitz selection, one looks to consistently select a point from the interior of each convex body, in way which is robust to perturbations of the body. The Steiner point is celebrated for being the optimal Lipschitz selector in this setting. Just recently, this construction proved to be instrumental in the resolution of the chasing nested convex sets problem [BKL*20, Sel20, AGTG21] a problem in online learning, related Lipschitz selection. It is precisely this optimal robustness that makes the Steiner point insensitive to individual sample points, a desirable property in the design of DP algorithms. To the best of our knowledge, this is the first time the Steiner point and its properties have been used it to build differentially private estimators, and we believe it might be useful in other similar problems.
Theorem (informal), There exists an E-differentially private algorithm that draws
n n=ō d d2.5
a
EA
samples from any admissible distribution Y ~ D and produces an estimate in E Rdd that satisfies ||m - ((F(())) S a with probability at least 0.9.
In comparison, the best known dependence of the dimension in the worst case literature is of order (dd)) for pure eDD [KSS20] and of order Ö(f-55 for the weaker notion of approximate (c, 6D [BMNS19]. Thus, Theorem 4 achieves essentially the same dependence as the best known approximate DP result while enjoying the stronger guarantees of pure DP. We note again that the results are not fully comparable; see Section 1.2 for a thorough discussion.
Private sampling from the floating body. Outputting an, a-priori, arbitrary point from the floating body comes with possible drawbacks, for example biasing the output point towards or away from its boundary. This can lead inaccurate statistical conclusions if a more detailed description of the "typical datapoints" is needed. For this reason, we undertake the harder task of outputting a uniform sample. The sampling from convex bodiey problem has long and rich history with many deep results, see [KLS95, KLS97, LV06] for some prominent examples. In many cases, the computation preformed by the sampling algorithm reduces to iteratively projecting points into the convex body, along the trajectory of an appropriate Markov chain [BEL18, Lch21].
It is precisely the idea described above which serves as the working engine behind our private sampling algorithm. To cope with privacy constraints, we capitalize on known robustness properties
"See Supplementary material for definition and comparison between the different privacy notions.

---

of the projection operator (see (8)) on convex bodies, as proved in [AW93]. Remarkably, when the projected point is fixed and one considers the convex body as the variable, the projection operator is known to be 1/2-Hölder with respect to the Hausdorff distance. This allows us to build noisy projection oracle for the floating body, in private fashion. Combining the noisy oracle with known results leads to new sampling algorithm, which operates under pure differential privacy, and with guarantees in the quadratic Wasserstein distance, W2 (see Section D.2 for the definition).
Theorem 5 (informal). Let (F, be the uniform measure on the floating body. There exists an e-DP algorithm that draws
n á=ō
d2
d+
a
=2aB
samples from any admissible distribution D, and whose output, (Y) satisfies
d' W2 (P sa.
We note that the à normalizing factor in Theorem 5 serves as the correct scale for the W2 metric which typically scales as square-root of the dimension, see [Lch21] for further discussion on this.
1.2 Further Comparison with [BMNS19, KSS20]
The most closely related work to our point estimators of the floating body (Theorems and 5) are by Beimel et al. [BMNS19] and Kaplan et al. [KSS20]. Both of these works address under worst-case input the private interior point problem: namely, given (worst case) set of points 31,...; Jn in d dimensions, the task is to privately output a point that lies within the convex hull of these points. While the non-private analogue is trivial (since one can always output, say, I1), the problem becomes interestingly non-trivial when privacy considerations are introduced. To achieve such guarantees, the set of points is assumed to be a subset of a finite grid of possible points Ud (where U some finite universe). This is necessary condition for the existence of successful private estimators under worst-case assumptions [BNS13, BNSV15]), whereas this assumption is not required in our case. On the other hand, due to the use of the extension lemma, our algorithms do not have any explicit bound on the running time (see Section 1.3 below), unlike the situation in the worst case works, whose running time is generally exponential in d.
The first work [BMNS19] solves the private center point problem under approximate (c. d)ddifferet privacy, a weaker privacy guarantee than e-differential privacy, assuming that the dataset is of size at least some = ( log" ([U1)) (in the Ô term here we suppress dependencies in 6, and lower order terms). The second work [KSS20] solves the problem under pure differential privacy (as in our paper) for n = Odd log (U]), and obtains an improved ((n)) running time using Odd log (U)) samples under approximate DP. The n = Ōdd log (U) bound is currently the best known sample complexity under pure DP for this worst-case task. In both [BMNS19] and [KSS20], the authors' approach is to output a point of high Tukey-depth with respect to the set of the n points, which can be interpreted outputting element of the g-floating body of the points for some appropriate, and perhaps data-dependent, value of 4.
While our considered settings are similar but incomparable, we recall that our Theorem 4 obtains pure e-differentiall private guarantees that for any q outputs a point of the g-floating body with Ō(d-5) samples. Finally, we note that matching the sample complexity of the best (s, -appproxiie private algorithm with an E-private algorithm has been challenging in the privacy literature, e.g., in the context of high-dimensional Gaussian mean estimation [KLSU19, KSU20J, and in fact provably impossible in the worst-case context for many problems of interest; see [BMNS19] for more details.
1.3 General Approach
Our approach towards building all E-private algorithms in this work is based on an appropriate use of Lipschitz extension tool called the Extension Lemma Ba, BCSZ18b]. This lemma was also the main tool behind the construction of the private median estimator in [TVGZ20]. One of the main hurdles in constructing sample-efficient a-differentially private algorithms under distributional assumptions is that the privacy constraint needs to hold for all input data-sets, while the accuracy based on the behavior of the algorithm on wutth-igh-probbbiie or typical data-sets. The Extension
5

---

Lemma completely resolves this issue and allows the algorithm designer to focus on ensuring privacy Lipschitz Extension argument takes care to private algorithm on all possible inputs,
solely on the typical data-sets' Then pprivacy-presevvii of extending the private algorithm on typical-inpus while maintaining the original algorithm's 's output on the typical inputs (see Proposition for more details). Leveraging this tool, our results are based on a two-step procedure.
1. First we consider the (non- coon-private) estimator of interest. For example, this is the Steiner point of the floating body for Theorem 4 and the projection of a point to the floating body for The- orem 5. Then we define typical set of possible input datasets X = (X1,..., x.,)., E (R which is realized with high probability over all inputs drawn from admissible distributions. Following this we establish Lipschitzness properties of the non-private estimator seen as function of the input X with respect to the Hamming distance between two inputs of the (non (non-private) estimator, when defined only inputs from the typical set. Such robustness properties can be non-trivial and to do so we use interesting tools from convex geometry establish them for the Steiner point [BL00], and for the projection of point [AW93]. Notably, none of these estimators is inon-trivially Lipschitz with respect to the Hamming distance of the input, unless the input is the typical set. Using now the Lipschitzness properties combined with classic differential privacy ideas we can "privatize" the estimator by applying the (flattened) Laplace mechanism [TVGZ20], while ensuring high accuracy.
2.
With the Extension Lemma, we extend estimator to be defined and private on all possible inputs. The Extension Lemma also guarantees that the estimator remains identical when the input is from the typical set. These allow to obtain globally private algorithm with the same accuracy guarantee.
2 Getting Started
Extension Lemma Let us consider an arbitrary e-differentially private algorithm defined on n samples in R2 as input and belonging in some set H C (IR")d. Then the Extension Lemma guarantees that the algorithm can be always extended to a 2e-differentially private algorithm defined for arbitrary input data in (I")d with the property that if the input data belongs in H. the distribution of output values is exactly the same with the original algorithm. We note that the result in [BCSZ 8a] is "generic", in the sense of applying any input metric space and output probability space, but here we present it for simplicity only on inputs from R" and equipped with the Hamming distance, du-
Proposition 6 (The Extension Lemma, Proposition 2.1, [BCSZI8a)). Let À be e-disferentially private algorithm designed for input from H C (IRdy" with arbitrary output measure space (Ω,, F). Then there exists a randomized algorithu A defined on the whole input space (Redy" with the same output space which is 2e-differentially private and satisfies that for every X E H. A(X) A(X).
Quantiles and Floating Bodies For X a random variable over R. and E (0. 1). the q-quantile of X, which we denote Qg(X), is the smallest number in R satisfying IP (X < (X))) q. Our main object of interest is a high-dimensione analogue of the quantile, called the convex floating body, defined in (1). Notice, that for q < 3. Fg FX( necessarily empty and unfortunately it may sometimes by empty for 2 1. Assumption 2. in Definition ensures that F, (D) A and moreover that (D) contains a ball of radius Rmin. centered at (see Supplementary material for more details).
Useful Distances The following pscudo-metre measures the maximum difference between the q-quantiles of two (random) vectors.
Definition 7 (g-distance). Let q E (2, 1) and let A c sd-11 If and Y are two random vectors in Rd. their q-distance, with respect to A is defined by 5, Y: A) sup (Qg 8)) - ((Y(()))) BEA
A gd-1, we abbreviate 6, Y: A) = VY)
In the sequel, we will consider two types of set A, in Definition 7. First, finite sets of directions, which correspond to privately estimating a finite (but potentially large) number of quantiles. Second
'While this work is entirely focused on sample complexity guarantees, we note that the Extension Lemma comes in principle with no explicit termination time guarantee (see [BCSZI8a] and Appendix F).

---

the whole set of possible directions A = = In this case where 6,(X, Y; A) = (X, bounds on (X, Y) are strong enough yield allow estimation of high-dimensional statisties of (X).). such as the Steiner point of the body the projection operator to the body.
To further elaborate this remark, let recall that there is another natural convex geometric way measure distances between convex bodies, the Hausdorff distance. For two convex bodies K, K' C RR their Hausdorff distance is ÓHaus (K K2)= == inf 0|K K' tBa and K' C K + tBa), where Ba is the unit Euclidean ball in R The following connection between Haus and 6g holds.
Lemma 8. [Bru18, Lemma Let q E (,,1) and let X and Y be two random vectors in IR Suppose that (X) contains ball of radius Raann and is contained in a ball of radius Rmaxo for some Raaxx Rmin > 0. 5 (X, Y) I Rmin then, 8tans (F (X) (V))) S
3Rmaz (x Y).
2
Bmin
3 A Meta Algorithm for Hölder Queries
We are now ready to present our main result. In the introduction, we highlighted three results of our work, all of which follow from a meta-theorem resulting in a differentially private algorithm for querying generic Hölder statistics of the floating body with respect to the 6 norm. Since our result is general, requires certain notation.
Approximate Hölder queries Let E [1, oc], h E (0, 1J, and M E N. Denote by Ca the space of all convex bodies in R4, and assign M to be the dimension of the output space, equipped with the T norm. We say that map f Ca MR is h-Hölder (with constant K O, and with respect to set A Sd-l), simply Lipschitz when h 1, if
(5) where X and Y are random vectors. One example to keep in mind is when X and Y are both the empirical distributions of two samples that satisfy dx{(X,)) = 1. In this case we establish that, when drawn from admissible distributions, with high-probability (X, Y; A) is small (see Lemma 21). Thus, (5) will imply low sensitivity condition for f. a desirable property for the design of differentially private algorithms approximate f.
S (X,
turns out that many of the queries we study, like the Steiner point, are Hölder with respect to the Hausdorff distance. not the 6g metric. In light of Lemma 8, it will sometimes be convenient to restrict the domain in which (5) holds. In particular, for a fixed admissible class of measures, A2 Ruinn r, I.), we shall enforce the condition that the floating bodies contain, and contained in, a ball, as well as require some a-priori upper bound on the bg distance.
Definition 9 (Approximate Hölder functions for the class Ag (mmaax Rmin: L)). We say that is approximate h-Hööder if for all X, Y, which satisfy that for some Rd. which could depend on X,
Rmin
B(a, Rmin/ 2) C (X(X) C B(0, Rmax +r) and (,, < 4
(5) holds.
Since our private algorithm will be extended from a restricted algorithm typical set (recall the plan from Section 1.3) using Proposition 6, there no loss of privacy when considering approximate Hölder functions, as long as the desired conditions hold with high probability over the sample.
The main result. We are now prepared to state our main theorem. All results mentioned in the preceding sections will follow by working with suitable approximate Hölder functions.
Theorem 10. Fix q e (L/2, 1) and assume that D E Aq Rming v, L). Further, for h, K and A gd-1 let Ca + RM be an approximate h-Hölder function with constant K, with respect to A. Then, there is an e-differentially private algorithm A which for input X = (Xi,..., X,). sampled i.idd from D, satisfies for all a min (1, min(r, Rr.nm that P(I)A(X) -F(FF a) 2 1 -.r some n such that
2//h m/ d log ()))
WK W/' (log
(
1/h 1/1))
W/
n δ
2//h
(Ea)
( (Emin Rusn L
7

---

where W min [A]] + log
The obtained rate may seem complicated; this is to be expected, given the generality of our results and the number parameters. In the next section we demonstrate several concrete uses of Theorem 10, which show how the rate simplifies in various interesting settings.
4 Applications
Here we describe the main applications of Theorem 10. As mentioned we apply the theorem using suitable approximate Hölder functions.
Simultaneous estimation of quantiles Fix q E (0, and let A cdd1 with |A| = M. Define the multiple M --query function which random vector X, equals fa(X) = [Q₂ (X, 0)) beea-
It is immediately seen that fA is Lipschitz function', with constant 1, in the Loo (p xc) norm: max (g((x, Qg 0) 6, (X, Y; A).
( - fa(Y)l
BEA
We thus have the following result.
Corollary 11. Let Ag(Rmux, Renin: v. L) be an admissible measure on Rdd Then, there an e-differentially private algorithm A which for imput X = (X1,..., Xn), sampled i.i.d from D, satisfies for all a min(r,Reiu). P(]IA(X) fA(D)) S aa 2 0.r,
n n=Ō LLL2
M sLa + eLmin Rmin
M
+
Proof. The observation in (6) shows that Sa is a Lipschitz function with constant 1. The result now follows by invoking Theorem 10 for the Lex norm, with K / = B = 0.1, and W = =log(M). O
Privately returning an interior point: the Steiner point. Given Theorem 10 will be enough to show that one can select point from a convex body in a Lipschitz way. This naturally leads to the Steiner point, widely studied object in Lipschitz selection. For convex body K RRd define by
S(K) = d / (hk(0)do, S4-1
and its Steiner point, where is the normalized Haar measure on gd-1, and the support function of K, hg : gd-1 + R, is defined by hx (0) = max(r, 0).
The following result follows from well-known results in convex geometry and from Lemma Lemma 12. The Steiner point S Ca + I& is an approximate Lipschitz with constant
6 Buactr which satisfies S(K) E K for every convex body K.
We immediately get the following corollary to Theorem 10.
Corollary 13. Let D Ag( (omaxy Ponin v, L) be an admissible measure Rdd Then, there is an e e-disferentially private algorithm A which for input X = (X1,..., Xa), sampled i.i.d from DD satisfies for all min(r,Rmmn) P(IIA(X) S(F,
a) 2 0.9, some
= Ō (02 (Rmax + r)²
R 2? + 12.5 Rmax +r Rmin
R2
ELa minin Rmin
Proof. Consider the Steiner point S : C. - Rdd. Lemma 12 states that is an approximate Lipschitz function with constant 6v d Rmaxtr. for every X, Y. Ho. The result follows by invoking Theorem Rmin
10 for the Fuclidean norm, with K 6v/ Rmax M d, h
0.1, and W Ô(d). n
Raii
'Strictly speaking. fa is not function of the floating body. but of the sample itself. However, with trivial adaption, it still fits nicely within framework.

---

Private projection and sampling. Let K C Rd be a convex body. Define the projection operator, Px: R. RRRRR Rd by,
(x(x) arg min(y E Killy ==I}-
(8)
We shall establish that, for admissible distributions D and for any point x, one can privately estimate (F,(D)( with polynomially many samples. This follows by coupling a classic result in convex geometry, [AW93, Proposition 5.3], concerning the stability of projections with Lemma 8.
Lemma 14. Fix x E I&d and consider Pk (x(x)= Ca + R Then Px(x) is an approximate }
2 3-Hölder
function with constant 5. (1 Bray (r)nnytr][[mm (Rmast))
Rain
Now, to sample from the body K, for 17 >> we define the following discretized Langevin process:
X1+1 = Px(X; + ng))) Xo = SK),,
where {9:] J:20 are i..d. standard Gaussians and S(K) is the Steiner point of K. It is well known (see for example [Leh21, Theorem 2)) that this process mixes rapidly, in the Wasserstein distance. By applying the known results about the mixing time of the Langevin process, and by taking account of the inherent noise introduced by the privacy constraints, we prove the following result.
Corollary 15. Let D E Ag (Bmax Rmin v, L) be an admissible measure on I and let Un be random vector which is uniform on (D) Assume that Fg (D) contains a ball of radius Rmin around the Steiner point S(K). Then, there is an e-differentially private algorithm A which for input min Bmin)
X == (X1,..., Xn), sampled i..dd from from D. satisfies for all <
j W3
(3())))) sa,
for some
polyy SoolyRmaan Rmax +)+1) 1) p
df 1,1 :0
dt
dt
n Ō
+ c2 min Rmin 2
poly (Mmii)))
Corollary 15 requires that the floating body contains ball, centered the Steiner point. The reason for this assumption is that the discretized Langevin process is initiated at the Steiner point, and the distance from the initialization to the boundary of (D) will determine the mixing time of X,. We chose the Steiner point as an the initial point because, by Theorem 13, we can privately approximate it. Moreover, the Steiner point tends to lie "deeply" in the interior of the convex body, although exact estimates seem to be unknown for the general case [Sch93, Section 5.4] (however see [Shv04, Theorem 1.2] for a similar construction with relevant guarantees).
To improve performance, one might impose some extra assumptions. For example, if the distribution D is symmetric around its mean, then the Steiner point will be the center of (D) Another option is to assume that F, (D) contains a known point, like the origin, in which case we can initialize Xo = 0. We chose state Corollary 15 this way make it as general as possible.
Such sampling schemes are related to optimization of convex functions and could be of further interest. We expand this discussion in the supplementary material.
5 Proof Sketch of Theorem 10
To provide intuition, we now briefly describe how one can use the two-stage procedure from Section 1.3 to obtain Theorem 10, from which all our applications follow. We fix an approximate h--ööler query (Y),, Y D and assume for simplicity that is Hölder w.r.t 6X, Y), that = $d-1
Obtaining a "good" (non-private estimator Our first step is to obtain a (non- (rin-trivate) estimate of the query. For that, we sample n independent points { (X.) i=1 ~ DD and define X the uniform for which we compute fl (X)). In terms of accuracy, by an appropriate generalization of the arguments [AR20] to apply for any admissible distribution we have (X, Y) S (a/ K)1/h for some n = Ō(dK1/h /a//// Notice now that, by admissibility, and the discussion in Section A. it can be easily checked that (Y) satisfies the necessary geometric condition; it contains a ball and is contained in a ball, both of "controlled" radius. Hence, the approximate Hölderness implics (X)) ((F) I K&,(X, Y)*
empirical measure over (X1...., X,,, X,))

---

Designing the private estimator on a typical set. Our goal now turns to design a private, yet accurate estimate, of f(F, (X)). To do this, in principle we would desire f (FF((X) be Lipschitz (with a "good" constant, say Ay) with respect to the Hamming distance on X. Indeed, with such property the Laplace mechanism [DR14] produces an e-DP estimate of f(F with error A,/e. Unfortunately, such property cannot exist in general; as mentioned, in many cases of interest, is only known to be Lipschítz with respect to bg under certain conditions; for example, when (X) contains ball and is contained in ball. So, we must impose some restrictions on the input X.
For this reason, we design an appropriate "typical" High-probabilitg set H. S (R")", such that (X)(,, restricted to H. is Lipschitz, with respect to the Hamming distance on the input X. The properties of the typical set will allow that for all X, Y E H unless the Hamming distance du (X, "large" it holds (a)
- (X) I (X, Y and (b) 6 Y) S In ddd (X, Y). These results together imply (X)) - (X))()) S KC a variant of the Laplace mechanism, called the flattened Laplacian mechanism, [BCSZI8b, TVGZ20] which gives an e-DP, yet accurate, estimate of (X), when E H. The accuracy guarantee of the flattened Laplacian mechanism results from a careful multivariate integral caleulation.
KCt ((I"n")dH" (dn((, Y). We then apply
We now describe the typical set, H. is built as the intersection of two conditions, each one happening with high-probability The first condition is that, in every direction, the quantiles are appropriately bounded; this is satisfied since the empirical distribution of X is close to the population distribution D in the og distance. As discussed, this condition enforces property (a) from the paragraph above. The second condition more intricate, scales, to a non-negligible fraction of the points. This reduces the sensitivity of the quantile to the individual sample points and we use to establish property (b). The proof that the second condition holds with high-probability for any admissible distribution is a combination of a net-argument and an appropriate use of the one-dimensional result in [TVGZ20, Lemma B.2].
requires that, in every direction, the quantile is close, in several
Extension Lemma Finally, direct application of the Extension Lemma 6 extends the flattened Laplacian mechanism from the previous paragraph to 2--DP estimator on the whole (IZd), while remaining the same on inputs from H. Since H happens with high probability, the result follows.
Conclusion
Our work suggests several future directions. First, our estimators come with no polynomial termina- tion time guarantee since they are based on applying the generic Extension Lemma. Yet, in the one dimensional case, [TVG7200 showed that the Extension Lemma can be computed in polynomial time when applied the empirical median on an appropriate typical set. Given the analogies between our works, it is an important open problem to see if the high-dimensional estimators we propose can also be implemented in polynomial-time. Second, our work leverages classical robust convex geometric tools to construct private algorithms, which allow to demonstrate non-trivial high- high-dimensional phe- nomena. will be interesting to see if these newly introduced tools in the privacy literature can be further used to reveal other non con-trivial high-dimensions results.
Acknowledgments
DM is supported by a Vannevar Bush Faculty Fellowship ONR-N00014-2041-2226 IZ is supported by the Simons-NSF grant DMS-203 1883 on the Theoretical Foundations of Deep Learning and the Vannevar Bush Faculty Fellowship
References
[AAGM15] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman. Asymptotic geometric analysis. Part I, volume 202 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2015.
[ABC22] Daniel Alabi, Omri Ren-Eliezer, and Anamay Chaturvedi. Bounded space differentially private quantiles. CoRR, abs/2201.03380 2022.
10

---

[AGTG2I] CJ Argue, Anupam Gupta, Ziye Tang, and Guru Guruganesh. Chasing convex bodies with linear competitive ratio. Journal of the ACM (JACM), 68(5):1-10, 2021.
[Alo03] Greg Aloupis. Geometric measures of data depth. Data Depth: Robust Multivariate Analysis, Computationnal Geometry and Applications, volume 72 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 147-158, 2003.
[AMB19] Marco Avella-Medina and Eatoo-Emmanuel Brunel. Differentially private sub- sub-gaussian location estimators. arXiv preprint 190.. 2019.
[AR20] Joseph Anderson and Luis Rademacher. Efficiency of the floating body as a robust measure of dispersion. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 364-377. SIAM, 2020.
[AW93] Hédy Attouch and Roger J.-B. Wets. Quantitative stability of variational systems. II. A framework for nonlinear conditioning. SIAM J. Optim., 3(2):359-381 1993.
[BAM20] Victor-Emmanuel Brunel and Marco Avella-Medina. Propose, test, release: Differ- entially private estimation with high probability. arXiv preprint arXiv:2002.08774, 2020.
[BCS15] Christian Borgs, Jennifer T. Chayes, and Adam Smith. Private graphon estimation for sparse graphs. Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 1, NIPS' 15, page 1369-1377, Cambridge, MA, USA, 2015. MIT Press.
[BCSZ18a]
Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik. Private algorithms can always be extended. arXiv preprint wrXiv:1810.12516 2018.
[BCSZ18b] Christian Borgs, Jennifer Chayes, Adam Smith, and Haa Zadik. Revealing network structure, confidentiall:: Improved rates for node-private graphon estimation. In 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pages 533-543. IEEE, 2018.
[BEL18] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with projected Langevin Monte Carlo. Discrete Comput. Geom., 59(4)7757- 783, 2018.
[BGMNO5] Franck Barthe, Olivier Guédon, Shahar Mendelson, and Assaf Naor. A probabilistic approach to the geometry of the ey -ball. The Annals of Probability, 33(2):480-51 2005.
[BKL*20] Sébastien Bubeck. Bo' az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of the Fourteenth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 1496-1508. SIAM, 2020.
[BL00] Yoav Benyamini and Joram Lindenstrauss. Geometric nonlinear functional analysis. Vol.
1. volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.
[BMNS19] Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. Private center points and learning of halfspaces. In Proceedings of the Thirty-Secone Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 269-282. PMLR, 2019.
[BNS13] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 363-378. Springer, 2013.
[BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pages 634-649 2015.
11

---

[Bru18] Victor- EettorEmmanuul Brunel. Methods for estimation of convex sets, Statist. Sci., 33(4):615- 632, 2018.
[BS21] Claire McKay Bowen and Joshua Snoke. Comparative study of differentially private synthetic data algorithms from the NIST PSCR differential privacy synthetic data challenge. Journal of Privacy and Confideniiality 11(1), 2021.
[CKS20] Clément I. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676- 15688, 2020.
[DE13] Fida Kamal Dankar and Khaled EI Emam. Practicing differential privacy in health care: A review. Trans. Data Priv., 6(1):35-67, 67, 2013.
[DG07] PI. Davies and Ursula Gather. The breakdown point examles and counterexamples. REVSTAT Statistical Journal, 5(1):1-17, 2007.
[DJW18] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Minimax optimal pro- cedures for locally private estimation. Amer. Statist. Assoc., 113(521):182-001. 2018.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the Forty-Fine First Annual ACM Symposium on Theory of Computing, STOC '09, page 371-380, 2009.
[DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, ((3-4):211445 2014.
[Dup22] Charles Dupin. Applications de géométrie et de méchanique. Bachelier, successeur de Mme. Ve. Courcier, libraire, 1822.
[FLJ+14] 14] Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogenetics: An end-to-end case study of personalized warfarin dosing. In Proceedings of the 23rd USENIX Security Symposium, pages 17-32,
2014.
[GAH+14] 14] Marco Gaboardi, Emilio Jesus Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data. In Pro- ceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1170-1178, 2014.
[GJK21] J. Gillenwater, M. Joseph, and A. Kulesza. Differentially Private Quantiles. In Proc. International Conference on Machine Learning (ICML), 2021.
[Hea09] Thomas L. Heath, editor. The Works of Archimedes: Edited in Modern Notation with Introductory Chapters. Cambridge Library Collection Mathematics. Cambridge University Press, 2009.
[Hub81] Peter J. Huber. Robust statistics. Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1981.
[KLS95] Ravi Kannan, László Lovász, and Miklós Simonovits, Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry. 13(3):541-559 1995.
[KLS99]] Ravi Kannan, László Lovász, and Miklós Simonovits. Random walks and O" (n²) volume algorithm for convex bodies. Random Structures & Algorithms, 11(1):1-50, 1997.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, COLT 2019, volume 99
of Proceedings of Machine Learning Research, pages 1853-1902, 2019.
12

---

[KMST20] Haim Kaplan, Yishay Mansour. Uri Stemmer, and Eliad Tsfadia. Private learning of halfspaces: Simplifying the construction and reducing the sample complexity. In Advances in Neural Information Processing Systems, volume 33, pages 13965513985 2020.
[KSS20] Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1-52:15, 2020.
[KSS21] Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles. CoRR, abs/21 10.05429, 2021. To appear in ICML 2022.
[KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated gaussians. Advances in Neu- rul Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, pages 168-180, 2019.
[KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. CoRR, abs/2002.099464 2020.
[Leh21] Joseph Lehec. The Langevin monte carlo algorithm in the non-smooth log-concave case. arXiv preprint S.tii::2011.0000 2021.
[LGG+222] Clément Lalanne, Clément Gastaud, Nicolas Grislain, Aurélien Garivier, and Rémi Gribonval, Private quantiles estimation in the presence of atoms. CoRR, abs/2202.08969, 2022.
[LV06] László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an O (n²* volume algorithm. Journal of Computer and System Sciences, 72(2):392-417, 2006.
[LV07] László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithmss 30(3):307-358, 2007.
[MPSM21] Ryan McKenna, Siddhant Pradhan, Daniel Sheldon, and Gerome Miklau. Relaxed marginal consistency for differentially private query answering. CoRR, abs/2109.06153, 2021.
[MR97] M. Markatou and E. Ronchetti. Robust inference: the approach based on influence functions, volume 15 of Handbook of Statist. North-Holland, Amsterdam, 1997.
[NSW19] Stanislav Nagy, Carsten Schütt, and Elisabeth M Werner. Halfspace depth and floating body. Statistics Surveys, 13:52-118, 2019.
[PaY89) Krzysztof Przest awski and David Yost. Continuity properties of selectors and Michael's theorem. Michigan Math. J., 36( 36(1):113-134, 1989.
[Rac85] Svetlozar T Rachev. The Monge- Kantorovkt mass transference problem and its stochastic applications. Theory of Probability Its Applications, 2944):4476676, 1985.
[RRT17] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Conference Learning Theory, pages 1674-1703. PMLR, 2017.
[Sch93] Rolf Schneider. Convex bodies: the Brunn-Minkowski theory, volume 44 of Encyclo- pedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993.
[Se120] Mark Sellke. Chasing convex bodies optimally, In Proceedings of the Fourteenth Annual ACM- Symposium on Discrete Algorithms, pages 1500-1518. SIAM, 2020.
[Shv04] P. Shvartsman. Barycentric selectors and Steiner-type point of a convex body in Banach space. J. Funct. Anal., 210(1):1-42, 2004.
13

---

[SS21] Menachem Sadigurschi and Uri Stemmer. On the sample complexity of privately learning axis-aligned rectangles. In Advances in Neural Information Processing Systems, volume 34, pages (2286-28297,
[SU19] Adam Sealfon and Jonathan Ullman. Efficiently estimating erdos-renyi graphs with node differential privacy. CoRR, (at/19905.14477. 2019.
[TP16] Pingfan Tang and Jeff M. Phillips. The robustness of estimator composition. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, pages 929-937, 2016.
[TVGZ20] Christos Tzamos, Emmanouil- Vannalouil-Vasilcioos Vlatakis-Gkarakkuuue Gkaragkounis, and Ilias Zadik. Opti- mal private median estimation under minimal distributional assumptions. Advances in Neural Information Processing Systems, 33:3301-3311, 2020.
[VdVoo] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[YJvdS19] Jinsung Yoon, James Jordon, and Mihaela van der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, 2019.
[YK017] Buket Yüksel, Alptekin Küpçü, and Öznur Özkasap. Research issues for privacy and security electronic health services. Future Gener. Comput. Syst. 68:1-13, 2017.
[ZKKW20] Huanyu Zhang, Gautam Kamath, Janardhan Kulkarni, and Zhiwei Steven Wu. Privately learning Markov random fields. In Proceedings of the 37th International Conference on Machine Learning, ICML'20, 2020.
IZLZ 17] Jiajun Zhang, Xiaohui Liang, Zhikun Zhang. Shibo He, and Zhiguo Shi. Re-dpoctor: Real-time health data releasing with w-day differential privacy. In 2017 IEEE Global Communications Conference, GLOBECOM 2017, Singapore, December 4-8, 2017, pages 1-6. IEEE, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] our work
purely theoretical and has no societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
14

---

(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "hDOPqQiLdu3", "reviewer": "Reviewer_49vS", "summary": "The paper makes several contributions to the theory of private estimation from high-dimensional distributions, with a main focus on a) quantile estimation for $M$ marginals (where $M$ can be larger than the dimension $d$) and b) privately reporting an interior point in the so-called \"floating body\" of the distribution. \nPast work either makes relatively strong assumptions on the underlying distribution (e.g. subgaussian) or deal with worst-case distributions resulting in substantially worse sampling complexity. In this paper the authors seek a middle ground, identifying \"minimal\" sufficient assumptions under which $\\varepsilon$-DP sampling bounds can be shown.", "questions": "Questions:\n- Can you elaborate on the sense in which you are making \"minimal assumptions\"?\n- Can you present, at least theoretically, a class of distributions on which your estimators outperform existing ones?\n\nSmaller questions (no need to address in rebuttal):\n- Please clarify two things concerning Definition 2: Can $c$ depend on $\\theta$? Can poly$(n,d)$ depend on $\\theta$?\n- Line 91-93: I don't get this. Can't the same sample work with high probability for all $M$ directions, giving logarithmic dependence on $M$?\n- Line 106: Are you assuming $M\\geq d$ and ignoring polylogarithmic factors?\n\nComments:\n- Lines 141: Typos\n- Line 195: Missing last part of sentence", "limitations": "As far as I can tell the authors have done a good job at discussing limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper addresses an important type of questions in private statistics\n- The technical contribution over past work appears solid (based on the authors' own description, I am not familiar with the past work)\n- The simplified versions of the main results (Theorems 3 and 4) are appealing\n- Uses tools from convex geometry (Steiner point of the floating body) that are novel in this context and may be useful more generally in private estimation\n- The paper is well-written and clear\n\nWeaknesses:\n- The distributional assumptions made may be natural (given enough thought), but it is not clear in what sense they are \"minimal\" or \"needed\"\n- For problem b) the improvement over worst-case distributions lies only in replacing approximate DP with pure DP, which is arguably mainly of theoretical interest\n- The bound is on sample complexity only, there is no efficient algorithm; in particular, there is no empirical evidence that the new estimators can outperform existing ones in practice", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fiPQJml09U9", "reviewer": "Reviewer_8PiM", "summary": "This paper is on estimation of multivariate and high-dimensional quantiles under differential privacy constraints. Authors have considered the floating body representation of multivariate quantiles, which is related to Tukey depth. There are two streams of papers on differential privacy: one that considers worst-case scenario and the other that uses strong probabilistic assumptions. Unlike these mainstream lines of work, in this paper authors have attempted to use minimal probabilistic assumptions. Authors also propose privacy preserving interior point estimation and privacy preserving sampling from the floating body. \n", "questions": "Is it possible for the authors to discuss the technical assumptions more carefully and thoroughly, perhaps in the supplementary materials? Also provide a few examples of distributions and quantiles that satisfy these assumptions. \n", "limitations": "This is a theoretical work. In practice, running computations for all possible vectors on the unit ball $S_{d -1}$ is an impossible choice. Hence there has to be some more modifications when this work extends to algorithms and practical implementations. \n\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n\nThis is a study that has several interesting directions. The problem is important, and the paper and the supplementary materials are clearly written. While I did not check the technical details carefully, the arguments seem very transparent and clear in the portions of the proof of Theorem 7 that I glanced over. I think authors focus on moving away from both the stringent worst case scenario and also the strong assumption scenario is much welcome, and this is a significant contribution from that perspective. The comparison with related works from the literature shows both authors' understanding of the challenges and the areas that need further development. \n\n\nWeaknesses:\n\nWhile the technical assumptions are clearly stated, I could not find any discussion on them. For the assumptions in lines 71-77, does $R_{max}, R_{min}$ etc depend on $\\theta$ or are these constants valid uniformly for al values of $\\theta$? Depending on how it is interpreted, Assumption-2 (line 74) of Definition-2 in particular  seems a bit strange, and might be vacuously true. \n\n\nThere are quite a few typos, in particular with capitalization (or lack of capitalization) of proper nouns. \n\nAlso, I could not find any discussions on the limitations of this work, but since this is a purely theoretical work, this is less important. \nIn practice, running computations for all possible vectors on the unit ball $S_{d -1}$ is not a viable alternative. Hence there has to be some more modifications when this work extends to algorithms and practical implementations. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RrVnMf9kuL3", "reviewer": "Reviewer_Ntuo", "summary": "This paper studies sample complexity for estimating quantiles in high dimensions, which is called the convex floating body (Turkey depth at least 1-q). It shows polynomial sample complexity of a differentially private algorithm for querying generic Holder statistics of the floating body with respect to the \\delta_q norm. The result is under mild distributional assumptions. The general approach relies on the appropriate use of Extension Lemma to ensure privacy on all possible inputs rather than only the typical inputs. Following the general results, it gives three applications: private many-quantiles estimation, private interior point, and private sampling from the floating body. ", "questions": "For the three applications, the theorems statement are like ``There exists an \\epsilon-DP algorithm ...''. Can you elaborate on how to design the algorithm to achieve these bounds?", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The studied problem is interesting and important. It's a well-written paper and I enjoyed reading it. I appreciate the general results along with the three examples to make it more accessible. I'm not very familiar with private high-dimensional estimation literature. The paper provides a detailed discussion with relevant papers so that it makes it easier for me to understand the contribution. Moreover, I think the technical contribution is strong. I didn't read the appendix but the proof sketch is sound to me. In all three examples, the results improve upon the best-known previous results. \n\nWeaknesses: I have one question listed below.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KtIq-UFMGi", "reviewer": "Reviewer_zzac", "summary": "This paper looks at the problem of privately estimating the properties of the convex float body. Three different properties are considered: 1. privately estimating many-quantiles estimation; 2. private interior point; 3. private uniform sampling from the floating body. Furthermore, a nice framework of estimating approximate holder queries is proposed, which should be of own interest. ", "questions": "Is Proposition 1 technically correct? Do not we need some condition on Lipschitz?", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper looks at the problem of estimating properties of the convex body. Several upper bounds have been provided, which strictly improve the previous result.\n2. A framework of estimating approximate holder queries is proposed, which may have other applications.\n3. I like the idea of designing a Lipschitz estimator on a \"typical dataset\" and then extending it to all the possibilities of datasets by Lipschitz extension.\n\nWeakness:\n1. No lower bounds have been provided, making it hard to evaluate how \"well\" the estimators are.\n2. Many mathematical definitions are used in this work, making it a bit hard to follow. I understood that it was unavoidable in proposing a general framework. But adding more languages and intuitions will be more friendly to the readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept