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