Differentially Private Medians and Interior Points for Non-Pathological Data
This work addresses the challenge of private statistical estimation for non-pathological data, providing a practical solution for data analysts and privacy researchers.
The paper tackles the problem of constructing differentially private estimators for the median of arbitrary distributions under mild moment conditions, achieving low sample complexity, in contrast to prior negative results that showed no finite sample complexity was possible for arbitrary distributions.
We construct differentially private estimators with low sample complexity that estimate the median of an arbitrary distribution over $\mathbb{R}$ satisfying very mild moment conditions. Our result stands in contrast to the surprising negative result of Bun et al. (FOCS 2015) that showed there is no differentially private estimator with any finite sample complexity that returns any non-trivial approximation to the median of an arbitrary distribution.