Actually, All Learnable Distribution Classes Are Privately Learnable

Mohammad Afzali; Hassan Ashtiani; Alex Bie; Gautam Kamath; Peihan Liu; Argyris Mouzakis; Vikrant Singhal

cs.LGOct 20, 2026

Actually, All Learnable Distribution Classes Are Privately Learnable

Authors: Mohammad Afzali, Hassan Ashtiani, Alex Bie, Gautam Kamath, Peihan Liu, Argyris Mouzakis, Vikrant Singhal

Organizations: University of British Columbia. · McMaster University and Vector Institute. · Google Research. · New York University. ·

Abstract

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 ( $\varepsilon, δ$ )-differential privacy up to arbitrarily small target error with finitely many samples. This proves a conjecture of Ashtiani. Previous work by Bun, Kamath, Mouzakis, and Singhal [arXiv:2402.00267] gave a weak refutation of this conjecture, showing that this implication is not true when learnability is defined with respect to a fixed target error. In contrast, we show that, under the standard definition of learnability, the conjecture is true.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 276 papers

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
Feb 24, 2026Moïse Blanchard, Abhishek Shetty, Alexander RakhlinStatistical Learning Theory Online Learning
MIT
Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy
Oct 22, 2026Gautam Kamath, Mahbod Majid, Ankur Moitra +2Robust Statistics Differential Privacy
New York University · Massachusetts Institute of Technology · University of Texas at Austin and University of Waterloo +1
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Oct 15, 2026Mohammad Afzali, Hassan Ashtiani, Sivan SabatoDifferential Privacy Density Estimation
University of British Columbia · McMaster University · Vector Institute +1

Feb 24, 2026J/K move · Enter open · S save

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin

MIT

Statistical Learning Theory Online Learning

Open paper AskPDF arXiv

Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning theory, such as the VC theorem and Littlestone's characterization of online learnability, establish conditions on the hypothesis class that allow for learning under independent data and adversarial data, respectively. Building upon recent work bridging these extremes, we study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family

U

and ask when such problems are learnable with sample complexity that behaves like the favorable independent case. We provide a near complete characterization of families

U

that admit learnability in terms of a notion known as generalized smoothness i.e. a distribution family admits VC-dimension-dependent regret bounds for every finite-VC hypothesis class if and only if it is generalized smooth. Further, we give universal algorithms that achieve low regret under any generalized smooth adversary without explicit knowledge of

U

. Finally, when

U

is known, we provide refined bounds in terms of a combinatorial parameter, the fragmentation number, that captures how many disjoint regions can carry nontrivial mass under

U

. These results provide a nearly complete understanding of learnability under distributional adversaries. In addition, building upon the surprising connection between online learning and differential privacy, we show that the generalized smoothness also characterizes private learnability under distributional constraints.

Abstract

Differential Privacy

Explore similar work

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

Efficient and Optimal Learning of Discrete Distributions with Person-Level Privacy

Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy