Abstract

We study the online learnability of hypothesis classes with respect toarbitrary, but bounded loss functions. No characterization of onlinelearnability is known at this level of generality. We give a newscale-sensitive combinatorial dimension, named the sequential minimaxdimension, and show that it gives a tight quantitative characterization ofonline learnability. In addition, we show that the sequential minimax dimensionsubsumes most existing combinatorial dimensions in online learning theory.

 

Quick Read (beta)