A Combinatorial Characterization of Supervised Online Learnability
Not on the map. Why?
Abstract (arXiv)
We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No characterization of online learnability is known at this level of generality. We give a new scale-sensitive combinatorial dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability. In addition, we show that the sequential minimax dimension subsumes most existing combinatorial dimensions in online learning theory.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 3 of its 19 references that are in the map. First posted on arXiv 7 Jul 2023.
Builds on
3 of 19 references.
References · 3
- 2023Multiclass Online Learning and Uniform Convergencecited by 19
- 2023Optimal Prediction Using Expert Advice and Randomized Littlestone Dimensioncited by 18
- 2023Online Learning with Set-Valued Feedbackcited by 7
Built on by
Not cited yet.