Metraipolis › archive › dc_ecfadd1b75ab
Nearly Linear Private Learning of Littlestone Classes — arXiv:2610.23160
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.23160
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T08:48:38.228Z
- SHA-256 of the archived text
7a3055e3762e914c00b8d8e60d1308c82562abfa046b30cab2c58b839ffd37e3- Stable URL of this page
https://metraipolis.com/documento/dc_ecfadd1b75ab
How to cite
Nearly Linear Private Learning of Littlestone Classes — arXiv:2610.23160 — arXiv (en), https://arxiv.org/abs/2610.23160 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ecfadd1b75ab (Metraipolis archive dc_ecfadd1b75ab, sha256 7a3055e3762e914c00b8d8e60d1308c82562abfa046b30cab2c58b839ffd37e3)
BibTeX
@misc{dcecfadd1b75ab,
title = {Nearly Linear Private Learning of Littlestone Classes — arXiv:2610.23160},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.23160},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ecfadd1b75ab; sha256 7a3055e3762e914c00b8d8e60d1308c82562abfa046b30cab2c58b839ffd37e3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23160. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno). Categorie arXiv: Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2610.23160 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T08:42:40.262Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).