Private Selection from Public Candidates with Wasserstein Guarantees

Given a sensitive dataset $D$ and a public candidate set $C$ of size $k$ belonging to a metric space $(\mathcal{X},d)$, we study how to select a size $m$ multiset supported on $C$ that approximately minimizes the $1$-Wasserstein distance between its empirical distribution and that of $D$, under $\epsilon$-differential privacy. Existing approaches typically rely on nearest-neighbor histograms over $C$, treating candidates essentially as unrelated bins and ignoring the geometry induced by $d$, despite its central role in $1$-Wasserstein distance. At the same time, the number of possible size-$m$ multisets $\left(\genfrac{}{}{0ex}{}{k+m-1}{m}\right)$ grows combinatorially, making generic exact approaches computationally prohibitive. We therefore develop efficient geometry-aware algorithms. The main insight is to approximate the distance $d$ on $C$ by a randomized tree metric $d_T$ with controlled expected distortion. This tree metric is induced by a weighted tree $T$ whose leaves correspond to the candidates in $C$. The distance $d_T$ between two candidates is their shortest-path distance in $T$, while the tree levels define increasingly fine partitions of $C$, from all candidates at the root to singletons at the leaves. Under $d_T$, $1$-Wasserstein distance decomposes hierarchically across the tree, enabling two efficient $\epsilon$-differentially private algorithms based on dynamic programming. The first exactly samples a size-$m$ multiset from the exponential mechanism with score given by its negative empirical $1$-Wasserstein distance to $D$ under $d_T$, while the second privately estimates hierarchical subtree masses and post-process them into a compatible size-$m$ 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.