mlsanityData to 7 Oct 2026

Learning with User-Level Privacy

arXiv 2102.11845 ↗First posted 23 Feb 2021cs.LG cs.CR math.OCcited by 72

Not on the map. Why?

Abstract (arXiv)

We propose and analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution (m ≥ 1 samples), providing more stringent but more realistic protection against information leaks. We show that for high-dimensional mean estimation, empirical risk minimization with smooth losses, stochastic convex optimization, and learning hypothesis classes with finite metric entropy, the privacy cost decreases as O(1/√m) as users provide more samples. In contrast, when increasing the number of users n, the privacy cost decreases at a faster O(1/n) rate. We complement these results with lower bounds showing the minimax optimality of our algorithms for mean estimation and stochastic convex optimization. Our algorithms rely on novel techniques for private mean estimation in arbitrary dimension with error scaling as the concentration radius τ of the distribution rather than the entire range.

Key facts. Cited by 72 papers in the map (data through 7 Oct 2026). Builds on 34 of its 74 references that are in the map. First posted on arXiv 23 Feb 2021.

Builds on

34 of 74 references.

References · 34

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2014Convex Optimization: Algorithms and Complexitycited by 569
  4. 2018Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learningcited by 242
  5. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  8. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  9. 2017Collecting Telemetry Data Privatelycited by 147
  10. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  11. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
  12. 2016Distributed Mean Estimation with Limited Communicationcited by 134
22 more
  1. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  2. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  3. 2018Privately Learning High-Dimensional Distributionscited by 103
  4. 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
  5. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  6. 2016The Landscape of Empirical Risk for Non-convex Lossescited by 86
  7. 2019Generative Models for Effective ML on Private, Decentralized Datasetscited by 85
  8. 2018A General Approach to Adding Differential Privacy to Iterative Training Procedurescited by 84
  9. 2018Private Selection from Private Candidatescited by 75
  10. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  11. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  12. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  13. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  14. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  15. 2020Learning discrete distributions: user vs item-level privacycited by 41
  16. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  17. 2017Calibrating Noise to Variance in Adaptive Data Analysiscited by 28
  18. 2019Differentially Private SQL with Bounded User Contributioncited by 27
  19. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  20. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
  21. 2019Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noisecited by 9
  22. 2019Geometry, Computation, and Optimality in Stochastic Optimizationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 13; 2023: 21; 2024: 16; 2025: 9; 2026: 4.

72 papers.

Sort:

By area:

  1. 2022What Does it Mean for a Language Model to Preserve Privacy?cited by 194
  2. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  3. 2021Node-Level Differentially Private Graph Neural Networkscited by 43
  4. 2023Training Data Extraction From Pre-trained Language Models: A Surveycited by 43
  5. 2022On Privacy and Personalization in Cross-Silo Federated Learningcited by 36
  6. 2023User Inference Attacks on Large Language Modelscited by 36
  7. 2023SoK: Memorization in General-Purpose Large Language Modelscited by 36
  8. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  9. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  10. 2022New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemmacited by 32
  11. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  12. 2024Fine-Tuning Large Language Models with User-Level Differential Privacycited by 28
38 more
  1. 2021Tight and Robust Private Mean Estimation with Few Userscited by 26
  2. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  3. 2022Personalization Improves Privacy-Accuracy Tradeoffs in Federated Learningcited by 23
  4. 2022Learning to Generate Image Embeddings with User-level Differential Privacycited by 23
  5. 2024Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuningcited by 21
  6. 2021Adapting to Function Difficulty and Growth Conditions in Private Optimizationcited by 19
  7. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  8. 2023Randomized Quantization is All You Need for Differential Privacy in Federated Learningcited by 16
  9. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  10. 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
  11. 2023Share Your Representation Only: Guaranteed Improvement of the Privacy-Utility Tradeoff in Federated Learningcited by 13
  12. 2025Towards User-level Private Reinforcement Learning with Human Feedbackcited by 13
  13. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  14. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  15. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  16. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  17. 2021Private Multi-Task Learning: Formulation and Applications to Federated Learningcited by 11
  18. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  19. 2021User-Level Private Learning via Correlated Samplingcited by 9
  20. 2023Post-processing Private Synthetic Data for Improving Utility on Selected Measurescited by 9
  21. 2023ULDP-FL: Federated Learning with Across Silo User-Level Differential Privacycited by 9
  22. 2023On User-Level Private Convex Optimizationcited by 8
  23. 2023Mean Estimation with User-level Privacy under Data Heterogeneitycited by 8
  24. 2024Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Lossescited by 8
  25. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
  26. 2024Clients Collaborate: Flexible Differentially Private Federated Learning with Guaranteed Improvement of Utility-Privacy Trade-offcited by 6
  27. 2022Continual Mean Estimation Under User-Level Privacycited by 5
  28. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  29. 2024Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Testscited by 5
  30. 2022Algorithms for bounding contribution for histogram estimation under user-level privacycited by 4
  31. 2022Algorithms with More Granular Differential Privacy Guaranteescited by 4
  32. 2024Minimax And Adaptive Transfer Learning for Nonparametric Classification under Distributed Differential Privacy Constraintscited by 4
  33. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  34. 2022Subject Granular Differential Privacy in Federated Learningcited by 3
  35. 2023Multi-Task Differential Privacy Under Distribution Skewcited by 3
  36. 2023Subset-Based Instance Optimality in Private Estimationcited by 3
  37. 2024Defending Against Data Reconstruction Attacks in Federated Learning: An Information Theory Approachcited by 3
  38. 2024Learning with User-Level Local Differential Privacycited by 3

50 most cited of 72 All 72 (JSON)