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 =
\Thetałeft(1\alpha^2 +
1\alpha^kk-1\varepsilon\right)$ samples are necessary and
sufficient to estimate the mean to $\alpha$-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 2$. We also give algorithms for the multivariate setting whose
sample complexity is a factor of $O(d)$ larger than the univariate case.
Description
[2002.09464] Private Mean Estimation of Heavy-Tailed Distributions
%0 Journal Article
%1 kamath2020private
%A Kamath, Gautam
%A Singhal, Vikrant
%A Ullman, Jonathan
%D 2020
%K differential-privacy inequality privacy robustness stats
%T Private Mean Estimation of Heavy-Tailed Distributions
%U http://arxiv.org/abs/2002.09464
%X 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 =
\Thetałeft(1\alpha^2 +
1\alpha^kk-1\varepsilon\right)$ samples are necessary and
sufficient to estimate the mean to $\alpha$-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 2$. We also give algorithms for the multivariate setting whose
sample complexity is a factor of $O(d)$ larger than the univariate case.
@article{kamath2020private,
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 $n =
\Theta\left(\frac{1}{\alpha^2} +
\frac{1}{\alpha^{\frac{k}{k-1}}\varepsilon}\right)$ samples are necessary and
sufficient to estimate the mean to $\alpha$-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.},
added-at = {2020-02-26T14:14:06.000+0100},
author = {Kamath, Gautam and Singhal, Vikrant and Ullman, Jonathan},
biburl = {https://www.bibsonomy.org/bibtex/24d787c75384b647ab57657c92beb0893/kirk86},
description = {[2002.09464] Private Mean Estimation of Heavy-Tailed Distributions},
interhash = {62a16b3d96269c0154f42fd27e4b5174},
intrahash = {4d787c75384b647ab57657c92beb0893},
keywords = {differential-privacy inequality privacy robustness stats},
note = {cite arxiv:2002.09464},
timestamp = {2020-02-26T14:14:06.000+0100},
title = {Private Mean Estimation of Heavy-Tailed Distributions},
url = {http://arxiv.org/abs/2002.09464},
year = 2020
}