Generalization Bounds

Why the Margin Matters

A Perceptron may update its weight vector whenever it makes a mistake. The important question is not only whether it eventually finds a classifier that makes no mistakes, but also how many updates may be required. A separation margin γ supplies that information: when the training set is separated with margin γ, the Perceptron makes at most 1/γ² updates before reaching a solution with no mistakes on the entire training set.

Margin-Separated Training Sets

A training set is separated with margin γ when a separating boundary places every positive example and every negative example on its correct side, with the separation from the boundary measured by γ. The larger the margin, the stronger the separation condition. The generalization-bound result uses this condition to control how many mistakes-driven updates the Perceptron can make.

Following the Perceptron Updates

The Perceptron update process can be viewed as a sequence. A mistake causes an update to the weight vector. The algorithm continues processing the training set. Once it reaches a classifier that makes no mistakes on the entire training set, convergence has been reached.

The Update Bound

maximum number of Perceptron updates = 1/γ²

The bound makes the relationship between margin and work explicit. A larger margin produces a smaller value of 1/γ², while a smaller margin produces a larger value. Thus, stronger separation corresponds to a lower upper bound on the number of updates. The guarantee says that the Perceptron reaches a solution with no mistakes on the entire training set after at most this many updates.

Updates as a Compression Scheme

The Perceptron update bound also gives a compression result. The examples that triggered Perceptron updates can be retained as a compressed representation of the final classifier. Because there are at most 1/γ² updates, the associated compression scheme has size k satisfying k ≤ 1/γ².

Connecting the Three Results

The reasoning chain is compact. First, assume the training set is separated with margin γ. Second, use that condition to bound the Perceptron's updates by 1/γ². Third, interpret the result in two ways: after at most that many updates, the Perceptron reaches a classifier with no mistakes on the entire training set; and the examples that triggered those updates provide a compression scheme of size at most 1/γ².

Common Reasoning Mistakes

• Treating 1/γ² as the exact number of updates.

  The result gives a maximum number of updates, not necessarily the number the algorithm actually performs.

  Fix: Say that the Perceptron makes at most 1/γ² updates.

• Describing convergence as merely finding a boundary.

  The stated convergence meaning is stronger: the solution makes no mistakes on the entire training set.

  Fix: Check convergence against the whole training set.

• Using γ² instead of 1/γ² as the update bound.

  The guarantee uses the reciprocal of the squared margin.

  Fix: Compute the bound as 1 divided by γ².

• Separating the compression size from the update bound.

  The associated compression scheme has size k ≤ 1/γ².

  Fix: Use the same upper bound for the retained update-triggering examples.

Check Your Understanding