BriefGPT.xyz
Apr, 2023
二元乘积分布的纯差分隐私估算器的多项式时间实现
A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
HTML
PDF
Vikrant Singhal
TL;DR
本研究提出了第一个能够在满足异质性隐私保护的同时，以多项式对数的复杂度准确地估算0、1分布乘积的均值的计算方法。这个方法能够以最优的样本复杂度来达成这个目的，并在总变差距离上实现精准估算。相比之前的工作，本方法能够在更低的保护要求下实现高效算法，同时不失最优性能，且不需要运行时间指数级增长。
Abstract
We present the first $\varepsilon$-differentially private,
computationally efficient
algorithm that estimates the means of
product distributions
over $\{0,1\}^d$ accurately in
→