mlsanityData to 7 Oct 2026

Tight and Robust Private Mean Estimation with Few Users

arXiv 2110.11876 ↗First posted 22 Oct 2021cs.DS cs.CR cs.LGcited by 26

Not on the map. Why?

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.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). Builds on 18 of its 41 references that are in the map. First posted on arXiv 22 Oct 2021.

Builds on

18 of 41 references.

References · 18

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  4. 2018Privately Learning High-Dimensional Distributionscited by 103
  5. 2019Generative Models for Effective ML on Private, Decentralized Datasetscited by 85
  6. 2018A General Approach to Adding Differential Privacy to Iterative Training Procedurescited by 84
  7. 2021Learning with User-Level Privacycited by 72
  8. 2021Robust and Differentially Private Mean Estimationcited by 66
  9. 2020Learning discrete distributions: user vs item-level privacycited by 41
  10. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  11. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  12. 2020Differentially Private Clustering: Tight Approximation Ratioscited by 34
6 more
  1. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  2. 2019Differentially Private SQL with Bounded User Contributioncited by 27
  3. 2018Differentially Private k-Means with Constant Multiplicative Errorcited by 22
  4. 2019Locally Private k-Means Clusteringcited by 15
  5. 2019Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noisecited by 9
  6. 2018Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outlierscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 6; 2024: 9; 2025: 2; 2026: 2.

26 papers.

Sort:

By area:

  1. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  2. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 28
  3. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  4. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  5. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  6. 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
  7. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  8. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  9. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  10. 2023On User-Level Private Convex Optimizationcited by 8
  11. 2023Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codescited by 8
  12. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
14 more
  1. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  2. 2022Continual Mean Estimation Under User-Level Privacycited by 5
  3. 2024Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Testscited by 5
  4. 2022Algorithms for bounding contribution for histogram estimation under user-level privacycited by 4
  5. 2022Renyi Differential Privacy of Propose-Test-Release and Applications to Private and Robust Machine Learningcited by 4
  6. 2024Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysiscited by 3
  7. 2024Better Locally Private Sparse Estimation Given Multiple Samples Per Usercited by 1
  8. 2024Optimal Federated Learning for Functional Mean Estimation under Heterogeneous Privacy Constraintscited by 1
  9. 2025Improved subsample-and-aggregate via the private modified winsorized meancited by 1
  10. 2023Robust and differentially private stochastic linear banditscited by 0
  11. 2023Learning across Data Owners with Joint Differential Privacycited by 0
  12. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0
  13. 2026Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacycited by 0
  14. 2026Computationally tractable robust differentially private mean estimationcited by 0