Instance-Optimal Private Density Estimation in the Wasserstein Distance
Authors: Vitaly Feldman
Audra McMillan
Satchit Sivakumar
Kunal Talwar
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Density Estimation
Instance Optimality
Wasserstein Distance
Primary area: privacy
TL;DR: We give instance optimal (differentially private) algorithms for density estimation in Wasserstein distance.

Abstract: Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances.

For distributions $P$ over $\mathbb{R}$, we consider a strong notion of instance-optimality: an algorithm that uniformly achieves the instance-optimal estimation rate is competitive with an algorithm that is told that the distribution is either $P$ or $Q_P$ for some distribution $Q_P$ whose probability density function (pdf) is within a factor of 2 of the pdf of $P$. For distributions over $\mathbb{R}^2$, we use a slightly different notion of instance optimality. We say that an algorithm is instance-optimal if it is competitive with an algorithm that is given a constant multiplicative approximation of the density of the distribution. We characterize the instance-optimal estimation rates in both these settings and show that they are uniformly achievable (up to polylogarithmic factors). Our approach for $\mathbb{R}^2$ extends to arbitrary metric spaces as it goes via hierarchically separated trees. As a special case our results lead to instance-optimal learning in TV distance for discrete distributions.

Instance-Optimal Private Density Estimation in the Wasserstein Distance
Vitaly Feldman Apple
Audra McMillan Apple
Satchit Sivakumar" Boston University
Kunal Talwar Apple
Abstract
Estimating the density of a distribution from samples is a fundamental problem in statisties. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population den- sities in geographic region, small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances.
For distributions P over I, we consider a strong notion of instance-optimallty: algorithm that uniformly achieves the instance-optimal estimation rate is com- petitive with an algorithm that is told that the distribution either or Qp for some distribution Qp whose probability density function (pdf) is within factor of of the pdf of P. For distributions over TR? we use a different notion of in- stance optimality. We say that algorithm instance-optimal if it is competitive with an algorithm that is given a constant-facte multiplicative approximation the density of the distribution. We characterize the instance-optimal estimation rates in both these settings and show that they are uniformly achievable (up to polylogarithmic factors). Our approach for IR extends to arbitrary metric spaces as it goes via hierarchically separated trees. As special case our results lead to instance-optimal private learning TV distance for discrete distributions.
1 Introduction
Distribution estimation is fundamental problem in statistics. this work, we focus on the problem of learning the density of distribution over low-dimensional real space. Our motivation for studying this problem comes from practical problems such as estimating the population density in geographical area (defined by bounded two dimensional space, for e.g. [0, {) learning the
distribution accuracy of machine learning model (i.c. a distribution over [ò, 1)), estimating the average temperature across latitude, longitude, and altitude (i.c. a distribution over [o, ( etc.
In this work, we are interested in the non-pareen non-paraettric version of this question, where we make no assumptions on the form of the distribution we are learning. This is frequently of interest in practice, where population densities for example may change over time (become more or less concentrated), and it is difficult to specify meaningful parametric class that will simultaneously capture all densi- ties of interest. Given estimation is often done using sensitive data (for e.g. health data), our interest in this question is in, and consequently all our results are for, the differentially private version of this question. While we believe our results in the non non-private setting are also novel and interesting, we view the private results
main contribution.
Any statistical algorithm learning from samples is inexact. The appropriate gauge measure the (in)accuracy of density estimation algorithm depends on how this density estimate is used. In this work, we focus on the Wasserstein distance between the original distribution and the learnt
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

distribution as our measure of accuracy. Known by many names (Earthmover distance, Kantorovich distance, Optimal Transport distance), this distance is defined over any distance metric d as the minimum over all couplings from P to Q of the quantity R (x)))] It is arguably one of the most natural ways to define distances between distributions over a metric space and has been extensively studied (see Appendix C). We note that Wasserstein distance is particularly salient in many practical applications of density estimation where the geometry of the space is significant. As simple example, when creating population density estimates, if the population is concentrated in few cities, then outputting a distribution concentrated close to these cities (even if not exactly at the cities) is intuitively better than outputting distribution that is more spread out. Metrics such as TV distance that do not incorporate the geometry of the space do not capture this nuance. Additionally, Wasserstein distance is versatile and can be adapted to the setting of interest by varying the metric. In the case of the metric being a discrete metric with d( y) = [ F y), it reduces to the commonly used total variation (TV) distance. Our focus in this work on the case of Fuclidean distance metric on [0. 1] or [o, 1]2. though our results apply to both to higher-dimensional Euclidean space as well as to any finite metric. In the [0, 1] case (with the standard Euclidean metric), the Wasserstein distance is equivalent to the total area between the cumulative distribution functions.
The problem of learning a distribution under Wasserstein distance has long history, starting with [Dud69] proving worst-case bounds on the rate of convergence of the Wasserstein distance between the empirical distribution Pa and the target distribution P over R Similarly, this question for the case of the discrete metric (d(x,, y) 1(x F y)) has been very well studied. However, most known results for this problem look at it from the point of view of worst-case analysis. This can paint rather pessimistic picture. For example, the minimax rate of e-privately learning a discrete distribution over {o....,kt 3} in TV distance (i.e. Wasserstein with the discrete metric described above) scales linearly with k; which can be prohibitive for large support size k. For Wasserstein distance with & norm, the rate of convergence of the empirical distribution suffers a curse of di- mensionality, with the worst-case error between the distribution and the empirical distribution being ((n=*) +) for distributions over [o, 1]d. For the differentially private version of this question, recent works [BSV22, HVZ23] have shown that the optimal Wasserstein minimax error between the sam- ple and the private estimate is (((E))= =). This worst-case analysis viewpoint fails to distinguish between algorithms that perform very differently on the types of instances one may see in practice. In particular, many practical distributions may be more feasible to estimate than suggested by the minimax rate. As an example, Figure shows the cumulative distribution function of a bimodal distribution on j0, 1] with very sparse support, and the cdf learnt by minimax optimal algorithm, as well as an algorithm we present in this work (See Appendix F for details on this experiment). As is clear from the figure, the minimax optimal algorithm is easily outperformed. This phenomenon only gets worse in higher dimensions. Similarly, if the distribution in Re lies on a k-dimensional subspace, the worst-case error scaling with Ö((e)==à) is significantly larger than our algorithm's scaling of (()m)=t).
This motivates the problem of viewing this question through the lens of instance optimality. 2 Briefly, instance optimal algorithms those that on any given instance of the problem, are able to perform competitively with what any algorithm can do on this instance. Let M be a class of algo- rithms of interest (e.g. all (e, diifffrrrrtt private algorithms) and cost(-, be a cost measure for an instance P. our setting, we have a distribution P over a metric space, and given set P., of n samples from P. we want to learn an estimate A(Pp) for the distribution. Our measure of performance is the Wasserstein distance W, so cost P) = like say that an algorithm A is a-instance optimal in class M if for all instances P, and all A' E M,
We would ideally
cost((((..)) P) S a- cost((A((P))) P).
(InstanceOptimallty-laee
The reader would have noticed that this definition is however impossible to achieve except for trivial classes M. The algorithm A' that ignores its input and always outputs P makes the right hand side O. However, this algorithm performs poorly on any distributions far from P and so is not a reasonable benchmark. A common approach in many works is to measure the performance of the competing algorithm A' not just on the given instance, but on a small neighborhood around it. Thus we say
ec.f. related work section for discussion of other beyond worst case analysis approaches for this question and Appendix for a more in-depth discussion of our approach.

---

1.-
0.8
0.5
0.4-
0.6
0.4
0.2-
0.2
0.1-
200 400
800 1000
200
800
1000
Figure 1: (Left) A sparsely supported distribution on integers [0.999] (pdf). (Right) CDF for the same distribution (green, solid line), along with a (non-private) minimax optimal learnt distribution (blue, dashed line), as well as I-DP instance-optimal algorithm (red, dotted), both learnt from the same 1600 samples. The W1 error for the minimax optimal algorithm is 13.4, whereas the DP estimated distribution has W1 error of 0.86. While this example artificial, demonstrates the large potential gap between minimax optimal and instance optimal algorithms on specific instances.
that that an algorithm A is a-instance optimal amongst a class M with respect to a neighborhood function A if for all instances P, and all A' E M
cost P) a. sup (Ps) P"). P'EN(()
In other words, the benehmark we evaluate against is the cost of the best algorithm for neighbor- hood (P) that knows this neighborhood. We would like our algorithm A, that is not tailor-made for (P),, to nevertheless be competitive against this benchmark.
This definition general, and captures most notions of instance optimality that have been studied in the literature. The set (PP) must be carefully defined for this notion to be meaningful; we can always define (P) to be the set of all instances whence this notion reduces to worst-case analysis. In many previous works, this neighborhood map has been defined to capture the belief that any natural algorithm must not have significantly different performance on different members of ((P). For example, [FLNO1, ABC17, VV16, OS15, GKN20] include in (/P) appropriate renamings of P to capture some kind of permutation invariance of natural algorithms. In statis- ties, one often enforces that the cardinality of (PP) is often called the hardest one-dimensional subproblem [CL15, AD20, DLSV23). Some recent works in privacy [HLY21, DKSS23] have de- fined instance optimality w.r.t. neighboring datasets obtained by deleting small number of data points. Any reasonable definition of instance optimality for problem must justify its choice of the neighborhood map: similar choices must be justifiable in every other notion of beyond worst case analysis [Rou21]. In instance-optimant lates what class of domain-specific algorithms our algorithm competes against. good definition thus depends on the context and on the kind of domain knowledge we imagine an expert designing a custom algorithm for an application may have. Ideally, the definition broad (i.e. the neighbor- hoods (oodssN[PP ((P)) are sufficiently contained) so that in large class of applications, knowledge to not be enough to rule out any member of (P)). We discuss this general definition of instance optimality further in Appendix B. We remark that for reasonable neighborhood maps, this is an extremely strong requirement: an instance-optimal algorithm must simultancously do well on every single input, in fact as well as any other algorithm that is given this neighborhood N (P) in advance!
definitions, this choice of neighborhood is what encapsu-
expect the domain
Instance optimality guarantees are most useful when there is a big difference between achievable utility guarantees for typical cases and the worst-case utility guarantees. Wasserstein estimation is an example of such a problem. We will see that achievable utility bounds for, for example, con- centrated distributions are a lot better than worse case distributions. Our definition of instance op- timality is particularly suitable for metric spaces, and our notion of neighborhood allows the target utility bound to adapt to the distribution. We note that for estimation in Wasserstein distance with practically important metrics such as E and lg norms, it is unclear if existing instance optimality
3

---

definitions (using notions of neighborhood discussed above) capture this. For example, for discrete distributions, setting the neighborhood to be all permutations of the distribution destroys all struc- ture of the distribution (for e.g. concentration), and hence performance on this neighhorhood may not capture the relative ease of estimation of a concentrated distribution. Similar problems apply to other previously studied definitions of instance optimality, which are not well-suited to density estimation with error metrics that incorporate the geometry of the metric space. See Appendix B and Appendix C for further discussion on the inadequacy of existing instance optimality definitions for our setting of interest.
Our notion of neighborhood will correspond to small balls in one of the strictest notions of dis- tance between distributions. Recall that for distributions P. Q on X, D (P. Q) defined as S max In P(z) In f(a) Our neighborhood map A will have the property that for all P. and for all Q E (PP), (P,Q) < 2. This corresponds to the benchmark algorithm A'' be- ing given as auxiliary input a multiplicative constant factor approximation to the probability density algorithm that
Q()) P(a)
function P(x) (and we replace the constant 2 by any constant). In particular, knows the support of the distribution P will not be able to do much better than our algorithm that gets such information. Notice that this implicitly implics that algorithm is able to exploit sparsity in the data distribution since it is competitive with an algorithm that is told the support. In the one-dimensional real case can achieve an stronger notion of instance-optimality In this case (P) is defined to be {P. Q) where Q is a distribution with Dx (P, S 2n This is a strengthening of the rate defined by the hardest one-dimensional subproblem.
We also give a definition that captures another aspect of instance optimality, related to the notion of super efficiency, that we term local minimality in Appendix B. Informally, local minimality says that if any comparator algorithm does better than A on P, then there is a distribution Q in the neighborhood of P where A does better than the comparator. Approximate local minimality relaxes the latter condition to being better than some constant times the comparator. The two definitions of in general incomparable (see Appendix B)
approximate local minimality and instance optimality but for suitable smooth algorithms, we show that these definitions are equivalent. Our algorithms, both for the I-dimensional and the case of general metric spaces approximately satisfy both these definitions.
In order to show that the instance optimality definition is achievable, give both algorithmic upper bounds and matching, up to logarithmic factors, theoretical lower bounds. The algorithms we use in upper bounds are built largely from ingredients previously used for similar problems. We see this as an asset since these algorithms are implementable in practice. A key ingredient that we do introduce is the use of randomised HST approximation of finite metric spaces. This replaces deterministic hierarchical decompositions that were used in prior work, allowing us to gain tighter utility guarantees. Our main conceptual contribution is to introduce what believe the right no- tion of instance optimality for this problem, including the definition of a meaningful neighbourhood function. The main technical challenge in the lower bounds, which require carefully building nets of distributions within each neighborhood ((P) that allow us to use a slight generalisation of DP Assoud's Lemma to give a lower bound on the target estimation rate for each distribution P.
First, we define differential privacy. Further discussion on differential privacy can be found in Appendix A.
Preliminaries:
Definition 1.1 (Differential Privacy [DMNS17, DKM+06], A randomized algorithm A: X -> y (e, differerettl private if for every pair of datasets x, x' E X" that differ in at-most one data entry, and for all events Y C..
ef Pr(A(X)) +
Given an estimation algorithm A + M, the estimation rate of A for distribution P is: R.A. (P)
inf (t: w.p. 2 0.75 over x un and the randomness of the algorithm, Wa(A(x), P) St.. FER
(1)
1.1 Our Results
We start by stating an informal version of our result in the one-dimensional real case.

---

Theorem 1.2 (Informal I-dimensional result). Let (0, 1]. There is an e-differentialy private algorithm A such that, for all distributions P supported in [0, 1], for all natural numbers n > polylog 1/2, there exists a distribution Q (with Dxo (P,, Q) S In 2) such that the following is satisfied.
For any E-DP algorithm A', with probability at least 0.75 over the randomness of x p and additional randomness of the algorithm,
W(A(P.),)) S polylog
Ra (P') +Y
sup P'E(P.Q)
where n' polylogn/>
In this one-dimensional case, our algorithm is based DP quantile estimation. The additive yy term can be made polynomially small. The lower bound is based on (differentially private) simple hypoth- esis testing where for each distribution P, we find distribution in (PP) that is indistinguishable from P given n samples but also sufficiently far from in Wasserstein distance.
Extending the quantiles based approach from the one dimensional setting to even the two dimen- sional setting is challenging, as there is no "right" way to generalize quantiles to dimensions 2 or beyond. Several previous works on Wasserstein density estimation (e.g. [BNNR09]) have used hi- crarchical decomposition approach to address this question. A hierarchical approach has also been used in various more practical works private density estimation (e.g. [CB22, QYL12, BKM 21, MJT ZXX16]). These works focus on practical performance and do not offer tight theoretical bounds. A hierarchical approach was also used by [GHK 233,, who proved theoretical bounds for related problem, but not through the lens of instance optimality. We compare our results to theirs in more detail later in this section.
The use of deterministic hierarchical decompositions in all these papers means that some points that are very close (but on opposite sides of the boundaries of the hierarchical decomposition) get mapped to relatively far points, resulting in high distortion factors that are not appropriate for in- stance optimality.
Inspired by the above approaches but noting their constraints, use randomized embedding into hicrarchically separated trees instead of a deterministic one. We define our algorithm on any hierarchically separated tree metric and use the fact that there randomized embedding [o, 1]² on hierarchically separated tree metric space with low distortion. This, along with some other important technical modifications (such as truncating low values to 0), allows to analyze a variant of the above practical algorithms theoretically and show that it satisfies our strong notion of instance optimality, up to polylogarithmie factors the number of samples.
Theorem 1.3 (Informal woodimensionall result). There is a polynomial time e-differentially private algorithm A that for any distribution P on [0, 1]2, any integer n, and any e-DP algorithm A' with probability least 0.75, satisfies
()(A(P)),.) & (logn) 0(1)
(P
sup
where n' polylog n Here, the expectation is laken over the internal coin tosses of A as well as over the choice of the i.i.d. samples P...
In fact, since our algorithm is defined on any hierarchically separated tree metric space, it has the added bonus of giving instance optimality results for any finite metric space (since powerful sults [Bar96, FRT03] show that any finite metric space can be embedded in hierarchically separated tree metric space with distortion factor most logarithmic in the size of the metric space).
Theorem 1.4 (Informal finite metric result). Let (X, d) be arbitrary metric space with diameter There is a polynomial time e- E-differentially private algorithm A such that for any distribution P on X any integer and any E-DP algorithm A' with probability at least 0.75, satisfies
((A(P)), < (log -logn)
E[ (P',,,, P.D.
sup
where n' polylog,' Here, the expectation is taken over the internal coin tosses of A as well as over the choice of the i..dd samples P...
5

---

Our lower bound result is actually slightly stronger than stated in Theorem 1.4 since it holds not only for E-DP, but also for (e,6)-DP. At this point, we also compare specifically the paper of [GHK+23] who give an algorithm for obtaining two-dimensional heatmaps and analyze it theoret- ically. They focus on the empirical version of variant of this problem as opposed to the population version, and aim to compete with the best k-sparse distribution. Their algorithm takes the sparsity parameter k input in order to set parameters and achieves additive error vk/n (and a constant multiplicative factor). On the other hand, our algorithm also performs better for sparse distributions but is automatically adaptive to the sparsity (and hence doesn't need to take it as input). Addi- tionally the additive term in our work can be made polynomially small (for any polynomial) in n at logarithmic cost the multiplicative error (regardless of the sparsity of the distribution). On the other hand, for large their results have additive error that scales with 1/ Their use of a deterministic hierarchical decomposition makes their algorithm unsuitable for our notion of instance optimality (as discussed earlier), and it is unclear if their algorithm can be directly extended to all finite metric spaces.
Note that instance optimality for all finite metric spaces implies instance optimality results for a wide variety of applications not addressed in prior work. For example, our results immediately extend to other low-dimensional real spaces with arbitrary metrics (for e.g. Eg norms). They also give non-trivial improvements worst-case analysis for main focus of work (for [0, 1j4, we can use fine grid of size (1/(n/ (L/n/vd))) vd) at additive cost of 1) in the Wasserstein distance in order to create a finite metric space to apply our result on. Since the dependence on | the result above logarithmic, this translates to a d & multiplicative overhead term replacing the log X factor above. While this is still a significant overhead, all previous results on density estimation in the Wasserstein distance (in both the private and non- private literature) are worst case, where the sample complexity is exponential in d. Since our results only have a polynomial dependence in d over the optimal error, this is a non-trivial improvement over worst-case error, even when d is large.
spaces that are not the
Another immediate application of our results is to give (to the best of our knowledge) new bounds for private estimation of discrete distributions in TV distance. Generally, for learning a discrete distribution defined by probabilities (p1, (P1..... pPk), results lead to rate (up polylogarithmic
factors) of E, min (c((1 - p.),
1 + E, min (pi, (1 (1-p.), d.)
This can give significant improvements over the worst case bounds for practically important distri- butions. The minimax rate is linear in the support size k, namely ((k/en) (for sufficiently small E). Now, consider the following power-law distribution over support size k: p(i) i-2 (Power law distributions arise frequently in practice for e.g. frequencies of family names, sizes of power outages etc. all follow power law distributions.) Applying our result above gives bound that is k min en ) which is much better than the worst case bound for large support distributions.
Our result also applies other practically important settings such building lists of popular quences such as n-grams over words. We leave open the questions of designing instance-optimal algorithms for other practically important questions in private learning and statistics, and of de- signing better instance optimal algorithms for higher dimensional spaces. We also leave open the question of removing the polylogarithmic factors in our instance optimality bounds.
1.2 Techniques
1.2.1
Distributions over TR:
We start by describing the rate we obtain for distributions P over IR.In order to state the rate, we will use da to represent the a-quantile of the distribution P and use Pla,s to define a certain restricted distribution described below. The rate consists of three terms and roughly looks as follows- we suppress logarithmic factors in n.
(P Ö
E W (P.
1
(9
9 + WWP.P Pla ) em
9--
The first term is (P P.)). the expected Wasserstein distance between the true distribution and the empirical distribution over samples, and is the non-private term. The remaining two terms

---

represent the cost of privacy- the first is specific interquantile distance, roughly 3 (9) - ) and the second can be thought of as capturing the weight of the tails- represented by the Wasserstein distance between P and a 'restricted' version of P with its tails chopped off (i.e. the cumulative distribution function is 0 below ///en and 1 above //-n/sn and identical to P otherwise). Observe that all 3 of the terms above are smaller for distributions with small support or greater concentration, and hence the rate adapts to the hardness of the distributions.
in
The upper bound involves estimating roughly en equally spaced quantiles of the empirical distribution differentially privately (using known private CDF estimation algorithm), and placing roughly 1/en mass at each of the estimated quantile points. For the analysis, the intuition for each of the terms is as follows: since we only have access to the empirical distribution, the non-private term (P, Pr))] comes from that. Next, if the quantile estimates are good, then the pointwise CDF differences between the empirical distribution and the estimated distribution are at most 1/en (due to the discretization), and so we will pay 1/en multiplied by the interquantile distance of the empirical distribution. This aligns with the accuracy of state-of-the estimation algorithms. Finally, since the distribution is restricted to the estimated quantiles, the distribution is before the first estimated quantile and 1 above the last estimated quantile and so pay the Wasserstein distance between the empirical distribution and restricted version of the empirical distribution. Some care needs to be taken while reasoning about expectation versus high probability (for various terms), and in relating population quantities to empirical quantities (which we do using various concentration inequalities). Details can be found in Section E.2.
Upper Bounds:
DP quantile
Lower Bounds: We prove that the private and non-private terms are lower bounds separately. Both proofs follow the same framework. The idea is that given knowledge of two distributions and Q. can (private) Wasserstein estimation algorithm to construct a hypothesis test distinguishing P from Q. If the (private) estimate for P and Q with n samples gives error smaller than _ ((P, Q), can use this to distinguish P from Q. This would give a contradiction if P and Q are (privately) indistinguishable with n samples. Hence, this would give a lower bound of 2 W(P, Q) on the error of the Wasserstein estimation algorithm on P or Q.
Thus the task reduces to constructing a distribution Q that satisfies three properties: 1) it is (pri- vately) indistinguishable from P given samples, 2) the Wasserstein distance between P and Q is sufficiently large, 3) (P, (), S 2n The main technical work is in identifying a distribution Q that satisfies these properties.
For the privacy term, we construct the distribution Q by taking half the mass from the first 1/en- quantile of P (scaling the density function by half) and moving it to the last 1/en-quantile of P (scaling the density function by 3/2). The third property satisfied by definition, so we reason about the other two. Intuitively, since the Wasserstein distance captures how hard it is to 'move' P to Q, this mass needs to move at least the interquantile distance to change P to Q. This implies that the Wasserstein distance is at least the interquantile distance scaled by 1/En, as described in the rate. Additionally, mass that further out in the tail needs to move more, which is captured by the Wasserstein distance between the distribution P and its 'restriction'. Hence, the Wasserstein distance between P and Q is lower bounded by these two terms of interest. The intuition behind Property 2 is that it is hard for any e-DP algorithm to pinpoint the location of an fraction of the points in the dataset. Overall, this shows the privacy lower bound.
The non- non-private lower bound requires a more careful construction of Q. We divide P into various scales and carefully adjust them differently to obtain the desired properties. Formally, to construct Q from P. we consider Q1/2 and all quantiles of the form /1/2* and -1 for i > 1. For < i < log n, we add mass to (1,22)) by setting the density fo to be (1 + /2//n)fr and balance out the extra mass by setting SQq to be (1 //2//n) fr between by setting fo to be (1 + 1)fr and balance the
21-1222-1 For i 2 log
(i.e. the tail), we add mass to extra mass by setting fo to be (1 f)ff between [g) 191-1/2 -1/2+++))
The third property is again trivially satisfied. For the first property, observe that to 'move' P to Q the extra v mass between (11/22+1,91/2/) has 'travel' between 41/2- and 91-1/25, and so the Wasserstein distance between P and Q can be lower bounded by a sum of various scaled in- terquantile distances. We attempt to upper bound the expected Wasserstein distance between P and Pn by a similar term. It is more intuitive to reason about this using alternative (equivalent) for-
7

---

mulation of Wasserstein distance as the area between the CDF curves of P and Q. The intuition is that the expected pointwise CDF difference between P and P, in the interval ( 91/2)) would be roughly V (by properties of Binomial) and hence the contribution of this interval to the area would be roughly V2in (91/2- 91/2++1) and similarly for the corresponding interval [g 1//-1/25> (1/2211). Hence, the expected Wasserstein distance would be a sum of these scaled quantile interval distances. We formalize this intuition using a result of Bobkov and Ledoux [BL19] that character- izes the expected Wasserstein distance between P and Pa as integral of a function of the CDF of P. We now have a bound terms of the sum of scaled quantile interval distances, but we want to bound it by sum of scaled interquantile distances. We can telescope the sum to indeed bound it by a sum of scaled interquantile distances. This establishes that W(P, 2 EIW((P P.]- Next, we show that is indistinguishable from Q by analyzing the KL divergence between P and Q- The main idea is that high density intervals are modified by small multiplicative factor of roughly 1+ Vn but low density intervals (with mass less than 1/n) are modified by a constant multiplicative factor, so overall the contribution of each interval to the KL. divergence is sufficiently small. This establishes indistinguishabiliyy with n samples. For formal details we refer the reader to Section E.
1.2.2 Distributions on HSTs
Since the main technical challenge of proving Theorem 1.4 is proving the equivalent result for distributions on HST metric spaces, we focus on that problem in this section. Standard results on low distortion embeddings of metric spaces into HST metric spaces can be used to translate the HST result to [o, 1J2 and to general metric spaces X with log XX| overhead.
Definition 1.5 (Hierarchically Separated Tree). A hierarchically separated tree (HST) a rooted weighted tree such that the edges between level & and E - 1 all have the same weight (denoted T²) and the weights are geometrically decreasing so rt+1 (1/2)r Let Dr be the depth of the tree.
HSTs can be defined with any geometric scaling but we will only need factor of 2 in this work. HSTs may also have arbitrary degree. A HST defines a metric on its leaf nodes by defining the distance between any two leaf nodes to be the weight of the minimum weight path between them.
HST metric spaces particularly well-behaved when working with the Wasserstein distance since the Wasserstein distance on a HST has a simple closed form. A distribution P on the the underlying metric space in HST induces function Gp the nodes of the tree where the value of node is given by the weight in P of the leaf nodes in the subtree rooted at v. For every level & E [Dr] of the tree, let Py be the distribution induced on the nodes level e where the probability of node is (v))) Thus P; is a discrete distribution on a domain of size N₁, where N₂ is the number of nodes in level of the tree.
Lemma 1.6 (Closed form Wasserstein distance formula). Given two distributions P and Q defined in a HST metric space, the Wasserstein distance between P and Q has the closed formula:
W(P, Q) = ( - -
Q.),
where vu is the weight of the edge connecting v to its parent, and the sum is over all nodes in the tree.
We will call a node v a-active under the distribution P if (P(v) 2 a. Let PP (a) be the set of o-active nodes under P and 7r, (a) be the set of oxaactive nodes at level f. Then there exists an algorithm A such that given a distribution P. > O, and n E N,
-((x)) P((x)( - (1(x)(1-
R.A..(P) Ō max Σ
min
-
Σ
Pe(x) + (TTR, (2x) 1)x
n
2EIN2)
SETTP (2m)
where the max is over all the levels of the tree and A O log(n)) ). Further, this bound matches (up logarithmic factors) the lower bound min A
(P,P") Etwr://///WWWWWWACC E[ n' polylog n The error rate RA,, does indeed adapt to easy instances as we expected. The error decomposes into three components. The first component is the non-private sampling error; the error that would occur even if privacy was not required. The second component indicates that we can not
where
8

---

privately estimate the value of nodes that have probability less than ~ 1/mm). The third component the error due to privacy on the active nodes. If P is highly concentrated then we expect most nodes to either be k-active or have weight O, so the first two terms in Ry n.el (P) are small. There should also be few active nodes, making the last term also small. Conversely, if P has a large region of low density then we expect a large number of inactive nodes, as well as non-zero inactive nodes that are at higher levels of the tree and hence contribute more to the final term. Thus, in distributions with high dispersion we expect the right hand side to be large.
Upper Bounds:
As in the oiediimesionnal setting, we want to restrict to only privately estimating the density at small number (= En) of points. While we could try to mimic the one-dimensional solution by privately estimating a solution to the en-median problem, it's not clear how to prove such an approach is instance-optimal. It turns out that a simpler solution more amenable to analysis will suffice. Our algorithm has two stages; first we attempt to find the set of k-active nodes, then we estimate the weight of these active nodes. Since these nodes have weight greater than log(n), we en can privately estimate them to within constant multiplicative error. Any nodes that are not detected as active, are initially ascribed a weight of O. The error due to not estimating the non-active nodes is absorbed into the third error term. The final step is to project the noisy density function into the space of distributions on the underlying metric space. The eπror of the upper bound algorithm is summed over all levels of the tree, although since the depth of the tree is logarithmic in the size of the metric space, this is within a logarithmic factor of the maximum over the levels.
We first observe that in order estimate the distribution well in Wasserstein dis- tance, an algorithm must estimate each level of the tree well in TV distance. This is derived from Lemma 1.6. This allows us to reduce to the problem of lower bounding the error of density estima- tion of discrete distributions in TV distance. The main tool we use is a differentially private version of Assouad's s method. Similar to how the technique in the previous section allowed us to relate lower bounding estimation rates to simple hypothesis testing, Assouad's lemma allows us to relate lower bounding estimation rates multiple hypothesis testing. Note that unlike the technique in the previous section, Assouad's 's lemma allows us to prove lower bounds on the expected error, rather than lower bounds on high probability error bounds. involves constructing nets of distributions in (PP) that are pairwise far in the relevant metric of interest (which for us in the TV distance) but the multiple hypothesis testing problem between the distributions is sufficiently hard. For proving the third term belongs in the lower bound, the standard statement of DP Assouad's 's lemma [ASZ21] suf- fices, where one builds a set of distributions indexed by a hypercube. For the first and second terms, we need to slightly generalise the statement to allow for sets of distributions indexed by product of hypereubes. We use the approximate DP version of DP Assouad's s so while our upper bounds are for pure differential privacy, our lower bounds hold for both pure and approximate differential privacy.
Lower Bound:
Let us start with the third term. Suppose the number of active nodes is even (a small tweak made if there is an odd number of active nodes). We pair up the active nodes and index each pair by coordinate of the hypercube. For each corner of the hypercube, (u", u² .......... u²) {+1]*, for each coordinate j E [k), if wd = +1, we move Ö(s) mass from one node in the jth pair to the other node. If u² = -1 then we leave the jth pair of nodes alone. Since each active node has mass > k, it's clear that each resulting distribution belongs in (P). We can also show that these distributions form sufficiently hard multiple hypothesis testing problem. By DP Assouad's (Lemma D.8), this allows us to lower bound the estimation error by [(kk),, which is within Ω of the third term when the number of active nodes is 2 2. We treat the case where there is a single active node separately.
For the second term, we want to pair up the inactive nodes in a similar manner and move half their mass from one node to the other. However, since we want to remain within (P),, we can't 't't pair any two inactive nodes together. Thus, we divide the inactive nodes into scales, where nodes within a certain scale all have weight within multiplicative factor of two. We then pair up nodes within each scale and have a different hypercube for each scale. Again, it's clear that these distributions are all in (P) and we can show that these distributions form a sufficiently hard multiple hypothesis testing problem. The proof for the first term follows similarly.
References
[AAK21] Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Vitaly Feldman, Katrina
9

---

Ligett, and Sivan Sabato, editors, Algorithmic Learning Theory. 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Re- search, pages 185-216. PMLR, 2021.
[AAL23a] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with a polynomial number of samples. CoRR, abs/2309.03847,, 2023.
[AAL23b] Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In Andreas Krause, Emma Brun- skill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, ed- itors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 1018-1040. PMLR, 2023.
[ABC17] Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. J. ACM, 64(1), mar 2017.
[AD20] Hilal Asi and John C. Duchi. Instance-optimality in differential privacy via approx- imate inverse sensitivity mechanisms. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neu- ral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 62, 2020, virtual, 2020.
[AD]+1I] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, and Shengjun Pan. Competitive closeness testing. In Sham M. Kakade and Ulrike von Luxburg, editors, COLT 2011 The 24th Annual Conference on Learning Theory, June 9-11, 201 I, Budapest, Hungary, volume 19 of JMLR Proceedings, pages 47-68. JMLR.org, 2011.
[AD]+ 12] Jayadev Acharya, Hirakendu Das, Ashkan Jafarpour, Alon Orlitsky, Shengjun Pan, and Ananda Theertha Suresh. Competitive classification and closeness testing. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 22.1 12.1-22.18 18. JMLR.org. 2012.
[AJOSI3a] [3]] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. competitive test for uniformity of monotone distributions. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013, Scottsdale, AZ, USA, April 29 May 1, 2013, volume 31 of JMLR Workshop and Conference Proceedings, pages 57-65. JMLR.org, 2013.
[AJOS13b] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Op- timal probability estimation with applications to prediction and classification. Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 The 26th Anmual Confer- ence on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 764-796. JMLR. 2013.
[AKT+23] Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating a gaussian: Efficient, robust, and optimal. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on The- ory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 483-496. ACM, 2023.
[AL22] Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning gaussians and beyond. In Po-Ling Loh and Maxim Raginsky, editors, Con- ference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1075-1076. PMLR, 2022.
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Pro- ceedings of the S1 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860. ACM, 2019.
10

---

[ASSU24] Maryam Aliakbarpour, Rose Silver, Thomas Steinke, and Jonathan R. Ullman. Differ- entially private medians and interior points for non-pathological data. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 February 2, 2024, Berkeley, CA, USA, volume 287 of L.Plcs, pages 3:1-3:21. Schloss Dagstuhl Leibniz-Zentruum für Informatik, 2024.
[ASZ17] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. CoRR, abs/1707.051 2017.
[ASZ20] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. CoRR, abs/2004.06830, 2020.
[ASZ21] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private Assouad, Fano, and Le Cam. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 48-78. PMLR, 16- 19 Mar 2021.
[BA20]
Brunel and Marco Avella-Medina. Propose, test, release: Differen- tially private estimation with high probability. CoRR, abs/2002.08774, 2020.
[Bar96] Yair Bartal. Probabilistic approximations metric spaces and its algorithmic appli- cations. In 37th Annual Symposium Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193. IEEE Computer So- ciety, 1996.
[BBDS13] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 87-96. ACM, 2013.
[BG14] Emmanuel Boissard and Thibaut Le Gouic. On the mean speed of convergence of em- pirical and occupation measures in Wasserstein distance. Annales de I'Institut Henri Poincaré, Probubilités et Statistiques, 50(2):539 563, 2014.
[BGS+21] Gavin Brown, Marco Gaboardi, Adam D. Smith, Jonathan R. Ullman, and Lydia Za- kynthinou. Covariance-aware private mean estimation without private covariance esti- mation. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Process- ing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 1021, December 6-14, 2021, virtual, pages 7950-7964, 2021.
[BHS23] Gavin Brown, Samuel B. Hopkins, and Adam Smith. Fast, sample-efficient affine- invariant private mean and covariance estimation for subgaussian distributions, 2023.
[KM++1] Eugene Bagdasaryan, Peter Kairouz, Stefan Mellem, Adrià Gascón, Kallista Bonawitz, Deborah Estrin, and Marco Gruteser. Towards sparse federated analyt- ics: Location heatmaps under distributed differential privacy with secure aggregation. arXiv preprint urXiv:2111.02336. 2021.
[BKSW21] Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypoth- esis selection. IEEE Trans. Inf. Theory, (7(3):198120000 2021.
[BL19] Sergey G. Bobkov and Michel Ledoux. One-dimensional empirical measures, order statistics, and kantorovich transport distances. Memoirs of the American Mathematical Society, 2019.
[BM23] Daniel Bartl and Shahar Mendelson. On a variance dependent Dvoretzky-Kiette Kiefer- Wolfowitz incquality. arXiv e-prints, page arXiv:2308.04751 August 2023.
[BNNR99] Khanh Do Ba, Huy L. Nguyen, Huy Ngoc Nguyen, and Ronitt Rubinfeld. Sublinear time algorithms for earth mover's distance. Theory of Computing Systems, 48:428- 442, 2009.
11

---

[BNS16] Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy, Theory Comput, 12(1):1-61, 2016.
[BNSV15] Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. CoRR, abs/ 1oss/5504.0753,, 2015.
[BS19] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Ad- vances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8 14, 2019, Vancou- ver, BC, Canada, pages 181-191, 2019.
[BSV22] March Boedihardjo, Thomas Strohmer, and Roman Vershynin. Private measures, ran- dom walks, and synthetic data, 2022.
[BUV18] Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codes and the price of approximate differential privacy. SIAM J. Comput., 47(5):1888-1988 2018.
[BY0 Z. Bar-Yosseff The Complexity of Massive Data Set Computations. University of California, Berkeley, 2002.
[Can17] Clément L. Canonne. A short note on distinguishing discrete distributions., 2017.
[CB22] Graham Cormode and Akash Bharadwaj. cample-and-threshole differential privacy: Histograms and applications. In International Conference on Artificial Intelligence and Statistics, pages 1420-1431. PMLR, 2022.
[CCD+23) Karan Chadha, Junye Chen, John Duchi, Vitaly Feldman, Hanich Hashemi, Omid Javidbakht, Audra McMillan, and Kunal Talwar. Differentially private heavy hitter detection using federated analytics, 2023.
[CD20] Rachel Cummings and David Durfee. Individual sensitivity preprocessing for data privacy. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 528-547. SIAM, 2020.
[CDK17] Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it: Private and sam- ple efficient identity testing. In Doina Precup and Yee Whye Teh, editors, Proceed- ings of the 34th International Conference on Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 Proceedings of Machine Learning Research, pages
PMLR, 2017.
[CKM+19] Clément L. Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, and Jonathan R. Ullman. The structure of optimal private tests for simple hypotheses. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 310-321. ACM, 2019.
[CL15] T. Tony Cai and Mark G. Low. A framework for estimation of convex functions. Statistica Sinica, 25(2):423 2015.
[C] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differ- entially private learning of thresholds and quasi-concave optimization. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 472-482 ACM, 2023.
[CR12] Guillermo Cañas and Lorenzo Rosasco. Learning probability measures with respect to optimal transport metrics. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 2501-25099 2012.
12

---

[CSS1I] T.-H. Hubert Chan, Elaine Shi, and Dawn Song, Private and continual release of statistics. ACM Trans. lnf. Syst. Secur, 14(3):26:1-26:444 2011.
[CWZ19] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. CoRR, abs/1902.04495, 2019.
[CZ13] Shixi Chen and Shuigeng Zhou. Recursive mechanism: towards node differential pri- vacy and unrestricted joins. In Kenneth A. Ross, Divesh Srivastava, and Dimitris Papa- dias, editors, Proceedings the ACM SIGMOD International Conference Manage- ment of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, pages 653-664. ACM, 2013.
[DHS15] Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Informa- tion Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2566-2574, 2015.
[DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In International Conference on the Theory and Applications of Cryptographic Techniques, EURO- CRYPT "06, pages 486-503, St. Petersburg, Russia, 2006.
[DKS223] Travis Dick, Alex Kulesza, Ziteng Sun, and Ananda Theertha Suresh. Subset- based instance optimality in private estimation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference
Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 7992 8014. PMLR, 2023.
[DL91] David L. Donoho and Richard C. Liu. Geometrizing Rates of Convergence, II. The Annals of Statistics, 19(2):633 667, 1991.
[DL09] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. Michael Mitzenmacher, editor, Proceeuliggs of the 41st Annual ACM Symposium Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, pages 371-380. ACM, 2009.
[DSV233] Trung Dang, Jasper C.H. Lee, Maoyuan Song, and Paul Valiant. Optimality in mean estimation: Beyond worst-case, beyond sub-gaussian and beyond $1+) mo- ments. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[MNN177] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Journal of Privacy and Confidentiality, 17351 2017.
[DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential pri- vacy under continual observation. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Mas- sachusetts, USA, 5-8 June 2010, pages 715-724. ACM, 2010.
[DR18] John C. Duchi and Feng Ruan. The right complexity measure in locally private esti- mation: It is not the fisher information. CoRR, abs/1800.05756, 2018.
[DSS11] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt. Constructive quantiza- tion: Approximation by empirical measures. Annales De Institut Henri Poincare- probabilites Et Statistiques, 49: 10111883-2200 2011.
[Dud69] M. Dudley. The speed of mean glivenko-cantelll convergence. The Annals of Mathematical Statistics, 40(1):00-50, 1969.
13

---

[DY95] Vladimir Dobric and Joseph E. Yukich. Asymptotics for transportation cost in high dimensions. Journal of Theoretical Probability, 8:97-118, 1995.
[FG15] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein dis- tance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707, August 2015.
[FLNO1] Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. In Proceedings of the Twentieth ACM SIGMOD-SIGACT-SICAN Sym- posium on Principles of Database Systems, PODS '01, page 102- 113, New York, NY, USA, 2001. Association for Computing Machinery.
[Fou23] Nicolas Fournier. Convergence of the empirical measure in expected wasserstein dis- tance: non asymptotic explicit bounds in R. 2023.
[FRT03] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the Thirty-Fifth Anmual ACM Symposium on Theory of Computing, STOC '03, page 448-455, New York, NY, USA, 2003. Association for Computing Machinery.
(GHK+23) Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, and Nachiappan Valliappan. Differentially private heatmaps. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirly-Seventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innoaaivee Appli- cations of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 7696-7704. AAAI Press, 2023.
[GJK21] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quan- tiles. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, vol- ume 139 of Proceedings of Machine Learning Research, pages 3713-3722. PMLR, 2021.
[GKN20] Tomer Grossman, Ilan Komargodski, and Moni Naor. Instance Complexity and Unla- beled Certificates the Decision Tree Model. In Thomas Vidick, editor, 1 11th Innova- tions in Theoretical Computer Science Conference (ITCS 2020). volume 151 of Leib- niz International Proceedings Informatics (LJPPcs)) pages 56:1-56:38, Dagstuhl, Germany, 2020. Schloss Dagstuhl Leibn-Li-zizzizrrure für Informatik.
[HKM22] Samuel B. Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via sum-of-square exponential mechanism. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Sympo- sium on Theory of Computing, Rome, Italy, June 20- 24, 2022, pages 1 1406-1417. ACM, 2022.
[HKMN23] Samuel B. Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robust- ness implies privacy in statistical estimation. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FI., USA, June 20-23, 2023, pages 497-506. ACM, 2023.
[HLY21] Ziyue Huang, Yuting Liang, and Ke Yi. setaacce-opimall mean estimation under dif- ferential privacy. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Informa- tion Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 25993-26004, 2021.
[HO19] Yi Hao and Alon Orlitsky. combetccompetitive distribution estimation. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICML. 2019, 9-15 June 2019, Long Beach, Cali- fornia, USA, volume 97 of Proceedings of Machine Learning Research, pages 2614 2623. PMLR, 2019.
14

---

[HVZ23] Yiyun He, Roman Vershynin, and Yizhe Zhu. Algorithmically effective differentially private synthetic data, 2023.
[KDH23] Rohith Kuditipudi, John C. Duchi, and Saminul Haque. A pretty fast algorithm for adaptive private mean estimation. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 251 2551. PMIR, 2023.
[KLM+20] Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Pri- vately learning thresholds: Closing the exponential gap. Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 2263-2285. PMLR, 2020.
[KLSU19] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately leam- ing nigh-dimensional distributions. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pages 1853-1902. PMLR, 2019.
[KMS22a] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for pri- vate estimation and generalized fingerprinting lemma. In NeurlPS, 2022.
IKMS+22b) Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan R. Ullman. A private and computationally--ffiiien estimator for unbounded gaussians. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 544-572. PMLR, 2022.
[KMV22] Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Po-Ling Loh and Maxim Raginsky, editors, Con- ference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 723-777. PMLR, 2022.
[KNRSI3] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Analyzing graphs with node differential privacy. In Amit Sahai, editor, Theory of Cryptography 10th Theory of Cryptography Conference, TCC TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, volume 7785 of Lecture Notes in Computer Science, pages 457-476. Springer, 2013.
[KSS22] Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially private approximate quantiles, In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 10751-10761. PMLR, 2022.
[KSSU19] Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan R. Ullman. Differen- tially private algorithms for learning mixtures of separated gaussians. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buce Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 20/9, Vancouver, BC, Canada, pages 168-180) 2019.
[KSU20] Gautam Kamath, Vikrant Singhal, and Jonathan R. Ullman. Private mean estimation of heavy-tailed distributions. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event |Graz, Austria), volume 125 of Proceedings of Machine Learning Research, pages 2204 2235. PMLR, 2020.
[KU20] Gautam Kamath and Jonathan R. Ullman. primer on private statistics. CoRR, 0..22005.00010 2020.
15

---

[KV18] Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of L.Ples, pages 44:1-44:9 Schloss Dagstuhl Leibniz--Zentrum für Informatik, 2018.
[Lei20] Jing Lei. Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767 - -98, 2020.
[LKO22] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Po-Ling Loh and Maxim Raginsky, editors. Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 1167-1246. PMLR, 2022.
[MJT+22] Audra McMillan, Omid Javidbakht, Kunal Talwar, Elliot Briggs, Mike Chatzidakis, Junye Chen, John Duchi. Vitaly Feldman, Yusuf Goren, Michael Hesse, Vojta Jina, Anil Katti, Albert Liu, Cheney Lyford, Jocy Meyer, Alex Palmer, David Park, Won- hee Park, Gianni Parsa, Paul Pelzl, Rehan Rishi, Congzheng Song, Shan Wang, and Shundong Zhou. Private federated statistics in an interactive setting. arXiv preprint drXiv:2211.10082. 2022.
[MSU22] Audra McMillan, Adam D. Smith, and Jonathan R. Ullman. Instance-optinn differ- entially private estimation. CoRR, abs/2210.15811 2022.
[Nar23] Shyam Narayanan. Better and simpler lower bounds for differentially private statistical estimation. CoRR, abs/23 10.06289, 2023.
[NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In David S. Johnson and Uriel Feige, editors, Pro- ceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 75-84, ACM, 2007.
[NWB19] Jonathan Niles-Weed and Quentin Berthet. Minimax estimation of smooth densities in wasserstein distance. The Annals of Statistics, 2019.
[OS15] Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is good-turing good. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, De- cember 7-12, 2015, Montreal, Quebec, Canada, pages 2143-2151, 2015.
[QYL12] Wahbeh Qurdaji, Weining Yang, and Ninghui Li. Differentially private grids for geospatial data. Proceedings International Conference on Data Engineering, 09 2012.
[Rou21] Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithums. Cambridge Uni- versity Press, 2021.
[RS16] Sofya Raskhodnikova and Adam D. Smith. Lipschitz extensions for node-private graph statistics and the generalized exponential mechanism. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 Oc- tober 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 495-504. IEEE Computer Society, 2016.
[Sin23] Vikrant Singhal. A polynomial time, pure differentially private estimator for binary product distributions. CoRR, abs/2304.06787, 2023.
[SP19] Shashank Singh and Barnahás Póczos. Minimax distribution estimation in wasserstein distance, 2019.
[TC Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friend- lycore: Practical differentially private aggregation. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, Interna- tional Conference Machine Learning, ICML. 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Muchine Learning Research, pages 21828-2188 PMLR, 2022.
16

---

[vdV97] A. W. van der Vaart. Superefficiency, pages 397-410. Springer New York, New York, NY, 1997.
[Vov09] Vladimir Vovk. Superefficiency from the Vantage Point Computability, Statistical Science, 24(1):73 - 86, 2009.
[VV16] Gregory Valiant and Paul Valiant. Instance optimal learning of discrete distributions. Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 142-155. ACM, 2016.
[WB19] Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of conver- gence of empirical measures in wasserstein distance. Bernoulli, 25(4 A):2620-2648, 2019.
[Wol65] J. Wolfowitz. Asymptotic efficiency of the maximum likelihood estimator. Theory of Probability Applications, 10(2):277-600 1965.
[KM Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, and Wei Li. Feder- ated heavy hitters discovery with differential privacy. In International Conference Artificial Intelligence and Statistics, pages 3837-3847. PMLR, 2020.
[ZXX16] Jun Zhang, Xiaokui Xiao, and Xing Xie. Privtree: A differentially private algorithm for hierarchical decompositions. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD '16, page 155-170, New York, NY, USA, 2016. Association for Computing Machinery.
17

---

Organization of Appendices
Preliminaries
19
A.1 Distribution Distances
19
A.2 Differential Privacy
20
B On Instance Optimality
20
B.1 Local Estimation Rates
21
B.2 Locally Minimal Algorithms
................................
23
B.3 Relaxed Definitions
25
Additional Related Work
25
D Distribution Estimation Hierarchically Separated Trees
27
D.I Preliminaries on Hierarchically Separated Trees
27
D.2 The Target Estimation Rate
28
D.2.1 Reduction to Estimation in TV distance of Discrete Distributions
29
D.2.2 Characterizing Target Estimation Rate for Discrete Distributions
29
D.3
An c-DP Distribution Estimation Algorithm
33
Instance Optimal Density Estimation on R Wasserstein distance
36
E.1
General Lower Bound
37
E.1.1
The Privacy Term
37
E.1.2
Empirical Term
39
E.2
Upper Bound
41
E.2.1
Algorithm for density estimation
42
F Experiment Details
44
G Proofss for Section D
44
H Local Minimality in the High Dimensional Setting
50
I Differentially Private Quantiles
52
J Proofs in Section E
54
J.1 Omitted Proofs Section E.
54
J.2 Omitted proofs in Section E.1.2
55
J.3 Omitted Proofs Section E.2
58
J.4 Local Minimality in the One-Dimension Setting
61
18

---

A Preliminaries
For all distributions P. we will use fp to denote the density of P (when it exists) and Fp denote the cumulative distribution function of P. Given a space X, let ( be the set of distributions on the space X. Given a logical statement a, let Xa 0 is false and if a is true. For example, Xo=0 and Xu=1 0.
A number of distances between distributions are important in this work. We start by defining the infinity divergence, which is important in the notion instance optimality we use.
Definition A.1 (D -iveerregg..... Given two distributions P and Q with the same support, the P(O) Q(i Q(1) P0 if P and Q are discrete, and (t))) fr(t) J. if P and Q continuous distributions on R. and have density functions. If P and Q don't I have the same support, then (Px(P.Q) oc.
Ro-Rényi divergence (2, = In susup, max
Do () In sup, max [r(t) felt)
We will use KL(P, divergence and Q)( to denote the total variation distance, defined later.
(L(P.) Q) to denote the di-eeeeeeence, H² (P, Q) denote the squared Hellinger
Wasserstein Distance: The error metric that use judge our performance on the density estimation task is 1- I-Wasserstein distance (that we will call just Wasserstein distance where it is clear from context). In this subsection, we define Wasserstein distance.
Definition A.2. For any separable metric space (E, D), let P, P.Q represent Borel measures on E. Then, the 1- W-Sassrsteiin distance between P. is defined as
W(P. Q) = inf f /
(o), 20),
E
where the infinum is over all measures on the product space E x E with marginals P and Q respectively.
Finally, for one dimensional real spaces where the metric of interest is l norm, we will use the following equivalent formulation of Wasserstein distance extensively.
Lemma A.3 (Wasserstein formula over RR. Let P, Q represent probability distributions on R with finite expectation. Then, the 1- --Wasserstein distance between P, Q is equal to
W(P.Q) J
|FP(t)-Fo(tjdd)
where the F(-) represents the cumulative distribution function.
Given an metric space X, the Wasserstein metric is a well-defined metric on the set of the probability distributions over X.
A.1 Distribution Distances
number of other distances between distributions are used in this work.
Definition A.4 L-iiverggecc). Given two distributions P and Q with supp(P) C supp(Q),, the KL divergence KL(P, Q) ErEsuppip) P(I) In P(t). QUT if and Q are discrete, and K KL(P, Q) =
(1)):fo())20 JP(() In (o(t) di if P and Q are distributions on R, and have density functions. If Jo(t)
supp P) & supp(Q), then KL(P,, Q) Dc.
Definition A.5 (Hellinger distance). Given two distributions P. and Q, the Hellinger dis- IVVP - -VQ22z (where we think of P and Q as vectors represent-
tance H(P.Q) ing the probability masses, and the square root being component-wise.), if P and Q are dis- crete. If P and Q are distributions on TR, and have density functions, then ((P.Q) = + Sheresptosoo (F((t))-d
Note that we use (P(P. Q) to represent the squared Hellinger distance. Next, we define total varia- tion distance, which will come up in our high-dimensional results.
19

---

Definition A.6 (Total Variation distance). Given two discrete distributions P and Q, the Total Vari- ation distance TV (V(P.Q) Q) = 21P Ql1 (where we think of P and Q as vectors representing the probability masses). More generally, for any two probability measures P and Q defined on (Ω, the total variation distance is defined as sup P(A) QA() where P(A) represents the prob- ability of A under measure P and likewise for Q
We use the following relationship between Hellinger distance and KI. divergence.
Lemma A.7. For all distributions P, P.Q such that Kl-divergence of P, P,Q is well defined, have that
(P, S KL(..Q), (P) ( SV((P.)
A.2 Differential Privacy
Lemma A.8 Post-Processiig (DMNS17). If Algorithm A X - is (e, (e))) -)dfferrrentiall pri- vate, and B y + Z is any randomized function, then the algorithm B A is (E, differrentilll private.
Secondly, differential privacy is robust to adaptive composition.
Lemma A.9 (Composition of (s, 8)-differential privacy [DMNS17]). If A an adaptive composi- tion of m differentially private algorithms , where Aj (g,5,)) difserentially private,
then A E; 5,) -differentially private.
Finally, we discuss the Laplace mechanism, which we will use in one of our algorithms. Definition A.10 (6 Senniiiiti, The El-sensitivity of a function f de - Rd is
As max x.x' " dham (x,x')
flf(x)) f(x))l1.
Lemma A.11 (Laplace Mechanism). Let f X" + Ed be a function with Ei-sensitivity Ay. Then the Laplacian mechanism is algorithm
Ay(x) = f(x) + (Zi,..., Zz).
where Zi ~ Lap (2) (and Zi...., Za are mutually independent). Algorithm A5 is S-DP.
B On Instance Optimality
In this section, we discuss the notion of instance optimality, and argue that it provides useful benchmark that captures the idea of going beyond the worst case. The notion of instance optimality we propose can be see generalisation of the hardest one-dimensional subproblem, or hardest local alternative introduced by [CL15]. Suppose we have a family of distributions C AAX)) on space X' and our goal is to learn the parameter 0 P + M where M is a metric space with metric Given an estimation algorithm A 2 + MM, we can define the estimation rate* of A to be the function RA, P > R4 where
RAm(PP) = E.D.P ((0)))(((((())AA(()))
Since the estimation rate is function of the distribution P, the estimation rate of an algorithm may be lower at "easy" distributions and larger at "harder" distributions. As a classic example, consider the estimation rate of Bernoulli parameter estimation where A simply outputs the empirical mean. Then R... (Ber(p)) min (p(1 p). / pp(1 p)/n). this algorithm performs better when the Bernoulli parameter is close to or 1, and has it's worst case error when p = 1/2.
Cai and Low [CL15] proposed three desiderata that target estimation rate R. A(X) + R+ should satisfy in order to be a meaningful benchmark;
*We note that while the estimation rate here is defined in expectation, we will sometimes show results (for e.g. in the one dee-dmmmniionl case) where estimation rate is defined with probability at least 0.75 over the randomness of the algorithm and the data; Equation 1.
20

---

1. (P) varies significantly across P
2. R, is an achievable estimation rate; there exists an algorithm A and constant a such that (RA((P) (P) for all P E
3. Outperforming the benchmark R., at one distribution leads to worse performance at another distribution.
In this section we will discuss the definition instance optimality we will use in this work by defin- ing the target estimation rate that will serve of this paper establish that our chosen benchmark achieves desiderata and above. is not imme- diately obvious that desiderata holds. We will show in Section B.2, through the introduction of related notion of instance optimality which we call local minimality, that desiderata 3 holds in many important settings, including the problem studied in this paper.
benchmark estimation rate. The main theorems
B.1 Local Estimation Rates
We will start by defining target estimation rate. We'll say algorithm is a-instance optimal if it uniformly achieves this target estimation rate up to multiplicative a factor. For each distribution P E P, we define a neighbourhood N (PP).
Definition B.1. Given function N P - P(P), where B(P) is the power set of P, define the optimal estimation rate with respect to N to be:
R. = min sup QEN(P)
RAn(Q).
(3)
An algorithm is a-instance optimal with respect N for all P
R... (.
If an algorithm A uniformly achieves the optimal estimation rate wrt function N, then this implies that for all distributions P. the error the algorithm A on P is competitive with an algorithm that is told the additional information that the distribution is in (PP). Given function N, it is possible that there does not exist an algorithm that uniformly achieves Rv For example, as discussed in the introduction, if (P)) = {P), then Rv,, is not uniformly achievable. Conversely, if (P)) is not chosen carefully, then the estimation rate RN,, may not define a meaningful benchmark; e.g. an estimation rate that adapts to easy instances.
different formalization may be more probabilistic: the algorithm designer may have in mind distribution DD over distributions that they care about, and their objective may be to minimize Ep-D RR Suppose that for the A chosen by the algorithm designer, and for our neighbor- hood map N, the function Re (P) does not vary too much over N(P) on average. Formally, let
disc (P) = sup P'EN(P)
(P' (P)
No and let disc (P) = E |disex (P)). Then for any algorithm A that is a-instance optimal with respect N. write
E PwD
RR (P) a
E sup ,.',
P-D P'EN(P)
E RA n (P) disc (P))
a E RA (P)) + F.
Idiscy (P))
P-D
PWD
=a -a (.E.RRRRR disc
In other words, long as the algorithm 's performance is relatively constant over M/P) on average over the distribution of interest, the instance optimal algorithm (that is not tailored D) competitive with A". A similar result holds for multiplicative definition of disc.
21

---

This discussion can help guide the choice of the neighborhood function that is appropriate for a particular application. In the case of density estimation in the Wasserstein distance, we will define (PP) be a small Dac ball around P. We believe this captures the kind of domain information an algorithm designer may have. E.g. one may have a small amount of public data samples, in which case the posterior over distributions in a Do ball will be relatively constant. If the algorithm designer's custom algorithm needs to do well for all distributions in this set, an instance-optimal algorithm will be competitive with this custom algorithm.
Previous work in instance optimality has largely focused on two notions of neighborhood. In [FLNO1, ABC17, VV16, OS15]. where the objects of interest are discrete subsets with no a priori structure,
natural to ask that the algorithm work well for any permutation of the inputs. For example, if the goal is to compute the set of maximal points from a 2-d point set, the algorithm designer would typically want an algorithm that works well for any permutation of the set of input points. In our setting where the points of interest have metric structure, this is not an appropriate notion, In fact, even for the discrete case studied in Appendix D.2.2, permutation invariance cannot capture natural prior beliefs that may arise in practice. For example, for power-law distributions that one often sees in private learning applications [ZKM 20, CB22, CCD+23], a small number of samples are sufficient to get good estimate of the heavy bins, and rule out large fraction of permutations of the input space.
A second line of work arising from the statistics literature [CL15] has looked at defining instance- optimality with respect to neighborhoods of size 2. While this approach has been very successful for many problems, we find it inappropriate for density estimation (outside of density estimation on IR) as neighborhoods of size two are too weak to capture the difficulty of problems of interest. Even in the simple case of discrete distributions, this neighborhood is provably insufficient to get instance- optimality results with any o(K) competitive ratio. Indeed, for any two given distributions on [K] with TV distance a, Ó 22)2 samples suffice to distinguish them, whereas learning a near uniform distribution on K atoms requires ((K)) samples. In the private setting, the need to multiple distributions to prove lower bounds is well-studied. Our approach shares this similarity of using a multi-instance lower bounding argument with packing lower bounds in privacy, and local Fano's 's and Le Cam's ' methods in statistics. Our work shows that some of the same lower bounding techniques can be used to prove instance-optimality results with respect natural neighborhood maps, going well beyond the the worst-case results those works prove.
In the special case of density estimation in the Wasserstein distance on I. instance optimality with respect to neighborhoods of size 2 is achievable. In the standard version of this benchmark met- ric, (PP) However, this notion may not be an appropriate notion of instance optimality by itself. To see this, consider a distribution P supported on an interval [a., bj. Moving a small amount of mass from one end of the interval to the other would create an indistinguishable distribution that is far from P in Wasserstein distance, and a hypothesis testing argument can be used to show that the target estima- tion rate defined above (for the hardest one-d sub problem) depends on the interval size b - a. This implies that the adaptivity of algorithms support size of the distribution (crucial in Wasserstein estimation) is not captured by this notion of instance optimality. Instead, we add a further restriction to the definition make it more appropriate for our setting; we only consider distributions Q that are in a small Dxo ball around P (Dxo (P, Q) < In 2n, and ask that an algorithm is competitive with an algorithm that is told the additional information that P E (P. Q} (in the worst case over distributions Q that are in this Doc ball). That is, we define the benchmark estimation rate to be
[P} where Qp can be any distribution and is chosen to maximise Rv (P).
Ri (P) Q.D (PQQ)
sup min (RA,, (P). A
Note that all such distributions Q have the same support as P. which allows us to capture the adaptivity of algorithms the support size of the distribution. Specifically, we define the following target estimation rate in the one-dimensional setting. In the case of estimating distributions on a bounded subset of R. we will show that this error rate is achievable, up to logarithmic factors.
We also note that our notion of instance optimality more naturally captures the accuracy of algo- rithms even for basic tasks. Note that for the Bernoulli case, our technique achieves bound of
/ Vp(1-)) + min(p, 1 - P. J which also appear to be better than the instance-optimal lower bounds v
in MSU22], which take the form
/p(l-p) vn
+ 1. This apparent contradiction can be explained by
22

---

the the use in [MSU22] of the hardest-one dimensional sub- -oopproobem to define the instance- optimall rate, i.e. (V()) is (P.Q) Q} for worst-case Bernoulli Q. On the other hand, the notion of instance- optimality we use would only consider Bernoullis Q such that (P. Q) < 2. When p is close to 0, the lower bound in [MSU22] would on this instance consider Q to be Bern(p + en ). which can have a large disttanee from P. and so isn't in the neighborhood used in our notion of instance- optimality. Hence, the target rate one would obtain from our definition is smaller when p is close to O. Our algorithm can achieve this improved rate, as it is likely to output 0 as an estimate of p in this case, pushing small counts down to zero.
Recent differentially private algorithms such as those in [HLY21, DKSS23] have shown instance- optimality for problems such as mean estimation. Relatedly, other works have designed algorithms that adapt to the local/smooth/delltion sensitivity of the underlying function. An instance in these works in a dataset rather than a distribution, and is not clear how to extend the corresponding notion of neighborhood to our setting. Our neighborhood notion perhaps comes closest to the deletion neighborhoods considered in some of these works.
Finally, we remark that while we have stated our results as being competitive with the worst-case instance in (P)),, they apply for the average case over a specific distribution over (P)).. Since that specific distribution is adversarial, we don't 't view this version as more natural than the worst case.
Given that we focusing on private estimation, we will use use Rioc,n,e to denote the version of Eqn where the minimum is taken over all s-DP mechanisms, and RA,,,. to define the optimal e-DP estimation rate, i.e. Eqn 3 where the minimum is taken over all s-DP mechanisms.
B.2 Locally Minimal Algorithms
In this section we address the third desiderata of [CL15]. An important concept in statistics that of efficiency of an estimator, which informally compares the rate of convergence of the estimator with a benchmark that in general is not beatable. This idea has been used argue that for some fundamental estimation problems, the Maximum Likelihood Estimator (MLE) is the best possible. Hodge showed an example of a superefficient estimator that is asymptotically as good as the MLE everywhere, but beats the MIE on certain set of inputs. The statistics community has argued in multiple ways that these superefficient estimators do not limit our ability to argue that MLE is "opttial".. We refer the reader to [vd, Wol65, Vov09] for discussion of superefficiency. One of the more compelling arguments here is a result saying that the set of points where superefficiency is achieved has Lebesgue measure zero This in particular implies that in small neighborhood around any point, there is a point (in fact many points) where the superefficient estimator does no better than the MLE. In the partial order estimators, the MLE is thus minimal and this is true even when looking at the performance of the estimator only on a small neighborhood around a given point.
This motivates a slightly different notion capturing the goodness of the algorithm locally. Definition B.2. Let M be class of algorithms. We say that an algorithm A is a-locally minimal with respect to neighborhood map N. for all instance P, and all A' E M, there is Q (P)) such that (Q) S ax (QQ).
In words, local minimality says that for any other A', the algorithm A is competitive with A' for some instance in the neighborhood of P. Put differently, no A' can be uniformly much better than A on the neighborhood, even one that knows P.
We show that in general, this notion is incomparable to our notion of instance optimality. Neverthe- less, under reasonable assumptions, the two notions are closely related.
Example B.3 (Local Minimality # Instance Optimality). Consider a pair of instances (P,Q) with = {P. Q). Let M contain two algorithms A, and A with
M(P)=N((C) =
RAn(P) = 1; RA = O; (Q) 0;
RAn = 0;
Then one can verify that is (1-jlocally minimal in M. However, it is not o--instance optimal for any finite a it fails to sattisyy the definition at P. Example B.4 (Instance Optimality & Local Minimality). Consider a set of instances (P₁, P2, Ps) with (Pa) (Pi, (P)(P)))((PP)) = (Pi, P2, Ps).N((s) (P2, Pa). Let M contain algorithms
23

---

A, A" with
R (P:) 1;
RA 20;
R (P2) = 20;
RAm((P2) = 4a
RA = 4a";
(As(Ps)) = 4a
Then one can verify that is (1-)instance optimal in M. However, is not a-locally minimal at Pt.
Under smoothness assumptions on with respect N, one can argue that the two notions are essentially equivalent.
Proposition B.5. Let A be such that for all instances P and for all Q E N(P). (A)(QQ) S 3 (P). Further, suppose that (P) is compact for any P. If A is a a-instance optimal in M with respect to N, then it is a--locallly minimal.
Proof. Let P be an instance and let A' be competing algorithm. By definition of a-instance optimality.
RA a a.
sup (a)...Q).. QEN(P)
By compactness, this implies that there is Q achieving the supremum. In other words, there exists Q* (PP) such that
(P) S a (Q*).
Since Q' EN((), our smoothness assumption implies that
RA,((Q))) s 8. RA, (P)(P).
Combining the last two inequalities, this Q* satisfies
RA,((()) S aB (Q²))
Since P and A' were arbitrary, this implies that A is a-B-locally minimal.
Proposition B.6. Let A be such that for all instances P and for all Q E N(P). RA,(Q)) > (P). If A is a-locally minimal in M with respect to N, then it is a--instance optimal.
Proof. Let be an instance and let A' be a competing algorithm. By definition of o-local minimal- ity, there a Q' (N(P) such that
RA,, S a (Q*).
Since Q* NNP), smoothness assumption implies that
(P) < 3- RAm(Q (Q").
Combining the last two inequalities, this Q* satisfies
(A) S a3 (a²"((()))
s <03 sup (ost(A'(QQ))) Q). QEA(P)
Since P and A' were arbitrary, this implies that A is a a --instancee optimal.
similar pair of results hold when the comparator algorithm A' is smooth with respect to the neighborhood map.
24

---

B.3 Relaxed Definitions
We finish by noting relaxations of the above definitions that share the same semantic meaning (our algorithms will achieve these relaxed notions).
Definition B.7. Given a function N : : - (P),, where B(P) is the power set of P, we define the optimal estimation rale with respect to N to be:
RN (P) = min sup QEN(P)
RA,((Q).
(5)
An algorithm A (a, B, 3) iinstance optimal with respect to N for all PEP,
(A)(P) S aRN (P)
Definition B.8. Let M be a class of algorithms. We say that an algorithm A is (a. 3, 3.y)olllllll minimal with respect to a neighborhood map N. for all instance P, and all A' E M, there is a Q (P) such that R.,. S a R 8n (Q) +%-
Note that we think of 3 E (0, 1] and 7 as non-negative. The reason these are relaxed definitions is because we allow for an additive approximation factor in addition a multiplicative factor, and also compare to a benchmark rate that depends on a potentially smaller number of samples (and is hence easier to achieve). The original definition of instance optimality (Definition B. can be obtained by setting 3 = 1 and y O.
In our work, for most settings of interest, we roughly achieve 3 (log n) (()) and y to be an arbitrarily small polynomial in the inverse of the number of samples 1/n at log(1/7) cost to the multiplicative factor. We don't it view this as a significant issue since we expect the benchmark rate with (n/ log n) samples to behave asymptotically similarly to that with n samples most cases. We leave it an open question as to whether the original definition of instance optimality can be achieved.
C Additional Related Work
Instance Optimality for Differentially Private Statistics: Several recent works have focused on formulating and giving 'instance optimal' differentially private algorithms for various statistical tasks. The work of McMillan, Smith and Ullman [MSU22] is most directly related to our work; they gave locally minimax optimal algorithms for parameter estimation for one-dimensional exponential families in the central model of differential privacy. The work of Duchi and Ruan [DR15 [0R18] also gives locally-minimax optimal algorithms for various one-dimensional parameter estimation problems un- der the stronger constraint of local differential privacy. The notion of local minimax optimality both these papers use is based on the hardest oieedimensional sub mub-problem described in Section B. While our results for density estimation in IR satisfy this notion, they also satisfy a stronger no- tion described in Section B. Additionally, as discussed in [MSU22]. this definition is provably unsuitable for higher dimensions; we instead suggest a looser definition of instance optimality that is more promising in higher dimensions. More importantly, our paper is primarily focused on the non-parann non-parametric setting, and hence our techniques are different than the ones used in those papers, which focused primarily parameter estimation.
Other Beyond Worse-Case Results in Central Differential Privacy: Several additional works in the differential privacy literature study algorithms with accuracy that varies with the input dataset. Nearly all of them look at the empirical setting where we are concerned with the specific input dataset, rather than distribution it may be drawn from. While initial algorithms in differential privacy added noise based on a worse case notion of global sensitivity, these works give various algorithmic frameworks that help develop algorithms with guarantees that adapt to the hardness of the input dataset. These include algorithms based on smooth sensitivity [NRS07, BS19], the cospose-tst-reeeass. framework [DL09, BA20], Lipschitz extensions [BBDS13, KNRS13, CZ13, RS16], and sensitivity pre- prepprcesssing [CD20]. However, none of these works study a formal notion of instance optimality.
In contrast, some more recent work do study definitions of instance optimality in the empirical set- ting. A work of Asi and Duchi [AD20] studies two notions of instance optimality: one by comparing
25

---

the performance of an algorithm on a dataset against the performance of the best unbiased algorithm on that dataset, and another based on an analogue of the 'hardest oie-dimesiional sub- uub-problem' for the empirical setting (they compare the performance of an algorithm on a dataset with all benchmark algorithms that know that the input dataset is either of two possible datasets but whose performance is evaluated as the worse over the two datasets). They give general mechanism known as the inverse sensitivity mechanism that they show is nearly instance optimal under these definitions for various problems such as median and mean estimation. Our work is focused on population quantities as opposed to empirical quantities-whil these are related, they can be very different. For example, as pointed out in McMillan, Smith and Ullman [MSU22], using the inverse sensitivity mechanism in [AD20] to estimate the mean of a Gaussian (by using a locally minimax optimal algorithm for empirical mean) will result in infinite mean squared error, whereas other approaches that reason directly about the population quantities can get much better error.
In [DKSS23] and [HLY21], different notions of instance optimality are defined. Roughly, they compare the performance of an algorithm on a dataset with a benchmark algorithm that knows the input dataset but whose performance is evaluated sets of the input dataset. While the details of the definitions in these papers vary slightly, both papers give instance-optimal algorithms for mean estimation under their respective definitions. For one-dimensional distributions, our algorithmic technique at a high level shares ideas with these algorithms- the algorithms in their papers try adapt the range of values in the dataset, whereas we try to adapt to the level of concentration of the distribution. However, the details of how this is done and the associated analyses vary. Our algorithm for general metric spaces uses different techniques. Our work differs from these works in a few other prominent ways: firstly, they are pri- marily concerned with estimating functionals of the underlying dataset, whereas are problems with different output types and
the worst-case performance over large sub-
concerned
with density estimation in Wasserstein distance-ther different error metries. Finally, it is not clear if notions such as subset-based instance optimality that are well defined in the empirical setting transfer meaningfully to the distributional setting.
Instance-Optimal Statistical Estimation without Privacy Constraints: Donoho and Liu [DL91] formulated the notion of the 'hardest mieddmmeniooal sub-problem' as way of capturing instance optimality for statistical estimation and gave non-private instance optimal algo- rithms for some one-dimensional parameter estimation problems. Cai and Low [CL15] formulated an instance-optimaltty type definition for non-parameteric estimation problems. Our results for Wasserstein density estimation over IR use stronger version of this notion of instance optimality. In higher dimensions, this notion is provably unachievable, and so we define a different notion.
The other line of work most related to ours is on instance-optimal learning of discrete distribu- tions [OS15, VV16, HO19]. In their setting, instance optimality is defined by comparing the per- formance of an algorithm on a discrete distribution P to the minimax error of any algorithm on the class of discrete distributions with probability vectors that are permutations of the probability vector of P. We note that this notion is not well suited to many metric spaces, because permutations may not preserve properties such as concentration of the distribution, and hence this notion of instance optimality may provide an overly pessimistic view of the performance of an algorithm. Our notion of instance optimality (in terms of Dxx neighborhood) compares against algorithms with a different type of prior knowledge- i.e., the location of where the distribution concentrates, and approximate values of the probabilities at each point. We note that these are technically incomparable, and may be useful in different settings. For estimation in Wasserstein distance, knowledge of where the dis- tribution is concentrated could be very useful in algorithm design, and so comparing to algorithms with this type of knowledge is more appropriate. See Appendix B for more discussion.
Finally, there is another line of work on getting similar instance optimal guarantees for other statis- tical problems [AD]+1] 11, 1, ADJ+ 12, AJOS13b, AJOS13a]. For the closeness testing problem (given two sequences, determine if they are produced by the same distribution, or different distributions), Acharya, Das, Jafarpour, Orlitsky, Pan and Suresh [AD]+11, ADJ 12] developed a test (without any knowledge about the generating distributions) that achieves the same error with 3 sam- ples that an optimal invel-invariant test that knows the distributions p and q would achieve with n samples.
Other work on Differentially Private Statistics: There is a lot of other work on private sta- tistical estimation, and we survey the most relevant parts of the literature here. There is a long
26

---

line of work on minimax parameterrdditriiutioo estimation on various parametric distribution fam- ilies: product distributions [BUV18, KLSU19, ASZ20, CWZ19, Sin23], Gaussian, uub-Gaussian distributions (and more generally exponential families) [KV18, KLSUU19 AAK21, BGS+21, KMS+22b, KMS22a, HKM22, KMV22, AI.22, LKO22, TCK+22, HKMN23, AKT+23, BHS23, KDH23J, mixtures of Gaussian distributions [KSSU19, AAL23b, AAL23a]. heavy-tailed distribu- tions [KSU20, Nar23J, discrete distributions with finite support [DHS 15, ASZ20J, distributions with finite covers [BKSW2I] and more. This line of work focuses minimax guarantees in the paramet- ric setting, i.e. optimizing the worst-case error of an algorithm over the entire class of distributions. Our work, on the other hand works in the non non-parametric setting where we do not make assumptions about the distribution the dataset is drawn from, but instead give 'instance-optima algorithms that adapt to the hardness of the distribution the input dataset is drawn from.
There is also a line of work on differentially private CDF estimation [DNPRRO, I0, CSS11, BNS16, BNSV15, ALMM19, KLM CLN+233, and quantile estimation [KSS22, GJK21, ASSU24). Our algorithm for density estimation over uses a quantile estimation algorithm (based on CDF estimator) as subroutine. Finally, there is a line of work on differentially private testing [ASZ17, CDK17, CKM 19], and the work characterizing the sample complexity of simple hypothesis tests forms an important part of our analysis of the instance-optimal rate for distributions over R.
Work on Estimation in Wasserstein Distance: In addition to the recent works [BSV22, HVZ23] on private Wasserstein learning on [0, 1js, there is a plethora of works studying it in the non-private setting.
One line of work studies the convergence in Wasserstein distance of the empirical measure (on n samples) to the true measure, as a function of the measure and the number of samples n [Dud69, DY95, CR12, DSSI1, BG14 FG15, BL19, WB19, Lei20, Fou23]. Some of the later works above can be viewed as studying this problem from a beyond worst-case analysis viewpoint. They give upper and lower bounds for the expected value of this quantity, in terms of various no- tions of 'dimension' of the underlying measure, such as the covering number of the support of the distribution, the upper and lower 'Wasserstein dimensions' of the measure, and others. Our work shows that the empirical measure, appropriately massaged, approximately instance-optimal for density estimation without privacy constraints (for the notions of instance optimality we con- sider), and hence these works give us a handle on the instance-optimal rate as a function of the distribution and sample size n. Some more recent work studies minimax estimation in Wasserstein distance [SP19, NWB19], and show that without additional assumptions on the distribution, the empirical measure is minimax optimal. Our work extends this result to show that in the general non- parametric setting, the empirical measure is also approximately instance- -ottance-optimal; to the best of our knowledge, instance optimal estimation in Wasserstein distance (even without privacy constraints) has not been previously studied.
D Distribution Estimation on Hierarchically Separated Trees
Let us now turn to distribution estimation on arbitrary finite metric spaces. We will use the fact that any metric on a finite space can be embedding in a hierarchically separated tree (HST) metric to reduce the problem of density estimation in Wasserstein distance on an arbitrary metric space to density estimation in Wasserstein distance on an HST. In Section D.2 we'll characterise the tar- get estimation rate RN In Section D.3, we'll then provide an c-DP algorithm and prove that it achieves this target estimation rate up to logarithmic factors.
D.1 Preliminaries on Hierarchically Separated Trees
A key component of our proof strategy is the reduction to Hierarchically Separated Trees (HSTs). HST' are special class of tree metrics that are able to embed arbitrary metric spaces with low dis- tortion. They are particularly well-behaved when working with the Wasserstein distance since the Wasserstein distance on an HST has simple closed form.
Definition D.1 (Hierarchically Separated Tree). A hierarchically separated tree (HST) is rooted weighted tree such that the edges between level & and E all have the same weight (denoted r&) and the weights are geometrically decreasing so T (1 (2/2)r Let Dr be the depth of the tree.
27

---

An HST defines a metric on its leaf nodes by defining the distance between any two leaf nodes to be the weight of the minimum weight path between the two nodes. We will rely on two main facts about HST' in this work.
Lemma D.2 (Low distortion metric embeddings [FRT03]). Let (V,d) be metric space with M points. There exists a randomized, polynomial time algorithm that produces an HST where the leaf nodes of the tree correspond to the elements of the metric space and the induced tree metric dr such that for all u, v
. d(u, v) S (u,
El, v)] & O(log M) d(u, v)
The depth of the HST is logarithmic in the size of the metric space, Dr = log M.
An immediate consequence of the O(log M) metric distortion in Lemma D.2 is that the Wasserstein distance in the original metric space also preserved up to Ollog M) factor expectation. Thus, Lemma D.2 allows us to translate the problem of learning densities an arbitrary metric space in Wasserstein distance to learning densities in Wasserstein distance on an HST. This is a useful tool since HST metrics are generally easier to work with and, as we'll see below, the Wasserstein distance is particularly well- -ehavee on an HST. order to use Lemma D.2 to translate the problem of density estimation metric, paying a small additive term.
bounded ball in Rd into density estimation on an HST, one discretizes the
Corollary D.3. Given > O, there is probabilistic embedding f of [0, 1] into an HST such that for all y E [0,
. d(I, v) - a (f)()))
[[dr(f(x), & O(d log 2)) (d(æ, y) +a)
The distortion is logarithmic be Ogdlog n). It is easy to see that this implies that the Wasserstein distance is preserved in both directions up to (dd log d. up to an a additive error.
1. so taking a to be polynomially small, one gets the distortion to
A distribution P on the the underlying metric space in an HST induces function Gp on the nodes of the tree where the value of node v is given by the weight in P of the leaf nodes in the subtree rooted at v. For every level & E [Dr] of the tree, let Pt be the distribution induced on the nodes at level l where the probability of node
6 (P)). Thus is discrete distribution on domain of size Ne, where N₂ is the number of nodes in level l of the tree.
Lemma D.4 (Closed form Wasserstein distance formula). Given two distributions P and Q defined on an HST metric space, the Wasserstein distance between P and Q has the closed formula::
W(P.Q) Σ > - - Qr),
where Ty is the length of the edge connecting v to its parent, and the sum is over all nodes in the tree.
D.2 The Target Estimation Rate
Recall the definition of our neighbourhood.
N(P) E (P. < 1n2]
We will call node v, a-active node under the distribution P if the weight in P of the sub-tree rooted at v/ is greater than a. Let 7P (a) be the set of a-active nodes under P and YP, (a) be the a-active nodes level L.
Theorem D.5. Given a distribution P on [N], E > O. E [0, and E let
10ER min(W (245E) ,0.6) where W (x) is the Lambert W function so W ((x)e then
Pi(x)(1 Pp(x) n
Rx....(P) (P)= =Ω
max Σ min
Σ ed (2x)
Pe(x) + (1n, (2k) 1 1)m
zEINe)
where the max is over all the levels of the tree.
28

---

Note that K 2 1 (1)n)) so the dependence on and in Theorem D.5 matches the Th
upper bound in Theorem D.13. The error rate RN. . does indeed adapt to easy instances as we expected. The error decomposes into three components. The first component is the non-private sampling error; the error that would occur even if privacy was not required. The second component indicates that we can not estimate the value of nodes that have probability less than 1/(en). The third component is the eгror due to privacy on the active nodes. If P is highly concentrated then expect most nodes to either be - -actvvvve or have weight O, so the first two terms in Ry (P) are small. There should also be few active nodes, making the last term smaller as well. Conversely, if P has large region of low density then we expect large number of inactive nodes, as well as non-zero inactive nodes that are at higher levels the tree and hence contribute more to the final term. Thus, in distributions with high dispersion expect the right hand side to be large.
The proof of Theorem 4.1 I will involve two main steps. First, we will reduce the lower bound on the HST to lower bound on star metric, or equivalently estimation of discrete distribution in TV distance. We'll then use variant of Assouad's inequality to prove the lower bounds on estimating discrete distributions in TV distance.
D.2.1 Reduction to Estimation in TV distance of Discrete Distributions
The key observation that in order to estimate the distribution well in Wasserstein distance, an algorithm must estimate each level of the tree well in TV distance, Any estimate of P also induces an estimate of Pr: let P be an estimate of the distribution P and P3 be the induced estimate of the distribution at level f. Then for any distribution
W(P, P) = Σ rETV((E, RE(Dr]
The following observation ensures that our notions of instance optimality in both the Wasserstein metric and the per-level TV distance are compatible at every level f.
Theorem D.6. For every level E [Dr), define the neighborhood of Pa as No A((N)) -
P(A((N))) by Ny(P)) = (Qel Do0 (Pe Qc) S In 2). Then,
RN Z max Tε RN (E(DT)
where the error of P is measured in the Wasserstein distance and P: is measured in the TV distance.
Recall that R. (Pt) is the optimal estimation rate with respect to Ne where the error is measured with respect to the total variation error. The proof of Theorem D.6 can be found in Appendix G.
D.2.2 Characterizing Target Estimation Rate for Discrete Distributions
In light of Theorem D.6, we will focus characterizing the difficulty of estimating the distribution at a single level of the tree for the remainder of this section. Since this fundamentally a statement about estimating discrete distributions in TV distance, we will state everything in this section in terms of general discrete distributions. Let N E N, and let P be a distribution on [N]. Define ((P) {Q Doo (P, () I In 2). Our goal is to give a lower bound for R.,,, (P), where the metric is the TV distance.
Theorem D.7. Given
0.63 where W(x) is the and d [0, let == Tum W (0.45E) Lambert W function so W (x)e = x. Given a distribution P,
Σ min ((0) P(x)), FE[N
((x)(1- P(x))
R. (P)= =Ω
P(x) + (2x) - 1)mc
ZETP (2x)
Theorem D.5 follows immediately from Theorem D.6 and Theorem D.7. The main tool we will use a differentially private version of Assouad's method. This gives us method for lower bounding the error by constructing nets of distributions that are pairwise far in the relevant metric of interest, which for us the TV distance. The following a slight variant on the differentially private variant of Assouad's lemma given in [AS721]. Rather than building set of distributions indexed by hy- percube, we will build set of distributions over a product hypercubes. Since this an extension of the version that appears in [ASZ21], we include a proof in Appendix G for completeness.
29

---

Lemma D.8. [A extension of (e. (.. Assouad's 's method [AS22I]] Let ko. k1.-.. be a sequence of natural numbers such that Σ, k2 oc, > and d E [0, 1]. Given a family of distributions P C ( a space X, parameter 0 P - M where M is metric space with metric suppose that there exists a set V. C P of distributions indexed by the product of hypercubes Eko x Eks x ... where & == {=1} such that for a sequence To, T1
"u ) (v 0 ....) E ENo Eng x.,, (((0)))0(pp))) 2 2
Σ Ta
Xugzug.
(6)
jml
For each coordinate & E N. E [Kis], consider the mixture distributions obtained by averaging over all distributions with a fixed value the (s. j) 1h coordinate:
Σ P+(ad)) 1Ek x Eh, x ... MEEKY &&, x-mug==1
Σ
Pus P-(o,)) = 1Eho x Eki x...
Pus
uEEko XEk, x-mug==1
and let doGt :x= + 1-1, +1} be a binary classifier. Then
Pr (xs)(X) +1+ 1 Σ Pa, DP NoTT
min max RA, Ai (P DEV
min
Pr (0s)(X) + -1)) X-p" (ui))
where the min on the LHS is over all (s, DDP mechanisms, and on the right hand side is over all (e, ()P binary classifiers. Moreover, if for all N. j [big], there exists coupling (X, between P*(ss) and p" (5.5) with Had (X, YY, S D,, then
kGTs (0.9c 10 10D₂6)
min As DP PEV
max (A) (p)
Σ
2
Note that an upper bound on TV,P, P3) S y implies there exists coupling (X, Y) between P. and Pf such that am Y)] my.
We will separately prove that each of the three terms in Theorem D.7 belong in the lower bound. Each proof will follow the same underlying structure. Given distribution P. the main technical step carefully designing a family of distributions in (P) that satisfy the conditions of Lemma D.8. Lemma D.9 and Lemma D.10 give lower bounds the noise due to privacy. Lemma D.11 gives lower bounds based on the error due to sampling.
Let
1 10g
(0.45c 5
min (W
0.6),
where W (z) Rs In (1 o(1)) In In x is the Lambert W function satisfying W (z)ee W(x) = x. In both lemma proofs we will use the inequality that if D I K, then
(0.45s
w ((24 1.4 6
0.45s
0.9e-10: 10=D 10DS 2 e 10eD 0.9 W
e
10:D
0.9
2 e 100
100 2 0.2
8
8
(7)
Lemma D.9. Given a distribution P, > 0, 0. E [0, 1] and n E N.
(1e
2x - 1
K
Rxm,e (P) 2 0.1
Proof. Let L = hp (2n/n)) be the number of active nodes. If L = 1 then the RHS is 0 and so we done. Otherwise, assume L > 1 and let L/2] 1. Using the notation from Lemma D.8, let kn = k and k; = 0 for all s > 0. We will drop the reference to in the notation since only s significant.
Pair up the active nodes to form pairs of active nodes denoted by (at a.)...... -a ..)) Given u E Eg. define the distribution Pa as follows: for all as E 7p (2x/n), , Pa Pa(aa) = =((a))+ (k/n)) and Pa(a,) P(a,) ) (x/n)) if u, +1 and Pa = P(a.)- and Pu(a,) ) = P(ay (k/n))
30

---

if u = -1. For all other I, Pa(x) = P(x). It is immediate that for all u, P. E N(P). For any pair v. d(0(p.),
TV (p., Pv) = d (u, (x/nn) so that Equation (6) is satisfied with T = (x/n). Further, given j E [k], P+j and p-j only differ on the probability of az and 0j so D/n = maxj TV(== = r/n and by Equation (7), 0.9e 10eD - 10D8 2 0.2. Noting that k> (1/2) (2k/n) 1) completes the proof.
Lemma D.10. For all 0, 8 10. n N and distributions on [N] if n/2, then
RN (P) 2 S2
Σ
P(x)
(2
en the condition that K n/2 a mild condition. For example, it is satisfied whenever E > 2/n².
Since
Similar to the proof of Lemma D.9, we are going to pair up the coordinates and move mass between the coordinates to create the distributions indexed by the product of hypercubes. Since want all the distributions we create to be in (P),, we will divide the space into scales such that all elements in the same scale have approximately the same probability of occurring. We'll then move mass within these scales. For 8 E N, let S. = {i E [N] P(x) E (2- 1,2,]
Proof. Given E N. let Sy S, n for P(x) S 2x/n) and dg = (S%
Let us first consider the case that there exists a scale s* with dg. = and P(x*) 2 E P(z) where x* is the element in S... Define P" by P'(x*) (1/2)P(x*) and for all # x", P'(x)= 1-(1/3)P(a")
I-P(x=) P(x). Since (1/2)P(x*) S 2x/n 1/2, P N(P). In this case we will use Lemma D.8 with ho = 1, k2 = 0 otherwise, and E corresponds to the set of distributions {P. P'). Then noting that TV(P, P') = (1/2)P(x*) and using eqn (7) we (1/2) )n S x so that RN Z ((x))) =
have that T = - and
(Engrp(2a) P(x)) and we are done.
Next suppose that for all scales s such that d, = 1 we have P(x*) < & P(x). Let s" be the smallest such that de 1. Since the scales 2 are geometrically decreasing,
Σ En Σ
(()) Σ 2- <4.2
Σ P(r).
S 2
sdd, =d =1 BES, DEEEEES, (cT)()))
s:d,=1
(2k)(2N)
follows that End, > ExeS, P(x) 2 (1/2) E E2ggp((2) P(x). Further,
Σ (()) Σ
Σ
P(z) 4 Σ 2 2-2-id S 16
Σ 2 [d.22.
(ET)(2x)
sd,,b
sd,,>1
s:d,
Thus we can (up to constants) ignore scales such that d, S and assume that d, is even for all scales.
Let k2 [d./2]. Now, within each scale S,, pair the elements to form k2 distinct pairs (o a.,)). Given (u": ...) E & x Ex, x define Pu by (a(att) p(a.,) + --2 and Pa (a(a)) = p(an,)) 2- if uf +1 and pr. (a p(az.)) 2 2- and p=( = p(as.) + 2 2-9-2 easy to see that for all u, Pa.
if uz -1. For all other elements, Pu (=( p(z). Then, (P)). Further, using notation from Lemma D.8, Equation (6) is satisfied with T, = $2- s-2 since
d(O(pu), ((..)) TV(pu, Po) = 2 E, Tyd (u², u²) and D./n max, TV (P++( 2 2- which less than g whenever k2 > O. By equ (7), 0.9e 10sD. 10D,6 0.2 whenever k. > 0 so by Lemma D.8 we have
m. (P) 2 Σ 2 2k (0.2)
(0.2))
0.2
Σ
2- [d./2 4x 16
0.2
Σ P(x)
4
sdd,
(27)(2k)
which completes the proof.
31

---

Next we lower bound the statistical term.
Lemma D.11. For all n E N, E > 0, 8 E [0, 1] and distributions P, if 2 and E > 2/n, then
Σ min (()((1)((a) P(x)(1- (p(()))(a)) P(x)
R RN (P) 29
n
[EIN]
To streamline the notation, we will use L(x) to denote min x(1 - x), 211 2(1-x)
In order to
prove Lemma D.1I, will need the following standard result from the statisties literature which allows us to lower bound the performance of any simple classifier distinguishing two distributions P and Q by the KL divergence between P and Q. We give a specific result for distinguishing Bernoulli random variables since we" Il use this in the proof of Lemma D.11.
Lemma D.12. Given any pair of distributions P and Q on the same domain,
min Pr (x() =) (~-P
Pr (x()) = (0)) 2 2 (1-1 (1-VKKLL(P.Q) (nKL((PQ)), X-QQ
where the minimum over all binary classifiers. particular, if P Bernoulli(p - a) and Q = Bernoulli(p + oi) where O S a [Tpp) then
Pr (x(X) 1) Pr (6(X) ( -11) 2 1/4. X~pm
min
X-Q"
where again the minimum is over all binary classifiers.
The proof Lemma D.12 can be found in Appendix G
Proof of Lemma D. As in the proof of Lemma D.10, first suppose there exists scale s" with de- = and there exists x" E SS, such that
L(P(x*))
1 Σ L(P(x)).
60
øE[N]
Then define a distribution P' by P²(x)) P(z)) (L((2=)) and for all * x", P'(x) 1- 4 P(x). Then P (P)) since [((((=))) < 2/2 min(P((")) ). P(x)))}
I-P(z*) Then we will use Lemma D.8 with kn = and k2 = 0 for s > 0. and EN, corresponds to (P.P)). Now,
KL(P", P)= - (P(x") (P((T)) in P(x)) [((((=))) + P(x*) + 1 - 1- +( (P(((=) P(x*)
(L(PPP))=(0
1- P(x*)
1
4n
(for more detail on the proof of this inequality see the proof of Lemma D.12) so
min ( Pr (o(X) 1) Pr Pr. (o(X) 11) 2 (1 VnKL(P,P)) 2 1/4
x
and Tp = TV(P, Pd) = (P(x')))) Thus by Lemma D.8,
1 RN... (P) 2 Rv (P) L(P(="))
1 1
Σ ((P()))
480
sE[N]
and we are done.
On the other hand, suppose that for all scales such that d, 1 have
I(P(s.)) S 30 .E[N]
Σ L(P(x)),
32

---

where S = {.z}. As in the proof of Lemma D.10, we will argue that we can ignore any singleton scales, and assume that d, is even for all scales. Let s min(s d, 1} so
2-
Σ L(P(x.)) & ((P2) 8:d
+
min 2
*> 200d
2 2-
Xdb=1 (2 + v2) min 2 2-
n
P(x.')
Xdb=1 + 2(2 + V2) min
P(xx-);
n
S Xdo=1 + 4(2 (2)L(P((x.))
1 4(2 + V2)
Σ L(P(x))
30
ME[N]
Therefore, End, 21 Exes, [(P(x)) 2 (1/2) EnE(N] L(P(x)) and so
E 1(2---1) [d, 2
Σ L(2-5-1) 1-11--11- d
edd,>1
1/3 s:d, <d,>11 aES
Σ
L(2
1
3
Σ L(P(z))
3v2
2E[M]
where the first inequality follows from [d./2] 2 (1/3)d, whenever d, > 1, and the second follows because 2-a-1 < P(x))= S 1/2 for all x: E S, such that d, > 1.
Assume that d, is even for all s. Within each scale S,, pair the elements to form kg = ds/2 distinct 1 (LL22s1), I). and note that for all x E S, and pairs (at am,) ) per scale. For all s E N, let a, -2
s > O, as S (P()))) Given (u" "u,,""" .... Ex, XE, x..., define pa by Pu (a = p(a +a, and (a(aT,) p(a,,) = 02 if uz +1 and pu(at,)) = p(at,) as and Pu (a (..))) p(a_,) + as ug -1 For all other elements, P=(x)) p(z). Then, for all u, Pu E N(P.. Further, using notation from Lemma D.8, we have T. = agg. Also, for any (). P+(a)) and p- (x(s)) only differ on ax and a.,; where (+(+s))att,)) = P(att)) ) + as and p-(as)(att)) = P(at,) as. Therefore, by Lemma D.12, and the post-pin post-processing inequality,
min
Pr (0(X) = 1)+ X-Pi(e""
Pr (6(X) -11) 2 1/4.
x~p (0.s
Lemma D.8 then implies the result.
Theorem D.7 follows immediately from Lemma D.9, Lemma D.10 and Lemma D.1
D.3 An eDD Distribution Estimation Algorithm
Now, let us return to HST's and designing an estimation algorithm that achieves the target estimation rate, up to logarithmic factors. As in the one-dimensional setting, we want to restrict to only privately estimating the density at a small number ( en) of points. While we could try to mimic the one- dimensional solution by privately estimating solution to the en-median problem, it's not clear how to prove that such an approach instance-optimal.
turns out that a simpler solution more amenable to analysis will suffice. Our algorithm has two stages; first attempt to find the set of log(1/6) -active nodes, then we estimate the weight of these active nodes. Since these nodes have en
weight greater than (16)
privately estimate them to within constant multiplicative error.
33

---

Let A' be the underlying metric space so P ((X). For any set S of nodes and a function F defined on the nodes, define the function F as (V) F(z) if E S and Fls(v) 0 otherwise. Given two functions F and G defined on the nodes, we define
2 = Σ rul(()) - G(v)]:
where Tu is the length of the edge connecting v its parent, and the sum over all nodes in the tree. So by Lemma D.4, W(P, Q) W, (q). Note that 20 satisfies the triangle inequality.
Algorithm Pri PrivDensityEstTree
I: Input: D E .
2: Bp EmpDist(D)
Compute empirical distribution.
3: 9 = Locatehctivellldess@P:::
P Privately approximate set active nodes.
if x & % otherwise.
4: Define Pn by 6 P.n (x) p)))) + Lap ())
> Approximate densities.
5: Pr,e = Projection p Pontte)
Project noisy densities onto space of distributions.
6: return Pn.s
A high-level outline of the proposed algorithm is given in Algorithm 1. Now, we state the main theorem of this section.
Theorem D.13. Given any E > O, PriuDens t Tree
(Dr + DP. Given distribution P, with probability 1 - (Dr logn + 4Dren)8,
W(P, P3) =0 ( Σ Σ min
log(n/)
(E(Dr] [E[Ne]
lpp, Ben
log (1/3)
3 pp(v)+ +
" maxx{ 2 +2 (ox(2/3) 192 1oglo/1/3)
om 2m
This bound has the same three terms as our lower bound on R.v..e in Theorem D.5 corresponding again to the empirical error (the error inherent even in the absence of privacy requirement), the error from the private algorithm not being able to estimate the probability of events that occur with probability less than s log(1/ (og(1/8)/en) /8)/en, and the error due to the noise added to the active nodes. The maximum over the levels that appeared in the lower bound is replaced with a sum over the levels in the upper bound, up logarithmic factors, the upper bound is within factor of Dy of the lower bound, Since we can not hope to locate the set of log /6))(Enn)aattvv) nodes exactly with a private algorithm, find set %n that is guaranteed satisfy
2
log(2/3) 192 log(n/ ( C C YP
7P
max
+
en
n
n
2en
Note that max estimating Yp
log(2/8) 192 log(1/8)
C Clog(n/8)
so the error introduced here by not
ER
n
"
En
perfectly at most logarithmic multiplicative factor.
The first step of our algorithm is to estimate the empirical distribution. We use truncated
version of the standard empirical distribution. This allows us achieve an error rate of min(P(x), /P(x)/n} even when P(x) small.
The proof of the following lemma is contained in Appendix G.
Lemma D.14. For any distribution P, lllog(n/)) > 1 then with probability 1 -DDr
Pe(x)(1 (00((111(xx)))))))) log
20 110..ppm
Σ
Σ min P1(x) - Pe(x)), ((4)))44 4/
n
tE(Dr) N
34

---

Algorithm 2 EmpDist
1: Input: D E X",
2: Let Pr be the empirical distribution.
3: for all node do
P (v) (n//)
4:
8 Bp(D)
Pr (D) >1
Vlogn/3)
+
otherwise
Algorithm Locaatecttiveeeds
1: Input: p
2: Let é = and 7e,0 {u} where is the root node.
3: while i,,e + Ø and < Dr do
4: fe,8+1
5:
for all v/ Te,e do
6:
for all children // of y/ do
7:
if @p(()) + Lap( en > 2x
log(2/8)
then
8:
7e,0+1 fe,4+1 + {v/}
9:
1=t+1
10:
return Uff,t
The goal of Algorithm 3 is to estimate the set of 1 1/(En)-activg nodes.
The next lemma allows bound how close to the goal get. The proof is contained in Ap- pendix G.
Lemma D.15. Let 9e be the set of active nodes found in Algorithm Then with probability Dr(log n + 4sn)3,
2 +
log(2/8)
192 log(n/
1) C+c C up
TP
max
En
2en
We also prove the following lemma relating the error due to estimating the active nodes to quantity depending on the true active nodes.
Lemma D.16. IfP [max{ 2
log(2/3)
192 lo2(n///
})
Ge then
20 p. ppkx) < 20 Bp 3p) + ( 8p Tp (maxt +1 (om(2/8)) tollogn//1)
The key component of this proof is that any discrepancy between the weight of the nodes on P and that assigned by @p was already paid for in W(P, Bp). The final step in Algorithm is to project the noisy function 3 P. into the space of distributions on the underlying metric space. We'd like to do this in way that preserves, up to constant, the 22 distance between P and G P.... We will do this iteratively starting from the root node, by ensuring that the sum of each node's 's children add up to it's assigned value. Since we know the root node has value 1, this results in a valid distribution. We start from the top of the tree since errors in higher nodes of the contribute more to the Wasserstein distance. While errors in higher nodes of the tree propagate can propagate to lower levels, the predominant influence on the overall error is retained at the top level due to the geometric nature of the edge weights.
Lemma D.17. For any real-valued function on the nodes of the HST such that ((vo) 1 where Po is the root node and given any distribution P.
W(P, Projectionn (B) < (20 6 8).
Combining the above lemmas appropriately gives the proof of Theorem D.13 (see Appendix G).
35

---

Algorithm 4 Projectioon
1: Input: 6, real-valued function the nodes of the HST such that G(vo) = 1 where Mo is the root node.
2: @ Ø
3: for = O: Dr- 1 do
4:
for all nodes v at level é do
5:
Let A = Σ G(v)) where the sum is over the children of v.
6:
Let d, be the number of children of y
7:
if A, = then
8:
for all children v/ of do
9:
B(v') = d (vv)
10:
else
11:
for all children vf of do
G ((v)) = (( (1)) A
12:
13:
return
Proof of Theorem D.13. The privacy follows from the fact that each user contributes to at most Dr
queries in LocateActiveNNodes and at most one coordinate in the computation of 6 P., 4n in line PrivDensityEsttrren
For the utility, we will consider each level & individually. First suppose that hnp, (1/(2en)) > 1.
((PP,(Pe)) s 22)(( pm )a)
2 (2((()))) (Gr))) 20 (Gr), (rl(fe)) (Grl5))) Pr (9)
2 220 (BP). (p)) + 20 ( (8P),. (8 (max 2 +2 lox(2/0) اليا 1) p(
where the first inequality follow from Lemma D.17, the second inequality follows from the triangle inequality and Lemma D.4, and the third follows from Lemma D.16 and Lemma D.15. Finally,
20 ( ( Ponte
Σ ru Lap
1
Σ
ru ru|Lap( )
en
en
METP 2en
VETP( 2t.))
The final statement then follows from Lemma D.14 and basic concentration bounds on the Laplacian distribution.
If he,, (1/(2en)) = 1, then the proof goes through for all except the final term related to the noise due to privacy. We consider two cases. Let x E 7r, (1/(2n)).. First suppose that Pz(x) > Zen then node that is in level above x. but is not direct ancestor of x: is in Yr, (1/(2en)). Therefore, since the projection algorithm is top-down. (Pr.c): will be concentrated on æ. Therefore, the error of level f is simply (1 P.x)), which can be charged to the first term plus the sum of the weight of the inactive nodes, which in the second term. Next, suppose that Pε(ar) < 1 1 then sum of the inactive nodes (in term two) dominates the error due to adding noise to P(x)
2en
E Instance Optimal Density Estimation on IR in Wasserstein distance
Let us now consider the setting of estimating distributions /' on X' = R. In this setting, the target estimation rate that of an algorithm that knows that the distribution is either P Qr for a dis- tribution Qp such that Dxo Qr) < In 2. This definition of instance- -oitancc-opiimalityy strengthens that corresponding to the so-called hardest-one dimensional subproblem [DL91], since this harder estimation rate to achieve. A formal description of the target estimation rate is given in Appendix B. and Appendix B.3. Appendix 1, we lower bound this estimation rate using hypothesis testing techniques. Then, in Appendix F.2, we give an algorithm that up to polylogarithmic factors, uni- formly achieves the lower bound, and hence approximately achieves the instance-optimal estimation rate. Our instance optimality results apply to all continuous distributions in bounded interval with
36

---

density functions (though it is likely that they apply more generally). All omitted proofs can be found in Appendix
E.1 General Lower Bound
To state the main theorem in this section, we will introduce some notation. We start by defining the restriction of distribution.
Definition E.1. For any distribution P over R with density function, the restriction Pla.e of P
with respect to u S U E R is defined as the distribution with the following CDF function F":
t u
FP.... (1) Fp(x)
u u <tt
t t2v
If = then F is a step function that goes to at that point and is 0 prior to that point.
Also recall the following definition of quantiles.
Definition E.2. For 0 < a S the o-quantile of distribution P over R is defined as follows:
qa arg min Pr S t)
g~p
When the distribution P is clear from context, we will sometimes abuse notation and use qa when we mean la (P). The main theorem we will prove in this section is the following:
Theorem E.3. There exists a constant C such that given a continuous distribution P on with bounded expectation and E (0, 1], n E N,
R.oc, (P) (ooe,,,(P))= =
41 (9--2-- - W(P, Ply
91 cen
Gen
4 1 )
E [(P1)
Pa
Vlog
4 41-e
where Pn, is the empirical distribution samples drawn independently from P.
The same result can be extended to (E, algorithms as well for o
We discuss each of the terms in turn. Note that the final term is related to the expected Wasserstein distance between the empirical distribution and the true distribution. There is now a long line of work characterizing this quantity in terms of the distribution (See Section C), but essentially, if the distribution is more concentrated, this term smaller. The first term is very particular inter-quantile distance that is also much smaller for concentrated distributions, and can be large for relatively dispersed distributions. The second term characterizes the length of the tails of distribution- longer tails make this Wasserstein distance larger. Overall, this rate is significantly lower for more concentrated distributions with small support, and relatively large for more dispersed distributions. We prove this theorem over the following couple of sections; in Section E.1.1 we characterize the cost of private instance optimality, and in Section 1.2 we characterize the cost of achieving instance optimality without privacy (this non-private characterization is also new to work, to the best of our knowledge). Combining the theorems in those sections gives the above result.
E.1.1 The Privacy Term
The main theorem we will prove in this section is the following.
Theorem E.4. Fix s E (0, 1]. E N. For all distributions P over R that have a density function and finite expectation, there exists another distribution Q" such that D (P, Q) 2, that is indis- tinguishable from P given (nn) samples such that for all e-DP algorithms A Rn + A (IR), with probability at least 0.25 over the draws P x' Qu the following holds for some constant C.
max(WW(P. A(x)) W(Q", ,(('))) 2 4Con 91- 1 -9
Con 4 Cen
37

---

We start with some notation. For any distribution P with density, let fo denote its density function. Throughout this section, we will use 9a to represent the a-quantile of distribution P. Let L(P) be the sstrrtig point' of distribution P (defined as inf Fr(() > 0} if the infimum exists, and -0o otherwise.
Next, we describe some results on differentially private testing that we will use. We say that testing algorithm Atesr distinguishes two distributions P' and Q with n samples, if given the promise that a dataset of size is drawn from either P or Q", with probability at least &. it outputs P if the dataset was drawn from P and Q if it was drawn from Q". We now state a theorem lower bounding the sample complexity of differentially private hypothesis testing.
Theorem E.S (ICKM+19 19, Theorem 1.2)). Fix n E N > O. For every pair of distributions P. over R. if there exists an e-DP lesting algorithm' Atest that distinguishes P and Q with samples, then
(P, (PQ))) -
1
== (T( (1-
where
T(P,Q)= max { fr(tf
fo(t), (p(()) / max ff())))(((t))t)))o)e))))))))())) O)dt)
/
and (:,.,)) -) is the squared Hellinger distance between P min(e
1-7(P.2) and Q' min(e P.)
1-T(P.)
where 0 < E' S is such that if T (P,, Q) SR max fQ()), (e(t,,0dtt Ofdt, then e' is the maximum value such that
7 (P,, Q) / max( - é {sp(),0)d..
else g' is the maximum value such that
T(P,Q) Q) max{ff(()) e (f())
We now are ready to start proving our main theorem.
Proof. (of Theorem E.4) The idea is to construct Q from P by moving mass from the leftmost quan- tiles to the rightmost quantile. We do this such that Q is statistically close enough to P such that the two distributions can not distinguished with n samples, but is also far from P in Wasserstein distance. This produces a lower bound of (1/2) Q) on how well an algorithm can simulta- neously estimate and Q since there was an algorithm that produced good estimates of P and Q in Wasserstein distance with samples, then we could tell them apart, and this would give contradiction.
Let &o be quantity to be set later. Formally, we define Q as the distribution with the following density function.
{ fff(t), (p((),
for t < 91/k:
fa(1)
for 41/8 S 9 1
(1)(()
for -1- S
Note that by the definition Q, we have that (P..Q)
We will prove that the sample complexity of telling apart P and Q under (e, 6)-DP is (2(kss), using known results hypothesis testing. Then, will argue that the Wasserstein distance between P and Q is sufficiently large. Setting appropriately will complete the proof.
Define SCs,, Q) to be the smallest such that there exists an (e, DD- testing algorithm that distinguishes and Q; called the sample complexity of privately distinguishing P and Q.
Lemma F.6. SC,,
'The same bounds (and hence all our results in this subsection) can be extended to (e, 8)DP) (with 8 < s) by using equivalence of pure and approximate DP for identity and closeness testing [ASZ17, Lemma 5].
38

---

The proof of this lemma is in Appendix J. We next argue that P and Q are sufficiently far away in Wasserstein distance.
Lemma E.7. W(P, Q) 2 2% (1- - + W.P P.P. Pl 9-
The proof of this lemma also in Appendix J.
Finally, we are ready to prove the theorem. Assume that with probability larger than 0.75 over the draw of two datasets have that max( ((x)). ((Q,((x') < ?W((P. Then, given a dataset x" size n, we can perform the following test: run the differentially private algorithm A on the dataset x" and com- pute W(P, ..xx((x")) and W(Q, A(x")) and output the distribution with lower distance. Then, note (MP.A((")) )(x")) + W(Q, A(x")) which implics that with probability at least 0.75, Q) if the dataset x" was sampled from pm (by the accuracy guarantee). JW(P, Q) if the dataset x" was sampled from Q". Hence, with samples we have defined a test that distinguishes P and Q. However, for k = Cen for some constant C, by Lemma E.6 we get that any differen- tially private test distinguishing P and Q requires more than n samples, which is contradiction. Hence, with probability at least 0.25 over the draw of two datasets x ~ PR, x' ~ Q", and the randomness used by invocations of algorithm A we have that max(W((P A(x)), A(x))) 2 W(P, Q) 2 ICen (1) ot. Q1/Cen) ) + WW(P,, Pl, 41 invoking Lemma E.7 with = Can.
pm, x' Q", and the randomness used by invocations of algorithm A
that W(P, Q) & W(P,
W(Q,
A similar argument shows that with probability least 0.75, W(P, A(x"))
,where the last inequality is by
E.1.2 Empirical Term
In this section, we prove the following result.
Theorem E.8. Fix sufficiently large natural numbers n. & >> O and let C, C' >> O be sufficiently small constants. For all algorithms A I2" - Ag, the following holds. For all continuous distributions P over I with density and with bounded expectation, there exists another distribution Q (with Doo P. Q) S In 2), that is indistinguishuble from P given O(n) samples, such that with probability at least 0.25 over the draws x ~ Pm, x' ~ Q", the following holds.
(ax( W(Q
C'
C'
Ex"~ Pm [W (Plag-013 A1 (WPPla
Vlogn
where qa is the a-quantile of P.
Before going into the proof, we state the following result on the sample complexity of testing. This a folklore result but for a proof the lower bound see [BY02] and the upper bound see [Can17].
Theorem E.9. Fix E N. O. For every pair of distributions P. Q over R, if there exists testing algorithu Atest that distinguishes and Q with n samples, then
n =
(P(())))
wherer (²(:.)) represents the squared Hellinger distance between P and Q. Throughout the proof, will use 4a represent the a-quantile of distribution P.
Proof of Theorem E.8. Q is constructed by adding progressively more mass to P up until 01/2 and subtracting proportionate amounts of mass from P afterwards. Intuitively, this is done in such way that to 'change' P to Q, for all 2 2 one has to move roughly min /2'n" 2: mass from 4//24 to
41-1/2 This ensures that the Wasserstein distance between P and Q is larger than the expected
Wasserstein distance between and its empirical distribution on n samples P,.. This is carefully done to ensure that P is indistinguishable from Q.
Formally, consider i in the range [2, logn
1). For all (11/2/.11/2-- we set fo(t) For all E (q1-1/2 1, 41 1/2], we set fo(t) = fp(t)
fP(t)
1 1+
2:
/ Next,
39

---

consider i in the range [log oo). For all & (91/25: 91 /1 we set fo(() = fr(t) [1+ 2} For all & E (/1-1/2 i, 11111//21,, we (t) fr(() [1 2). Note that P has bounded expectation by assumption, and hence, so does Q. Additionally, note that (P, S 2.
There are two key considerations balanced in the design of Q. On one hand, we need Q be in- distinguishable from P given (n) samples. On the other hand, we need Q to be sufficiently far away from P in Wasserstein distance. This ensures that given an accurate algorithm for estimat- ing the density of the distribution (in Wasserstein distance) given access to O(n) samples from it, we can design a test distinguishing P and Q with that many samples, thereby contradicting their indistinguishabilit.
Detailed proofs of claims below be found in Appendix First, show that P is indistinguish- able from Q.
Lemma E.10.
KL = OOlggn//))
Next, we establish lower bound on the Wasserstein distance between P and Q.
Lemma E.11.
log n-1
oc:
W(P. Q) 2
191-1/2
91/20] +
Σ j=log n
[9-11/20
91/21]
2
27
Next, we upper bound the expected Wasserstein distance between the distribution and its empirical distribution on n samples.
Lemma E.12.
Ing n-
1
Σ
20
1 11- 91/2
11-1
91/22|
2
2
lnlng n
We now prove simple claim regarding restrictions.
Claim E.13 (Restrictions preserve Wasserstein distance). For all dalasets x, and any natural num- ber we have that
W(Plg 91.4 1² Pulay +) WPP,
n Finally, we are ready to put the above lemmas together to prove Theorem E.S. Fix n' = C'oog x² Assume, for sake of contradiction, that with probability larger than 0.75 over the draw of two datasets x ~ pn' x' ~ Q"', and the randomness used by invocations of algorithm A we have that max(W((P, A(x)), perform the following test: the differentially private algorithm A on the dataset x" and com- pute ((P,A(x") and W(Q, A(x")) and output the distribution with lower distance. Then, note that W(P, I W(P, A(P))) + W(Q, A(x")) which implies that with probability at least 0.75, A(x)) 2 Q) xf pa' (by the accuracy guarantee). similar argument shows that with probability at least 0.75, W(P,A(x")) > WWP, xf ~ Q"", Hence, with ní' sam- ples we have defined a test that distinguishes P and Q. However, by Lemma E. bounding the KL divergence between /' and Q, Theorem E.9 on sample complexity lower bounds for testing, and Lemma A.7 on the relationship between KL and Hellinger distance, we get that any statistical test distinguishing P and Q requires more than n'' samples, which is contradiction. Hence, with probability at least 0.25 over the draw of two datasets pn' x Q"' by invocations of algorithm A we must have that
A(x') S (P, Then, given a dataset x" of size n', we
and the randomness used
max,P((,AAx)). W(Q, 2 !
2 W((PQ)
(10)
40

---

Next, note that by Lemma E.12 (with value n'), we have that
Tog
E[W(P,
22'n' 11-1122
91/25]
Σ
1
[1
1111/22
91/20]
2
looo
log log
8
91/22] + 111-1/2-
2 11-1 91/24
V2'n
i=log Tooo
log n- Cogi n)
log
1
VClogn
[9
91--
91/21 +
91-1
91
-1122
2
2
1=2
== n (O log
1
91 1/2
91/20|
2
mmgg
Analyzing the middle term in the above sum, we have that
log 1-1
logn-1
1
111-1/2
[2/22]
V200 n log(C logn) 111- - 41/22
2
2
é=log n (C logn)
im log n lC log m)
logn- n-1
VC'log n1
[12 1/22 92/22
2
Vn.
im log n log log
log n-
1
Colog
[91-1/2- 91/24]
V2'n
i= log(C logn)
Substituting this back in the previous sum, we have that
log nognn (C n)
VClogn
[9 112/ 91/2i
2'n
1
n-1
8
+ VClogn
Σ
V2in 191-1/21 - 91122] +
Σ
2 1-2 - 91/21)
l=lo n - (C ('loog))) m)
imlng
log n-1
1
1
< 8V lol
11-1/22
-11/2
91 1/2- 91/22]
V2nn
2
1=2
i=log n
log n-1
< 16 L16/Clogn Cog
Σ
[1 11211/2
41/2: +
Σ i=log
11-1/22 - 91/21
V2tn
2
where in the last inequality we use the fact that n' > Vn. Hence, by Lemma E.11 (which gives a lower bound on W)P.Q)) in conjunction with the above equation, we have that W(P,Q) > LIP, Par] for some sufficiently small constant C". Substituting back in Equation 10, we have that with probability at least 0.25 over the draw of two datasets pm x' Q and the randomness used by invocations of algorithm A we have that
C' ([)))
C" 2 Vlogn' n'
max A(x)), W(Q, A(x)) 2 2 Vlogn'
B [WPPoo 11-2 Par (erlgg
as required.
E.2 Upper Bound
In this section, we describe an algorithm that achieves the instance optimal rate described in the previous section (up polylogarithmic factors in some of the terms).
41

---

We will be looking at distributions P supported on a discrete. ordered interval {a, at%. b.,. b). Note that by simple coupling argument, any continuous distribution poont on [a, is at most ? away in Wasserstein distance from a distribution on this grid. The dependence on 7 in our bounds for discrete distributions will be inverse polylogarithmic (or better), and so our algorithms for estimating distributions P in the interval {a, a-tr,.... b-7; b) also work to give similar bounds for continuous distributions on [a, bl. up to a small additive factor of y, which can be set to any inverse polynomial in the dataset size without significantly affecting our bounds.
Formally, we will prove the following theorem (See Theorem E.15 for more detailed statement).
Theorem E.14. Fix B E (0, a, E R, and 7 < - a E IR such that b-a is an integer. Let b-o Biy for some sufficiently large constant There exists an s-DP algorithm A that
n E N > 02 log" for any distribution P on {a, a + ",a- -2,...,bb 7, satisfies the following. When run with input a random sample ~ P", A outputs a distribution pDp such that with probability at least 1 B over the randomness of and the algorithm,
W(P, pDP) =0
(1-:---)))) -9:) + W(P. 0 -
T +) log E [w Pl Play.n + Polay a 1)) V
where Pn is the empirical distribution on n samples drawn independently from P. qa represents the for a sufficiently large constant c3.
a-quantile of distribution P. and k Seg log"
37
log
Since k se en/ log(n). this upper bound matches the lower bound in Theorem E.3 in its dependence on e and its dependence on n (up to logarithmic factors in n). The algorithm that we will analyze proceeds by estimating sufficiently many quantiles from the empirical distribution and distributing mass evenly between the chosen quantiles. The number of quantiles is chosen carefully to ensure that the estimated a-quantiless are also approximately a-quantiles for the empirical distribution (and hence also approximately for the true distribution), and to ensure that the CDF of the output distri- bution closely tracks the CDF of the empirical distribution. Through careful analysis, are able to leverage these properties to give instance optimality guarantees for the accuracy of the algorithm.
E.2. Algorithm for density estimation
Algorithm 5 is our algorithm for density estimation, and proceeds by differentially privately estimat- ing sufficiently many quantiles of the distribution and placing equal mass on each of them. We argue that simple CDF based differentially private quantiles estimator A Aquant satisfies specific guaran- tee that will be key to our analysis. See Appendix for more details about the quantiles algorithm and formal statements and proofs therein.
Algorithm 5 Algorithm for estimating a distribution on IR
Input: x (II, ...,........ Zn) P", privacy parameter c, interval end-points a, granularity 7
access to algorithm Aquant Output: Distribution PDP on R.
1: Let k be set to 4eg log" gm
for a sufficiently large constant cg.
log H
2: Use Algorithm Aquant referenced in Theorem 1.2 with inputs interval end points a, b, gran- ularity 7,
(2I....,
.........,)) In)
{a, Y.... b 7, 6)", and desired quantile values a (2k - 1)/2k}, and let the outputs be ...,
(1/2k, 3/2k,5/2k,
3: for [ do
4: Set pDP(O)) k-'
5: Output PDP.
Observe that Algorithm inherits the privacy of Aquants since it simply postprocesses the quantiles it receives from that subroutine, and hence is also s-DP.
Now, we are in a position to state our main theorem, which bounds the Wasserstein distance between the distribution output by our algorithm, and the underlying probability distribution P.
42

---

Theorem E.15. E, E (0, a, R. and y < E R such that b-a is an integer. Let
EEN MEN> log' T8e for some sufficiently large constant C2. Let P be any distribution supported on {a, [a,a+7: 7, 2....... 60, and x ~ P".
Then, Algorithm 5, when given inputs x, privacy parameter e, interval end points a, b, and granular- ity 3, oulputs a distribution PDP such that with probability at least 1 (3)) over the randomness of x and the algoritiu,
W(P,PDr) PDP) V.logn-BB n-E W(PPg 4- Palgg 91
PC 91 ) (9) (91-1/k 91/R))
where Pn is the uniform distribution on x, qa represents the a-quantile of distribution P, c, C" are sufficiently large constants, and k log
en b-a log
where is sufficiently large constant.
We that using more sophisticated differentially private CDF estimators estimate quantiles (such as ones in [BNSV15, C3)) we can also obtain a version of the same theorem for approx- imate differential privacy, with a better dependence on the size of the domain b-a (only log" ( (b=a)
opposed poly log
b-a
where log" is the number of times log has be applied to get
be < 1).
To prove Theorem E, we first relate the Wasserstein distance of interest (between the true dis- tribution P and the algorithm's output distribution pDP to quantity related to appropriately chosen restriction. Let qo represent the a-quantile of P and 'r. represent the a-quantile of Ps and Ta represent the a-quantiles of PDP, We also note that all these distributions (and others that will come up in the proof) are bounded distributions over the real line and so we can freely apply the triangle inequality for Wasserstein distance, and the cumulative distribution formula for Wasserstein distance (Lemma A.3). The proof of the main theorem will follow from the following lemmas (all proved in Appendix J).
Lemma E.16. Let C" > 0 be sufficientll large constant, and let >> 0 be sufficiently large. With probability at least 11-0( 0(3) over the randomness in data samples and Algorithm 5,
W(P, pDP) S W(P) 11 -.- DDDP (ag---)) C",,PP Pla
Lemma E.17 (Wasserstein in terms of quantiles). For all datasets (with data entries in (a, b)). with probability at least 3 over the randomness of Algorithm 5, we have that
2
W(Pnlg W[Pnlay.4. 4 91-91-44 (g1-1/k 92/1k)
PPP
where Ps, is the uniform distribution over
Now, argue about the concentration of the Wasserstein distance between restrictions of the em- pirical distribution and restrictions of the true distribution.
Claim E.18. Fix 3 E (0,1) and sufficintly large constants C3, Co- Let n. > 0 be sufficiently large such that n > log n/ (as in Theorem E.15), For all such that &o C3 least 1 - ((3) over the randomness in the data,
log $ with probability at
W(Pl ((Play.9 9
PPPllg s
n Ca log
B (E[W(Plagg I Pulay. 1
Now, we give the proof of our main theorem.
'The theorem would be same form Theorem E. except that Algorithm would (e, 6).D. with the lower bound on n instead being n Q polylog" Ted log 1/8 (1g(1))) and & being set instead to log h-nn en polylog B
43

---

Theorem E. Using Lemma E. 16, Claim 18 and the triangle inequality, we have that with prob- ability least 1 1 (3) over the randomness the data and the algorithm,
PDP)
- W(P 41
PDP
91 C" Pla Plag. 1A
s W( 1 1t²
PDP
+ W(Pnla ((Pnlla .1 +² Plog. + -"CW(P. Pla 19 =²
S W(PP 9g 1
PDPL
- +
Ca log
W( - p. Plag -1 + C"M((P, 4
Finally, applying Lemma E.17 and taking union bound over failure probabilities, we get that with probability least 1 ((3) over the randomness of the data and the algorithm.
2 W(P, PDP)
"1 < 1/1 q1/x) v ca log "E 3
1. -1---- /t Plag 21 + CC" -
as required.
F Experiment Details
Below we describe the experiment referenced in the introduction.
The distribution: We have taken a distribution on [o, 999], which concentrated on two points 430 and 440, with P430 from this distribution.
3 and p440 = 2/4 These algorithms have been run with 1600 samples
Minimax Optimal Algorithm: The minimax-optimal algorithm here is the algorithm PSMM from [HVZ23] that considers a fixed partitioning of the interval into 2(m²) equal intervals and places the empirical mass in each interval an arbitrary point each interval. Here we consider this algorithm with e = cc, so that no noise is added. We have run it here with K = 40 buckets.
The instance-optimal algorithm finds & quantiles as in Algorithm 5. In this particular implementation, we used the recursive exponential mechanism of [KSS22], but we expect other quantile algorithms would work similarly. In this particular case, we use k: 10 quantiles with E =
Instance-optimal Algorithm:
G Proofs for Section D
Theorem D.6. For every level & E [Dr]. define the neighborhood of Pt Ne A((N))
P(A((N)) by N2(P)) (Qel ( Qc) I 2n2]. Then,
RN,,,((P) 2 (E(Dr]
TE (Nt.)..(P)).
where the error of P is measured in the Wasserstein distance and Pe is measured in the TV distance.
Proof of Theorem D.6. Given distribution P, let
Ap arg min max ED-P- (W(P,((D)) A QEA((P
So (P) = (ax ED ED=O (M(P)A)((D)) Let [Dy]. want to define an algo- rithm Ar, on the distributions in (Pr) that achieves maximum error rate R.... Define a randomised function 9P which given node D, at level f, (P())) is sampled from the distribution P restricted to the leaf nodes that are children of vy. Given set of nodes at level e, define gr gp()) to be the set where yn is applied to each set element individually. Then define A', (D) (A)())(D))) Since gp is applied individually to each element D, Ar, cDD..
Given a distribution Q' E (Pt)), define a distribution Q on the leaves the tree as follows:
(v(ve) Po(ve)
Q(v)
* P(v),
44

---

where is the parent node of v at level L. Note Q E ((P), gp(()) 9x(()) = Q and Qt = Q² Now,
TV(Q', Ap, (D)) = TV2 (Ap(gr(D)))
S
Σ (eT Tt PE(Pr]
= W(O.
rt
where the first inequality follows by definition of AT, and the fact Qi Q². Since gp((%) Q, this implies that for all distributions in Ne(P:).
D [TV(Q' (D)) S ED_Q 1 Lw(Q.AA(D)) 1 Rr
which implies for all levels e, RN (P)) t RN and are done.
Lemma G.1. [A extension of (e, DDP Assouad's s method [ASZ21]] Let ko ky. be a sequence of natural numbers such that E kg oc, > and 5 E [0, 1]. Given family of distributions P - M where M metric space with metric suppose that there exists set V C. EP of distributions indexed by the product of hypercubes = { such that for a sequence To, "
P C ((X) on a space X, a parameter
Ex, x Ek, x.. where E
hx Xugsut-
V(u u. ... ..........) (, 0t, ...) E Eko Ek, x x,, d(O(pa), 0(p.) 2
Σ Ts
(6)
For each coordinate s E N, j E [.g). consider the mixture distributions obtained by averaging over all distributions with fixed value at the (s.j)tt j)th coordinate:
Σ
Σ
P+(ad) EE Ek, ... W X&y x.maa==11
Pus P-(s5) {Eko Ex, x x...
Pus
uEENo X&E, x-muf==11
and let 2o : :nn + 1-1, +1} be a binary classifier. Then
min max RAn(D) (p) 2 Σ To A DP DEV
1 2
min Pr (Xss(X) 11+ X~pp (a.3)
Pr (0s & -1))
Das is (P X
where the min on the LHS over all O) mechanisms, and on the right hand side over all (e. 8)D binary classifiers. Moreover, if for all E N, E [kg,], there exists a coupling (X, Y)
between P*tss)) and p" (5.)) with Hld (X, (X,Y)] s Da, then
KTTa (0.9e 10D,6)
min max (P)(p) ( PEV
2
Proof of Lemma D.8. We will follow the proof of Theorem 3 in [AS721]. Given estimator A.
define a classifier A by projecting on the product of hypercubes so
A² arg
min uE XEE, x-..)
d ((A(X))0(pa))
By the triangle inequality and the definition of A", for any p E V, d( d(O(P.)(())) (p)) - d(A(X), ((244))))((
A(p)) $ (()((())))())))
Therefore, we can restrict to lower bound on the performance of DP classifiers:
1
min max (p) 2 min max mxxxxxpp (d) (II) A is (E.))-DP PEV
2 A is (E PEV
45

---

Also, for any (E, (D. classifier A",
max Rx (11) PEv
2
Σ
Ex (())
[V]
"E(Eng XEn, X
R
Σ
Pr (A (X)) + uz), x M.
j=1 uEE XE
where the first inequality follows from the fact that the max is greater than the average, and the second follows from assumption (6). For each (s,j) pair, we divide Enr En, x ... into two groups;
max Xmpp (x(O(pa)xx))
PEV
2
Σ
Pr (A)()); # #w))+ +
Σ
Pr (A) + u3)) X
1
x x
j=l
"E(Enn XEn x 1ug=+1
uE(ENo Xk4, X ug==11
2
Σ
Σ
Pr (A'(X), + Fuz)
Σ
Pr (A) + ug)
V
Xmp2
Xxpt
ME(EEo Xy4, X.") 11g=41
wE(Ekg XEn X (
T8
Pr X
Pr
(A*(X) -1))
Xmpp
Ts
Pr X-up (oa)
(x,) +1)
Pr X~pp (2.5)
-1)).
Combining with eqn 11 we have the first statement. Next, since for each pair (s, f), there exists coupling (X, Y) between (+(j.) and p-(x.) such that am (X, Y)] S Ds, we can use the DP version of Le Cam's method from [ASZ21] to give for any classifier ds.j.
Pr
(x)
Pr (dng(X) + 1) 2 (0.9 10.9e-10=D. 10=D.
101)8),
X-
X-p"((s)
which implies the final result.
Lemma G.2. Given any pair of distributions P and Q the same domain,
min
Pr (o(X) =) X~Pm
Pr (0(X) -x1) 2 21 ((UI-NL((P,)). X-Q=
where the minimum over all binary classifiers. In particular, if P = Bernoulló(p - a) and Q Bernoulli(p + a) where 0 S a (pp) then
(0(X) = + Pr (6(X) = -1) 2 1/4, X~Pa
min
Pr
x-Q"
where again the minimum is over all binary classifiers.
Proof of Lemma D.12. A standard result in the statistics literature states that for any pair of distri- butions P and Q,
(o(X) = 1) + Pr (6(X) = -D) = 1 -1- (1 (ILVVKLL(P.)) Xmpm
min
Pr
x-Q
46

---

where the minimum is over all binary classifiers. Bernoulli(p+ a) where 0 E a S (p) then
If P Bernoulli(p - a) and Q =
p - a
+ p 21-p-aa) a) - p - a
(L. P) = (p + an
p p-a
1
2a
2a
=
1
+ pp p- In
p - a
1 - + a
20
20
$ <pp+a) a)
(1 p a)
p p-a a
p +
4a
4a
p
1 p O
2
10-a][
p +
$ 4n
where the first inequality holds since In(1 + xx) < for E [-1, and by assumption 2a/(p a), 20x(11 - + a) E [0, 1] and the second follows again because of the constraint on a.
Lemma G.3. For any distribution P. ioloog///
then with probability 3D
Σ E min Pc(x)(1 - Pc(x)), AV Pi(x)(1 Pe(x)) log( (n/g/)/)))
(p))pp)
n
<E(
Lemma D.14 is an immediate corollary of the following lemma. Lemma G.4. For any distribution P, if log(nn/)) then with probability 1 3D
20 6 Bp) S Σ Σ min Pe(x),1- P((x), 4/3 Pc(x) log(n/3)
(1 P((x)) log (n/3)
4
n
(E(Dr] xE(Ne)
Proof of Lemma D.14. We'll consider each level of the tree individually then use a union bound over all the levels to obtain our final bound. Let (n be the empirical distribution without truncation.
The following conditions are sufficient ensure that the bounds hold for a single level e:
(P)) < 7 (n
sup Pe(M)s 3la(n/0)
7
(P)). 7ln(n/3)
sup Pe(v)21- 3lafn/81
n
v.s. Po(u) 3 3lm(1/3)
3 3n(n/33)
((P:),,z) P((v) S min {
3P((v) In(n/3) 3(1 Pa(x)) In(n/3)
We will begin by showing these conditions are sufficient. If Pe(v) (31n(n/8) 1 3 3lm(n/2) then these conditions imply that the empirical density for node v is truncated, and hence the error that that node is either Pe(v) 1 Pv(v) (when Pr(u) 1/2 and Pr(u) 1/2, respectively), as required. If P((v)= E (3n(n/0) 1 3l(nn/8) then either the estimate is not truncated and the error
& min (P()), (v()). as required. Or the estimate is truncated and the error is min (P)()) Pa(k)). Under the above conditions, Pε(v) < 1/2 then truncation will only occur if
less than min
In
3p In (2n2/33) 7 7ln(n/3)
In In
73 ln
7lnnn/B B)
7
7
3 In(nn/3
Pr(v)-
3
p.
71
11
7
71.
11
47

---

in which case Pr(nu)= Σ // ( as required. Similarly, if Pr(v) > 1/2 then truncation
will only occur if Pe(v) v 4V 3(1 3(1- ln(n/3) required.
We will now show that these conditions hold simultaneously with probability at least - 3,3 for all the nodes at level f. If Pr(u)= S en then using the multiplicative form of Chernoff bound,
3 3ln(n/8)) Pr (P)(())())) 2 1 Pr Pr(1Pa) (Pt))i()) 2
3ln(n/3)
-1)
-1) Pe(v))
Pe(v)m
n
3lmfs/81 mp((()
Pe(M)n
A1(61/8)
)lmin/91
mP/(v)
enPe(v)
3ln(n/8)
3ln(n/3)
3lm(n/3)
S Pe(v)m
e
(nPP(v))3la(n//))-
3n(n/33
3 3lm(n/8)
Firstly, since In(n/3)= 2 1, Tmn(n/A)
e
S 1. Further, nP:(v)= = 1/e and 3ln(n/3) 12
In(n/3) so
I (1/c)in(n/8)
= B/n. Therefore,
Pr (P))n(v) 31m(n/3) < Pr(y)B.
(12)
Let S = f2 [Ne] Pt(x) 1/(en)} then using a union bound and Eqn (12) we have
2/2log(n/3)
Pr fx E S.t. (P))a 2
Pr(v) S PES
n
There exist at most n elements in [Ne] that do not belong in S. We will prove that, independently. each of these elements satisfy the required condition with probability s 23/n then union bound proves the final result. If Pe(v) E [3 (lm((np) , 3lm(n//0] then using the multiplicative form of Chernoff bound (If X, are all i.d.d and 0 << < 1, then Pr( E X; - n 2 5nE[X,]) I 2e- 2c-6'nB n1B[X.1/3).
Pr 2 (x) log(n/3)
3 3log(n/3) Pt(x)n
-Pt())
Pr (z)) Pd(x))
Pr(x))
n
3lon(m/8) Pylemn
Pe(min
< 2e
2,3 n
Next, if Pt(v)= < 3la(n/8) then using the additive form of Chernoff bound (If X; are all i.i.d. and E 2 0, then Pr (1 Σn X
2 + =e ===22(((((tte)))
Pr (P)))()) 7In(n//3) < Pr (P)) 2 (7 In(n/8) p)
n
In(a/ 2
(4 In(a//d) ,
14 In[n/11
$
5 e In(n/0)
3/n.
48

---

log(2/3) By symmetry, if Pr(v) 2 3la(n/8) then
Pr (Pe)ll)) $1- 7ln(n/33
$ 8/n.
Lemma G.5. Let & be the set of active nodes found in Algorithm 1. Then with probability 1 Drolo n + 4,
2
192 log(n/3)))
1)
1 25n
PP
max
+
che CP
EY
En
n
Proof of Lemma D.15. First notice that if node is an a-active node, then all it's ancestor nodes are also a-active. So, it suffices to show that (with high probability) if at any stage a node makes
to it Line of Algorithm 3, then if & Yp (2k) then pv(v) + Lap( + I 2k + log(2/8) and if
[max
2 log(2/8) log(n/B) } then (p(v) Lap( 2. 2x 1og(2/0)
YP
cm
By Lemma 14, with probability -3D all nodes v satisfy
(B(()) - Gp(()] S min (0(0)(1 Gr(p)), 4V
36 p8p(z) 8 (v)) (og(n///))
Further, if one samples X independent samples from Lap( 2 then with probability 1 X
In(2/3)
sup Lapp
So conditioning on both these events if x $ 7P Zen
< pp(v) + In(2/3)
1
In(2/8)
H (v)v + Lap(
<
+
2=n
so they will not survive Line 7 of Algorithm 3. Ifr E 7p
max {
2
log(2/3)
192 log(n/3)
then
en
2 (p(v) 41 Bp(v) log(n/3)
In(2/3)
3p(w) Lap(
En
n
En
log(2/8) en
3 pv)
log(2/3)
Each level has most 2en in 7P 2mm LocateActivellodes since each node has at most children. Therefore, we can set X = 4en DT.
query at most 4en nodes in the tree when running
Lemma G.6. !f mmxx{2 2 + (oo(2//)) 192 192log(n//8) 1) c. fye then
WG krls) 1p kp) + 20 p.. 8p ly (max) 2. +1 (02(2/2) 102tog(n/
49

---

Proof of Lemma D.16. The key component of this proof is that any discrepancy between the weight of the nodes P and that assigned by Gp already paid for in W(P, Gp).
2 Pp (pk))) = Σ Tv/ rr])r(v)
Σ
Ty Or()
" (max +4 (22(2/8))
w0llogm/H11))
Σ
Tv T2/Op(v) - pp(p) + 6p(p)
upre (max +4 (ou(2/9) 102log(n/21
Σ
r2 rz/Bp(u) - 3r(
vēTP (max) in (og(e/n) 1
en
ro rr/Or(v)
" [max +2 lont2/8) 192
I 22 p., Spl,, (max 2. (ogt///))) 102 (ost///))))
as required.
Lemma G.7. For any real-valued function & on the nodes of the HST such that ((v)) = 1 where Vg the root node and given any distribution P.
W(P, Projectiionn B)) < 420 (2 63)
Proof of Lemma D.17. We first note that for any pair of sequences of real values ag and by bb, and constant A such that E, 0; + O,
A a; bul Σ
A
Σ
a. ail
+|a val++la.
1A- -1-- ail aa
Σ by +2 Σ
aa la;-bsl.
Σ
ag
Σ a
Also
"Σ 0; = 0 then
A
Σ, b
Σ, bi |A Σ by +2 Σ
Σ l
1bd = |A Σ 0,++2 Σ
bel
Let Tf be the function @ after only levels 0, have been updated. So σ matches G6-1 on all levels except Let be node in the 9th level the HST. we suppose the sum is over the normalised children of node v, A = (v) and for all the children / of v/ G(v') and (p/)). we can see that the contribution to the Wasserstein distance by the children increases by an additive factor of ( (v)
6 p())). Iterating, we can see that
Dr
Dr
W[P, Projectioonnnoooo (6) 2
Σ (retre+1 -. 6p(v)
E ()))(1)
Em at level
Z= x at level
which is 4 times the wasserstein distance.
H Local Minimality in the High Dimensional Setting
Theorem H.1. Given any E > O, and a distribution P, and ler n'' = 4 min ( 0.455 1,0.6) n, then for all (e, 8)-DP algorithms A', there exists a distribution Q E N(()) such that with probability 1 - (Dr log n + 4Dren)3,
)(
s S0 Q1),
where Qen is the output of PrissDensiityEsttreeeeee with n' samples.
50

---

Proof. First, let us obtain slightly simpler upper bound on W(P, P.). From eqn (9) in the proof of Theorem D.13 have that for each level E.
W(Pe, (P:)a) <
+ ( (6 (6 (c)
from Lemma D.15 we have that with probability - Dr.logn + 45m)
2
log(2/3) 192 log(n/8)
})
PP
max
C TP
EY
En
n
2sn
and if one samples 4e independent samples from Lap( E then we have that with probability
- 4g
sup Lapp -
ln(2/3)
en
en
Therefore, for all v & 9/8 we have Pa(P)= S max some constant C' therefore,
+ log(2/
1og(n/0)
C
In(333) for cm
In(2/8)
()(())). (6pl)))) ( 20 (GP())))) (6 P.. ) E((u +
Σ
En
ME9.
In(n/3)
ln(2/3)
Σ
Po(v)
Σ
NEYP Ao
ME
Σ
Pe(u)
Cln(n/3)
en
VETP Zen
For the same reason as in the proof of Theorem D.13, we can upper bound Everp (he ( 1) 2 by dealing with the hyp (2mn) case separately. Therefore,
Tem En by
Pc),P.)
2C (n(n3)))
Emin min { (p(v)(L-0p(1n)) /
Σ
-
Gp(v) + (TPP
2en - 1)
1
M zmm
Further, by Theorem D.7 and Theorem D.6, given 0 and 8 E 10, 1], let K =
10en min(W 8 0.6} where ((x) is the Lambert W function so W()ee = x. Given a distribution P. there exists constant C" such that
C" Σ min { (p(v)(1-0pl)) Dr
8p(v) (1p((())) Σ wgTp(2k)
RNm (P)
Gp(v) + (hyp (2x) 1)
n
Let Q E (PP), then 7P (1) C IQQ
Yp Ten so
So(v) + (17
1
Σ BQ(v)+ +
Σ
Bo(v) + (170
1)
2en
2
" VETP ( xt
DETP at (79
Σ
28 28p(v)+ +
Σ
+ (110
1)
1
en
2en
en
VÆTP
vE sn Nire )mm)
Σ
25 25 (hr
1)
4en
En
VÆTP 3mm
51

---

Now, let n'
5 mmn (2(22.)))) 2 so for all Q E (P)),
W(Q.Qew) Qen)
Σ min (0(()((-8o(v))) (Q([)(1 (Q(())
Σ
Bolv) + (1r
1)
1
2En
en
u470 Ten
Σ 2mn 6r(v)(1-Brlp) (r(v)(1-Gr((u) Gr(())
S
Σ
28.(v) + (hrp
1)
n
4En'
en!
(p(v)(1- -p(p))
Σ 2in (p(U)(1-6(()))
28p(v) (hp (2k) 11)
en
(2K)
2 min max Q'EN(P)
A x (M(A(()))
As in Proposition B.5, since (PP) is compact, for all A', there exists a specific Q N(() such that
W(Q",0 S (( (0Exx(1)))
I Differentially Private Quantiles
Estimating appropriately chosen quantiles is the main part of our algorithm for approximating the distribution over R in Wasserstein distance, and so in this section, we describe some known differ- entially private algorithms for this task and derive some corollaries that use extensively in application. We will use to represent CDF functions, with Ep representing the CDF of distribu- tion P. We start by stating important theorem private CDF estimation. This follows from use of the binary tree mechanism [CS$11, DNPRI0) A version of this theorem for approximate differential privacy is described in survey by Kamath and Ullman [KU20, Theorem 4. The ver- sion presented here for pure differential privacy follows from a very similar argument, except using Laplace Noise instead of Gaussian noise (and basic composition instead of advanced composition to analyze privacy). Their accuracy was also in expectation, but a similar analysis yields a high probability bound, in the theorem below.
Theorem L.I [KU20, Theorem 4.1]
5, E (0, 1], let D be an ordered, finite domain, and let x E D be a dataset. Let Pa be the uniform distribution on Then, there exists an E-DP algorithm ACDF that on input and the domain D outputs vector G over D such that with probability at least 1 - 3 over the randomness of ADDF
log
3
[D]
||G F2 0
CDF estimation is intimately related to quantile estimation, and use the following quantitative statement that will follow from a simple application of Theorem L.l.
Theorem 1.2. Fix any n. O 8 E (0, 1). a, E R. and < b E TR. such that b-a is an integer. Let C be sufficiently large constant. Then, there exists an e-DP algorithm Aquants that on input interval end points a, b, granularity 7, x = (II,,.., E {a, + .....,b b..,bbb.3..... 7,, and desired quantile values a (0, 1)*. outputs quantiles q {a, a + 7...., 7, b) such that with probubility at least 1 B over the randomness of Aquant. for all r E [k]]
?.
log
b-a
ar FFp, (..)) SC
By
EN
52

---

and
log" b-a By
Pr ()) < or C
gr.P.
En
where Pn is the uniform distribution on the entries of x.
Proof. Algorithm Aquant operates by running the algorithm ACDF referenced in Theorem I.1 on and domain {a, r,...,b Y, b), and postprocessing its outputs get quantile estimates as follows. For every quantile or that we are asked to estimate, Aquant simply scans the vector G output by algorithm ACDF in order, and outputs the first domain element whose CDF estimate in G' crosses a,, Conditioned the accuracy of the CDF estimation algorithm G, we have that this output zr satisfies
b-a log
a, ---Fp. (7+) I
ET Additionally, since q. is the first domain element whose estimate in G crosses we also have that
log
3 b-a
Pr pr (y <.) < a, C
BY
Hence, with probability at least we have this property for all [k].
We now state a corollary this theorem that we will use extensively in our presentation.
Corollary 1.3. Fix any E, 3 E (0, 1}, a, R, and y < b - a E R such that b-a is an integer. Let
is an integer greater than or equal to 1, 40z (og"((5n)) such that k set to 4cglog Rime log
n MEN
cm
where 02 and C3 are sufficiently large constants.
Then, there exists an E E-DP algorithu Aquant (the same one referenced in Theorem 1.2), that on input interval end points a, b, granularity 7,, X (I1, (.1 Fn. {a, (a,a+7,-- 7.-...b b 7; b, and desired
quantile values = (1/2k, 3/2k, 5/2k. (2k - 1) 1)/2k), outputs quantiles q E {a, a toraat%%.... 7,...
y, bjkk such that with probability at least 3. for r [k]]
- : S q. q 9 +
where Pa is the uniform distribution the entries of x and for all p E (0, 1), On is the p-quantile of P..
2 Sogg FT
1 Proof. First, note that is set such that 46
Hence, by Theorem I.2, we have that with probability at least 0.99, for all r [k:].
2r -1
1
Fp. (g-) <
2k
41:
and
2r
Pr (y < (r)
2k 4k
Condition the event above for the rest of the proof. Note that the first equation implies that for all E [k).
2r
1
(y S qr)
P
2k
4k
which implies that q. 2 92
"I is set to be sufficiently small order to relate the accuracy of the quantiles algorithm to a parameter depending on k., and n is set sufficiently large that & is not less than 1. The dependence on 3 comes in the proof of Claim 1818.
53

---

Next, note that we also have that for all E [ks]
2r - 1
Pr (v < x-) yr
2k
4k
This implies that for all r E [k]. dr S Q20-1 #
J Proofs in Section E
J.1 Omitted Proofs in Section E.1.1
Proof of Lemma E.6. We evaluate the various terms in Theorem E.5.
ma max(fr(t) ef fo O)dt, fR max(fo(t) e {fp(1), }. Consider the first term in the outer maximum. For all E ((P)))1/k) we have that ft) fr((). For all other one see that the value of the integrand is 0. Hence, the value of the first term [L(P) max(fr(() - [t), 0)dt = max - R 0} N 2F Now, consider the second term in the outer maximum. For all f < - +, the value of the integrand is O. For all 1 S S q1 the value of the integrand is max (3 e (t) Hence, the second term is max{ (2 - e²) 03 S 2
We start by evaluating T(P.Q)
Put together. we get that =(P. - 26
When > 2, we have that 1 - + I 0, and so we have that the largest value of e' E [0, that makes Js mmx((f((t) e ft((), 0)dt = T(P, Q) = 0, is E' = E. When E < 1n we have that the value of e' that makes Sa max(SQ(()= - of (e()),0dl = max e' = (²
e t. = - i is
Finally, describe the distributions P' and Q' and compute the squared Hellinger distance between them. There are two cases, based on the range of E. First, consider E 2 2n First, we calculate P = minfe=Q, Q, PJ. This value is equal to min(e= /2. ()((() = ff(() for < q (P), and is also equal to ft(t) for to S t S 91- Similarly, consider
minfe P. P,Q}
P Q}:
it is equal to fe(t) for < (P), and is equal to fr(t) for d S t S - - also equal to min(e {t)p(t)= (t) for 9 S 91- Since rPP.Q) Q) 0, and by the above calculations, have that P' P. and Q' = Q. Upper bounding the squared Hellinger distance between p' and Q' by the TV distance (See Lemma A.7), get that H (2' (P'))') ( (P. Q) < TV Q) = 2k S
2
2(In 2)z (where we have used that E 2 ln)).
Next, consider e < 1n2. First, consider P minfe /2, ())()(( eº fr(() for t q (P), and also equal to fr(t) for q I t S qi- Similarly, consider Q = min(e" P,Q] min 1+e ", it is equal (t) for (P), and is equal to fr(() at tb t S 4 It is also equal to min lte - ft(((())) at 91- S LtS S 91- Note that T(P,Q) = -1 ) Pr and Q' are the distributions created by normalizing P and Q by dividing by factor of Q). Now, we upper bound the squared Hellinger distance between f' and Q' by the TV distance (See Lemma A.7), to get that HP' ("))"")) < (V', Q') = =()).
U, This value is equal to
2 fr(()
Substituting into the lower bound for sample complexity of distinguishing P and Q, this tells that for all & 10, (P.((.()))) 22 (+2 2(k/s))
Proof of Lemma E.7. Note that P has bounded expectation (and hence, so does Q). Hence, use the following form of the Wasserstein distance:
W(P.Q) = Fr((t) - (ttt)
54

---

Now, given the settings of P and Q. we can precisely write the forms of their cumulative distribution
function as follows. Note that for L(P) S < 91 we have that [F) Fo(()) = (t))
For 91/k I S 91 a we have [Fr(t) - Fo(t) 1. Finally, for - S t S a. we have that
2k
Fr(() = 1 1 + I ft(t)dt and (t(t) = -1- 24 +
3 Jet 1/4 fr(t)dt, which gives us that
1/4
Fr(t) (t(() 24
1
ft(t)dt 2 -Fr(t)).
2
Hence, we have that
/
Q(P.Q)
1 (F((()-FQ(()uu
- (o)li
1 ( Fp(t)dt+ + f |FP(t) (o(t))dt+
I[" [Fp(t) (o(t) 91
2 ((P)
41/K
1 (u/
99
1
Fp(t)dt +
[1- [P(((dd]
-
(91 97p)
2
((PP)
2 -1
2k
1 g9
Fp(() -Frlag -
(1)ldt= +
1 farz
Fp(t) FPla 1
1 (1)ddt+ + (1- 97)) 2k
2 4
L(P)
1
(11 (1/k)) + 1 ww(P, Play Plap,PPa
2k
J.2 Omitted proof's in Section E.1.2
Proof of Lemma 10 The KL divergence is defined as Seso log This can be broken up into a sum over the dyadic quantiles as:
log n-1
fp(t), dt + To(()
11/2
fP(t) dt Ta(t)
KL(P,Q) =
Σ
fp(t) log
fp(t) log
1=2
91y2i
1/21
91/21-1
fr(() dl +
1/21
fr(() [o(1]
Σ
(p(1)
(P(1) log
dl
[Q(1)
lng
1//21
91-1/21-11
log n-1
91/22-1
1
1-11/
1
Sp(()log
dl
fr(() log
dl
91/21
1
2
91 11-1/21-1
2
8
91/21-1
1
11-1/22
9
(r(() log
di+
+
fr(1) log
di
1
1
I
i=log
91/21
2
11-1/21-1
log Ans
1
1
log
+ log
log
+ log
2
2
2
1 +
i= log
log n-
1
log
+
O
2
1=2
log
2 2
1
+
0
2 n
n2
log n
12
where the third inequality from last is by the fact that the geometric series E Li=logn n 27
1 converges to
O(L), the second inequality from last from the fact that 2' < 1/2, and log(1 ()((11 - -y) < 2y for
0 y < 1/2.
55

---

Proof of Lemma E. First, we recall the definition of the 1-Wasserstein distance in terms of the cumulative distribution function.
W(P.Q) / [F((t) (t(t)l
JR
Fix any 2 v < logn 1. Observe that by construction, for all E 91/22;91-1/22 and for all t E (11-1/2--..)1111/))) [Fp(t) - Fo(()) 2 1j=i+1 v2n
Iogg=- 1 + و=loo n z. Similarly, fix any
- - oc. Observe that for all t E 91/22199-1122), and for all 191-1/2-1,,)- Q1-1/2)), have that - Wasserstein distance, get that
Sن T Substituting the above bounds in the formula for the
log ngn--
41/2/-1
log n-
8
91-1/26
logn-2
1
86
1
W(P,Q)
Σ
+
dt.
+
dl.
V
2
V22n
2
1=2
91/21
j=log n-
91-1/21-1
j= n-1
/1/22
() 1/2'
1
1
dt
+
dt
2
2)
2
i=
91/2i
j=i-1
91
1/2i-1
j=i+1
Pulling the summation over outside the integral and grouping terms,
log n-2
1ogn-2
91/21-1
1111/2
9./22-1
1
4-1122
1
W(P.Q) 2
dt +
dt
+
dt +
dt
V2nn
v 2
2
2
2
1=2
j=++1
91/22
1/-1/21-1
j=log
91/2'
91-1/21-1
00
00
1//21-1 1
91 1-12/2
dt +
2) dt
25
i= log n f=i+1
11/2i
1/21
log n-2
logn-2
1
[(11/251 - /11/2)) + (1) 91 91-1/2 1/2
V2n
2
2
j=i
jimlog
1
[191/2-1- 91/2.) + (q1-1/2- - 91-1/21-
Σ
2
2
mmlog n-
jmit1
Switching the order of summation (summing over j first), and grouping terms, we get
log n-2
W(P.Q)
[0//2-1 91/2 + (41-1/2" -1-1122-1)]
2
1=2
[(1//2 91/26 + (91-1/25 - 1122 1)]
2
27
j=log T1
1=2
Telescoping the inner sums over we get that
n-g
W(P,Q)
2 11111/2011 -1122-1
1
Σ
1
1 91122-11
2j
change of variables (where we now set j to j - then gives
log n
W(P.Q)
1
9 - -91/2i]
Σ
Q1-1/22 91/2
2
22n
j=logn-2 n-2
log
1
1
8
11-1/22 - 91/25|
+
9Q1-1/23 9//21
4
2nn
4
1=2
j=logn
56

---

where the last inequality is by pulling the first two terms from the summation in second term to the summation in the first term, and using the fact that for log 2. log 1, we have that
4:27 2/2 v2
Proof of Lemma 1. We first state a theorem of Bobkov and Ledoux [BI.19].
Theorem J.1 (Theorem 3.5, [BL19]). There is an absolute constant 0, such that for all distri- butions P over R. for every n 2 1,
AAn + B,) < E[W(P, S An + Ba-
where
An = 2
and
1 Bn Vn. FOO- VF(IL--(ON F())JL.
Now, we are ready to prove the main theorem. Fix natural number 2 2. Restricted to S 41/2. (p(()(1 PP(()) is increasing function, and hence for / E [41/21, (1//2/91//--1) we have that Fr(()(1 Fr(()) - ]-r].
Similarly, restricted to > 41/2, F is a decreasing function, and hence for t [1 - 91/2-1, (1-/2=) we have that (1())(1- - = -
Using this, we can now upper bound the expected Wasserstein distance between P and its empirical distribution using Theorem J.1. Hence, we upper bound the terms Bn and A,- We start by upper bounding BR. Note that for all & 9 11.91-1 | we have that Fp(()(1 Fr(t)) i. Hence,
B, = Vn /
- Fp(t)]dt
FP())(I- ((M))(I-F((M)) 2
+ /Fr(t)[1 Fp(t))ct
log 4m
91/21
1-122 1/28
Fp(t)[1 - dp(t)
FP((t[ - (p(t)]
91/22
41 1/21-1
log 4n
11/2111
1
0 -/2
dt
dt
Vn
2i-1
2
2
2
J4z 1/2
2=
log An
1
1
[91/21-1 41/2 + 91 1/2" 91 111-112-11
2
2--1
1=2
log An
2
11-1 - [1/2
2'n
1=2
logn-1
log Anz
2
2
[9
11/2//2
91/20]
2 [11-1/2
4//2-]
2'n
2
i=logn
log n-1
log 1n
2
4
1112//2
41/2-]
2 111-1/2
41/22]
2'n
2
where the last inequality is because for i log(4n), have that - 1.
Next, we bound A,- Note that for all 2 41/2n and for all S 91 + we have that Fp(()(1 1. Ft(t)) & in Hence,
57

---

An 2
Fr(t)[ Fr(()]dt
PP(())1PP(())s
2 Fr([)] Fr(E)]dt + |
2 2
Fr(1)11 dr(())dt
41
91/21
1/21/2
2
Fr(t)[1
Fr(E)]dt +
Fr(t)(1 Fr(t)]dt
i= 1=1+log22 2n
91/21
11-1/21
00
91/21-1
91-1/26
1
1 2
dt
dt
2i-1
2
2
+log 2m
91/21
91
-1/1121-1
191/20-1 - 91,22 + 91-1/22 - -1-11/2-1]
21-1
2'-1
1=++og 2n
91
1/21 - 91/2-]
2
Am 11 2n
Then, using the upper bound in Theorem J.1, substituting in the bounds for An and B, and simpli- fying, we get the claim.
Proof of Claim E.13. By the definition of Wasserstein distance and restrictions of distributions, we have that
W(Pnlag.sn- 9 Plg
Plag.
21
/ FPulo 4
(0) 10-FPlogg 1- (8) (0)at dt
19-1
Frullgios
(t) - Frluy 1 (t) dt
91 à (t) -Fr(F))())))))))))))) di W(P, P()
J.3 Omitted Proofs in Section E.2
Before going into the proofs, we state the standard Chernoff concentration bound that we will use multiple times.
Theorem J.2 (Binomial Concentration). Let X Bin(n, p) with expectation = np, and O < Then, 5 <
Pr([X 11 2 6n) S 2e
Proof of Lemma 1.
J. [FP(t) Fppr
WDP)
(13)
/ [Fp(1) (por(()dd +
91/k
(1- [Fp(1) Fpor + l"
[Fr(() - Fpor (1)
(14)
Note that for all f E [q1/k: Ø1 1//b,, we have that the cumulative distribution functions of P and its restricted version are identical and likewise for pDP, Additionally, the cumulative density functions
58

---

for the restricted versions of the two distributions are identical to each other outside of this interval. Hence, we can simplify the middle term in the RHS of the inequality above follows:
(P)
FF(() - (ppe(())dt W(( ley 91 la 9h
PDP
t=
Next, we reason about the remaining terms,
Consider the term 1 [Fp(t) Pop (t)ldt, First, condition on the event in Theorem 1.3 (on the accuracy of the private quantiles for the empirical distribution), which tells us that with probability at least 1 - 3, we have for all r E [k], that
a 1 i S 12 S Qag +
(15)
which implies in particular that Q1/4K S 91/2k S 93/4k.
Next, argue that 01/4k 2 91/88 with high probability. By the definition of quantiles, have that Py (1/88) SE The number of entries in the dataset less than 91/8k is hence Binomial with mean less than SE and hence, we have by Theorem J.2 (with 8 set to 0.9) that with probability at least 1 3, the number of entries in the dataset less than /1/8k is at most 1.9 n < a 8k 4k*
which means the total mass less than 9 9% in the empirical distribution is less than 1 ak"
This implies
that /1/4 /4k 2 91/8k by the definition of quantiles.
Additionally, note that for all < 91/k- Fp(t) < ..- The number of entries in the dataset that are less than 91/k is hence a Binomial with success probability less than }. By Theorem J.2, we can again argue that with probability at least 3, there is constant è' such that the total mass of the empirical distribution on values less than 4ı/k is less than E. Hence, 91/k I Ge/k- This implies by Equation 15, that q1/2 S Look for some constant c. Hence, for all t < 4i/k, we have that FpDr (t) S E.
Hence, taking a union bound, with probability at least 1 - 0(8),
21/k
41/2k
91/k
[FP(1) - Fpor (1)lde
[Fr(1) - Fpor (1)ldt +
[Fp(t) - Ppno (1)]dt
41/2k
11/22
|Fp(t) Fr 41 t
(t)ldt +
191/2
|Fp(t) c
ldt
t=a
/1//2
|Fp(F) - FPlag
(1)ldt +
(Fp(t) - 8cFp(1)
tma
p01/2z
91/6
< (1 8c)
|Fr(t)
FPlu 9 (f)ldt +
|Fr(t)|dt
tt=a
41/84
< (1 8c)
[Fr(t)
Fri - (f)ldt+
[Fr(t) Friug - (f))dt
t=a
4//0
2(1 - 8c) Play. 9
By a symmetric argument, we also have that with probability at least - -(3).
FF((t) - Fpor (t)ldt 2(1 (e)
1/k
Taking a union bound to ensure that all terms in Equation 14 are bounded as required, the proof is complete.
Proof of Lemma E. First, we condition on the event in Corollary I.3 (on the accuracy of differ- entially private quantile estimates) that for all E [Rc].
S q. < g -
24
59

---

note that this event happens with probability at least 1 - 3 over the randomness of the algorithm.
Observe that this implies that Fop increases by & somewhere in the range [ d -- (for all r E [k) and remains constant outside these intervals.
Now, we show that for all / [a, we have that |Fpp (1) Fr, (1) S E
If there exists [a, 9 have that Fp (t) O, and Fp. (t) S
1 which implies that
(fr(()) - Pp, (+) - iк: If there exists no such i, then we have that a = - and the corresponding interval collapses to single point (which will fall in another interval considered below).
Next, fix any [k 1]. Note that if there exists t [@ t that r-1 v (t)
92 - we have for all such This implies that for all such [t)p(t) Fp. (4) E. If there exists no such t, then we have that 9 * 9 + and this r not relevant since the corresponding interval collapses to a single point (that considered in another interval).
and 2r-1 2 4k
1
S Fp. (t) S 2r+1
1.
2k
4k.
Finally, for E I b], we have that Foo (t) 2 1 E. and Fp. (t) 2 1 [FD((t) Fp. (1) S E-
1 we have that 2
Note that every E (a, b] is considered in some interval above and hence we have shown that for all i E [a, bj. we have that [F (o) - Pp, (4) Aik
Finally, using the formula for Wasserstein distance (and the definition of a restriction), we have that
W(Pn WP
PDP 4 1pm0- 1 )===))=
F Fulloi 1
(t) EyDeleg
(t) dt
(16)
lo
[Fp(t) -Fpor (t)r dt
(17)
41
1 2 dl k
(18)
< k (11 11111/k 91,kk
(19)
Before the proof of Claim E.18, state the following variance-dependen version of the DKW inequality that uniformly bounds the absolute difference in CDFs between the true and empirical distribution.
Theorem J.3 (See for example Theorem 1.2 in [BM23]). Fix n > There are absolute constants co, C1 such that for all A
Cn log
Pr
sup
Pr(()
Fp, (1) 2 VA F(O(1 - F(I)
< 26 2c
5: FF -F
We also state the following lemma Binomial random variables, which is simple consequence of Lemma by Bobkov and Ledoux [BL19].
Lemma J.4 (Lemma 3.8 in [BL19]). Let S, = Σt
-ー th be the sum of n independent Bernoulli p (for all i). Also assume
random variables with Pr[m: = 1] = p and Pr(m = 0] =
p E 1- 11. Then, for some sufficiently small constant
c/nppg E[S., mpl] < /npg
Proof of Claim 1818. Now, by the formula for Wasserstein distance, the definition of restriction, and Fubini's theorem, we have that
EP q 4-
P. Palg 11----1444 ---
E
Fr(t) Fp, (t)
Fr(t) Fp, (t) (t)l
60

---

By Lemma J.4, using the fact that Fy. (t) Ei=1 1x2 S f). where each term in the sum is an independent Bernoulli random variable with expectation (t),), with ot S t - (ensuring that
Fp F which the conditions of the lemma are met), we get that EE [F((t) Fp, (t) cv gives
1-- ]
Fr(()(1 - Fr(t)] dt
(M 4. 2²= Palog
#
41
Now, consider the random variable W(Pl lag - Pula # 9 ). Note that 1 2 0g log 3 (for an appropriately chosen c3), and so we are the regime where we can apply Theorem J.3 for an appropriately chosen A.
In particular, have that for 1 lag 91- (t(() E 1
cin we have that A 2 ep large ca). In particular, this implies for E [ 41 +) 1 (p(() (t)()) 2 A, as long
Setting
log 3
log log and S J (the second inequality for sufficiently 2k
12
FF(() E [2A,1 - 24), which implies that e4 log 3 for some sufficiently large constant c4.
Now, using Theorem J.3, we have that with probability at least 2e 21 0(3,
log n 3
Fr(1) - Pp, (1) S
sup Aelo 4 -
cin
Condition this for the rest of the proof. Then, write the following set of equations.
W(P 44 -1 1 Pulog 11
Fp((t - Fp. (t)
t4
91
log Fp(1(11 - FF(())d
Fp(t)(1 - FF(())) di
cs log 3 41
<
n cs log EP 3
l 9 Pala 14. )
as required.
J.4 Local Minimality the One-Dimensional Setting
In this subsection, argue that the instance-optimal algorithm discussed in Section E.2 is also locally-minimal (See Appendix B.2 for discussion local minimality).
First, we state a corollary of our upper bound for continuous distributions. Theorem E.14. This corollary follows by discretizing the distribution and applying the previous upper bound the dis- cretized distribution. The parameters of the discretized distribution are related to that of the original distribution via simple coupling arguments.
Corollary J.S. Fix E B E (0, 1]. a, b. R. E N. Let P be any continuous distribution supported b-n
for log'
on (a, b). Consider any 7 < b a E R (such that r divides b a), and let n. > C2 some sufficiently large constant c2. Then, there exists algorithm, that when given inputs x pm
61

---

privacy parameter E, interval end points b, gramularity ",. and access to algorithm Aquant, outputs a distribution pDr such that with probability at least 1 - (3) over the randomness of x and the algorithm.
=o(VlognE - (WPPog a Polog Palogm- -
1 ] Pla., (41-1/k (1/ke) +7
W(P, PDP)
where
Pn is the uniform distribution on x, go represents the a-quantile of distribution P, and where C3 is a sufficiently large constant.
k
Log log"
log
We state a lemma of Ledoux and Bobkov that we will use in the main proof of this section.
Lemma J.6 (Lemma 3.8 [BL.1]). Let Sn = Σi= th be the sum of n. independent Bernoulli random variables with Prim: 1] p and Pr[m = 0 = 1-p (for all i). Then, for some sufficiently small constant
emin(2npq, mpg S S, npl S minf2npg, vnpq)
Now, we are ready to state and prove the local minimality result. Note that the statement will reference the rates defined by Equation in the introduction.
Theorem J.7. a, R. y E R. For any continuous distribution over (a, b) with a density, let N(P) (Q (P,QQ 2o. Fix 3, (0,1), and let n Ω log" with
n' cr log n log Lan for some constant ct. There exists algorithm A such that for all continuous distributions P, for all algorithms A', there exists a distribution Q E (N)) such that
RA, S O(polylogn) max R (Q), (x +
for sufficiently large constant c4- Then, by Corollary J.5 with appropriately chosen have that with probability least 0.95, for any distribution Q (and hence particularly any distribution Q e N(P).
Proof. Let
and set n'
2n ca log
4cg log By log %
5e log 2 zn
W(Q.A(Qn) = o o en (41- 2 (Q) - 2 (2))
(11-22
- + W(Q Ql
Cen (2) (Q))
Ccn
)1
+ v log nl
w
(Q)
(Q): Qmlg 2 (2),
2 (2)
+ 7,
Cen!
Gen
where C' is the constant referenced in Theorem E.3. We will show that for distribution P, each of the corresponding distribution-dependder terms is closely related to the terms for Q.
First, consider 1 19---2 (Q) q_ (2)) Firstly, note that for all la/2 Q), and go (P) (Q), since (P, Q) 2, which implies that FF((() Fp(() < (t) for all t R. Similarly, note that for all (0,1), (P)a(P) > -1-2a (Q), and Φ 41-(PP) (P) S a (Q).. Hence, we have that
c.n (Q)
(0,1), (a()) >
en'
en! 91- cen (Q) - Cenl (2))
1
1
(P) - Cen' (P)
en' 91- cen'
62

---

Next, consider W(P. Plg -.. (P) (p)). Recall that 9cc (P) S 9ce (Q),
and 91 cen
(P) 2
n (Q). Then, (noting that L(P) L(Q) and 91 (P) = 21 (Q)), we have that
(
99)1)
W(Q (4)44 2
(Q)) =
Folt)dt+ +
11 - Fo
Can
can
nQ))
(
Cen
(Q)
(()
2
Cen'
Fp(t)dt +2
[1 Ep(()]dt
((Q)
(Q)
"9 o'n
(P)
(P))
< 2
Fr(t)dt+ +2
Fr(())dt
L(P)
(P)
2W(P, Plg
(M)g -e (P))
Finally, consider Vlog and applying both inequalities in Lemma J.6, we have that
E
[(Pl,
(P): Pulg
(P))
By Fubini's theorem
com (p) ozm
con (pr
00m
E
2 (Q), Qnly
cen 10) 2 (2))
2 Can
(0)9
(Q)
Cin
(() Fq. (f)]]
(P)
Fl) - -FQ. (t)l)ct
91
(P)
Fe((]] dt.
min 2Fo(1) FQ(1)), V
n
Gen (P)
Fp(t)[1 - Fp(t)]
min
8FP(t)(1 2
dt.
n
91
(P)
FP(t)[1 Fp(t)]
Cen
min
8FP(()[1- -FD(0),
(nd]
Cpn
(P)
< C5
den
E
Fr(() - FM (t)l
Dow (P), Pmu 2d (py oin (m)
= E W(P), (P) (py
where es is sufficiently large constant and the fourth inequality holds since [n|] n.
By the above observations connecting the distribution for P. we have that for all Q, with probability least 0.95,
iistrbuttin-ddepndeen dependent terms with the corresponding terms
(P) ( En (n-
W(Q,
a (P)) W(P, Ple Oen
(P) - (P))
W 1P(Pl
(p) (P )) +y
Vlog niE
( (P) (P):1--1 (P): P
(P)
Cen can
oiny
1
O(log m)
( V1-oston (P) g (P) WWPPPP
cal ( col (P))
TTn'l
(20)
cstin (m) )1 -7
E W
Pl
catan (P), 1p)7l1n7l (P)g
(P).
Vlg n
catin
catin
63

---

Now, we proceed with the analysis in two cases. Firstl, consider the case when the first and third terms inside the bracket on the RHS of equation 20 larger than the second term inside the bracket. Then, we have that for all Q, with probability at least 0.95,
A(Q,) Ollog n)
(11-antor (P) Cstnup (P))
W (Ple cclNn (P) लपंर (P), Pln cctor (P). करोग (P) )]
-
Vlog
By Theorem E.3 and the fact that nt' < n, for all algorithms A', there exists a distribution Q NN) such that,
(91- (P)
(P))
Czlnn
(P
लলोग (P) )
E. W
(Pl
(P).1 Jelno (P): Plnel
Vlogn
Deln't
Gelu
(P)a
Hence, for all algorithms A' and the corresponding distribution Q, with probability at least 0.95,
A(Q.A((A)) O(log RA [n']) +
Next, consider the case where the first and third terms inside the bracket on the RHS of equation 20 are smaller than the second term inside the bracket. Then, we have that for all Q, with probability least 0.95,
A(Q.A(Q,)) = O(log WPP, लाक
(P) लयाि (P)) + +.
By Theorem E.3, for all algorithms A', there exists a distribution Q ((P) such that
Ro Ln = Ω (W(P.Pl, G (P) ب. (m))
Hence, we have that for all algorithms A' and for the corresponding distribution Q, with probability least 0.95,
W(Q, A(Qm) Ollogn) [r//4]) + +,
as required. This completes the proof.
64

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [TODOJThe abstract and introduction clearly explain the main claims of the paper, the informal theorems provided in 'Our Results' section of the introduction make these explicit.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [TODO]We explain where our bounds are suboptimal, for example in the case of high dimensional distributions over Rd, we explain how our bounds improve over previous work but still involve significant overhead. As we indicate in both our theorem statements and the discussion the introduction, we achieve instance optimality upto poly- logarithmic factors, and getting rid of these is an open question we leave for future work.)
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex, system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
65

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: [TODO]The informal theorems provided in the introduction give simplified versions of our main results (and explain the high level techniques used to obtain them). In the supplementary material, discuss these results in more generality and give complete proofs of these results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: [TODO]Expprimeni]] contributions they have been extensively addressed in previous work, as discussed in the introduction and related work sections. For the experiment do, give detailed description of the distribution used, the methods we compare to and appropriate parameters (along with citations)- the experiment can be reproduced with this information.
main focus of this work since
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
66

---

(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. the case of glosed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: [TODO]Our experiment is not main contribution of our work (we are fo- cused on theoretical bounds) and simply shows how different instance optimal and worst- case bounds can be. We provide the distribution
precisely, which corresponds to the exact data we use. We also explain the method and hyperparameters we use, but don't 't re- lease the code- however, the complete descriptions of the algorithms are publicly available in previous work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https: pottts://nips.com
Policy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips wttpcccppbb... cc/publici / w/wpides////eeeeeeeeeeecccc.ee Seeiides/oodSSuuie (CodeSubmisss www.ummmiiiiioiii.iiie.iiiiiiiis sssinnolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ye]]
Justification: [TODO]As described in the experiment details section in the appendix, give all the details necessary to understand the experiment and its results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
67

---

7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
Justification: [TODO] The experiment is not the focus of our paper (rather, we are focused on theoretical analysis) and is just used to demonstrate one drawback of worst case bounds (which we also discuss theoretically) hence, we don't I comment on statistical significance in detail.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetrie error bars that would yield results that are out of range (e.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: [TODO]We do not explicitly address this since the experiment can be per- formed on essentially any laptop since is simple (both time and memory efficient) and does not require any significant compute.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt////eeripppeeee httpubiice/ciiceccddeeeeeeee
Answer: [Yes]
Justification: [TODO] have reviewed the code of ethics in detail- both societal impact guidelines and impact-mitigation measures and are confident that our paper conforms to the code of ethics in every respect.
68

---

Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: [TODO]Our paper is motivated by theoretically explaining the performance differentially private algorithms. As touched upon in the introduction, differential pri- vacy is important because estimation is frequently done on sensitive data and so developing methods to better understand the privacy-utility tradeoff is societally valuable. We don't t anticipate any negative societal effects from this work.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
69

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Ys]]
Justification: [TODO]In the experiment conducted, we cite the subroutine we use in an- other paper, as well as the method from another paper we compare to. We however imple- ment them ourselves and so official licenses are not needed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswi thcode cwm/daaacaaooocooo ddtassets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
70

---

Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, cura- Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects. and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Answer: [NA]
Justification: (TODO)
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
71


Reviews:
[{"review_id": "GxpiRLHxL4", "reviewer": "Reviewer_WXt4", "summary": "The paper studies distribution estimation under Wasserstein distance while requiring the estimator to be differentially private and \"instance-optimal,\" i.e., being competitive against the algorithm optimal on a distribution neighborhood. The derived class of estimators can achieve comparable performance up to polylogarithmic factors and is extendable to other HST (hierarchically separated tree) metric spaces. Besides the theoretical advancement, the primary conceptual contribution is the new formulation of instance optimality in distribution estimation.", "questions": "Please see the comments in the \"weaknesses\" section. I appreciate the authors' time and efforts.", "limitations": "The authors discussed and compared their results, which seems sufficient given the page limit. Negative societal impact is not applicable here.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors put significant effort into motivating the problem and their \"instant-optimal\" formulation. Relevant sections are well-written and present detailed comparisons to some of the prior results and works. \n- The estimators are constructed concretely rather than shown to exist. Their guarantees extend from 1-D and 2-D Rea to HST metric spaces while maintaining privacy. \n- Construction of distribution nets and using Assoud's Lemma may be of independent interest in establishing the lower bounds in other settings where (local) distribution geometry matters.", "weaknesses": "- It seems that the reference (optimal) estimator evaluates its performance on both the actual underlying distribution and the worst possible distribution, which differs from the actual by a constant factor of 2 in the distribution density ratio. This formulation significantly weakens the power of the reference distribution since, intuitively, it has to produce something in between that could largely deviate from the actual underlying distribution.\n- The poly-log multiplicative factors in the upper bounds do not seem optimal. It would be better if the authors could provide some lower bounds to justify this dependence.\n- The formulation is much weaker than some prior works in the discrete distribution setting. For example, OS15 shows that their estimator is comparable to all \"natural estimators\" on each distribution instance, where the best natural estimator essentially knows the actual distribution (without permutation) and only has to output the same probability estimator for symbols that appear the same number of times (a natural requirement).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address their questions below.\n\n**“It seems the reference…distribution.”:**\n\na) In Wasserstein estimation (unlike TV estimation, for example), it is important to accurately estimate the support of the distribution- putting even a very small amount of mass far away from the support could result in large error. Our notion of neighborhood ensures that the distributions we consider have to have the same support as the original distribution. The infinity divergence is stronger than this, and approximately captures the concentration properties of the distribution- regions with large density will continue to have significant density, and regions with very small density will continue to have small density. Hence, comparing to algorithms with knowledge of such a neighborhood is indeed a strong guarantee for Wasserstein distance- since it captures whether the algorithm can adapt to the sparsity and concentration of the distribution without knowledge of it. In particular, we believe that our notion of neighborhood is natural when considering points with a metric structure.\n\nb) We note that the constant $2$ that we choose (to bound the infinity divergence in our neighborhood definition) can be replaced by any constant (strictly) between $1$ and $2$ with appropriate adjustments of the constants in the lower bound- we chose $2$ since we believe it captures the essence of the arguments and makes the presentation cleaner.\n\nc) Our fundamental goal in defining our notion of instance optimality is to ensure that the target estimation rate (defined by the lower bound) adapts as much as possible to easy instances of the problem. In our instance optimality notion, this is achieved if all the distributions within the neighborhood of a distribution P are (up to constants) as hard to estimate as P. Our specific definition of neighborhood is based on the intuition that the concentration and sparsity of a distribution are what controls its ease of estimation in the Wasserstein distance. This is backed up by the fact that our rates are controlled by these parameters. This is an indication that indeed all distributions within the neighborhood of P are approximately as hard to estimate as P.\n\nd) In the one dimensional setting, we note that the notion of instance optimality is even stronger- we not only give the algorithm a multiplicative approximation of the density, but also tell it that the distribution is one of two distributions $P$ or $Q$ (where $Q$s density is within a multiplicative factor of $P$). \n\n**“The formulation is much weaker….(a natural requirement).”:**\n\nWe believe that a good definition of instance optimality depends on the context and for the problem of discrete distribution estimation, indeed the work of OS15 presents two compelling definitions. However, the definition based on permutations is inappropriate when the domain has a metric structure on it, e.g. the unit line. Here knowing the distribution up to a permutation can allow for a very large Wasserstein radius, and an algorithm that knows the support can be significantly better. Indeed in Fig. 1, we give an example of such a distribution, where our benchmark is a lot smaller than the permutation neighborhood benchmark. Additionally, for the definition based on natural algorithms, when the distribution is continuous, “counts” as used in the definition of natural algorithms are meaningless as all counts will be 0 or 1, and hence this corresponds to competing with a mixture of the empirical distribution and uniform distribution- a very strong restriction on the algorithms we compare to. Additionally, such a notion of instance optimality is unachievable under the constraint of differential privacy (even for discrete distributions).  Thus the notion of instance optimality must be chosen carefully, based on the kind of domain knowledge we imagine an expert designing a custom algorithm for an application may have. In the case of Wasserstein estimation, we believe that a strong but realistic benchmark is an algorithm that knows roughly where the mass is concentrated, i.e. a multiplicative approximation to the pdf of the distribution. Our algorithm competes with the best such algorithm, on every distribution, even without knowing anything about the distribution a priori.\n\n**“The poly-log multiplicative factors in the upper bounds do not seem optimal. It would be better if the authors could provide some lower bounds to justify this dependence.”**\n\nIt is possible that these logarithmic factors could be tightened, but we suspect this would require new techniques. In particular, in the 2-dimensional setting, a log factor arises from the metric distortion in the HST where the distortion factor is tight. Even with the polylog factors, our instance-specific differentially private upper bound is significantly lower than the worst case bounds studied in prior work (which become vacuous when the dimension is $\\log n$ or larger).", "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": "", "extra_scores": {}}, {"review_id": "Al0fuEF2Ca", "reviewer": "Reviewer_8M6K", "summary": "The paper focuses on estimating densities while preserving privacy (differential privacy). Preserving privacy comes with trade-offs in terms of accuracy of their estimates, which is measured using the Wasserstein distance in this paper. One of the main conceptual contribution is introducing a notion of instance optimality for this problem. The authors motivate the choice by comparing the notion against some alternatives from related literature. \n\nTheir new definition of instance optimality is similar to the hypothesis testing problem where one has to look at a sequence of samples and decide whether they come from distribution X or Y. Here, instance optimality is defined as the performance of an algorithm that a priori knows that the samples are either from X or Y, and once it successfully determines which, it can return the density. For some real algorithm to be instance optimal, it has to match the performance of this algorithm without the prior knowledge, unto a constant slowdown.  There are some further nuances to the definition that make the definition robust to trivial edge cases.\n\nThe paper then considers (DP) estimation with respect to Wasserstein error, which is a well motivated problem in ML. The paper shows improved algorithms for private estimation, that beat the previous baselines wrt to the special case of Discrete distributions and TV metric. \n\nOne other technical insight is in a tighter analysis of existing HST algorithms which are a surprisingly good fit for the problem when considered over R^2.", "questions": "--", "limitations": "--", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "--", "weaknesses": "Minor Typos — \n(250) follow\n\nPerhaps not the main focus of the paper, but it would be nice to have all the constants. It encourages implementation, and also constants seem to make or break practical DP algorithms. And further since algorithms are inspired from practical HST algorithms, aren't a some of the source constants already available?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for their review.\n\n**“Perhaps not the main focus of the paper, but it would be nice to have all the constants.”**\n\nWe agree that constant factors are very important for practical implementations. From the implementation point of view, the constant factors relating algorithm parameters to privacy parameters are important to ensure the correct privacy guarantee is achieved. We have made sure that all constants related to the privacy guarantees are explicit. The constants in the utility bound are left implicit in our work as they are not needed to correctly implement the private algorithms. Our theoretical analysis can likely be tightened and thus we don't expect the constant factors will be useful for practitioners. We further note that the quantile algorithms used in the one-dimensional setting have been used successfully in practice, so we expect this algorithm to be practical. Similarly, as the reviewer notes, there exist practical HST algorithms, so we also expect the algorithms in the 2-dimensional setting to be practical.", "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": "", "extra_scores": {}}, {"review_id": "w1uHBw6Qsg", "reviewer": "Reviewer_FtyV", "summary": "This paper looks at the problem of private instance optimal density estimation in wasserstein distance. The starting point of their research is the recent result that shows that the minimax rate of  eps differentially private density estimation in wasserstein distance scales as (eps*n)^{-1/d}. Therefore, the authors take an instance optimal approach, where given samples from an unknown distribution P the algorithm wishes to achieve a cost of at most alpha times the maximum cost of any other algorithm’s cost in a neighborhood around P, that knows neighborhood. For defining the neighborhood, they consider the class of distributions that are close to P in D infinity distance. Coming up with this notion of instance optimality is claimed to be the main contribution of the paper. They authors provide tight upper and lower bounds for such an instance optimal private density estimation guarantee. The upper bounds mostly use the existing techniques from prior work.\n\nThe first result shows that when P is one dimensional and its sample space is [0,1], they can achieve an polygon-factor approximate cost as compared to an algorithm that knows that the unknown distribution is either P or Q, for some distribution Q that exists. Question to the authors, do they mean for every Q or there exists such a Q? If the later is the case, the theorem sounds weak to me.\n\nSimilarly, for two dimensional distributions over [0,1]^2, they could get a (log n)^{O(1)} approximation (how is it different from polylog n?) as compared to an algorithm that knows the distribution is ln 2 close to P in D infinity distance.", "questions": "None.", "limitations": "None.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Overall, while I believe the notion of instance optimality introduced has some merit.", "weaknesses": "I did not find any theorems that justifies that their polylog n factors are tight or not. I would like to believe the approximation factors are quite pessimistic. Moreover, the results do not apply beyond two dimensions. The choice n’=n/polylog(n) also seems ad-hoc.\n\nI found the results derived in this paper are quite weak for a venue like NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for their review. \n\n**“they can achieve an polylog-factor approximate cost as compared to an algorithm that knows that the unknown distribution is either P or Q, for some distribution Q that exists. Question to the authors, do they mean for every Q or there exists such a Q? If the latter is the case, the theorem sounds weak to me.”** \n\nPlease allow us to clarify the definition of instance optimality we use in the one-dimensional setting. As explained in Section B.1, our notion of instance optimality in the one-dimensional setting builds on one suggested by Donoho and Liu in terms of the ‘hardest one-dimensional subproblem’- where the distribution Q to compare to is chosen to be close to P, making the bounds instance specific. Below, we provide additional intuition on this definition and the choice of Q. If Q is chosen so that P and Q are distinguishable (there exists a hypothesis test that can with high probability distinguish samples from P from samples from Q) then the algorithm that is told that the unknown distribution is either P or Q has 0 error (whp) on both P or Q. Thus, we can not hope to be competitive with such an algorithm. If P and Q are indistinguishable  (there does not exist a hypothesis test that can with high probability distinguish samples from P from samples from Q) then there can not exist an estimation algorithm whose error on both P and Q is less than half the distance from P to Q since such an estimation algorithm would induce a hypothesis test. Thus, the only distributions Q such that we can hope to be competitive (on both P and Q) with the estimation rate of an algorithm that is told the unknown distribution is P or Q are distributions Q that lie on the boundary of indistinguishability for P and Q. In fact, the only Q for which we have such a hope are those which are furthest from P on this boundary. Thus, achieving this for any Q is indeed a strong notion of optimality. In this work, we actually study a stronger notion of instance optimality that essentially amounts to not only comparing to an algorithm that is told that the unknown distribution is P or Q, but is also told the support of P.\n\n**“I did not find any theorems that justifies that their polylog n factors are tight or not.”**\n\n Our upper and lower bounds are tight up to polylog n factors. It is possible that these factors can be tightened, although we suspect this would require new techniques. In particular, in the 2-dimensional setting, a log factor arises from the metric distortion in the HST where the distortion factor is tight. Even with the polylog n factors, our instance specific upper bound is significantly lower that the worst case bound studied in prior work. \n\n**“Moreover, the results do not apply beyond two dimensions.”**\n\n Our results apply for any metric space by building a HST approximation to that metric space and leveraging our result for general HSTs. This induces a factor of $\\log|X|$ gap in the upper and lower bounds resulting from the distortion factor in the HST approximation. We focus on the 2-dimensional case since this factor is small in this case and this setting captures many interesting realistic scenarios (e.g. population densities). Our algorithm works equally well in other low-dimensional metric spaces, as we describe in the introduction. In higher dimensions the gap has a linear dependence on the dimension. While we agree the result is less useful in high dimensions, we note that it gives better bounds than the worst case results  for Wasserstein learning that have rates that are $n^{O(-1/d)}$ and are thus vacuous already for $d \\approx \\log n$. We also anticipate that in many practical settings, some knowledge of the data distribution (through some public data for example) would allow for the building of better tree embeddings, and then using our algorithm would give better bounds in high dimensions. We leave such an exploration to future work.\n\n**“The choice n’=n/polylog(n) also seems ad-hoc.”**\n\n Precise formulations of $n’$ are given in Theorem J.7 for the one-dimensional setting and Theorem H.1 for the HST setting. In both settings, we give precise formulations of the upper and lower bounds in terms of n. In order to compare these bounds, we need to compare the upper bound to a lower bound with slightly fewer samples.", "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": "", "extra_scores": {}}, {"review_id": "2i8AZBwjEU", "reviewer": "Reviewer_e9RQ", "summary": "The paper addresses the problem of differentially private density estimation using the Wasserstein distance. It approaches this problem in a non-parametric manner, meaning it does not assume any specific distribution. Instead of focusing on worst-case error guarantees, the authors aim to design algorithms that achieve instance-optimal error. In other words, the algorithms provide the best possible error within a small \"neighborhood\" around any given input.\n\nThe authors explore various definitions of \"neighborhood\" in the context of instance optimality for distribution estimation in both $\\mathbb{R}$ and $\\mathbb{R}^2$. They present algorithms that achieve performance close to the instance-optimal ones, up to multiplicative polylogarithmic factors. Furthermore, the algorithm for $\\mathbb{R}^2$ is extended to arbitrary metric spaces, though this generalization results in an extra polylogarithmic factor in the performance guarantee.", "questions": "In Theorem 2.3, the established error includes a multiplicative factor of $\\log |X|$, where $|X|$ represents the size of the metric space. I would like to confirm that if $X$ is a finite $m$-dimensional space, this implies that the error scales with $m$, which can be relatively large.\n\nI did not read the appendices.", "limitations": "Same as ''Questions\"", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Instance optimal algorithms can achieve significantly better performance on specific inputs. Designing such algorithms and proving their instance optimality is nontrivial.\n\n2. The paper introduces a notion of instance optimality for the problem. An instance optimal algorithm under this notion is quite strong, as its performance is competitive with an algorithm that knows a constant multiplicative approximation of the distribution density (such approximation has a small absolute error on points with low density values).\n\n3. The writing is excellent. The problem is well-motivated, and the paper is carefully structured and easy to follow.", "weaknesses": "The multiplicative factors in the instance optimality guarantee can be large.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you to the reviewer for their review. \n\n**“In Theorem 2.3, the established error includes a multiplicative factor of log|X|, where |X| represents the size of the metric space. I would like to confirm that if X  is a finite m -dimensional space, this implies that the error scales with m, which can be relatively large.”**\n\nThis is correct, in dimension $m$, the gap between our upper and lower bounds scales with a multiplicative factor of $m$ making the results less useful in high dimensions. We note however that \n\n(a) There is a large class of applications where the dimension is naturally small, for example, building a population heatmap.\n\n (b) While we have a linear dependence on the dimension, we note that our bounds are significantly better than worst case bounds for Wasserstein learning which have rates that are $n^{O(-1/d)}$ and are thus vacuous already for $d \\approx \\log n$. \n\n(c) In settings where data lies on a lower-dimensional manifold that we have some access to, we anticipate that this dependence can be improved to the dimensionality of the manifold, rather than the ambient dimension (by building a better HST embedding). This may happen, for e.g., when we are learning a distribution of embeddings of images, and we can sample from the manifold of all possible images (using a generative model) to build the HST embedding. We leave a formal exploration of this to future work.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of learning potentially arbitrary distributions with respect to the Wasserstein distance under differential privacy constraints. The authors define a natural notion of instance-optimality in this setting and develop a nearly-instance-optimal learning algorithm (within poly-logarithmic factors). While there was a divergence of scores, after reading the reviews and subsequent discussion, my understanding is that this work is technically and conceptually novel, and clearly meets the acceptance bar at NeurIPS.
Decision: Accept (poster)