A Combinatorial Characterization of Supervised Online Learnability

  • 2024-02-09 18:27:51
  • Vinod Raman, Unique Subedi, Ambuj Tewari
  • 0


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)

loading the full paper ...