Optimal Randomized Proper Online Learning

Zachary Chase; Idan Mehalel

cs.LGSep 18, 2026

Optimal Randomized Proper Online Learning

Authors: Zachary Chase, Idan Mehalel

Organizations: Rutgers University · The Hebrew University

Abstract

We prove that the optimal expected mistake bound of online learning a function class $\mathcal{H}$ by a randomized proper learning algorithm is $O(\mathtt{L}(\mathcal{H}) \log T)$ , where $\mathtt{L}(\mathcal{H})$ is the Littlestone dimension of $\mathcal{H}$ and $T$ is the time horizon. Our result improves upon the previously best known bound of $O(\mathtt{L}(\mathcal{H}) \log^6 T)$ given by Daskalakis and Golowich (STOC 2022), and is optimal up to a universal constant for worst-case classes.

Figures & tables

Bound	Comments	References
$\tilde{O}\sqrt{\mathtt{L}(\mathcal{H})T}$	Agnostic regret bound	[ 16 , 11 ]
$O(\mathtt{L}(\mathcal{H})\log^{6}T)$		[ 7 ]
$O(\mathtt{L}(\mathcal{H})\log T)$		[this work]
$\geq\mathtt{L}(\mathcal{H})$		[ 14 ]
$\Omega(\mathtt{L}(\mathcal{H})\log T)$	$\forall\mathtt{L}(\mathcal{H})$ , $\exists\mathcal{H}$	[this work]

Table 1: Summary of previous and current bounds for proper online learning. The lower bounds hold for any large enough

T

. The comment in the last row means that for any

d\in\mathbb{N}

there exists a class

\mathcal{H}

with

\mathtt{L}(\mathcal{H})=O(d)

for which the lower bound holds. That is, the lower bound does not hold for all

\mathcal{H}

. This is not an artifact of the lower bound’s proof: it is not hard to find classes for which the optimal proper mistake bound is

\mathtt{L}(\mathcal{H})

, even using a deterministic proper learner.

Panel of Figure 1 — Figure 1: Main algorithm

Panel of Figure 2 — Figure 2: Leaf splitting algorithm

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 131 papers

Private online learning and prediction for Littlestone classes
Oct 5, 2026Amartya SanyalPrivacy-Preserving ML Differential Privacy
Department of Computer Science University of Copenhagen
Optimal Multiclass Online Regret with Arbitrary Label Spaces
Oct 23, 2026Sajad Ashkezari, Shai Ben-DavidMulticlass Classification Statistical Learning Theory
University of Waterloo
Robust Learning with Optimal Error
Apr 2, 2026Guy BlancAgnostic Learning Robust Classification
Stanford

Oct 5, 2026J/K move · Enter open · S save

Private online learning and prediction for Littlestone classes

Amartya Sanyal

Department of Computer Science University of Copenhagen

Privacy-Preserving ML Differential Privacy

Open paper AskPDF arXiv

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

\mathbb E [M_T]= O\left(\frac dε\log^{2/3} T\right)

. 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(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\left(\log^{2/3} T\right)

expected mistakes, whereas private prediction admits

O(\log\log T^2)

Abstract

Online Learning

Explore similar work

Private online learning and prediction for Littlestone classes

Optimal Multiclass Online Regret with Arbitrary Label Spaces

Robust Learning with Optimal Error