Instance-Optimal Private Density Estimation in the Wasserstein Distance

Thank you to the reviewer for their review.

“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.”

This 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

(a) There is a large class of applications where the dimension is naturally small, for example, building a population heatmap.

(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$.

(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.

Thank you to the reviewer for their review.

“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.”

Please 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.

“I did not find any theorems that justifies that their polylog n factors are tight or not.”

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.

“Moreover, the results do not apply beyond two dimensions.”

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.

“The choice n’=n/polylog(n) also seems ad-hoc.”

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.

Thank you to the reviewer for their review.

“Perhaps not the main focus of the paper, but it would be nice to have all the constants.”

We 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.

We thank the reviewer for their comments and address their questions below.

“It seems the reference…distribution.”:

a) 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.

b) 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.

c) 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.

d) 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$).

“The formulation is much weaker….(a natural requirement).”:

We 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.

“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.”

It 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).