Optimal Private Median Estimation under Minimal Distributional Assumptions
This work addresses a fundamental statistical task for privacy-preserving data analysis, offering a robust solution for distributions with unbounded values and no moment assumptions.
The paper tackles the problem of estimating the median from samples under differential privacy with minimal distributional assumptions, achieving nearly-tight statistical bounds and providing a polynomial-time algorithm that matches these optimal rates.
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.