# Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2014.

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

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [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)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem](https://mlsanity.com/paper/2407.07765/) (2024)
- [A Unified Characterization of Private Learnability via Graph Theory](https://mlsanity.com/paper/2304.03996/) (2023)
- [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)
- [The Limits of Differential Privacy in Online Learning](https://mlsanity.com/paper/2411.05483/) (2024)
- [Multiclass versus Binary Differentially Private PAC Learning](https://mlsanity.com/paper/2107.10870/) (2021)
- [Algorithms with More Granular Differential Privacy Guarantees](https://mlsanity.com/paper/2209.04053/) (2022)
- [Distributional PAC-Learning from Nisan's Natural Proofs](https://mlsanity.com/paper/2310.03641/) (2023)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [On the Price of Privacy for Language Identification and Generation](https://mlsanity.com/paper/2604.07238/) (2026)
- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Bridging Privacy and Robustness for Trustworthy Machine Learning](https://mlsanity.com/paper/2403.16591/) (2024)
- [Improved Bounds for Pure Private Agnostic Learning: Item-Level and User-Level Privacy](https://mlsanity.com/paper/2407.20640/) (2024)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2510.01291/) (2025)
- [Private Isotonic Regression](https://mlsanity.com/paper/2210.15175/) (2022)
- [Private Prediction via Shrinkage](https://mlsanity.com/paper/2602.05219/) (2026)

## Abstract (arXiv)

In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by Dwork et al. (2006) that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private PAC and agnostic learning was studied in a number of prior works starting with (Kasiviswanathan et al., 2008) but a number of basic questions still remain open, most notably whether learning with privacy requires more samples than learning without privacy. We show that the sample complexity of learning with (pure) differential privacy can be arbitrarily higher than the sample complexity of learning without the privacy constraint or the sample complexity of learning with approximate differential privacy. Our second contribution and the main tool is an equivalence between the sample complexity of (pure) differentially private learning of a concept class C (or SCDP(C)) and the randomized one-way communication complexity of the evaluation problem for concepts from C. Using this equivalence we prove the following bounds: 1. SCDP(C) = Omega(LDim(C)), where LDim(C) is the Littlestone's (1987) dimension characterizing the number of mistakes in the online-mistake-bound learning model. Known bounds on LDim(C) then imply that SCDP(C) can be much higher than the VC-dimension of C. 2. For any t, there exists a class C such that LDim(C)=2 but SCDP(C) ≥ t. 3. For any t, there exists a class C such that the sample complexity of (pure) α-differentially private PAC learning is Omega(t/α) but the sample complexity of the relaxed (α,β)-differentially private PAC learning is O(log(1/β)/α). This resolves an open problem of Beimel et al. (2013b).