acceptodds
Under review as a conference paper at ICLR 2027

Private Selection from Public Candidates with Wasserstein Guarantees

Abstract

Given a sensitive dataset and a public candidate set of size belonging to a metric space , we study how to select a size multiset supported on that approximately minimizes the -Wasserstein distance between its empirical distribution and that of , under -differential privacy. Existing approaches typically rely on nearest-neighbor histograms over , treating candidates essentially as unrelated bins and ignoring the geometry induced by , despite its central role in -Wasserstein distance. At the same time, the number of possible size- multisets grows combinatorially, making generic exact approaches computationally prohibitive. We therefore develop efficient geometry-aware algorithms. The main insight is to approximate the distance on by a randomized tree metric with controlled expected distortion. This tree metric is induced by a weighted tree whose leaves correspond to the candidates in . The distance between two candidates is their shortest-path distance in , while the tree levels define increasingly fine partitions of , from all candidates at the root to singletons at the leaves. Under , -Wasserstein distance decomposes hierarchically across the tree, enabling two efficient -differentially private algorithms based on dynamic programming. The first exactly samples a size- multiset from the exponential mechanism with score given by its negative empirical -Wasserstein distance to under , while the second privately estimates hierarchical subtree masses and post-process them into a compatible size- multiset. The two mechanisms have similar worst-case utility guarantees, but our experiments characterize three distinct regimes where Tree-EM, hierarchical tree projection, and the nearest-neighbor baseline each outperform the others, demonstrating that our methods are complementary and present substantial gains whenever the target distribution has geometric structure that can be exploited.

Primary area:
learning theory
Keywords:
Differential privacy, synthetic data, private selection, tree metrics, exponential mechanism

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_92oYOpenReview ↗
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 DD in a metric space (X,d)(X,d) with a marked (public) subset C⊂XC\subset X, and the goal is to privately generate a multiset aa supported on CC that minimizes the Wasserstein distance between DD and aa.

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 dTd_T on CC (which requires no private information). From prior work there exists a way to do this such that the tree TT has as leaves the points of CC, and as internal nodes subsets of CC, with the entire set CC 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 log⁡∣C∣\log |C| factor of the original distance in (X,d)(X,d). 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 tt records down the tree to help determine what the dataset should be.

This paper has two main theoretical contributions:

  1. A proof of privacy, accuracy and efficiency for the exponential mechanism based construction described above (tree-EM).
  2. 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
  1. 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.

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

  3. 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
  1. Can you please expand upon any points of novelty which you feel I missed?
  2. 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

Thanks for your feedback. We address your comments below.

Theoretical novelty seems limited

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-kk 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\mathcal A_m 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 η\eta, giving an (L+1)η(L+1)\eta-DP guarantee. We instead optimize the allocation across levels according to their contribution to the error bound, with budgets summing to ε\varepsilon and no additional LL factor in the accuracy bound. This matters because raw FRT depth LL 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ℓ}\min\{2m,K_\ell\} largest (absolute) Laplacian noises at every level ℓ\ell. 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.

More experiments should be carried out, and with real world datasets

We have extended the first experiment to real datasets. Our tree methods outperform all the baselines as kk 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\epsilon = 1, \delta = 10^{-5}. Some details:

  • Sensitive dataset: 5,000 fixed test images (500 per class).
  • Public candidates: pools of training images (k/10 from each class), disjoint from the sensitive data.
  • Embeddings: 64-dimensional LeNet features for MNIST (trained on public candidates); 2,048-dimensional InceptionV3 pretrained on ImageNet features for CIFAR-10.

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

kTree-EMTree-projectionBest histogram errorBest histogram variant
5003.568 ± 0.0233.553 ± 0.0283.913 ± 0.026Gaussian / L1 / round
1,0003.567 ± 0.0273.547 ± 0.0283.929 ± 0.049Laplace / L1 / round
2,0003.677 ± 0.0433.654 ± 0.0234.141 ± 0.046Laplace / L1 / round
5,0003.682 ± 0.0323.666 ± 0.0214.210 ± 0.064Laplace / L1 / sample
10,0003.709 ± 0.0323.706 ± 0.0204.214 ± 0.054Gaussian / L1 / sample
20,0003.721 ± 0.0333.757 ± 0.0374.306 ± 0.037Laplace / L1 / round

