NeurIPS 2020

Optimal Private Median Estimation under Minimal Distributional Assumptions

Meta Review

This paper addresses a basic problem in privacy-preserving data analysis, namely, the problem of differentially private mean estimation. Under minimal distributional assumptions, the paper provides tight upper and lower bounds on the sample complexity of this problem. Moreover, the constructed algorithm runs in polynomial time. These are strong theoretical results for a fundamental problem of broad interest.