The convergence promise

The oldest guarantee in machine learning, and still one of the cleanest. If your data can be split by a line, the perceptron will find one — and it will do so after a bounded number of mistakes that depends on nothing but the geometry. Not the dimension. Not the number of points. Watch it obey.

1958 Rosenblatt builds it → 1962 Novikoff & Block prove it can't loop forever on separable data → the bound: (R/γ)²

✓ PROVEN THEOREM Novikoff (1962), Block (1962). A real theorem with a real proof. The mistake bound (R/γ)² is exact, dimension-free, and holds for every separable dataset. Nothing speculative here — this is bedrock.

The theorem, running

Points are drawn separable by a hidden line, with a clear band of width γ (the margin) on either side. The perceptron starts at w = 0 and only moves when it's wrong: w ← w + y·x. Each correction is a "mistake." The promise: total mistakes ≤ (R / γ)² where R is the radius of the data. Shrink the margin and the bound balloons — but the count never breaks it.

margin γ speed

hidden true boundary (faint) · margin band (γ) · the perceptron's current line (violet, moves on each mistake)

mistakes so far

—

bound · ⌈(R/γ)²⌉

mistakes ≤ bound …

Tighten the margin and the same data takes more corrections — the line has a narrower slot to find. But the count always lands under the bound. Push γ to its smallest and watch the bound explode into the hundreds while the perceptron still quietly converges below it.

What's proven — and the one honest catch

Proven: on linearly separable data the perceptron stops after ≤ (R/γ)² updates, finding some separating line. The proof is two inequalities: each update grows w·w* by at least γ (progress), while |w|² grows by at most R² (it can't run away). Squeeze them together and the mistake count is capped. That's the whole proof — two lines.

The catch (still honest, still proven): the promise is only for separable data. If no line splits the points, the perceptron never converges — it cycles forever, and which line you'd "stop" on is arbitrary. It also gives you a separator, not the best one (that's the max-margin / SVM story, a different guarantee). The theorem is strong precisely because it claims something narrow and delivers it completely.