论文标题
最佳分配假设下的最佳私人中位数估计
Optimal Private Median Estimation under Minimal Distributional Assumptions
论文作者
论文摘要
我们研究了在纯粹的差异隐私约束下估算有限数量样品中基本分布的中值的基本任务。我们专注于分布，满足最低的假设，即它们在中值周围的一个小社区中具有正密度。特别是，允许分布输出无界值，并且不需要有限的矩。我们通过提供几乎紧密的上限和下限来计算中位数的确切，最新的术语，估计值的统计率。此外，我们设计了一个多项式差异私有算法，可证明可以实现最佳性能。在技术层面上，我们的结果利用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.
