[Spotlight at NeurIPS 2020] Optimal Private Median Estimation under Minimal Distributional Assumptions

NeurIPS 2020

[Spotlight at NeurIPS 2020] Optimal Private Median Estimation under Minimal Distributional Assumptions

Nov 28, 2020
|
31 views
Details
NeurIPS 2020 Spotlight talk Title: Optimal Private Median Estimation under Minimal Distributional Assumptions Presenter: Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University) Authors: Christos Tzamos (University Winsconsin-Madison), Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University), Ilias Zadik (NYU) 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 LipschitzExtension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined “typical” instances of the samples

Comments
loading...