Metraipolis › archive › dc_9bbcfe86e439

New Lower Bounds for Private PAC Learning — arXiv:2610.41980

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41980
License (as archived)
CC0-1.0
Archived
2026-11-03T05:41:02.210Z
SHA-256 of the archived text
6623da91d4c61e56fceb696e7d081bd12ded5a5ed8f8bbc2c64ff91606bf53a7
Stable URL of this page
https://metraipolis.com/documento/dc_9bbcfe86e439

How to cite

New Lower Bounds for Private PAC Learning — arXiv:2610.41980 — arXiv (en), https://arxiv.org/abs/2610.41980 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9bbcfe86e439 (Metraipolis archive dc_9bbcfe86e439, sha256 6623da91d4c61e56fceb696e7d081bd12ded5a5ed8f8bbc2c64ff91606bf53a7)
BibTeX
@misc{dc9bbcfe86e439,
  title = {New Lower Bounds for Private PAC Learning — arXiv:2610.41980},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41980},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9bbcfe86e439; sha256 6623da91d4c61e56fceb696e7d081bd12ded5a5ed8f8bbc2c64ff91606bf53a7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41980. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, \delta)$-DP, $(\alpha, \beta)$-PAC learner for $\mathcal{H}$, possibly improper, uses $\Omega\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(\alpha\varepsilon)\right)$ examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.

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.41980 — 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-11-03T05:26:25.727Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).