# Characterizing the Sample Complexity of Private Learners

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

## Key facts

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

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

- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [How unfair is private learning ?](https://mlsanity.com/paper/2206.03985/) (2022)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [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)
- [Federated Learning on Riemannian Manifolds with Differential Privacy](https://mlsanity.com/paper/2404.10029/) (2024)
- [Privacy Amplification Via Bernoulli Sampling](https://mlsanity.com/paper/2105.10594/) (2021)
- [Do PAC-Learners Learn the Marginal Distribution?](https://mlsanity.com/paper/2302.06285/) (2023)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Private List Learnability vs. Online List Learnability](https://mlsanity.com/paper/2506.12856/) (2025)
- [Privacy Amplification by Subsampling in Time Domain](https://mlsanity.com/paper/2201.04762/) (2022)
- [Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions](https://mlsanity.com/paper/2312.08685/) (2023)
- [Differentially Private Relational Learning with Entity-level Privacy Guarantees](https://mlsanity.com/paper/2506.08347/) (2025)

## Abstract (arXiv)

In 2008, Kasiviswanathan et al. defined private learning as a combination of PAC learning and differential privacy. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. gave a generic construction of private learners for (finite) concept classes, with sample complexity logarithmic in the size of the concept class. This sample complexity is higher than what is needed for non-private learners, hence leaving open the possibility that the sample complexity of private learning may be sometimes significantly higher than that of non-private learning. We give a combinatorial characterization of the sample size sufficient and necessary to privately learn a class of concepts. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure RepDim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies RepDim(C)=O(m), and that there exists a private learning algorithm with sample complexity m=O(RepDim(C)). We further demonstrate that a similar characterization holds for the database size needed for privately computing a large class of optimization problems and also for the well studied problem of private data release.