Online Learning via Sequential Complexities
  We consider the problem of sequential prediction and provide tools to study
the minimax value of the associated game. Classical statistical learning theory
provides several useful complexity measures to study learning with i.i.d. data.
Our proposed sequential complexities can be seen as extensions of these
measures to the sequential setting. The developed theory is shown to yield
precise learning guarantees for the problem of sequential prediction. In
particular, we show necessary and sufficient conditions for online learnability
in the setting of supervised learning. Several examples show the utility of our
framework: we can establish learnability without having to exhibit an explicit
online learning algorithm.
