We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.
翻译:我们提出了第一个 $\varepsilon$-微分隐私, 有效的算法, 可以准确地在总变异距离下估计$\{0,1\}^d$上的乘积分布的平均值, 同时在多项式对数因子内实现了最优样本复杂度. 先前的工作已经在更弱的隐私概念下有效地解决了这个问题, 或者在指数时间下达到了最优结果.