Private online learning and prediction for Littlestone classes

Amartya Sanyal

cs.LGOct 5, 2026

Private online learning and prediction for Littlestone classes

Authors: Amartya Sanyal

Organizations: Department of Computer Science University of Copenhagen

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{ε,δ}$ -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}$ .

Figures & tables

Result	Point domain	DP Learner	Lower bound
[ 5 ]	$\left\{{1,2,3}\right\}$	Concentrated	$\Omega\left({{\log T}}\right)$
[ 4 ]	$\left\{{0,\ldots,T}\right\}$	All	$\Omega\left({{\log T}}\right)$
[ 9 ]	$\left\{{1,2,3}\right\}$	All	$\Omega\left({{\log\log T}}\right)$
Theorem A	$\left\{{1,2,3}\right\}$	All	$\Omega\left({{\left({\log T}\right)^{2/3}}}\right)$

Table 1: Lower bounds for expected total mistakes of private online learners on

\mathrm{POINT}_{3}

\delta=1/(\log T)

. [ 5 , 9 ] ’s results also extend to other Littlestone classes. [ 4 ] considers point functions on

\left\{{0,\ldots,T}\right\}

, a domain that grows with

T

. The [ 9 ] entry follows by setting

T^{\prime}=\left\lfloor\varepsilon\log T\right\rfloor

, applying their theorem to the first

T^{\prime}

rounds, and filling the remaining rounds with dummy points.

Panel of Figure 1 — Figure 1: Expected total mistakes ${\mathbb{E}}\left[{M_{T}}\right]$ for $\mathrm{POINT}_{3}$ at $\varepsilon=1/100$ . Solid curves are upper bounds and dashed curves are lower bounds; grey shading marks the open gap.

Panel of Figure 2 — Figure 2: In (a), we recurse inside a uniformly chosen third. If we choose the middle third, we insert an informative example at a uniformly random position in the first third with probability $p$ ; otherwise, we make no insertion. In (b), we compare this insertion with a counterfactual insertion in the last third. The first may affect the middle-third predictions (vertical marks), whereas the counterfactual insertion cannot, since those predictions are made before the example arrives.

Panel of Figure 3 — Figure 3: A shattered Littlestone tree with $d-1$ hard blocks along a root-to-leaf path after the initial zero edge. Each block applies the $\mathrm{POINT}_{3}$ construction from Theorem 1 using the parent point $x_{i}$ as its informative point and $x_{0}$ as its shared dummy. The point $z_{i}$ is the unused third point of this construction and never appears in the stream (as in Theorem 1 ). The informative label $B$ is the label of the edge.

Panel of Figure 4 — Figure 4: ${\mathcal{S}}_{i}$ collects group $i$ ’s retained samples. Each mistake batch contributes one coloured oval (denoted $A$ ) of $\leq n$ points. $\operatorname{err}_{A}(h)$ is the mistake count on $A$ , divided by $n$ . The list $C_{p}(G_{i})$ contains the essential hypotheses of $G_{i}$ .

Explore similar work

Private Component-by-Component Learning
Oct 4, 2026Dvir Karni, Eliad TsfadiaLearnability
Department of Computer Science and Artificial Intelligence, Bar-Ilan University.
Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning
May 27, 2026Tommaso Cesari, Roberto ColomboniOptimal Regret Standard Differential-Privacy
School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom
Certification-Based Differentially Private Learning
Sep 30, 2026Mihnea Ghitu, Matthew WickerLearn
Department of Computing Imperial College London London, United Kingdom

Oct 4, 2026, cs.LGJ/K move · Enter open · S save

Private Component-by-Component Learning

Dvir Karni, Eliad Tsfadia

Department of Computer Science and Artificial Intelligence, Bar-Ilan University.

Learnability

Open paper AskPDF arXiv

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by

k

components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy

\varepsilon

, pays only

\widetilde O(\sqrt{k}/\varepsilon)

overhead relative to the active sample requirement of a single component learning step at target accuracy

Θ(α/k)

. For learning

d

-dimensional halfspaces over a finite coordinate grid of size

L

, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of

\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right),

which improves on the previously known bound of

\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot\min\{\frac{1}α\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right).

We also apply the framework to Boolean compositions: given proper private learners for classes

H_1,\ldots,H_k

, we obtain a proper private learner for

G(H_1,\ldots,H_k)

for any fixed Boolean function

G:\{0,1\}^k\to\{0,1\}

. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from

\widetilde O(k/\varepsilon)

\widetilde O(\sqrt{k}/\varepsilon)

Abstract

Explore similar work

Private Component-by-Component Learning

Optimal Gap-Dependent Regret for Private Stochastic Decision-Theoretic Online Learning

Certification-Based Differentially Private Learning