Littlestone Dimension
A combinatorial dimension characterizing the complexity of a concept class in online learning theory. It equals the length of the longest sequence that is mistakenly classified and determines the regret bound of online learning.
Timeline (last 90 days)
For language classes with finite Littlestone dimension d, the authors obtain the mistake bound in the realizable setting: O(d log(1+T/d)).
The Littlestone dimension is a combinatorial quantity measuring the online learning complexity of a binary concept class, defined as the maximum length of a sequence that can be "forced to error" by that concept class.
The Littlestone dimension is finite if and only if a no-regret online learning algorithm exists, with a mistake bound of O(d log T).
How to compute the Littlestone dimension of language classes and how to choose the length scale of demonstration sequences are questions that need to be answered subsequently.
The Littlestone dimension corresponds to the length of the longest non-redundant sequence; the teaching dimension is equivalent to the minimum basis size.
All Facts (5)
For language classes with finite Littlestone dimension d, the authors obtain the mistake bound in the realizable setting: O(d log(1+T/d)).
50%UnverifiedThe Littlestone dimension is a combinatorial quantity measuring the online learning complexity of a binary concept class, defined as the maximum length of a sequence that can be "forced to error" by that concept class.
50%UnverifiedThe Littlestone dimension is finite if and only if a no-regret online learning algorithm exists, with a mistake bound of O(d log T).
50%UnverifiedThe Littlestone dimension corresponds to the length of the longest non-redundant sequence; the teaching dimension is equivalent to the minimum basis size.
50%UnverifiedHow to compute the Littlestone dimension of language classes and how to choose the length scale of demonstration sequences are questions that need to be answered subsequently.
50%