Private Mean Estimation of Heavy-Tailed Distributions
Gautam Kamath Cheriton School of Computer Science, University of Waterloo. Vikrant Singhal Khoury College of Computer Sciences, Northeastern University. Jonathan Ullman Khoury College of Computer Sciences, Northeastern University.
Abstract
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
中文速览
在重尾分布下对均值进行差分隐私（differential privacy, DP）估计时，究竟需要多少样本，此前并无精确答案。本文针对有界 $k$ 阶矩的分布，同时给出了样本复杂度的上界和下界：在一维情形下，完成 $\alpha$ 精度估计所需的最优样本数约为 $\tilde{\Theta}(1/\alpha^2 + 1/(\varepsilon \alpha^{k/(k-1)}))$，而在无隐私约束时，无论 $k$ 取何值（只要 $k \geq 2$），样本复杂度均为 $O(1/\alpha^2)$，两者存在本质差异。算法层面，作者采用"加噪截断经验均值"的思路，通过精细平衡截断偏差与噪声幅度来实现最优；下界则通过假设检验框架建立，并对纯 DP 和近似 DP 均成立。多维情形下也给出了样本复杂度仅比一维多 $O(d)$ 倍的高效算法。这一工作完整刻画了隐私保护与重尾分布矩条件之间的权衡关系，填补了差分隐私均值估计理论的重要空白。
原文 arXiv:2002.09464;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2002.09464v3