Our methods achieve lower mean error at every reported pool size, and the difference generally grows with kk.

CIFAR-10

kTree-EMTree-projectionBest histogram errorBest histogram variant
50050.040 ± 0.02850.031 ± 0.02050.042 ± 0.026Gaussian / L2 / round
1,00049.887 ± 0.06549.856 ± 0.03349.703 ± 0.034Laplace / L1 / round
2,00050.263 ± 0.07750.282 ± 0.09049.994 ± 0.074Laplace / L1 / round
5,00050.687 ± 0.09751.045 ± 0.22350.795 ± 0.123Laplace / L2 / round
10,00051.859 ± 0.08752.332 ± 0.20453.162 ± 0.122Laplace / L1 / round
20,00052.470 ± 0.19153.270 ± 0.41554.652 ± 0.209Laplace / L1 / sample

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.

Lower bound

We now have a lower bound that uses the fixed output size property. For 0<ε≤10<\varepsilon\le1, nε≥8mn\varepsilon\ge8m, 2≤k≤ec0d2\le k\le e^{c_0d}, and any Δ>0\Delta>0, we can construct a public candidate set C⊂RdC\subset\mathbb R^d of size kk and diameter Δ\Delta such that every pure ε\varepsilon-DP mechanism M returning a size-mm multiset of candidates has some input D∈CnD\in C^n for which E[W1(μD,qM(D))]≥OPT⁡d,m(D)+c1Δmin⁡{m,k}nε,\mathbb{E} [W_1(\mu_D,q_{M(D)})] \ge \operatorname{OPT}_{d,m}(D) +c_1\frac{\Delta\min\{m,k\}}{n\varepsilon}, where c0,c1>0c_0,c_1>0 are universal constants, and the expectation is over the mechanism’s randomness.

The construction uses Θ(min⁡{m,k})\Theta(\min\{m,k\}) disjoint pairs of candidates in a nearly equidistant candidate set. Since output masses must be multiples of 1/m1/m, we place the nearest-neighbor histogram masses just above and below the midpoints b/m+1/(2m)b/m + 1/(2m), where the integers bb 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 mm points. The idea now is that moving Θ(1/(nε))\Theta(1/(n\varepsilon)) mass within a pair reverses which candidate should receive the extra copy, while changing only Θ(1/ε)\Theta(1/\varepsilon) records. Group privacy prevents the algorithm from reliably distinguishing these cases, forcing an (expected) excess TV error of Ω(1/(nε))\Omega(1/(n\varepsilon)) per pair. Summing the mistakes gives Ω(min⁡{m,k}/(nε))\Omega(\min\{m,k\}/(n\varepsilon)) 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 O(log⁡k)OPT⁡d,m(D)O(\log k)\operatorname{OPT}_{d,m}(D) instead of OPT⁡d,m(D)\operatorname{OPT}_{d,m}(D). We will include this lower bound in the paper.

Regarding the multiplicative factor O(log⁡k)O(\log k): 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 log⁡k\log k approximation.

We would like to follow up with the reviewer to see whether our response above has addressed their concerns.

Reviewer_qNREOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the following problem: Let (X,d)(X,d) be a metric space. Given a (sensitive) dataset D=(x1,…,xn)∈XnD = (x_1,\ldots,x_n) \in X^n and a public set of candidates C=c1,…,ck⊂XC = \\{c_1,\ldots,c_k\\} \subset X, the goal is to privately choose an mm-size multiset S∈CmS \in C^m such that the 11-Wasserstein distance (w.r.t. the distance measure dd) between the empirical distribution over DD and the empirical distribution over SS is small as possible. This problem can be solved accurately using the exponential mechanism, but is inefficient in terms of running time. So this paper uses a tree embedding to approximate the distance metric dd on CC by a randomized tree metric dTd_T, and by exploiting the structure of this new metric, the authors are able to perform the exponential mechanism efficiently. The resulting theorems achieve an O(log⁡k)O(\log k) approximation to the optimal fixed-size Wasserstein error, up to some additive error.

