Optimal Private Median Estimation under Minimal Distributional Assumptions
Optimal Private Median Estimation under Minimal Distributional Assumptions
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Christos Tzamos;Emmanouil-Vasileios Vlatakis-Gkaragkounis;Ilias Zadik
中科院分区：
文献类型：
--
作者：
Christos Tzamos;Emmanouil-Vasileios Vlatakis-Gkaragkounis;Ilias Zadik
我们研究的基本任务，估计从有限数量的样本的潜在分布的中位数，在纯差分隐私约束。我们专注于满足最小假设的分布，即它们在中位数周围的一个小邻域内具有正密度。特别地，允许分布输出无界值，并且不需要具有有限矩。我们通过提供近乎紧密的上界和下界来计算中位数的精确的、直到常数的统计估计率。此外，我们设计了一个多项式时间的差分隐私算法，可证明达到最佳的性能。在技术层面上，我们的研究结果利用Lipschitz扩展引理，使我们能够设计和分析差分私有算法，仅在适当定义的“典型”样本的情况下。
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.