Does It Always Converge? (Optional)

The worry from the previous lesson: correcting one example can upset another. Could the weights keep bouncing forever? If the data is linearly separable, no. The proof is short.

Setting up

To keep the algebra simple, use labels $t = +1$ for positive and $t = -1$ for negative examples. Then both update rules become a single one: on a mistake, $w \leftarrow w + t\,x$.

A mistake means $t\,(w \cdot x) \le 0$. For a positive example that is $w \cdot x \le 0$, and for a negative one it is $w \cdot x \ge 0$. (The zero case is included, because a score of exactly 0 counts as positive.)

Assume the data is separable with some margin:

• there is a unit-length vector $w^*$ and a number $\gamma > 0$ with $t\,(w^* \cdot x) \ge \gamma$ for every example, and
• every example has length at most $R$: $\|x\| \le R$.

Start from $w = 0$ and let $w_k$ be the weights after $k$ corrections.

Two inequalities

1. The weights line up with $w^*$. Each correction changes the overlap with $w^*$ by

After $k$ corrections, $w^* \cdot w_k \ge k\gamma$.

2. The weights cannot grow too fast. Since the last example was a mistake, $t\,(w_{k-1} \cdot x) \le 0$, so

After $k$ corrections, $\|w_k\|^2 \le kR^2$.

Putting them together

Because $w^*$ has length 1, $w^* \cdot w_k \le \|w_k\|$. So

which gives

The number of corrections is bounded. After at most $R^2 / \gamma^2$ corrections there are no more mistakes, which means a full pass is clean. That is convergence.

What the bound tells you

• Bigger margin, faster learning. If the classes are well separated (large $\gamma$), few corrections are needed. A thin gap between classes means many.
• The bound does not depend on the number of features or examples, only on $R$ and $\gamma$.
• Random initial weights change the constant but not the conclusion.