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}^2R2We use a different notion of instance optimality. We say that an algorithm is instance optimal if it is competitive with an algorithm given a constant factor multiplicative approximation of the density of the distribution. We characterize the instance optimal estimation rates in both settings and show that they can be achieved uniformly (up to polylogarithmic factors). Our approach to R2<annotation encoding="application/x-tex”>\mathbb{R}^2R2 It extends to arbitrary metric spaces as it passes through hierarchically disjoint trees. As a special case, our results lead to optimal private learning for each instance in the TV distance for discrete distributions.
