The study of prediction within the realm of Statistical Learning Theory is intertwined with the study of the supremum of an empirical process. The supremum can be analyzed with classical tools: Vapnik‐Chervonenkis and scale‐sensitive combinatorial dimensions, covering and packing numbers, and Rademacher averages. Consistency of empirical risk minimization is known to be closely related to the uniform Law of Large Numbers for function classes.

In contrast to the i.i.d. scenario, in the sequential prediction framework we are faced with an individual sequence of data on which we place no probabilistic assumptions. The problem of universal prediction of such deterministic sequences has been studied within Statistics, Information Theory, Game Theory, and Computer Science. However, general tools for analysis have been lacking, and most results have been obtained on a case‐by‐ case basis.

In this talk, we show that the study of sequential prediction is closely related to the study of the supremum of a certain dyadic martingale process on trees. We develop analogues of the Rademacher complexity, covering numbers and scale‐sensitive dimensions, which can be seen as temporal generalizations of the classical results. The complexities we define also ensure uniform convergence for non‐i.i.d. data, extending the Glivenko‐ Cantelli type results. Analogues of local Rademacher complexities can be employed for obtaining fast rates and developing adaptive procedures. Our understanding of the inherent complexity of sequential prediction is complemented by a recipe that can be used for developing new algorithms.

This is joint work with Karthik Sridharan and Ambuj Tewari.