Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical contexts, the Wasserstein distance is a suitable error metric for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate can roughly capture where the population mass is located. 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 be scaled to simple instances.
For distributions P<annotation encoding="application/x-tex”>PP on R<annotation encoding="application/x-tex”>\mathbb{R}RWe consider a strong notion of instance optimality: an algorithm that uniformly achieves the optimal instance estimation rate is competitive with an algorithm that is told that the distribution is P<annotation encoding="application/x-tex”>PP either QP<annotation encoding="application/x-tex”>Q_PQP for some distribution QP<annotation encoding="application/x-tex”>Q_PQP whose probability density function (pdf) is within a factor of 2 of the pdf of P<annotation encoding="application/x-tex”>PP. For distributions greater than R2<annotation encoding="application/x-tex”>\mathbb{R}^2R2