Optimal Private Median Estimation under Minimal Distributional Assumptions

Abstract

We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distributions satisfying the minimal assumption that they have a positive density at a small neighborhood around the median. In particular, the distribution is allowed to output unbounded values and is not required to have finite moments. We compute the exact, up-to-constant terms, statistical rate of estimation for the median by providing nearly-tight upper and lower bounds. Furthermore, we design a polynomial-time differentially private algorithm which provably achieves the optimal performance. At a technical level, our results leverage a Lipschitz Extension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined "typical" instances of the samples.

49 pages, NeurIPS 2020, Spotlight talk

References in corpus (7)

• A Survey of Privacy Attacks in Machine Learning
• The Discrete Gaussian for Differential Privacy
• Private Mean Estimation of Heavy-Tailed Distributions
• Locally Private Hypothesis Selection
• Propose, Test, Release: Differentially private estimation with high probability
• Privately Learning Markov Random Fields
• Private Algorithms Can Always Be Extended

Cited by in corpus (3)

• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Differentially Private Quantiles