# Private online learning and prediction for Littlestone classes

arXiv: https://arxiv.org/abs/2610.06822 · HTML: https://mlsanity.com/paper/2610.06822/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 13 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Abstract (arXiv)

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 (ε,δ)-private online learner has a deterministic realisable stream of length T on which the mistake bound is at least mathbb E [MT]= Oleft(frac dε log2/3 Tright). In particular, this is the first non-trivial lower in the range 1/T<δ<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 (ε,δ)-jointly private predictor with at most 2^2cd2ε-2log2(2/(εδ)) expected mistakes, independently of T, for some absolute constant c>0. Thus, for every fixed class of finite Littlestone dimension when δ=Theta(1/log T), private learning requires Oleft(log2/3 Tright) expected mistakes, whereas private prediction admits O(loglog T2).