The convergence theorem

In the book: Chapter 1, §"Why the Perceptron Works" — "the perceptron convergence theorem states that the algorithm finds a separating boundary after a finite number of updates." This page states and proves that theorem. Builds on: The learning rule · Background: dot-product identities · Background: the Cauchy–Schwarz inequality.

The book demonstrates that each update improves the score of the example that triggered it, and warns that an update "may worsen the margin on other examples." So why does this tug-of-war end? The answer is Novikoff's theorem (1962): if the data is linearly separable, the total number of updates the perceptron can ever make is bounded by a constant that depends only on the geometry of the data — not on the number of examples, not on the dimension, and not on the order in which examples are visited.

Setup

We are given a dataset $({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_N,y_N)$ with ${\mathbf{x}}_i\in {\mathbb{R}}^d$ and labels $y_i\in \{-1,+1\}$, and we run the perceptron rule from Chapter 1: predict with $\mathrm{sign}({\mathbf{w}}^{\top }\mathbf{x}+b)$, and on a misclassified example update

$$\mathbf{w}\leftarrow \mathbf{w}+y\mathbf{x},b\leftarrow b+y.$$

Absorbing the bias. The pair $(\mathbf{w},b)$ is awkward to carry through the analysis, and there is a standard trick to make it disappear: append a constant feature $1$ to every input. Define

$$\mathbf{x}=(\mathbf{x},1)\in {\mathbb{R}}^{d+1},\mathbf{w}=(\mathbf{w},b)\in {\mathbb{R}}^{d+1}.$$

Then ${\mathbf{w}}^{\top }\mathbf{x}={\mathbf{w}}^{\top }\mathbf{x}+b$, so predictions are unchanged, and the two-part update above becomes the single update $\mathbf{w}\leftarrow \mathbf{w}+y\tilde{\mathbf{x}}$: the bias update $b\leftarrow b+y$ is exactly the update of the last coordinate. From here on we work in ${\mathbb{R}}^{d+1}$ and drop the tildes: inputs are ${\mathbf{x}}_i$, the parameter is a single vector $\mathbf{w}$, and the update is $\mathbf{w}\leftarrow \mathbf{w}+y\mathbf{x}$. We start, as the book's code does, from ${\mathbf{w}}_0=0$.

The two geometric quantities. The bound is stated in terms of:

• the radius of the data, $R={\max }_i\Vert {\mathbf{x}}_i\Vert$ — how far any example sits from the origin;
• the margin $\gamma$ of the best separator: linear separability means there exists some unit vector ${\mathbf{w}}^{\ast }$ ($\Vert {\mathbf{w}}^{\ast }\Vert =1$) and some $\gamma >0$ with

$$y_i⟨{\mathbf{w}}^{\ast },{\mathbf{x}}_i⟩\ge \gamma \text{for every }i=1,\dots ,N.$$

In words: some hyperplane not only separates the classes but clears every point by at least $\gamma$. (Requiring $\Vert {\mathbf{w}}^{\ast }\Vert =1$ is what makes $\gamma$ a genuine distance rather than an artifact of scaling — made precise in Margin, formally, in the planned Maximum-Margin Separation section.)

Statement

Theorem (Novikoff, 1962). Run the perceptron algorithm, starting from ${\mathbf{w}}_0=0$, on any sequence of examples drawn from the dataset (in any order, with any repetitions). If the data is linearly separable with margin $\gamma >0$ and radius $R$, then the algorithm makes at most

$${\left(\frac{R}{\gamma }\right)}^2$$

updates. In particular, after finitely many mistakes the weight vector separates the data perfectly and never changes again.

Proof

Let ${\mathbf{w}}_k$ denote the weight vector after the $k$-th update. The proof tracks one quantity from two sides: the alignment $⟨{\mathbf{w}}_k,{\mathbf{w}}^{\ast }⟩$ between the learned weights and the perfect separator. Each mistake forces this alignment up by a fixed amount, while the length of ${\mathbf{w}}_k$ can only grow slowly. Since alignment cannot outrun length (Cauchy–Schwarz), mistakes must stop.

Step 1 — each update gains $\gamma$ of alignment. Suppose the $k$-th update is triggered by the example $(\mathbf{x},y)$, so ${\mathbf{w}}_k={\mathbf{w}}_{k-1}+y\mathbf{x}$. By linearity of the dot product,

$$⟨{\mathbf{w}}_k,{\mathbf{w}}^{\ast }⟩=⟨{\mathbf{w}}_{k-1},{\mathbf{w}}^{\ast }⟩+y⟨\mathbf{x},{\mathbf{w}}^{\ast }⟩\ge ⟨{\mathbf{w}}_{k-1},{\mathbf{w}}^{\ast }⟩+\gamma ,$$

where the inequality is exactly the margin condition $y⟨{\mathbf{w}}^{\ast },\mathbf{x}⟩\ge \gamma$. Starting from $⟨{\mathbf{w}}_0,{\mathbf{w}}^{\ast }⟩=0$ and applying this $k$ times,

$$⟨{\mathbf{w}}_k,{\mathbf{w}}^{\ast }⟩\ge k\gamma .\text{\hspace{1em}(1)}$$

Step 2 — each update grows the length by at most $R^2$. For the same update, expand the squared norm (Background: norms):

$${\Vert {\mathbf{w}}_k\Vert }^2={\Vert {\mathbf{w}}_{k-1}+y\mathbf{x}\Vert }^2={\Vert {\mathbf{w}}_{k-1}\Vert }^2+2y⟨{\mathbf{w}}_{k-1},\mathbf{x}⟩+y^2{\Vert \mathbf{x}\Vert }^2.$$

Now use the one fact that makes the whole proof work: the update only happens because the example was misclassified, which means $y⟨{\mathbf{w}}_{k-1},\mathbf{x}⟩\le 0$. The middle term is not just bounded — it helps us. Together with $y^2=1$ and $\Vert \mathbf{x}\Vert \le R$,

$${\Vert {\mathbf{w}}_k\Vert }^2\le {\Vert {\mathbf{w}}_{k-1}\Vert }^2+R^2,$$

and therefore, again starting from ${\mathbf{w}}_0=0$,

$${\Vert {\mathbf{w}}_k\Vert }^2\le k{R}^2.\text{\hspace{1em}(2)}$$

Step 3 — the two bounds collide. By the Cauchy–Schwarz inequality and $\Vert {\mathbf{w}}^{\ast }\Vert =1$,

$$⟨{\mathbf{w}}_k,{\mathbf{w}}^{\ast }⟩\le \Vert {\mathbf{w}}_k\Vert \Vert {\mathbf{w}}^{\ast }\Vert =\Vert {\mathbf{w}}_k\Vert .$$

Chaining (1), this, and (2):

$$k\gamma \stackrel{(1)}{\le }⟨{\mathbf{w}}_k,{\mathbf{w}}^{\ast }⟩\le \Vert {\mathbf{w}}_k\Vert \stackrel{(2)}{\le }\sqrt{k}R.$$

Reading off the ends, $k\gamma \le \sqrt{k}R$, and dividing by $\sqrt{k}\gamma$ (positive for any $k\ge 1$) gives

$$\sqrt{k}\le \frac{R}{\gamma }⟺k\le {\left(\frac{R}{\gamma }\right)}^2.$$

So the number of updates can never exceed $(R/\gamma {)}^2$. Once the algorithm completes a full pass with no mistake — which must happen, since passes containing a mistake are limited — the weights separate every example and no future pass changes them. ∎

Remarks

Where each hypothesis was used. Separability with margin $\gamma$ powered Step 1; misclassification-only updates powered Step 2 (it is the reason the cross term is $\le 0$); ${\mathbf{w}}_0=0$ made both accumulations start at zero. Drop any one and the proof — and the theorem — fails.

What the theorem does not say. It does not say the perceptron finds the best boundary, only a separating one; the book's "tug-of-war" ends, but possibly at a line that barely clears some points. It also says nothing when the data is not separable — the XOR case — where the algorithm cycles forever. Both gaps are picked up in Reading the bound and resolved properly in Maximum-Margin Separation (planned).

The bound is dimension-free. Neither $d$ nor $N$ appears. This is worth pausing on: a million points in a million dimensions cost no more updates than four points in the plane, so long as the geometry ($R/\gamma$) is the same. This is the first appearance of a theme that returns with kernels in Kernels and Feature Spaces (planned).

Going further

• A. Novikoff, On convergence proofs for perceptrons, Symposium on the Mathematical Theory of Automata, 1962 — the original.
• M. Minsky & S. Papert, Perceptrons, MIT Press, 1969 — the book-length study of what perceptrons can and cannot represent.
• Freund & Schapire, Large margin classification using the perceptron algorithm, Machine Learning 37, 1999 — what can still be said when the data is not separable.