mlsanityData to 7 Oct 2026

Learning with User-Level Local Differential Privacy

arXiv 2405.17079 ↗First posted 27 May 2024stat.ML cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

User-level privacy is important in distributed systems. Previous research primarily focuses on the central model, while the local models have received much less attention. Under the central model, user-level DP is strictly stronger than the item-level one. However, under the local model, the relationship between user-level and item-level LDP becomes more complex, thus the analysis is crucially different. In this paper, we first analyze the mean estimation problem and then apply it to stochastic optimization, classification, and regression. In particular, we propose adaptive strategies to achieve optimal performance at all privacy levels. Moreover, we also obtain information-theoretic lower bounds, which show that the proposed methods are minimax optimal up to logarithmic factors. Unlike the central DP model, where user-level DP always leads to slower convergence, our result shows that under the local model, the convergence rates are nearly the same between user-level and item-level cases for distributions with bounded support. For heavy-tailed distributions, the user-level rate is even faster than the item-level one.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 42 of its 62 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

42 of 62 references.

References · 42

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2019Federated Learning with Differential Privacy: Algorithms and Performance Analysiscited by 528
  4. 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 451
  5. 2018Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learningcited by 242
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
  7. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
  8. 2018Protection Against Reconstruction and Its Applications in Private Federated Learningcited by 127
  9. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  10. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  11. 2021Learning with User-Level Privacycited by 72
  12. 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
30 more
  1. 2021Robust and Differentially Private Mean Estimationcited by 66
  2. 2021DRIVE: One-bit Distributed Mean Estimationcited by 52
  3. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  4. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2014Rates of Convergence for Nearest Neighbor Classificationcited by 45
  7. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  8. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  9. 2016Differential Privacy as a Mutual Information Constraintcited by 41
  10. 2020Learning discrete distributions: user vs item-level privacycited by 41
  11. 2020Local Differential Privacy and Its Applications: A Comprehensive Surveycited by 40
  12. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  13. 2022Optimal Algorithms for Mean Estimation under Local Differential Privacycited by 36
  14. 2020Analysis of KNN Density Estimationcited by 28
  15. 2021Lossless Compression of Efficient Private Local Randomizerscited by 27
  16. 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
  17. 2017Local nearest neighbour classification with applications to semi-supervised learningcited by 17
  18. 2022Discrete Distribution Estimation under User-level Local Differential Privacycited by 17
  19. 2023A Huber Loss Minimization Approach to Byzantine Robust Federated Learningcited by 16
  20. 2020Sharp Concentration Results for Heavy-Tailed Distributionscited by 15
  21. 2022On robustness and local differential privacycited by 15
  22. 2023Fast Optimal Locally Private Mean Estimation via Random Projectionscited by 14
  23. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  24. 2023User-Level Differential Privacy With Few Examples Per Usercited by 12
  25. 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
  26. 2019Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regressioncited by 11
  27. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  28. 2019Classification under local differential privacycited by 9
  29. 2020Strongly universally consistent nonparametric regression and classification with privatised datacited by 8
  30. 2024Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messagescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 1.

3 papers.

  1. 2024CorBin-FL: A Differentially Private Federated Learning Mechanism using Common Randomnesscited by 1
  2. 2025Consistent Estimation of Numerical Distributions under Local Differential Privacy by Wavelet Expansioncited by 1
  3. 2026Matrix Factorization for Practical Continual Mean Estimation Under User-Level Differential Privacycited by 0