On Theoretical Limits of Learning with Label Differential Privacy

Puning Zhao, Chuan Ma, Li Shen, Shaowei Wang, Rongfei Fan

Abstract

This paper investigates the fundamental theoretical limits of machine learning under Label Differential Privacy (Label DP), a setting where only labels are privatized while features remain public. By establishing minimax convergence rates for classification and regression, the authors reveal a surprising dichotomy: relaxing to Label DP yields massive asymptotic accuracy gains in the local privacy model, but only marginal improvements in the central privacy model compared to standard full DP.

Introduction

Differential Privacy (DP) is the gold standard for protecting training data, but it often causes significant drops in machine learning model performance. In many real-world scenarios—such as medical diagnosis or ad click prediction—the input features (e.g., demographics) are public or less sensitive, while the labels (e.g., disease status or user clicks) are highly sensitive.

This observation led to the concept of Label DP, which relaxes standard DP by only requiring privacy for the labels. While recent empirical works show that Label DP improves model accuracy, the information-theoretic limits of this approach have remained a mystery. This research asks: mathematically speaking, exactly how much accuracy improvement is achievable by sacrificing feature privacy? Does it fundamentally change the learning complexity, or just provide a minor boost?

Theoretical Framework and Methodology

To find the absolute limits of what any algorithm can achieve, the authors establish minimax lower bounds and matching upper bounds for nonparametric classification and regression tasks.

Establishing Lower Bounds

The authors convert learning tasks into multiple hypothesis testing problems. For the local model (where data is privatized before reaching the server), they develop a tighter bound on the Kullback-Leibler (KL) divergence of joint distributions that mix public features and private labels. For the central model (where a trusted server aggregates data and privatizes the output), the authors develop new lower bounds on the minimum testing error for hypothesis pairs without relying on parametric assumptions, as standard packing methods often fail for nonparametric problems.

Proving Achievability (Upper Bounds)

To prove their lower bounds are tight, the authors design specific algorithms that hit those limits:

  • Local Classification: Randomized response mechanism (similar to RAPPOR).
  • Central Classification: Exponential mechanism.
  • Local Regression: Nearest-neighbor approach.
  • Central Regression: Locally averaging technique with cube-splitting.

Key Results: The Local vs. Central Dichotomy

The most striking finding is how differently Label DP behaves depending on the trust model. In Local DP, randomizing high-dimensional features destroys a massive amount of information. Therefore, protecting only the labels drastically improves the theoretical convergence rate compared to full Local DP. However, in Central DP, the noise added to protect features is much less destructive. Consequently, dropping feature privacy in the central model only improves the risk by a constant factor—the asymptotic convergence rate remains exactly the same as full Central DP.

Summary of minimax convergence rates for classification and regression under various privacy models.

Privacy's "Sample Complexity Tax"

In the local model, privacy acts as a strict multiplier on the required data. Having $N$ privatized samples is roughly equivalent to having $N\epsilon^2$ non-privatized samples. In the central model, the additional error introduced by privacy decays faster than the standard non-private learning error, meaning the cost of privacy becomes negligible as the dataset grows.

The Heavy-Tail Penalty

For regression tasks, if the label noise has heavy tails (i.e., extreme outliers are possible), achieving Label DP requires aggressive clipping and larger noise. The authors prove that this fundamentally slows down the convergence rate compared to the non-private setting, highlighting a specific vulnerability of DP to heavy-tailed distributions.

Conclusion

This work provides the first comprehensive theoretical characterization of Label DP. The results show that while Label DP is a powerful tool for improving utility in local privacy settings, its benefits in central settings are more modest. Future work may focus on relaxing the "strong density assumption" used in this analysis to accommodate more general, real-world feature distributions and translating these minimax-optimal algorithms into practical deep learning architectures.

Summary updated

Abstract

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.
BibTeX
@misc{zhao2025theoretical,
  author = {Puning Zhao and Chuan Ma and Li Shen and Shaowei Wang and Rongfei Fan},
  title = {{On Theoretical Limits of Learning with Label Differential Privacy}},
  year = {2025},
  eprint = {2502.14309},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.14309},
}
Figure