# Instance-Optimal Private Density Estimation in the Wasserstein Distance

arXiv: https://arxiv.org/abs/2406.19566 · HTML: https://mlsanity.com/paper/2406.19566/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2024.

## Built on by (most cited first, 9 of 9)

- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Locally Optimal Private Sampling: Beyond the Global Minimax](https://mlsanity.com/paper/2510.09485/) (2025)
- [Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansion](https://mlsanity.com/paper/2509.19661/) (2025)
- [Privacy-Computation trade-offs in Private Repetition and Metaselection](https://mlsanity.com/paper/2410.19012/) (2024)
- [Instance Dependent Testing of Samplers using Interval Conditioning](https://mlsanity.com/paper/2512.06458/) (2025)
- [Minimax optimal differentially private synthetic data for smooth queries](https://mlsanity.com/paper/2602.01607/) (2026)
- [Differentially Private Sampling from Distributions via Wasserstein Projection](https://mlsanity.com/paper/2605.10015/) (2026)

## Abstract (arXiv)

Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances. For distributions P over ℝ, we consider a strong notion of instance-optimality: an algorithm that uniformly achieves the instance-optimal estimation rate is competitive with an algorithm that is told that the distribution is either P or QP for some distribution QP whose probability density function (pdf) is within a factor of 2 of the pdf of P. For distributions over ℝ2, we use a different notion of instance optimality. We say that an algorithm is instance-optimal if it is competitive with an algorithm that is given a constant-factor multiplicative approximation of the density of the distribution. We characterize the instance-optimal estimation rates in both these settings and show that they are uniformly achievable (up to polylogarithmic factors). Our approach for ℝ2 extends to arbitrary metric spaces as it goes via hierarchically separated trees. As a special case our results lead to instance-optimal private learning in TV distance for discrete distributions.