Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
Authors:
Preprint
Abstract
A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class $\mathcal{H}$ equals its randomized Littlestone dimension, which is the largest $d$ for which there exists a tree shattered by $\mathcal{H}$ whose average depth is $2d$. We further study optimal mistake bounds in the agnostic case, as a function of the number of mistakes made by the best function in $\mathcal{H}$, denoted by $k$. We show that the optimal randomized mistake bound for learning a class with Littlestone dimension $d$ is $k + \Theta (\sqrt{k d} + d )$. This also implies an optimal deterministic mistake bound of $2k + O (\sqrt{k d} + d )$, thus resolving an open question which was studied by Auer and Long ['99]. As an application of our theory, we revisit the classical problem of prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth studied prediction using expert advice, provided that the best among the $n$ experts makes at most $k$ mistakes, and asked what are the optimal mistake bounds. Cesa-Bianchi, Freund, Helmbold, and Warmuth ['93, '96] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this question by providing an optimal learning rule in the randomized case, and showing that its expected mistake bound equals half of the deterministic bound, up to negligible additive terms. This improves upon previous works by Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth ['93, '97], by Abernethy, Langford, and Warmuth ['06], and by Br\^anzei and Peres ['19], which handled the regimes $k \ll \log n$ or $k \gg \log n$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Optimal Prediction Using Expert Advice and Randomized Littlestone DimensionSIAM Journal on Computing, 2025
- Private and Online Learnability Are EquivalentJournal of the ACM, 2022
- Active Classification with Comparison Queries2017
- Sample Complexity Bounds on Differentially Private Learning via Communication ComplexitySIAM Journal on Computing, 2015
- Characterizing the sample complexity of private learners2013
- Online Learning and Online Convex OptimizationFoundations and Trends in Machine Learning, 2012
- Learning with continuous experts using drifting gamesTheoretical Computer Science, 2010
- Structural Results About On-line Learning Models With and Without QueriesMachine Learning, 1999
- A Decision-Theoretic Generalization of On-Line Learning and an Application to BoostingJournal of Computer and System Sciences, 1997
- Learnability and the Vapnik-Chervonenkis dimensionJournal of the ACM, 1989