论文标题
私人平均估计重尾分配
Private Mean Estimation of Heavy-Tailed Distributions
论文作者
论文摘要
我们对具有限制性$ k $ thoments的分布的差异私有平均值估计的最小值样本复杂性提供了新的上限和下限。粗略地说，在单变量的情况下，我们表明$ n =θ\ left（\ frac {1} {α^2} + \ frac {1} {α^{α^{\ frac {k} {k-1} {k-1}} {k-1}}}} \ varepsilon} \ right）$ coply and coptime unive yatime $ \ varepsilon $ - 不同的隐私或其任何常见放松。与缺乏隐私限制的估计相比，该结果表明了质量不同的行为，对于所有$ k \ geq 2 $，样本复杂性都是相同的。我们还为多元设置提供了算法，其样本复杂性比单变量案例大于$ O（d）$。
We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded $k$-th moments. Roughly speaking, in the univariate case, we show that $n = Θ\left(\frac{1}{α^2} + \frac{1}{α^{\frac{k}{k-1}}\varepsilon}\right)$ samples are necessary and sufficient to estimate the mean to $α$-accuracy under $\varepsilon$-differential privacy, or any of its common relaxations. This result demonstrates a qualitatively different behavior compared to estimation absent privacy constraints, for which the sample complexity is identical for all $k \geq 2$. We also give algorithms for the multivariate setting whose sample complexity is a factor of $O(d)$ larger than the univariate case.
