Private Mean Estimation of Heavy-Tailed Distributions

Gautam Kamath; Vikrant Singhal; Jonathan Ullman

Private Mean Estimation of Heavy-Tailed Distributions

Gautam Kamath, Vikrant Singhal, Jonathan Ullman

Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2204-2235, 2020.

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.

Cite this Paper

BibTeX


@InProceedings{pmlr-v125-kamath20a,
  title = 	 {Private Mean Estimation of Heavy-Tailed Distributions},
  author =       {Kamath, Gautam and Singhal, Vikrant and Ullman, Jonathan},
  booktitle = 	 {Proceedings of Thirty Third Conference on Learning Theory},
  pages = 	 {2204--2235},
  year = 	 {2020},
  editor = 	 {Abernethy, Jacob and Agarwal, Shivani},
  volume = 	 {125},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {09--12 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v125/kamath20a/kamath20a.pdf},
  url = 	 {https://proceedings.mlr.press/v125/kamath20a.html},
  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.}
}

Endnote

%0 Conference Paper
%T Private Mean Estimation of Heavy-Tailed Distributions
%A Gautam Kamath
%A Vikrant Singhal
%A Jonathan Ullman
%B Proceedings of Thirty Third Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2020
%E Jacob Abernethy
%E Shivani Agarwal	
%F pmlr-v125-kamath20a
%I PMLR
%P 2204--2235
%U https://proceedings.mlr.press/v125/kamath20a.html
%V 125
%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\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.

APA


Kamath, G., Singhal, V. & Ullman, J.. (2020). Private Mean Estimation of Heavy-Tailed Distributions. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2204-2235 Available from https://proceedings.mlr.press/v125/kamath20a.html.

Related Material

Download PDF