Private online learning and prediction for Littlestone classes

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 $\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}$.

Machine Learning (cs.LG); Cryptography and Security (cs.CR); Machine Learning (stat.ML)

arXiv:2610.06822 [cs.LG]

(or arXiv:2610.06822v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.06822 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.