This work is closely related to the work of Feldman et al. (2024) who also uses a similar tree structure, but in their paper, they consider the setting where the data elements are i.i.d. from some distribution and the goal is to estimate the distribution, while here, the data is fixed, and the goal is to output new data (from the candidates set) that induces empirical distribution which is close to the empirical distribution on the data under 11-Wasserstein distance.

Critical strengths
  1. The studied problem is interesting, and the formulation and results about estimating the empirical distribution on the data in 11-Wasserstein distance using a fixed mm-size set of candidate seem novel.
  2. The writing quality is good.
Critical weaknesses
  1. My main concern is the technical novelty of the proposed algorithms. While the problem formulation appears novel and the results are interesting, the main techniques build on existing approaches (e.g., randomized tree embedding), which were already used by Feldman et al. (2024), and maybe also in other works. Although Feldman et al. do not directly solve the fixed-size selection problem studied here, it is not entirely clear to me whether the proposed algorithms constitute a substantial technical contribution beyond a natural adaptation of existing techniques to the new setting. I would appreciate a more detailed discussion of the technical differences and the main new ideas required to obtain Theorems 1 and 2.

  2. The paper, and in particular, the new setting and objective, would have been much stronger if there was a matching or nearly matching lower bound (especially on the additive error) which exploits the fact that the output size is fixed and must be from a given candidate set.

Questions for authors

Could you identify precisely which technical parts in Theorems 1 and 2 are not already available in Feldman et al. (2024), and explain why the they are necessary to your setting?

2 comments

Thanks for you feedback, we address your concerns below.

Identify precisely which technical parts in Theorems 1 and 2 are not already available in Feldman et al. (2024)

We first remark that approximation of metrics by randomized tree metrics and the tree-metric decomposition of W1W_1 are classical tools by now, tracing back at least to Kleinberg and Tardos (1999). The contributions both in Feldman et al. (2024) and our work concern how to leverage this approximation for algorithm design in specific problems of interest. With this in mind, we answer the question:

  • Theorem 1 gives guarantees for Tree-EM. This algorithm is completely different from the one in Feldman et al. (2024): it uses the tree Wasserstein formula to sample efficiently and exactly from the exponential mechanism over size-mm multisets. So we don't use any of the new techniques introduced in their work to prove this theorem.

  • Theorem 2 gives guarantees for the hierarchical histogram with tree projection. This algorithm resembles more Feldman et al. (2024) but there are crucial differences. The differences are both algorithmic and in the analysis:

    (1) Algorithmic differences: while we construct the noisy hierarchical histogram similarly to Feldman et al. (2024), we allocate the privacy budget differently over tree levels and project the resulting noisy histogram onto Am\mathcal A_m using a dynamic program that is not present in their work. Their algorithm uses a common per-level privacy budget η\eta, giving an (L+1)η(L+1)\eta-DP guarantee. We instead optimize the allocation across levels, with budgets summing to ε\varepsilon and no additional LL factor. This matters because raw FRT depth LL 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ℓ}\min\{2m,K_\ell\} largest (absolute) Laplacian noises at every level ℓ\ell. 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 can be found in lines 853 to 936.

Lower bound

We now have a lower bound that uses the fixed output size property. For 0<ε≤10<\varepsilon\le1, nε≥8mn\varepsilon\ge8m, 2≤k≤ec0d2\le k\le e^{c_0d}, and any Δ>0\Delta>0, we can construct a public candidate set C⊂RdC\subset\mathbb R^d of size kk and diameter Δ\Delta such that every pure ε\varepsilon-DP mechanism M returning a size-mm multiset of candidates has some input D∈CnD\in C^n for which E[W1(μD,qM(D))]≥OPT⁡d,m(D)+c1Δmin⁡{m,k}nε,\mathbb{E} [W_1(\mu_D,q_{M(D)})] \ge \operatorname{OPT}_{d,m}(D) +c_1\frac{\Delta\min\{m,k\}}{n\varepsilon}, where c0,c1>0c_0,c_1>0 are universal constants, and the expectation is over the mechanism’s randomness.

