Does differential privacy make PAC learning much harder?

Without privacy, the number of examples needed to learn a class of binary classifiers is governed by its VC dimension. Under differential privacy, what can be learned at all is governed by the Littlestone dimension, which can be far larger, and the known bounds on the number of examples are a tower of exponentials apart. How much data does privacy really cost?

Problem

Let $C$ be a class of functions $X \to \{0,1\}$. A learner receives $n$ examples $(x_i, c(x_i))$, where the $x_i$ are drawn independently from an unknown distribution and $c \in C$ is unknown, and must output a hypothesis whose error is at most $\alpha$ with probability at least $1-\beta$ (realizable PAC learning). The learner $A$ is $(\varepsilon,\delta)$-differentially private if for every two datasets $S, S'$ that differ in one example and every set $E$ of outputs,

$$\Pr[A(S) \in E] \le e^{\varepsilon} \Pr[A(S') \in E] + \delta .$$

The usual regime is $\varepsilon$ a small constant and $\delta$ much smaller than $1/n$. Write $m_{\mathrm{DP}}(C)$ for the least $n$ for which a private learner exists, treating $\alpha, \beta, \varepsilon$ as constants. Let $\mathrm{VC}(C)$ be the VC dimension and $\mathrm{LD}(C)$ the Littlestone dimension, the optimal mistake bound for learning $C$ online; always $\mathrm{VC}(C) \le \mathrm{LD}(C)$.

Question 1. Find a combinatorial parameter of $C$ that determines $m_{\mathrm{DP}}(C)$, as the VC dimension does without privacy. A concrete step: prove that $m_{\mathrm{DP}}(C) \le \mathrm{poly}(\mathrm{VC}(C), \log^{*} \mathrm{LD}(C))$ for every class, or even $\mathrm{poly}(\mathrm{VC}(C), \log \mathrm{LD}(C))$.

Question 2. Is there a sequence of finite classes $C_\kappa$ with $|C_\kappa| \to \infty$, $\log |C_\kappa|$ superpolynomial in $\mathrm{VC}(C_\kappa)$, and $m_{\mathrm{DP}}(C_\kappa) = \Omega(\log |C_\kappa|)$?

Background

In Valiant's PAC model, $\Theta(\mathrm{VC}(C))$ examples are necessary and sufficient. Private learning was introduced by Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, who showed that every finite class can be learned privately from $O(\log |C|)$ examples [4]. Alon, Livni, Malliaris and Moran [2] and Bun, Livni and Moran [3] then proved that a class is privately learnable if and only if its Littlestone dimension is finite, which ties private learning to online learning. Thresholds on the real line show how large the gap can be: their VC dimension is 1 and their Littlestone dimension is infinite. Nissim, Stemmer and Tsfadia posed the quantitative question as an invited open problem at COLT 2026 [1].

What is known

• Lower bound. Every private learner needs $\Omega(\mathrm{VC}(C) + \log^{*} \mathrm{LD}(C))$ examples (Alon et al., 2019) [2].
• Upper bounds in terms of $d = \mathrm{LD}(C)$. Doubly exponential in $d$ (Bun, Livni and Moran, 2020) [3]; $\widetilde O(d^6)$ (Ghazi, Golowich, Kumar and Manurangsi, 2021); $\widetilde O(d^5)$ (Lyu, STOC 2026) [5]; and $O(d \log d)$ in an unrefereed preprint of October 2026 (Moran and Yan) [6]. Against the $\log^{*}$ lower bound this still leaves a tower-of-exponentials gap.
• Specific classes. Thresholds over a finite domain need only $\widetilde O(\log^{*} \mathrm{LD})$ examples (Cohen, Lyu, Nelson, Sarlós and Stemmer, 2023), and classes of VC dimension 1 are essentially characterized by $\log^{*} \mathrm{LD}$ (Yan, 2025). Axis-aligned rectangles need $\widetilde O(\mathrm{VC} \cdot \log^{*} \mathrm{LD})$ examples (Sadigurschi and Stemmer, 2021; Cohen et al., 2023), and halfspaces $\widetilde O(\mathrm{VC}^{5.5} \cdot \log^{*} \mathrm{LD})$ (Nissim, Tsfadia and Yan, 2026); see the survey in [1].
• In every class studied so far, privacy costs a polynomial in the VC dimension times a very slowly growing function of the Littlestone dimension. No class is known to need even $\Omega(\mathrm{VC}(C) \cdot 2^{\log^{*} \mathrm{LD}(C)})$ examples.

What would count as progress

• A private learner for every class with sample complexity $\mathrm{poly}(\mathrm{VC}(C), \log \mathrm{LD}(C))$, with a proof; the posers describe even this as major progress.
• A family of classes with $\log |C_\kappa|$ superpolynomial in $\mathrm{VC}(C_\kappa)$ and a proof that private learning needs $\Omega(\log |C_\kappa|)$ examples. A first step would be private sample complexity provably closer to $\log |C|$ than to $\mathrm{VC}(C)$ on a logarithmic scale.
• Any explicit class with a proof that it needs $\Omega(\mathrm{VC}(C) \cdot 2^{\log^{*} \mathrm{LD}(C)})$ examples.

References

1. K. Nissim, U. Stemmer and E. Tsfadia, Invited open problem: Does differential privacy make PAC learning much harder?, COLT 2026, PMLR 336 (2026), 7129–7135. PMLR
2. N. Alon, R. Livni, M. Malliaris and S. Moran, Private PAC learning implies finite Littlestone dimension, STOC (2019), 852–860. doi:10.1145/3313276.3316312
3. M. Bun, R. Livni and S. Moran, An equivalence between private classification and online prediction, FOCS (2020), 389–402. arXiv:2003.00563
4. S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova and A. Smith, What can we learn privately?, SIAM J. Comput. 40(3) (2011), 793–826. doi:10.1137/090756090
5. X. Lyu, Private learning of Littlestone classes, revisited, STOC (2026). arXiv:2510.00076
6. S. Moran and C. Yan, Nearly linear private learning of Littlestone classes, preprint (2026). arXiv:2610.23160

Source

Imported from COLT open problems, COLT 2026, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.