Private Mean Estimation of Heavy-Tailed Distributions
share
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 = Θ(1/α^2 + 1/α^k/k-1ε) samples are necessary and sufficient to estimate the mean to α-accuracy under ε-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 ≥ 2. We also give algorithms for the multivariate setting whose sample complexity is a factor of O(d) larger than the univariate case.
READ FULL TEXT