Majorizing Measures, Sequential Complexities, and Online Learning
This work resolves several open problems in extending empirical process theory to the sequential case, providing sharp results for online learning researchers.
This paper introduces generic chaining and majorizing measures to control sequential Rademacher complexity. It establishes a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension, and a tight contraction inequality for this complexity.
We introduce the technique of generic chaining and majorizing measures for controlling sequential Rademacher complexity. We relate majorizing measures to the notion of fractional covering numbers, which we show to be dominated in terms of sequential scale-sensitive dimensions in a horizon-independent way, and, under additional complexity assumptions establish a tight control on worst-case sequential Rademacher complexity in terms of the integral of sequential scale-sensitive dimension. Finally, we establish a tight contraction inequality for worst-case sequential Rademacher complexity. The above constitutes the resolution of a number of outstanding open problems in extending the classical theory of empirical processes to the sequential case, and, in turn, establishes sharp results for online learning.