The construction uses Θ(min⁡{m,k})\Theta(\min\{m,k\}) disjoint pairs of candidates in a nearly equidistant candidate set. Since output masses must be multiples of 1/m1/m, we place the nearest-neighbor histogram masses just above and below the midpoints b/m+1/(2m)b/m + 1/(2m), where the integers bb 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 mm points. The idea now is that moving Θ(1/(nε))\Theta(1/(n\varepsilon)) mass within a pair reverses which candidate should receive the extra copy, while changing only Θ(1/ε)\Theta(1/\varepsilon) records. Group privacy prevents the algorithm from reliably distinguishing these cases, forcing an (expected) excess TV error of Ω(1/(nε))\Omega(1/(n\varepsilon)) per pair. Summing the mistakes gives Ω(min⁡{m,k}/(nε))\Omega(\min\{m,k\}/(n\varepsilon)) 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 O(log⁡k)OPT⁡d,m(D)O(\log k)\operatorname{OPT}_{d,m}(D) instead of OPT⁡d,m(D)\operatorname{OPT}_{d,m}(D). We will include this lower bound in the paper.

Thank you for the detailed response. The distinctions from Feldman et al. are now clearer, and it is good to know that you expect to provide a lower bound. I still have some reservations about the extent of technical novelty beyond existing works, but I appreciate the clarified contributions. I will maintain my positive score.

Reviewer_9UguOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the following problem: given a private dataset DD and a public dataset CC (over the same metric space), we wish to privately return a multiset supported on CC that has empirical distribution close to DD in W1W_1 (Wasserstein) distance. Such a problem appears in the context of privately generating synthetic data, and the authors argue that naive methods (i.e., just adding Laplacian noise to nearest neighbor counts and then processing) scale poorly with ∣C∣|C| in terms of accuracy as well as largely ignore the underlying metric space.

The paper presents two algorithms that, at a very high-level, make this problem more tractable by approximating the metric with a randomized tree metric (specifically the FRT tree). The first algorithm (called tree-EM) is essentially an exponential mechanism with some suitable modifications that exploit the tree structure in sampling from the EM. The second algorithm tries to privately estimate how "projecting" the elements in DD onto the support of CC would be distributed along every layer of the tree; then, the algorithm solves an optimization problem to try to match these estimates.

Altogether, I think the work is interesting and support acceptance, though this enthusiasm is somewhat dulled by the fact that not only are these methods are not strictly better than current nearest-neighbor routines, but also the regimes that these algorithms perform better in depends on the private data and it is unclear how to pick the best algorithm.

I have skimmed some sections of the appendices and have not checked any mathematical details past those only in the main text. I am not familiar with the literature and cannot sufficiently comment on novelty and positioning with respect to previous work.

Critical strengths
  1. The problem appears to be well-motivated, and I find the first algorithm showing that the exponential mechanism can be sampled from to be quite simple and elegant (and works over an arbitrary metric space).
  2. For the most part, the paper is easy to read and provides nice intuition on the algorithms.
Critical weaknesses
  1. For the purposes that the authors claim to motivate the problem, it seems to me that this algorithm is still computationally difficult for remotely realistic scenarios (although still quadratic). Furthermore, none of the methods presented make a strict accuracy improvement over the baseline, although the authors acknowledge this.
Questions for authors

Questions:

  1. This is not really about the paper per se, but is there any reason why the W1W_1 distance might be appealing or natural to consider for the purpose of synthetic data generation (e.g., are there bounds involving the W1W_1 distance?), or does this more have to do with how the W1W_1 distance is easy to compute in certain cases (as you show in this paper).

Comments:

  1. It was very unclear what was meant in the beginning of section 3.2 to me, particularly the phrase "coarse-scale information... accurately." It may be good to clarify what you mean by votes, since this terminologically wasn't really used before this point.
  2. Lines 370-377: I find this section very terse and hard to read. It seems that we fixing three datasets and running experiments using the NN histograms they induce. I do not quite understand why it makes sense to call these "complementary regimes" when we are just picking some different data distributions to test. Furthermore, in Appendix E, it appears that we call these regimes the "sparse regime," "tree-EM regime", and "tree-projection regime" suddenly?
