Timezone: »

 
Oral
Tight and Robust Private Mean Estimation with Few Users
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari

Wed Jul 20 10:15 AM -- 10:35 AM (PDT) @ Room 309
in SA: Trustworthy Machine Learning »
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 \emph{users} is independent of the dimension (though the number of \emph{samples per user} is allowed to depend polynomially on the dimension), unlike the previous work that requires the number of users to depend polynomially on the dimension. This resolves a problem first proposed by Amin et al. (2019). Moreover, our mechanism is robust against corruptions in up to $49\%$ of the users. Finally, our results also apply to optimal algorithms for privately learning discrete distributions with few users, answering a question of Liu et al. (2020), and a broader range of problems such as stochastic convex optimization and a variant of stochastic gradient descent via a reduction to differentially private mean estimation.
Keywords: PM: Everything Else · T: Learning Theory · T: Probabilistic Methods · SA: Privacy-preserving Statistics and Machine Learning

Author Information

Shyam Narayanan (Massachusetts Institute of Technology)
Vahab Mirrokni (Google Research)
Hossein Esfandiari (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors