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 (ε,δ)-private online learner has a deterministic realisable stream of length T on which the mistake bound is at least 𝔼 [MT]= O(d/εlog2/3 T). 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 22cd2ε−2log2(2/(εδ)) expected mistakes, independently of T, for some absolute constant c>0. Thus, for every fixed class of finite Littlestone dimension when δ=Θ(1/log T), private learning requires O(log2/3 T) expected mistakes, whereas private prediction admits O(loglog T2).
Related
- Private Online Prediction from Experts with Small Losses
- Understanding Private Evolution as Learning-Augmented Clustering
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- When to spend privacy: optimal allocation in private learning
BibTeX
@misc{sanyal2026private,
title = {{Private online learning and prediction for Littlestone classes}},
author = {Amartya Sanyal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06822},
eprint = {2610.06822},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06822},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Private online learning and prediction for Littlestone classes
AU - Amartya Sanyal
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06822
UR - https://arxiv.org/abs/2610.06822
AB - 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 (ε,δ)-private online learner has a deterministic realisable stream of length T on which the mistake bound is at least 𝔼 [M_T]= O(d/εlog^2/3 T). 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ε^−2log^2(2/(εδ)) expected mistakes, independently of T, for some absolute constant c>0. Thus, for every fixed class of finite Littlestone dimension when δ=Θ(1/log T), private learning requires O(log^2/3 T) expected mistakes, whereas private prediction admits O(loglog T^2).
ER -