mlsanityData to 13 Oct 2026

On Theoretical Limits of Learning with Label Differential Privacy

arXiv 2502.14309 ↗First posted 20 Feb 2025cs.LG cs.IT math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

Label differential privacy (DP) is designed for learning problems involving private labels and public features. While various methods have been proposed for learning under label DP, the theoretical limits remain largely unexplored. In this paper, we investigate the fundamental limits of learning with label DP in both local and central models for both classification and regression tasks, characterized by minimax convergence rates. We establish lower bounds by converting each task into a multiple hypothesis testing problem and bounding the test error. Additionally, we develop algorithms that yield matching upper bounds. Our results demonstrate that under label local DP (LDP), the risk has a significantly faster convergence rate than that under full LDP, i.e. protecting both features and labels, indicating the advantages of relaxing the DP definition to focus solely on labels. In contrast, under the label central DP (CDP), the risk is only reduced by a constant factor compared to full DP, indicating that the relaxation of CDP only has limited benefits on the performance.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 38 of its 70 references that are in the map. First posted on arXiv 20 Feb 2025.

Builds on

38 of 70 references.

References · 38

  1. 2016Deep Learning with Differential Privacycited by 2,718
  2. 2021Convex optimizationcited by 2,488
  3. 2016Semi-supervised Knowledge Transfer for Deep Learning from Private Training Datacited by 347
  4. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 271
  5. 2020Differentially Private Learning Needs Better Features (or Much More Data)cited by 235
  6. 2022Unlocking High-Accuracy Differentially Private Image Classification through Scalecited by 223
  7. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  8. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  9. 2017Collecting Telemetry Data Privatelycited by 149
  10. 2021Deep Learning with Label Differential Privacycited by 116
  11. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 106
  12. 2018Privately Learning High-Dimensional Distributionscited by 104
26 more
  1. 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
  2. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  3. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  4. 2019Private Hypothesis Selectioncited by 60
  5. 2021Antipodes of Label Differential Privacy: PATE and ALIBIcited by 52
  6. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  7. 2022Scalable and Efficient Training of Large Convolutional Neural Networks with Differential Privacycited by 48
  8. 2014Rates of Convergence for Nearest Neighbor Classificationcited by 46
  9. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  10. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  11. 2021Label differential privacy via clusteringcited by 20
  12. 2022Beyond Uniform Lipschitz Condition in Differentially Private Optimizationcited by 19
  13. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  14. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  15. 2022On robustness and local differential privacycited by 15
  16. 2022Regression with Label Differential Privacycited by 15
  17. 2022DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Samplingcited by 13
  18. 2019Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regressioncited by 11
  19. 2020Strongly universally consistent nonparametric regression and classification with privatised datacited by 8
  20. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  21. 2023Optimal Unbiased Randomizers for Regression with Label Differential Privacycited by 6
  22. 2024Machine Learning Approaches for Mental Illness Detection on Social Media: A Systematic Review of Biases and Methodological Challengescited by 4
  23. 2024Locally Private Estimation with Public Featurescited by 3
  24. 2025Tutorial on Using Machine Learning and Deep Learning Models for Mental Illness Detectioncited by 3
  25. 2024Enhancing Learning with Label Differential Privacy by Vector Approximationcited by 2
  26. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1

Built on by

Not cited yet.