# Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2014.

## Built on by (most cited first, 30 of 63)

- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Antipodes of Label Differential Privacy: PATE and ALIBI](https://mlsanity.com/paper/2106.03408/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization](https://mlsanity.com/paper/2303.12921/) (2023)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [Benchmarking Differential Privacy and Federated Learning for BERT Models](https://mlsanity.com/paper/2106.13973/) (2021)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Label differential privacy via clustering](https://mlsanity.com/paper/2110.02159/) (2021)
- [Privacy enabled Financial Text Classification using Differential Privacy and Federated Learning](https://mlsanity.com/paper/2110.01643/) (2021)
- [How unfair is private learning ?](https://mlsanity.com/paper/2206.03985/) (2022)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy](https://mlsanity.com/paper/2404.16706/) (2024)
- [Regression with Label Differential Privacy](https://mlsanity.com/paper/2212.06074/) (2022)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Differentially Private Approximate Quantiles](https://mlsanity.com/paper/2110.05429/) (2021)
- [Differentially Private Reward Estimation with Preference Feedback](https://mlsanity.com/paper/2310.19733/) (2023)
- [Learning from Aggregated Data: Curated Bags versus Random Bags](https://mlsanity.com/paper/2305.09557/) (2023)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Privacy-Preserving Models for Legal Natural Language Processing](https://mlsanity.com/paper/2211.02956/) (2022)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Eliminating Label Leakage in Tree-Based Vertical Federated Learning](https://mlsanity.com/paper/2307.10318/) (2023)
- [Optimal Unbiased Randomizers for Regression with Label Differential Privacy](https://mlsanity.com/paper/2312.05659/) (2023)
- [Public-data Assisted Private Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2403.03856/) (2024)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Private Everlasting Prediction](https://mlsanity.com/paper/2305.09579/) (2023)
- [On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective](https://mlsanity.com/paper/2402.16778/) (2024)

## Abstract (arXiv)

We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure ε-differential privacy [Dwork et al. TCC 2006] and approximate (ε,δ)-differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy. We define a family of optimization problems, which we call Quasi-Concave Promise Problems, that generalizes some of our considered tasks. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm solving such problems privately. Specifically, we construct private learners for point functions, threshold functions, and axis-aligned rectangles in high dimension. Similarly, we construct sanitizers for point functions and threshold functions. We also examine the sample complexity of label-private learners, a relaxation of private learning where the learner is required to only protect the privacy of the labels in the sample. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.