Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?

Kobbi Nissim, Uri Stemmer, Eliad Tsfadia
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:7129-7135, 2026.

Abstract

What is the optimal sample complexity of differentially private (DP) PAC learning? Recent results establish that a concept class $C$ is learnable under approximate DP if and only if it is online learnable. However, in any realistic computational model, $C$ is finite, and it is well known that a sample complexity of $O(\log |C|)$ suffices for both online and DP learning. In contrast, non-private learning is characterized by the VC dimension of $C$, which can be significantly lower than $\log |C|$. While the gap between $\log |C|$ and $\text{VC}(C)$ can be unavoidable for online learning (e.g., when learning thresholds over a finite domain), we currently lack evidence that the same holds true for DP learning. This leads to our central question: Is differentially private PAC learning much harder than non-private learning?

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-nissim26a, title = {Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?}, author = {Nissim, Kobbi and Stemmer, Uri and Tsfadia, Eliad}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {7129--7135}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/nissim26a/nissim26a.pdf}, url = {https://proceedings.mlr.press/v336/nissim26a.html}, abstract = { What is the optimal sample complexity of differentially private (DP) PAC learning? Recent results establish that a concept class $C$ is learnable under approximate DP if and only if it is online learnable. However, in any realistic computational model, $C$ is finite, and it is well known that a sample complexity of $O(\log |C|)$ suffices for both online and DP learning. In contrast, non-private learning is characterized by the VC dimension of $C$, which can be significantly lower than $\log |C|$. While the gap between $\log |C|$ and $\text{VC}(C)$ can be unavoidable for online learning (e.g., when learning thresholds over a finite domain), we currently lack evidence that the same holds true for DP learning. This leads to our central question: Is differentially private PAC learning much harder than non-private learning? } }
Endnote
%0 Conference Paper %T Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder? %A Kobbi Nissim %A Uri Stemmer %A Eliad Tsfadia %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-nissim26a %I PMLR %P 7129--7135 %U https://proceedings.mlr.press/v336/nissim26a.html %V 336 %X What is the optimal sample complexity of differentially private (DP) PAC learning? Recent results establish that a concept class $C$ is learnable under approximate DP if and only if it is online learnable. However, in any realistic computational model, $C$ is finite, and it is well known that a sample complexity of $O(\log |C|)$ suffices for both online and DP learning. In contrast, non-private learning is characterized by the VC dimension of $C$, which can be significantly lower than $\log |C|$. While the gap between $\log |C|$ and $\text{VC}(C)$ can be unavoidable for online learning (e.g., when learning thresholds over a finite domain), we currently lack evidence that the same holds true for DP learning. This leads to our central question: Is differentially private PAC learning much harder than non-private learning?
APA
Nissim, K., Stemmer, U. & Tsfadia, E.. (2026). Invited Open Problem: Does Differential Privacy Make PAC Learning Much Harder?. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:7129-7135 Available from https://proceedings.mlr.press/v336/nissim26a.html.

Related Material