OP-00299 Open

Private PAC learning with polynomial VC and iterated-logarithm sample cost

Let $X$ be a finite nonempty set and $\varnothing \ne \mathcal C \subseteq \{0,1\}^X$ a concept class with VC dimension $v \ge 1$ and Littlestone dimension $d$. For an integer $n \ge 1$, call a randomized learner $A : (X \times \{0,1\})^n \to \{0,1\}^X$, which may depend on $\mathcal C$, admissible if:

for every probability distribution $D$ on $X$ and every $c \in \mathcal C$, given $S = ((x_1, c(x_1)), \dots, (x_n, c(x_n)))$ with $x_1, \dots, x_n$ independent and distributed as $D$, the output $h = A(S)$ satisfies $$\Pr_{S, A}\Bigl[ \Pr_{x \sim D}\{h(x) \ne c(x)\} \le \tfrac{1}{16} \Bigr] \ge \tfrac{15}{16};$$
for all $S, S' \in (X \times \{0,1\})^n$ differing in one labelled record, including samples not realised by $\mathcal C$, and every $E \subseteq \{0,1\}^X$, $$\Pr[A(S) \in E] \le e^{0.1} \Pr[A(S') \in E] + \frac{1}{100 n^3}.$$

The output may lie outside $\mathcal C$, and running time is unrestricted. Let $m_{\mathrm{priv}}(\mathcal C)$ be the least $n$ for which an admissible learner exists, and let $\log_2^* t$ be the number of times $\log_2$ must be iterated to bring $t$ to at most $1$.

Ignoring the dependence on the accuracy and privacy parameters, every private learner for $\mathcal C$ needs $\Omega(\log^* d)$ samples (Alon, Livni, Malliaris and Moran), besides the $\Omega(v)$ samples needed without privacy, and $\tilde O(d^5)$ samples suffice (Lyu, improving a polynomial bound of Ghazi, Golowich, Kumar and Manurangsi). For $v = 1$, Yan gave a private learner with $\tilde O(\log^* d)$ samples.

Problem. Are there universal constants $K > 0$ and $q \in \mathbb N$, $q \ge 1$, such that $$m_{\mathrm{priv}}(\mathcal C) \le K \bigl(1 + v + \log_2^*(\max\{2, d\})\bigr)^q$$ for every finite nonempty set $X$ and every such class $\mathcal C$?

Source: Alon, Bun, Livni, Malliaris and Moran (2022), §6, first question; Nissim, Stemmer and Tsfadia (2026), §2, after Open Question 1. Stated by AIM — Open Applied Problems for finite domains with fixed accuracy, confidence and privacy parameters.

Imported from github.com/MColbrook/AIM.

Classification

Primary: ST — Statistics Theory
Secondary: CO
Keywords: AIM Open Applied Problems, differential privacy, Littlestone dimension, PAC learning

References

@article{alon2022,
  author  = {Alon, Noga and Bun, Mark and Livni, Roi and Malliaris, Maryanthe and Moran, Shay},
  title   = {Private and online learnability are equivalent},
  journal = {J. ACM},
  volume  = {69},
  number  = {4},
  year    = {2022},
  pages   = {28:1--28:34},
  doi     = {10.1145/3526074},
}
@inproceedings{nissim2026,
  author    = {Nissim, Kobbi and Stemmer, Uri and Tsfadia, Eliad},
  title     = {Invited open problem: does differential privacy make {PAC} learning much harder?},
  booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory},
  series    = {Proc. Mach. Learn. Res.},
  volume    = {336},
  publisher = {PMLR},
  year      = {2026},
  pages     = {7129--7135},
  url       = {https://proceedings.mlr.press/v336/nissim26a.html},
}
@inproceedings{alon2019,
  author        = {Alon, Noga and Livni, Roi and Malliaris, Maryanthe and Moran, Shay},
  title         = {Private {PAC} learning implies finite {L}ittlestone dimension},
  booktitle     = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)},
  publisher     = {ACM},
  address       = {New York},
  year          = {2019},
  pages         = {852--860},
  doi           = {10.1145/3313276.3316312},
  eprint        = {1806.00949},
  archivePrefix = {arXiv},
}
@inproceedings{ghazi2021,
  author        = {Ghazi, Badih and Golowich, Noah and Kumar, Ravi and Manurangsi, Pasin},
  title         = {Sample-efficient proper {PAC} learning with approximate differential privacy},
  booktitle     = {Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)},
  publisher     = {ACM},
  address       = {New York},
  year          = {2021},
  pages         = {183--196},
  doi           = {10.1145/3406325.3451028},
  eprint        = {2012.03893},
  archivePrefix = {arXiv},
}
@misc{lyu2025,
  author        = {Lyu, Xin},
  title         = {Private learning of {L}ittlestone classes, revisited},
  year          = {2025},
  eprint        = {2510.00076},
  archivePrefix = {arXiv},
}
@misc{yan2025,
  author        = {Yan, Chao},
  title         = {An {$\tilde{O}$}ptimal differentially private learner for concept classes with {VC} dimension 1},
  year          = {2025},
  eprint        = {2505.06581},
  archivePrefix = {arXiv},
}
@misc{aim-private-pac-vc-logstar,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Private PAC learning with polynomial VC and iterated-logarithm sample cost}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/343-private-pac-vc-logstar.md},
  note         = {Entry 343 at commit a153f46, 2026-10-13},
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00299, "Private PAC learning with polynomial VC and iterated-logarithm sample cost", clopen.solutions.