Finite Littlestone Dimension Implies Finite Information Complexity
This addresses a theoretical problem in online learning for researchers, providing incremental advances in understanding complexity bounds.
The paper tackles the problem of online learnable classes with finite Littlestone dimension by proving they admit learning algorithms with finite information complexity, achieving bounds roughly exponential in dimension d, and showing improvement to logarithmic bounds for a canonical class.
We prove that every online learnable class of functions of Littlestone dimension $d$ admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of such a globally stable algorithm is large yet finite, roughly exponential in $d$. We also show there is room for improvement; for a canonical online learnable class, indicator functions of affine subspaces of dimension $d$, the information complexity can be upper bounded logarithmically in $d$.