Littlestone Dimension

Two Ways to Measure Learning Difficulty

A hypothesis class can be studied through more than one notion of capacity. In the PAC learning model, the relevant measure is VC dimension. In online learning, the relevant structure is captured by Littlestone dimension, which is connected to the number of mistakes an online learner can be forced to make. These measures are related, but they describe different learning settings.

Shattered Sets in PAC Learning

VC dimension measures the largest shattered set of instances. A set is useful for this test when the hypothesis class can realize every possible binary labeling of the instances in that set. If the class can realize all those labelings, the set is shattered. The VC dimension is the size of the largest set for which this succeeds.

VC dimension has a specific role in the PAC learning model. PAC learning is a framework for studying learnability, and within that framework learnability is characterized by the VC dimension of the hypothesis class H. This does not make VC dimension the universal measure for every learning setting; online learning uses a different game and a different capacity measure.

The Online Prediction Game

Online learning proceeds round by round rather than from a complete training set. On round t, the environment first chooses an instance x_t. The learner then predicts a binary label p_t, either 0 or 1. Finally, the environment reveals the true binary label y_t. The learner can use that revealed label when making predictions in later rounds.

The important change in viewpoint is that the learner must predict before seeing the current true label. The revealed label becomes available for later predictions, so the game unfolds as a sequence of prediction and feedback rounds. Littlestone dimension measures the complexity of the label histories that a hypothesis class can support in this setting.

Shattered Instance Trees

To represent every possible history of the online game, arrange the rounds as a branching tree. Each level represents another online round. A node contains the instance chosen for that round, and its outgoing branches represent the possible labels that the environment might reveal next. A root-to-leaf path records one possible history of the game.

A Two-Hypothesis Tree Test

Consider the generated hypothesis class H containing two hypotheses: one always predicts 0, and the other always predicts 1. We can test how deeply this class shatters an instance tree by listing the label paths and matching each path with a hypothesis.

Definition and Mistakes

A deeper shattered tree means that the class can support a more deeply branching collection of label histories. This makes Littlestone dimension a complexity measure tied specifically to online learnability and achievable mistake bounds.

• Treating VC dimension and Littlestone dimension as the same quantity.

  The relationship only guarantees that VC dimension is no larger than Littlestone dimension. The inequality does not force equality.

  Fix: Conclude only that the Littlestone dimension is at least 4 unless additional information gives an upper bound.

• Checking only individual nodes instead of complete paths.

  Shattering requires every complete label path to be consistent with some hypothesis.

  Fix: Enumerate every root-to-leaf label history and match each one separately.

• Assuming that realizing both labels on one instance proves depth-two shattering.

  At depth two, mixed histories such as 0,1 and 1,0 must also be realized.

  Fix: Test all paths at the proposed depth.

Dimensions and Mistake Bounds

For every hypothesis class H, the VC dimension is less than or equal to the Littlestone dimension. This is an inequality, not an equality. Some classes have a strict gap between the two quantities, and the gap can be arbitrarily large. Therefore, a VC-dimension value cannot simply be substituted for the Littlestone-dimension value.

Littlestone dimension characterizes the best achievable mistake bound for the class in the online setting. The connection comes from the tree: each additional level represents another round, and a large maximum shattered depth means the class can support more extended branching histories of possible revealed labels.

Practice: Apply the Path Test

The point of this exercise is not merely to count hypotheses. Shattering depends on whether every required label history has a compatible hypothesis. The same path-by-path procedure works for larger trees, although the number of paths increases with depth.

Key Takeaways

1. VC dimension is the size of the largest set of instances for which a hypothesis class realizes every possible binary labeling. It is the capacity measure used to characterize learnability in the PAC model.

1. Online learning is a sequential game: the environment chooses an instance, the learner predicts, and the environment reveals the true label. A hypothesis class shatters a tree when every root-to-leaf label path agrees with some hypothesis in the class.

1. Littlestone's Dimension is the greatest depth of a shattered tree. It is tied to online learnability and achievable mistake bounds.

1. VC dimension is always less than or equal to Littlestone dimension, but the inequality does not imply equality. To test a proposed Littlestone dimension, enumerate every label path and check each path against the hypothesis class.