Privacy need not rule out learning probability distributions
A proof showed that families of probability distributions learnable to arbitrarily small error from finitely many samples remain learnable under approximate differential privacy.
Edited by Boris Djordjevic · Paperfoot
The paper proved that any family of probability distributions learnable to arbitrarily small error from finitely many samples is also learnable under approximate differential privacy. This privacy guarantee limits how much changing one sample can change the chances of an output, with a small allowance for exceptions.
The theorem measured error using total variation distance: the largest difference in the probabilities two distributions assign to the same event. It guaranteed learning with finitely many samples even with privacy protection. Earlier work had shown that this implication fails when learning means reaching one fixed target error. The new proof established the implication when learning instead requires reaching arbitrarily small error—the standard definition used in the paper.
Why it matters
The proof settled Ashtiani’s conjecture under the standard definition of learnability. It established that privacy does not make this kind of learning impossible, rather than demonstrating a practical system.
Caveats
The theorem guarantees a finite sample requirement, but the abstract gives no sample-count or computing-time bounds. The work is an arXiv preprint and has not been peer-reviewed.
In this paper
private distribution learning
- Methods
- Aggregate (this paper)Sampler (this paper)StabilityBasedMode
What it shows
- Every distribution class learnable to arbitrarily small target error in total variation distance with finitely many samples is privately learnable under differential privacy with finitely many samples.
We show that every class of distributions that is learnable up to arbitrarily small target error in total variation distance with finitely many samples is also learnable under (ε, δ)-differential privacy up to arbitrarily small target error with finitely many samples.
Abstract
- For any standard Borel space, the family of random variables induced by Construction A.4 constitutes a universal grand coupling scheme on the space of probability measures.
The family of random variables (Z_{P})_{P\in\Delta(\mathcal{Y})}≈\Gamma_{\infty} induced by Construction A.4x constitutes a universal grand coupling scheme on \Delta(\Y).
Proposition 3.3 (Informal version of Corollary A.7 and A.6).
- For sufficiently large k, the Aggregate algorithm is differentially private and produces an output distribution beta/2-close in total variation distance to the product ground-truth distribution when 7/8 of inputs are close.
Moreover, for any p\in\Q and input tuple \q\in\mathcal{F}^{k}, if at least 7/8 of the input distributions are O(\beta/\ell) -close to p in TV, then the law of its output is \beta/2 -close to p^{\ell} in TV.
Theorem 4.1 (Informal version of Corollary B.4).
Quoted word for word from the full text on arXiv.
The paper
Actually, All Learnable Distribution Classes Are Privately Learnable
arXiv, Oct 20, 2026, Open access, CC BY-SA, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.28878
arXiv:2610.28878v1 in cs.LG, also stat.ML
Cite as BibTeX
@misc{afzali2026actually,
title = {Actually, All Learnable Distribution Classes Are Privately Learnable},
author = {Afzali, Mohammad and Ashtiani, Hassan and Bie, Alex and Kamath, Gautam and Liu, Peihan and Mouzakis, Argyris and Singhal, Vikrant},
year = {2026},
eprint = {2610.28878},
archivePrefix = {arXiv},
primaryClass = {cs.LG},
doi = {10.48550/arxiv.2610.28878},
url = {https://arxiv.org/abs/2610.28878}
}
