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.
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