ICML 2022oral30 citations
Tight and Robust Private Mean Estimation with Few Users
Shyam Narayanan, Vahab Mirrokni, Hossein Esfandiari
Abstract
In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an $(\varepsilon,\delta)$-differentially private mechanism using as few users as possible. In particular, we provide a nearly optimal trade-off between the number of users and the number of samples per user required for private mean estimation, even when the number of users is as low as $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$. Interestingly, this bound on the number of
BibTeX
@InProceedings{pmlr-v162-narayanan22a,
title = {Tight and Robust Private Mean Estimation with Few Users},
author = {Narayanan, Shyam and Mirrokni, Vahab and Esfandiari, Hossein},
booktitle = {Proceedings of the 39th International Conference on Machine Learning},
pages = {16383--16412},
year = {2022},
editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
volume = {162},
series = {Proceedings of Machine Learning Research},
month = {17--23 Jul},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v162/narayanan22a/narayanan22a.pdf},
url = {https://proceedings.mlr.press/v162/narayanan22a.html},
abstract = {In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an $(\varepsilon,\delta)$-differentially private mechanism using as few users as possible. In particular, we provide a nearly optimal trade-off between the number of users and the number of samples per user required for private mean estimation, even when the number of users is as low as $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$. Interestingly, this bound on the number of