📊 statistics

Not All Learnable Distribution Classes are Privately Learnable

This paper presents a counterexample demonstrating that a class of distributions learnable with a finite sample size in total variation distance is not necessarily learnable under $(\varepsilon, \delta)$ -differential privacy, thereby refuting a conjecture by Ashtiani.

Original authors: Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Question: Can We Always Learn Privately?

Imagine you are a detective trying to figure out how a mysterious machine works. You can feed it inputs and see what comes out.

Standard Learning: You just want to figure out the machine's rules as quickly as possible.
Private Learning: You want to figure out the rules, but you must do it in a way that no single person's data (one specific input/output pair) can be identified by looking at your final report. This is called Differential Privacy.

For a long time, researchers wondered: "If a machine is easy to figure out normally, is it also easy to figure out while keeping everyone's data private?"

A researcher named Ashtiani guessed the answer was "Yes." He thought that if you can learn something with a few samples, you can also learn it privately with a few samples.

This paper says: "No, that's not always true."

The authors found a specific type of "machine" (a class of distributions) that is incredibly easy to learn normally, but impossible to learn privately, no matter how many samples you have.

The "Trapdoor" Machine

To prove this, the authors built a special kind of probability machine (a distribution) that acts like a trapdoor.

Imagine a box containing two types of marbles:

The "Key" Marbles (Rare): These are special. If you pick even just one of these, it instantly tells you the secret code for the entire box.
The "Noise" Marbles (Common): These are boring. If you pick one, it tells you almost nothing about the secret code. It's like trying to guess a 1,000-digit password by looking at a single random number.

How the machine works:

The machine is rigged so that 99% of the time, you get a "Noise" marble.
Only 1% of the time (or a tiny fraction), you get a "Key" marble.
Crucially, the "Key" marble and the "Noise" marbles are connected. The "Key" holds the master key to the whole system.

The Two Scenarios

1. The Normal Detective (Non-Private Learning)

If you are just a normal detective without privacy rules, you don't care about hiding which marble came from where.

You grab a handful of marbles.
Even though most are "Noise," you only need one "Key" marble to solve the whole puzzle.
Because the machine is rigged to give you a "Key" occasionally, you will find one very quickly (in a constant number of tries).
Result: You solve the puzzle easily with very few samples.

2. The Private Detective (Differential Privacy)

Now, imagine you are a private detective. You must produce a report that doesn't reveal which specific marble in your pile was the "Key."

If you see a "Key" marble, you know the answer. But if you report the answer, you might accidentally reveal, "Hey, I found a Key!" which breaks the privacy rule.
To stay private, you have to act as if you might have found a Key even if you didn't, or vice versa.
Because the "Key" is so rare, the only way to be sure you have the right answer without leaking privacy is to collect so many samples that you are guaranteed to find the Key.
The Twist: The authors designed the machine so that as the problem gets slightly more complex (by adding more dimensions), the "Key" becomes harder to find privately.
Result: To learn this specific machine privately with the same accuracy, you would need an infinite number of samples. It is mathematically impossible to do it with a finite amount of data.

The "Entangled" Secret

The paper uses a clever trick called entanglement.

The "Key" part of the machine is a simple binary code (like a string of 0s and 1s).
The "Noise" part is a complex set of numbers.
They share the same secret parameters.
Normally, the "Key" part is easy to read. But because the "Noise" part is so dominant (it appears almost all the time), a private algorithm gets "distracted" by the noise. It can't tell if a pattern it sees is the real secret or just random noise, unless it has infinite data to be sure.

The Conclusion

The paper proves that Ashtiani's guess was wrong.

Old Belief: If a problem is solvable, it's solvable privately.
New Reality: There are problems that are solvable with a handful of data, but become impossible to solve privately, no matter how much data you collect.

They didn't just say "it's hard"; they showed a specific example where the private version requires infinite samples to achieve the same result that a normal version achieves with one or two samples.

Summary Analogy

Think of a treasure hunt.

Normal Learning: You have a map. You walk a few steps, find a clue, and the treasure is yours. Easy.
Private Learning: You must find the treasure, but you are not allowed to let anyone know where you found the clue. The map is designed so that the clue is hidden in a massive crowd of people. To find the clue without pointing at a specific person (and revealing their location), you would have to interview every single person in the world (infinite samples) to be safe.

This paper shows that sometimes, the requirement for privacy makes a solvable puzzle completely unsolvable.

Technical Summary: "Not All Learnable Distribution Classes are Privately Learnable"

Problem Statement
The paper addresses a fundamental question in the intersection of statistical learning theory and differential privacy (DP): Is every class of distributions that is learnable in the standard (non-private) setting also learnable under the constraints of $(\varepsilon, \delta)$ -differential privacy?

