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

Oct 4, 2026cs.LG

Private Component-by-Component Learning

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)

Dvir Karni, Eliad Tsfadia

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

Learnability

Ask PDF

May 27, 2026cs.LG

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

We study stochastic decision-theoretic online learning with full information and event-level pure differential privacy. A COLT open problem of Hu and Mehta asks to determine the optimal gap-dependent regret rate for stochastic decision-theoretic online learning under pure event-level differential privacy. For

K

actions, losses in

[0,1]

, and a unique best action separated from the second-best action by gap

Δ_{\min}

, the known lower bound is of order

\frac{\log K}{\min\{Δ_{\min},\varepsilon\}},

or equivalently, up to universal constants, of order

\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}.

We give a horizon-free pure-DP algorithm and prove the explicit regret bound

\operatorname{Reg}_T \le 1000 \cdot \left(\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}\right)

for every horizon

T

. The numerical constant is not optimized. The algorithm partitions time into blocks of exponentially increasing size, plays a single action throughout each block, and chooses the next action by an exponential mechanism applied to a data-independent random prefix of the previous block. The random prefix converts block regret into a sum, over all prefix lengths, of softmax selection errors. A single entropy-potential argument controls all privacy-dominated large-gap actions at cost

\log K/\varepsilon

Tommaso Cesari, Roberto Colomboni

School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom

Optimal Regret Standard Differential-Privacy Learning-Augmented Algorithms Optimal Learner

Ask PDF

Sep 30, 2026cs.LG

Certification-Based Differentially Private Learning

Differential privacy (DP) in machine learning is typically achieved by adding noise to model parameters (private learning) or to model outputs (private prediction). Recent work uses formal methods, namely abstract interpretation, to provide tighter privacy guarantees, but only for private prediction in classification settings. In this work, we investigate the use of formal methods as a general tool for tighter privacy analysis. First, we generalize the abstract gradient training (AGT) framework to private prediction in continuous, unbounded regression. Second, by reducing learning in parameterized models to a regression problem over the parameter space, we introduce Abstract Gradient Sampling (AGS), an algorithm that enables reachability-based analysis to provide guarantees for private learning. In both private prediction and private learning, we provide tightened privacy accounting for the AGT framework and a theoretical analysis demonstrating when our smooth sensitivity upper-bounds yield favourable privacy-utility trade-off. In practice, we validate that our regression bounds are tighter than global-sensitivity baselines on regression benchmarks, and, notably, yield the first finite privacy guarantees in settings where global prediction sensitivity is a priori unbounded. We also find that under matched conditions, our private learning algorithm can outperform standard private learners.

Mihnea Ghitu, Matthew Wicker

Department of Computing Imperial College London London, United Kingdom

Learn

Ask PDF