# Label differential privacy via clustering

arXiv: https://arxiv.org/abs/2110.02159 · HTML: https://mlsanity.com/paper/2110.02159/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 22 references that are in the map.
- First posted on arXiv 5 Oct 2021.

## Builds on (most cited first, 8 of 8)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)

## Built on by (most cited first, 20 of 20)

- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Regression with Label Differential Privacy](https://mlsanity.com/paper/2212.06074/) (2022)
- [Differentially Private Reward Estimation with Preference Feedback](https://mlsanity.com/paper/2310.19733/) (2023)
- [GeoPointGAN: Synthetic Spatial Data with Local Label Differential Privacy](https://mlsanity.com/paper/2205.08886/) (2022)
- [Differentially Private Learning with Margin Guarantees](https://mlsanity.com/paper/2204.10376/) (2022)
- [Optimal Unbiased Randomizers for Regression with Label Differential Privacy](https://mlsanity.com/paper/2312.05659/) (2023)
- [Classification with Partially Private Features](https://mlsanity.com/paper/2312.07583/) (2023)
- [Improving the Variance of Differentially Private Randomized Experiments through Clustering](https://mlsanity.com/paper/2308.00957/) (2023)
- [Enhancing Learning with Label Differential Privacy by Vector Approximation](https://mlsanity.com/paper/2405.15150/) (2024)
- [Label Differential Privacy via Aggregation](https://mlsanity.com/paper/2310.10092/) (2023)
- [On Theoretical Limits of Learning with Label Differential Privacy](https://mlsanity.com/paper/2502.14309/) (2025)
- [RPWithPrior: Label Differential Privacy in Regression](https://mlsanity.com/paper/2601.22625/) (2026)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Online Distribution Learning with Local Private Constraints](https://mlsanity.com/paper/2402.00315/) (2024)
- [Privacy-Preserving Student Learning with Differentially Private Data-Free Distillation](https://mlsanity.com/paper/2409.12384/) (2024)
- [Aggregating Data for Optimal and Private Learning](https://mlsanity.com/paper/2411.19045/) (2024)
- [Privacy-Preserving Model Transcription with Differentially Private Synthetic Distillation](https://mlsanity.com/paper/2601.19090/) (2026)
- [BlockRR: A Unified Framework of RR-type Algorithms for Label Differential Privacy](https://mlsanity.com/paper/2602.03277/) (2026)
- [Private Learning with Public Feature Conditioning](https://mlsanity.com/paper/2606.18773/) (2026)
- [End-to-End Differential Privacy in Training Deep Neural Network Classifiers](https://mlsanity.com/paper/2607.19580/) (2026)

## Abstract (arXiv)

We present new mechanisms for label differential privacy, a relaxation of differentially private machine learning that only protects the privacy of the labels in the training set. Our mechanisms cluster the examples in the training set using their (non-private) feature vectors, randomly re-sample each label from examples in the same cluster, and output a training set with noisy labels as well as a modified version of the true loss function. We prove that when the clusters are both large and high-quality, the model that minimizes the modified loss on the noisy training set converges to small excess risk at a rate that is comparable to the rate for non-private learning. We describe both a centralized mechanism in which the entire training set is stored by a trusted curator, and a distributed mechanism where each user stores a single labeled example and replaces her label with the label of a randomly selected user from the same cluster. We also describe a learning problem in which large clusters are necessary to achieve both strong privacy and either good precision or good recall. Our experiments show that randomizing the labels within each cluster significantly improves the privacy vs. accuracy trade-off compared to applying uniform randomized response to the labels, and also compared to learning a model via DP-SGD.