Metraipolis › archive › dc_bc24537e01be

Private online learning and prediction for Littlestone classes — arXiv:2610.06822

Source
arXiv
Original
https://arxiv.org/abs/2610.06822
License (as archived)
CC0-1.0
Archived
2026-10-06T05:30:03.558Z
SHA-256 of the archived text
2d27b161023e8cac122254afee237e3200d6f0820b919e25a2fdb78c3985a15e
Stable URL of this page
https://metraipolis.com/documento/dc_bc24537e01be

How to cite

Private online learning and prediction for Littlestone classes — arXiv:2610.06822 — arXiv, https://arxiv.org/abs/2610.06822 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc24537e01be (Metraipolis archive dc_bc24537e01be, sha256 2d27b161023e8cac122254afee237e3200d6f0820b919e25a2fdb78c3985a15e)
BibTeX
@misc{dcbc24537e01be,
  title = {Private online learning and prediction for Littlestone classes — arXiv:2610.06822},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.06822},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc24537e01be; sha256 2d27b161023e8cac122254afee237e3200d6f0820b919e25a2fdb78c3985a15e},
  year = {2026}
}

Archived text

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

We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension $d$. First, we prove that every $\br{\epsilon,\delta}$-private online learner has a deterministic realisable stream of length $T$ on which the mistake bound is at least $\bE\bs{M_T}=\Om{\frac d\epsilon \log\br{ T}^{2/3}}$. In particular, this is the first non-trivial lower in the range $1/T<\delta<1/\log T)$ left open in earlier works[SR22,DSS24,LWY24]. Second, we prove that for every class of of Littlestone dimension $d$, there exists an $(\epsilon,\delta)$-jointly private predictor with at most $2^{2^{cd^2}}\epsilon^{-2}\log^2\br{2/\br{\epsilon\delta}}$ expected mistakes, independently of $T$, for some absolute constant $c>0$. Thus, for every fixed class of finite Littlestone dimension when $\delta=\Theta\br{1/\log T}$, private learning requires $\Om{\br{\log T}^{2/3}}$ expected mistakes, whereas private prediction admits $\bigO{\br{\log\log T}^2}$.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Cryptography and Security (cs.CR); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.06822 — 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-06T05:26:35.393Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).