While it is established that pure differential privacy ( $\varepsilon$ -DP, where $\delta=0$ ) imposes strict separations between learnable and privately learnable classes (often characterized by covering/packing numbers), the status of approximate differential privacy ( $(\varepsilon, \delta)$ -DP) remained an open question. Recent literature has produced increasingly general frameworks for private distribution learning, leading Ashtiani [Ash22] to conjecture that the answer to the above question is affirmative: that every learnable distribution class is privately learnable.

Methodology and Construction
The authors refute this conjecture by constructing a specific class of distributions, denoted as $\mathcal{H}_w$ , which serves as a counterexample. The construction utilizes a "trapdoor" mechanism involving mixtures of distributions:

The Class Structure: The class $\mathcal{H}_{w,d}$ $H_{w, d}$ consists of mixtures over $d+1$ $d + 1$ components sharing a common parameter vector $\mathbf{p} \in [0,1]^d$ $p \in [0, 1]^{d}$ .
- The "Key" Component: A binary product distribution over $\{0,1\}^d$ with mixing weight $w$ . A single sample from this component reveals information about the entire parameter vector $\mathbf{p}$ .
- The "Hard" Components: $d$ additional components, each supported on $\{\pm j\}$ for $j \in \{1, \dots, d\}$ , with mixing weight $(1-w)/d$ . A sample from any of these reveals information about only a single coordinate of $\mathbf{p}$ .
The Trapdoor: The mixing weight $w$ is set to $1/(2\alpha)$ (where $\alpha$ is the target error). This ensures the "hard" components dominate the mixture (high probability of sampling from them), while the "key" component is rare.
The Dimensionality Trick: The class $\mathcal{H}_w$ is defined as the union of these classes over all dimensions $d \ge 2$ . The construction ensures that while the dimension $d$ is not fixed a priori, the hardness of learning scales with $d$ .

Key Results and Proofs
The paper establishes a separation between non-private and private learnability for the class $\mathcal{H}_w$ with respect to Total Variation (TV) distance:

Non-Private Learnability (Finite Samples):
The authors demonstrate that $\mathcal{H}_w$ is learnable with a constant number of samples (independent of $d$ ) up to a constant error.
- Mechanism: Since the "key" component appears with probability $w$ , a non-private algorithm can collect enough samples to observe the key component. Once observed, the dimension $d$ is identified, and the parameter vector $\mathbf{p}$ can be estimated via the sample mean of the binary product distribution.
- Complexity: The sample complexity is $O(1/\alpha^3 \cdot \log(1/\beta))$ , which is constant with respect to the dimension $d$ .
Private Non-Learnability (Infinite Samples Required):
The authors prove that no $(\varepsilon, \delta)$ -DP mechanism can learn this class with the same error guarantee using a finite number of samples.
- Reduction: They construct a reduction from the problem of density estimation on $\mathcal{H}_{w,d}$ to the problem of $\ell_1$ -parameter estimation for binary product distributions.
- Lower Bound: Leveraging known lower bounds for private mean estimation of binary product distributions (specifically from [KLSU19]), they show that the sample complexity for learning $\mathcal{H}_{w,d}$ under DP scales as $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$ .
- Contradiction: Since the class $\mathcal{H}_w$ includes distributions for any $d \ge 2$ , and the required sample size grows with $\sqrt{d}$ , no finite sample size $n$ suffices to learn the entire class $\mathcal{H}_w$ under DP. As $d \to \infty$ , the required sample size approaches infinity.

Key Contributions

Refutation of Conjecture: The paper provides an explicit counterexample to Ashtiani's conjecture that every learnable distribution class is privately learnable under $(\varepsilon, \delta)$ -DP.
Separation of Learnability: It demonstrates a strict separation where a class is learnable with $O(1)$ samples non-privately but requires an infinite number of samples to learn privately.
Trapdoor Construction: The authors introduce a specific "trapdoor" construction where a rare component acts as a key to a high-dimensional parameter, which is otherwise obscured by a dominant, hard-to-learn component. This structure prevents private mechanisms from accessing the "key" without violating privacy constraints or requiring prohibitive sample sizes.

Significance and Claims
The paper claims to "weakly refute" the conjecture. The authors explicitly note that a "strong refutation" would require showing the class is learnable for any target error (not just constant error) with finite samples non-privately, which they do not prove. However, their result is significant because it shows that even for constant error guarantees, the landscape of private distribution learning is fundamentally different from non-private learning.

The work highlights that general frameworks for private learning cannot simply rely on black-box reductions from non-private learners without additional structural assumptions. It establishes that the existence of a "key" component that is rare but essential for learning can create an insurmountable barrier for private algorithms, even when the non-private algorithm is efficient.

Conclusion
The paper concludes that the agenda of designing general private learning algorithms that work for all learnable distribution classes cannot be fully realized. There exist learnable classes where the privacy constraint fundamentally alters the sample complexity from finite to infinite, regardless of the specific error tolerance (within the constant regime considered).