Instance-Optimal Private Density Estimation in the Wasserstein Distance

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

Strengths

1. Instance optimal algorithms can achieve significantly better performance on specific inputs. Designing such algorithms and proving their instance optimality is nontrivial. 2. 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). 3. 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.

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. I did not read the appendices.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Same as ''Questions"

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. The 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. Similarly, 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.

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. I found the results derived in this paper are quite weak for a venue like NeurIPS.

Questions

None.

Rating

3

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

None.

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. Their 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. The 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. One 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.

Strengths

--

Weaknesses

Minor Typos — (250) follow Perhaps 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?

Questions

--

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

--

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.

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

Questions

Please see the comments in the "weaknesses" section. I appreciate the authors' time and efforts.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

The authors discussed and compared their results, which seems sufficient given the page limit. Negative societal impact is not applicable here.

Read the rebuttal

I have read the rebuttal by the authors. I am afraid that the answers do not add much more clarity or new information to my previous assessment regarding the paper. Therefore, I'll maintain my score.