Differentially Private Medians and Interior Points for Non-Pathological Data
Differentially Private Medians and Interior Points for Non-Pathological Data
复制标题
DOI：
10.48550/arxiv.2305.13440
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
M. Aliakbarpour;Rose Silver;T. Steinke;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
M. Aliakbarpour;Rose Silver;T. Steinke;Jonathan Ullman
我们构造了具有低样本复杂度的差分私人估计，估计$\mathbb{R}$上任意分布的中位数，满足非常温和的矩条件。我们的结果与Bun et al.（FOCS 2015）令人惊讶的负面结果形成鲜明对比，该结果表明没有任何有限样本复杂度的差分私有估计器可以返回任意分布中位数的任何非平凡近似值。
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.