Timezone: »
Oral
Tight and Robust Private Mean Estimation with Few Users
Shyam Narayanan · Vahab Mirrokni · Hossein Esfandiari
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.
Author Information
Shyam Narayanan (Massachusetts Institute of Technology)
Vahab Mirrokni (Google Research)
Hossein Esfandiari (Google Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Poster: Tight and Robust Private Mean Estimation with Few Users »
Wed. Jul 20th through Thu the 21st Room Hall E #909
More from the Same Authors
-
2021 : Label differential privacy via clustering »
Hossein Esfandiari · Vahab Mirrokni · Umar Syed · Sergei Vassilvitskii -
2023 : Tackling Provably Hard Representative Selection viaGraph Neural Networks »
Mehran Kazemi · Anton Tsitsulin · Hossein Esfandiari · Mohammad Hossein Bateni · Deepak Ramachandran · Bryan Perozzi · Vahab Mirrokni -
2023 : k-Means Clustering with Distance-Based Privacy »
Alessandro Epasto · Vahab Mirrokni · Shyam Narayanan · Peilin Zhong -
2023 Poster: Robust and private stochastic linear bandits »
Vasilis Charisopoulos · Hossein Esfandiari · Vahab Mirrokni -
2023 Poster: Data Structures for Density Estimation »
Anders Aamand · Alexandr Andoni · Justin Chen · Piotr Indyk · Shyam Narayanan · Sandeep Silwal -
2022 Poster: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 Spotlight: Massively Parallel $k$-Means Clustering for Perturbation Resilient Instances »
Vincent Cohen-Addad · Vahab Mirrokni · Peilin Zhong -
2022 : Closing Remarks »
Vahab Mirrokni -
2022 : Private Algorithms Q/A »
Peilin Zhong · Alessandro Epasto · Vahab Mirrokni -
2022 : Graph Mining Q/A »
Vahab Mirrokni -
2022 : New Challenges in Graph Mining: Scalability, Stability, and Privacy Applications »
Vahab Mirrokni -
2022 Expo Talk Panel: Challenges Of Applying Graph Neural Networks »
Bryan Perozzi · Vahab Mirrokni -
2022 : Graph Mining at Google »
Vahab Mirrokni -
2021 Poster: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Spotlight: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time »
Laxman Dhulipala · David Eisenstat · Jakub Łącki · Vahab Mirrokni · Jessica Shi -
2021 Poster: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2021 Spotlight: Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering »
Shyam Narayanan · Sandeep Silwal · Piotr Indyk · Or Zamir -
2021 Poster: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Spotlight: Regularized Online Allocation Problems: Fairness and Beyond »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2021 Poster: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2021 Spotlight: Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni · Song Zuo -
2020 Poster: Robust Pricing in Dynamic Mechanism Design »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni -
2020 Poster: Dual Mirror Descent for Online Allocation Problems »
Santiago Balseiro · Haihao Lu · Vahab Mirrokni -
2020 Poster: Bandits with Adversarial Scaling »
Thodoris Lykouris · Vahab Mirrokni · Renato Leme -
2019 Poster: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2019 Poster: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Categorical Feature Compression via Submodular Optimization »
Mohammad Hossein Bateni · Lin Chen · Hossein Esfandiari · Thomas Fu · Vahab Mirrokni · Afshin Rostamizadeh -
2019 Oral: Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity »
Matthew Fahrbach · Vahab Mirrokni · Morteza Zadimoghaddam -
2019 Poster: Distributed Weighted Matching via Randomized Composable Coresets »
Sepehr Assadi · Mohammad Hossein Bateni · Vahab Mirrokni -
2019 Oral: Distributed Weighted Matching via Randomized Composable Coresets »
Sepehr Assadi · Mohammad Hossein Bateni · Vahab Mirrokni -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Poster: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Approximate Leave-One-Out for Fast Parameter Tuning in High Dimensions »
Shuaiwen Wang · Wenda Zhou · Haihao Lu · Arian Maleki · Vahab Mirrokni -
2018 Oral: Accelerating Greedy Coordinate Descent Methods »
Haihao Lu · Robert Freund · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2018 Oral: Proportional Allocation: Simple, Distributed, and Diverse Matching with High Entropy »
Shipra Agarwal · Morteza Zadimoghaddam · Vahab Mirrokni -
2017 Poster: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong -
2017 Talk: Tight Bounds for Approximate Carathéodory and Beyond »
Vahab Mirrokni · Renato Leme · Adrian Vladu · Sam Wong