Optimal Randomized Proper Online Learning
Not on the map. Why?
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.
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
9 of 19 references.
References · 9
- 2015The Optimal Sample Complexity of PAC Learningcited by 72
- 2014Optimal Learners for Multiclass Problemscited by 65
- 2020Proper Learning, Helly Number, and an Optimal SVM Boundcited by 53
- 2021Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Gamescited by 18
- 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
- 2024Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffscited by 9
- 2024Bounds on the price of feedback for mistake-bounded online learningcited by 4
- 2024Deterministic Apple Tastingcited by 4
- 2026Learning from Equivalence Queries, Revisitedcited by 2
Built on by
Not cited yet.