1 comment

We thank the reviewer for their feedback. We address the concerns below.

This algorithm is still computationally difficult for remotely realistic scenarios

The algorithms that we present are fairly efficient and can easily be run on personal laptops when n,kn,k are in the few thousands and mm is small. That said, we did not focus on fully optimizing the running time. The running time of both algorithms includes terms of order O(kn+k2+km2)O(kn + k^2 + km^2). Some of these costs can be reduced, potentially at the cost of accuracy. For example, the term knkn comes from the nearest-neighbor histogram and is shared with the simple baselines. For large nn, this shared computation can become the main bottleneck, and approximate nearest-neighbor methods can help reduce this cost. Similarly, the term km2km^2 can be reduced to O(kmlog⁡m)O(km\log m) by using FFT in the dynamic program of Tree-EM, as done in previous work. Finally, in Euclidean settings, the tree construction can also be accelerated from k2k^2 to subquadratic, at the cost of more metric distortion. This is an active area of research. So if compute becomes an issue, there are ways to run faster approximate variants of our method. We will add a comment about this in the paper.

None of the methods presented make a strict accuracy improvement over the baseline; the regimes that these algorithms perform better in depends on the private data and it's unclear how to pick the best one.

Our methods perform better than the baselines in many settings, including new experiments on MNIST and CIFAR-10 that we will include. We believe it is valuable to develop algorithms that work particularly well in certain settings. We have also acknowledged limitations: we do not expect our methods to outperform simple baselines always. When there is little useful geometry—for example, when candidates are nearly equidistant and each effectively forms its own cluster—or when most votes go to a few candidates whose counts are easy to estimate directly, baselines can win. We also compare against the best of eight baselines, and the best one changes across experiments, so even choosing the best baseline is unclear in practice. Private selection of the best algorithm or an instance-adaptive algorithms are interesting next steps, but go beyond the scope of this work.

Why W_1?

While the problem could be formulated using any distance between distributions, W1W_1 is a relevant metric. By Kantorovich duality, W1(P,Q)=sup⁡f∈F∣Ex∼Pf(x)−Ex∼Qf(x)∣,W_1(P,Q) = \sup_{f \in F} |E_{x \sim P} f(x) - E_{x \sim Q} f(x)|, where FF is the class of bounded, 1-Lipschitz functions. This means that if the W1W_1 between two datasets is small, then Lipschitz queries are roughly preserved. This is in line with early literature on DP synthetic data, where accuracy was typically measured as a maximum discrepancy over a class of queries. Furthermore, as stated in the related work, much of the recent theory on DP synthetic data has been developed in terms of W1W_1.

It was very unclear what was meant in the beginning of section 3.2 to me, particularly "coarse-scale information... accurately." It may be good to clarify what you mean by votes

We will explain this better. We meant that a sensitive datapoint “votes” for a candidate when that candidate is its nearest neighbor in the candidate set. By coarse-scale information, we mean the total votes received by groups of nearby candidates. For example, suppose there are four clusters of 10 candidates each, and each candidate in one cluster receives one vote while the other clusters receive none. The individual counts are only zero or one and can be overwhelmed by noise, but the cluster-level histogram has counts (10,0,0,0)(10,0,0,0). Estimating these totals can reveal where to allocate our output mass and help us avoid allocating it to low-weight groups. This is the useful coarse-scale information we have in mind: identifying which parts of the candidate space contain the sensitive data, even when individual candidate counts are difficult to estimate accurately.

Lines 370-377: I find this section very terse and hard to readl; I do not quite understand why it makes sense to call these "complementary regimes"; in Appendix E, it appears that we call these regimes the "sparse regime," "tree-EM regime", and "tree-projection regime" suddenly?

We will explain this better as well. We chose three synthetic datasets to showcase the kinds of data each method works well on, keeping the public candidate geometry fixed and changing only the nearest neighbor histogram. We call these regimes complementary because each highlights a different method’s strengths, and a different method achieves the lowest error in each setting. The names of the regimes in Appendix E refer to the regime where each algorithm performs better; we will clarify this.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.