1.5 — The perceptron algorithm and Novikoff's convergence theorem

1. Why this session exists

The perceptron (Rosenblatt, 1958)[1] is the first training algorithm for a linear classifier, predating gradient descent on smooth losses. It is also the first algorithm in this course we can prove a clean convergence theorem about. The proof — due to Novikoff (1962)[2] — is a one-page induction using the geometric quantities from 1.4. After we have it, every later statement about neural-network training will be measured against this baseline.

2. The model

Use $\pm 1$ labels: $y_i \in \{-1, +1\}$. The classifier:

To simplify notation, absorb the bias into the weight vector by augmenting every input with a constant feature:

Then $w^\top x + b = \tilde w^\top \tilde x$, and everything works in terms of $\tilde w \in \mathbb{R}^{n+1}$. For the rest of this session we drop the tildes and pretend the bias is just another weight on a constant-1 feature.

3. The learning rule

Initialise $w_0 = 0$. Iterate over the data (round-robin or arbitrary order). At each step, given the current $w_k$ and a chosen example $(x_i, y_i)$:

• Correct case ($y_i\, w_k^\top x_i > 0$): leave $w$ unchanged.
• Mistake case ($y_i\, w_k^\top x_i \le 0$): update

The update pushes $w$ in the direction that improves the score $y_i\, w_k^\top x_i$ for the example that was just misclassified:

Each mistake increases that example's score by $\lVert x_i \rVert^2 > 0$.

4. Novikoff's theorem

Setup. Suppose the dataset $\{(x_i, y_i)\}_{i=1}^m$ is linearly separable with geometric margin $\gamma > 0$, i.e. there exists a unit vector $u \in \mathbb{R}^{n+1}$ (with $\lVert u \rVert = 1$) such that

Suppose all inputs are bounded in norm: $\lVert x_i \rVert \le R$ for all $i$.

Claim. Starting from $w_0 = 0$ and running the perceptron rule of §3, the total number of mistakes (and hence updates) is at most

In particular, the algorithm terminates in finitely many steps.

Proof. Let $w_k$ be the weight vector after the $k$-th mistake. We track two quantities.

Bound 1 — alignment with $u$ grows linearly. Take the inner product of the update $w_{k+1} = w_k + y_i x_i$ with $u$:

By induction, since $u^\top w_0 = 0$,

By the Cauchy–Schwarz inequality, $u^\top w_k \le \lVert u \rVert \cdot \lVert w_k \rVert = \lVert w_k \rVert$, hence

Bound 2 — squared norm grows at most linearly. Expand the squared norm of $w_{k+1}$:

Because the update was applied only when $y_i\, w_k^\top x_i \le 0$, the cross term is $\le 0$. And $\lVert x_i \rVert^2 \le R^2$. So

By induction from $\lVert w_0 \rVert^2 = 0$,

Combining. From $(\star)$, $\lVert w_k \rVert^2 \ge k^2 \gamma^2$. From $(\star\star)$, $\lVert w_k \rVert^2 \le k R^2$. So

This holds at every $k$ at which a mistake occurs. Hence the total number of mistakes is $M \le R^2 / \gamma^2$. $\blacksquare$

5. What the bound says and does not say

• Margin matters. Halving the margin quadruples the worst-case update count. Wider margins → faster convergence.
• Scale matters only through $R$. Rescaling all $x_i$ by the same constant $c$ scales both $R$ and $\gamma$ by $c$, leaving $R^2 / \gamma^2$ unchanged.
• No assumption on data order. Adversarial orderings can hit the bound; favourable orderings finish faster. The total mistake count is invariant under reorderings.
• Non-separable data. The theorem fails — there is no $u$ with the required property. The perceptron will oscillate forever. The pocket variant (keep the best $w$ seen so far) is the classical workaround; in modern practice we use logistic regression with regularisation, which always has a unique solution.

6. A worked toy example

Two points in $\mathbb{R}^2$: $x_+ = (1, 0)$ with $y = +1$, $x_- = (-1, 0)$ with $y = -1$. Augment with the constant feature: $\tilde x_+ = (1, 0, 1)$, $\tilde x_- = (-1, 0, 1)$.

$R = \sqrt 2$ and $u = (1, 0, 0)$ achieves $y_i\, u^\top \tilde x_i = 1$ for both points, so $\gamma = 1$. Novikoff bound: $M \le 2 / 1 = 2$.

Start $w_0 = 0$. Both examples score $0$, so both trigger mistakes. Suppose we hit $\tilde x_+$ first:

Now check $\tilde x_-$: the signed score is $y\, w_1^\top \tilde x_- = (-1)(-1 + 0 + 1) = 0$, still a mistake. Update:

Both examples now score $+2 > 0$. Done. Two mistakes total, exactly hitting the Novikoff bound.

7. Takeaways

• Perceptron rule: $w_{k+1} = w_k + y_i x_i$ on mistakes, no-op on correct examples.
• Novikoff: $M \le R^2 / \gamma^2$ updates on a linearly separable dataset.
• Proof: two inductive inequalities and one Cauchy–Schwarz application.
• Margin is the central quantity; the same theme recurs in SVMs and in PAC-style generalisation bounds.