Private Selection from Public Candidates with Wasserstein Guarantees

Let $({\cal X},d)$ be a metric data space. Given a sensitive dataset $D$ and a public candidate set $C$ of size $k$, we study how to approximately minimize the $1$-Wasserstein distance to the empirical distribution of $D$ over all size-$m$ multisets supported on $C$ under $\varepsilon$-differential privacy. A natural solution to this private selection problem is the exponential mechanism that assigns score $-W_{1,d}(\mu_D,\mu_{C'})$ to a multiset $C'$, where $\mu_A$ is the empirical distribution of dataset $A$. However, its output space contains $\binom{k+m-1}{m}$ multisets, making direct sampling computationally infeasible. We address this challenge by approximating the metric $d$ on $C$ with a randomized tree metric $d_T$ of controlled expected distortion. Under this representation, candidates correspond to the leaves of a weighted tree, and $d_T$ is the shortest-path metric between them. Wasserstein distance between measures supported on the candidates now admits a hierarchical decomposition across subtrees. This decomposition yields a dynamic program that samples exactly from the corresponding exponential mechanism with score defined by the 1-Wasserstein distance with respect to the new metric $d_T$. The resulting mechanism runs in polynomial time, satisfies $\varepsilon$-differential privacy, and approximates the nonprivate solution (in terms of objective value) up to the expected tree distortion and an additive privacy penalty which scales logarithmically with $k$. Synthetic experiments identify regimes in which our mechanism outperforms noisy histogram baselines, whose error scales polynomially with $k$ in the worst case.