Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes a fundamental separation in sample complexity between differentially private online learning and online prediction for Littlestone classes. It achieves this by deriving a novel $\Omega(\frac{d}{\epsilon}\log^{2/3} T)$ lower bound for private online learning and a $O(2^{2^{cd^2}}\epsilon^{-2}\log^2(1/(\epsilon\delta)))$ upper bound for private prediction. The findings demonstrate that for finite Littlestone dimension classes, private prediction can achieve significantly fewer mistakes than private learning as the time horizon $T$ grows.
Private prediction can achieve logarithmic dependence on the time horizon, while private learning requires polynomial dependence, revealing a fundamental gap in their sample complexity for differentially private settings.
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{ε,δ}$-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ε\log\br{ T}^{2/3}}$. 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^{2^{cd^2}}ε^{-2}\log^2\br{2/\br{εδ}}$ expected mistakes, independently of $T$, for some absolute constant $c>0$. Thus, for every fixed class of finite Littlestone dimension when $δ=Θ\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}$.