# Optimal Randomized Proper Online Learning

arXiv: https://arxiv.org/abs/2609.21445 · HTML: https://mlsanity.com/paper/2609.21445/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 18 Sep 2026.

## Builds on (most cited first, 9 of 9)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games](https://mlsanity.com/paper/2111.08911/) (2021)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)

## Abstract (arXiv)

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