Convergence theorem: guaranteed to finish, silent about when

What the convergence theorem says

A perceptron is one of the simplest learning programs. It tries to split examples into two groups with one straight line, and every time it gets an example wrong, it nudges the line a little. Each nudge is called a correction.

In 1962, the mathematician Novikoff proved a promise about this process: if some straight line can separate the two groups at all, the perceptron will run out of mistakes after a limited number of corrections. That promise is the convergence theorem. "Converge" just means "settle on an answer and stop changing".

The catch is in what the promise leaves out. It gives a maximum number of corrections. It says nothing about how long they will take on your data, or whether you will still be watching when the learner finally settles.

What the video shows

The video's hook: the maths promised the learner would finish, but it never said when. It backs that up with two numbers from the course's own example. After 200 passes through the data (one pass means looking at every example once), the learner still has not settled, and it looks broken. It is not. Left alone, it finishes after 11,976 passes.

An everyday example

Imagine you lost your keys somewhere at home. You can make yourself one firm promise: as long as the keys really are inside the house, opening every drawer and checking every pocket will find them. That is a real guarantee, with a condition, just like the theorem's. It is also silent on whether the search takes five minutes or the whole weekend. How long it takes depends on the layout of the house and where the keys happen to be, not on the promise.

How the limit is calculated

The theorem's maximum depends on two measurements of the data:

• R, the size of the data: how far the farthest example sits from the zero point of the chart.
• The margin: how much empty space there is between the dividing line and the example closest to it.

The limit is (R ÷ margin)², that is, the size divided by the gap, then squared. Data that sits far from zero with only a thin gap gives an enormous limit.

In the course, the learner sorts eight factory parts measured in millimetres and grams. Raw, R is about 74 and the margin is only 0.045, so the limit comes out at roughly 2.6 million corrections. The real run needed 29,870 corrections over 11,976 passes: comfortably inside the promise, and about 60 times longer than a 200-pass budget. The theorem was never broken. It describes the worst possible case, not the usual one.

A common misconception

"It looks stuck, so it must be broken." At 200 passes the course's learner looked exactly like a failure, yet it was steadily heading toward a real answer. Stopping it there would have abandoned a run that was going to succeed. Some runs really are hopeless (the XOR problem, two concepts later, is the classic one), and the theory is what tells the two apart. The opposite mistake is just as real: a guarantee that something will finish is not a guarantee that it will finish in time to be useful.

Why it matters

The gap between "possible" and "practical" is usually about geometry: where the data sits and how much room separates the groups. The very same eight parts, shifted so they sit around zero, finish in 2 passes instead of 11,976 (that fix is the next concept in the series, input normalization). The course returns to this pattern later: the mathematics tells you something can work, and engineering decides whether it works in a reasonable time.

Learn it step by step in Chapter 1 of our free course AI From Scratch: The Perceptron From Scratch: What a Neuron Computes.