A Combinatorial Characterization of Supervised Online Learnability
This work addresses a foundational gap in online learning theory by providing a general characterization, which is significant for researchers in machine learning theory.
The paper tackles the problem of characterizing online learnability for arbitrary bounded loss functions, introducing the sequential minimax dimension as a new combinatorial dimension that provides a tight quantitative characterization and subsumes most existing dimensions in the field.
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.