- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the problem of generating a summary of a private dataset on a public set of candidate points in the data domain. The generation should be differentially private. This problem is well-motivated, and the goal of this line of work is to enable efficient and safe privatization of sensitive information. The idea is that by using publicly available knowledge about the data domain, one can reduce the amount of noise needed to generate a private summary of the data. This can be thought of as a private synthetic data generation problem.
Concretely, the solver is given a dataset in a metric space with a marked (public) subset , and the goal is to privately generate a multiset supported on that minimizes the Wasserstein distance between and .
The approach of this work is to appeal to the FRT construction (Fakcharoenphol, Rao and Talwar, 2003) to first generate a tree structure and metric on (which requires no private information). From prior work there exists a way to do this such that the tree has as leaves the points of , and as internal nodes subsets of , with the entire set as the root. The parent-child relationship encodes belonging. This FRT construction gives a weighted tree such that if we compute the distance between any pair of points through the weighted path in the tree, then the distance is within a factor of the original distance in . Further, the Wasserstein distance (in the tree metric) between two measures can be computed exactly using this FRT tree.
The key idea in this work is that one can run the exponential mechanism efficiently on this large tree to generate the desired privacy summary by using the Wasserstein distance in the tree metric as the score function to score candidate subsets. They use a recursive approach to split a mass of records down the tree to help determine what the dataset should be.
This paper has two main theoretical contributions:
- A proof of privacy, accuracy and efficiency for the exponential mechanism based construction described above (tree-EM).
- A variation of the first result that outputs a hierarchical histogram that also returns cumulative counts at all levels of the tree, not just the leaves (hierarchical tree projection). This is better because generating counts for internal nodes by just using leaf counts would lead to more error.
Critical strengths
This problem is well-motivated. I liked the overall presentation, it was quite clear, and the idea of using the tree based approach for an efficient solution is nice. The FRT tree has been used before for density estimation in Wasserstein distance. The main novel contribution seems to be identifying how to do an exact ExpMech implementation for the FRT tree Wasserstein distance score. The efficiency of the implementation seems to depend upon the fact that the additive score function factorizes nicely, and that one can use dynamic programming to compute the scores efficiently. Both of these ideas exist in prior work, but their combination here is nice.
Critical weaknesses
-
The theoretical novelty seems limited - this paper takes a known approach for a synthetic data generation problem (the FRT tree, as done in Feldman et al, 2024), and solves it with known techniques (structured score functions over large universes, as done in Gillenwater et al, 2021). These works are cited, which is good, but the work does seem a bit incremental.
-
Ideally many more experiments should be carried out, and with real world datasets. All experiments have been conducted with artificial datasets, and there are only two of them. The first experiment which demonstrates good performance of the methods of this paper with increasing candidate size seems promising, but without more datasets and more variation it is not convincing. I think there is some good theoretical content in this paper, but it really needs more experimental corroboration to be a strong submission.
-
There is no discussion of lower bounds. It is not clear whether theoretically the result is good or not - is a \log n approximation reasonable for this problem? Is the additive error close to optimal?
Questions for authors
- Can you please expand upon any points of novelty which you feel I missed?
- Please expand upon how far your theoretical results are from optimality, i.e. any lower bounds you know, or how good or bad the multiplicative approximation term \log n is compared to what is possible.
3 comments
Lower bound
We now have a lower bound that uses the fixed output size property. For , , , and any , we can construct a public candidate set of size and diameter such that every pure -DP mechanism M returning a size- multiset of candidates has some input for which where are universal constants, and the expectation is over the mechanism’s randomness.
The construction uses disjoint pairs of candidates in a nearly equidistant candidate set. Since output masses must be multiples of , we place the nearest-neighbor histogram masses just above and below the midpoints , where the integers are chosen so that rounding one candidate up to (b+1)/m and the other down to b/m in each pair produces an output with exactly points. The idea now is that moving mass within a pair reverses which candidate should receive the extra copy, while changing only records. Group privacy prevents the algorithm from reliably distinguishing these cases, forcing an (expected) excess TV error of per pair. Summing the mistakes gives expected excess TV error. With exactly equidistant candidates, Wasserstein distance is simply a scaled TV distance; our nearly equidistant construction is chosen so that the TV bound can still translate to a valid Wasserstein bound. This additive error matches up to logarithmic factors the additive error in our upper bounds, although our upper bounds contain a term instead of . We will include this lower bound in the paper.
Regarding the multiplicative factor : this distortion is known to be tight in the worst case for embeddings of general metrics into distributions over dominating tree metrics; see Fakcharoenphol, Rao and Talwar. Thus, improving it would require using additional geometric assumptions or going beyond this general tree-embedding guarantee. This does not establish, however, that every selection algorithm needs a approximation.
We would like to follow up with the reviewer to see whether our response above has addressed their concerns.
Thanks for your feedback. We address your comments below.
Novelty in tree-EM: Writing down an exponential mechanism over a large output space is possible for many problems; the challenge is finding a way to sample from it efficiently. The works on quantiles and top-k each develop a sampling scheme tailored to their particular score and output structure. We think identifying and exploiting the structure of tree Wasserstein for private selection of candidates is a meaningful algorithmic contribution, much as finding efficient samplers was a central contribution of those earlier works.
Novelty in tree-projection: similarly to our answer for Reviewer qNRE, we highlight the differences with Feldman et al. (2024) here, which are both algorithmic and analytical.
(1) Algorithmic differences: while we construct the noisy hierarchical histogram similarly to Feldman et al. (2024), we allocate the privacy budget differently and project the noisy histogram onto Am using a dynamic program that is not present in their work, since they are concerned with density estimation over the full set of candidates. Their algorithm uses a common per-level privacy budget η, giving an (L+1)η-DP guarantee. We instead optimize the allocation across levels according to their contribution to the error bound, with budgets summing to ε and no additional L factor in the accuracy bound. This matters because raw FRT depth L depends logarithmically on the ratio between the largest and smallest candidate distances, which can be arbitrarily large.
(2) Differences in the analysis: we leverage the fact that the union of the optimal size-m multiset and the output of our algorithm can include at most 2m candidates. Hence, in the analysis we do not need to deal with the noise added at every node of the tree, but rather we upper bound the error by dealing only with the min{2m,Kℓ} largest (absolute) Laplacian noises at every level ℓ. This is not done in previous work, and this technique is also what allows us to allocate the privacy budget in a nontrivial way to get our final error bound. These two main differences are easy to observe in lines 853 to 936.
We have extended the first experiment to real datasets. Our tree methods outperform all the baselines as k grows. We use MNIST and CIFAR-10 (we work with embeddings of these images). We set n = 5000, k increasing from 500 to 20000, m = 30 and ϵ=1,δ=10−5. Some details:
Results report mean ± SEM over 10 trials on fixed data in terms of W1. “Best histogram” is the lowest-mean variant among the eight histogram mechanisms, selected separately at each k.
MNIST
Our methods achieve lower mean error at every reported pool size, and the difference generally grows with k.
CIFAR-10
Here, histograms are competitive at smaller pool sizes, and both tree methods achieve lower mean error at k = 10,000 and 20,000. Our algorithms are competitive with the best baseline in all of these experiments.