# Tight and Robust Private Mean Estimation with Few Users arXiv: https://arxiv.org/abs/2110.11876 · HTML: https://mlsanity.com/paper/2110.11876/ ## Key facts - Cited by 26 papers in the map (data through 14 Oct 2026). - Builds on 18 of its 41 references that are in the map. - First posted on arXiv 22 Oct 2021. ## Builds on (most cited first, 18 of 18) - [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018) - [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018) - [Generative Models for Effective ML on Private, Decentralized Datasets](https://mlsanity.com/paper/1911.06679/) (2019) - [A General Approach to Adding Differential Privacy to Iterative Training Procedures](https://mlsanity.com/paper/1812.06210/) (2018) - [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021) - [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021) - [Learning discrete distributions: user vs item-level privacy](https://mlsanity.com/paper/2007.13660/) (2020) - [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021) - [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014) - [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020) - [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021) - [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019) - [Differentially Private k-Means with Constant Multiplicative Error](https://mlsanity.com/paper/1804.08001/) (2018) - [Locally Private k-Means Clustering](https://mlsanity.com/paper/1907.02513/) (2019) - [Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise](https://mlsanity.com/paper/1901.08788/) (2019) - [Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers](https://mlsanity.com/paper/1806.07356/) (2018) ## Built on by (most cited first, 26 of 26) - [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022) - [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024) - [DP-PCA: Statistically Optimal and Differentially Private PCA](https://mlsanity.com/paper/2205.13709/) (2022) - [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022) - [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023) - [Subspace Recovery from Heterogeneous Data with Non-isotropic Noise](https://mlsanity.com/paper/2210.13497/) (2022) - [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024) - [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024) - [User-Level Differential Privacy With Few Examples Per User](https://mlsanity.com/paper/2309.12500/) (2023) - [Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraints](https://mlsanity.com/paper/2406.06755/) (2024) - [On User-Level Private Convex Optimization](https://mlsanity.com/paper/2305.04912/) (2023) - [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023) - [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024) - [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024) - [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022) - [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022) - [Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learning](https://mlsanity.com/paper/2209.07716/) (2022) - [Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis](https://mlsanity.com/paper/2412.14396/) (2024) - [Learning across Data Owners with Joint Differential Privacy](https://mlsanity.com/paper/2305.15723/) (2023) - [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024) - [Optimal Federated Learning for Functional Mean Estimation under Heterogeneous Privacy Constraints](https://mlsanity.com/paper/2412.18992/) (2024) - [Improved subsample-and-aggregate via the private modified winsorized mean](https://mlsanity.com/paper/2501.14095/) (2025) - [Robust and differentially private stochastic linear bandits](https://mlsanity.com/paper/2304.11741/) (2023) - [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025) - [Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacy](https://mlsanity.com/paper/2601.22320/) (2026) - [Computationally tractable robust differentially private mean estimation](https://mlsanity.com/paper/2606.12654/) (2026) ## Abstract (arXiv) In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an (varepsilon,δ)-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(frac1varepsilonlogfrac1δ). Interestingly, this bound on the number of users is independent of the dimension (though the number of 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. 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., 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.