Research
Private online learning and prediction for Littlestone classes
arXiv:2610.06822v1 Announce Type: new Abstract: We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning require
arXiv:2610.06822v1 Announce Type: new Abstract: 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 r{epsilon,elta}-private online learner has a deterministic realisable stream of length T on which the mistake bound is at least Es{M_T}=Om{frac depsilon logr{ T}^{2/3}}. In particular, this is the first non-trivial lower in the range 1/T0. Thus, for every fixed class of finite Littlestone dimension when elta=Thetar{1/log T}, private learning requires Om{r{log T}^{2/3}} expected mistakes, whereas private prediction admits igO{r{loglog T}^2}.
Related
Source: arXiv cs.LG | 2026-10-06