Perceptron
The original linear classifier: mistake-driven updates and the Novikoff convergence bound.
On this page
Beginner: logistic regression (section 2.4.1) answers "what's the probability this point is positive?" The Perceptron asks a much blunter question: "which side of a line is this point on?" It draws a straight boundary through the data, checks each point one at a time, and whenever it gets one wrong, it nudges the boundary just enough to fix that mistake. Do this enough times and — if the data really can be separated by a straight line — the boundary stops moving entirely.
Intermediate: there is no probability anywhere in the Perceptron, and no smooth loss function either. It doesn't compute a gradient in the calculus sense — it has a discrete rule: correct predictions do nothing, wrong predictions trigger one additive update. This is a genuinely different learning paradigm from every gradient-descent method so far in this chapter, and it predates almost all of them — the Perceptron (Rosenblatt, 1958) is the oldest trainable linear classifier in this book.
Advanced: the interesting theory here is the Novikoff convergence theorem: if the data is linearly separable with some positive margin, the number of mistakes the Perceptron can ever make is bounded by a fixed constant that depends only on that margin and the data's scale — not on how many points there are, not on how many passes it takes. The proof is a clean two-inequality sandwich argument, worked through in full below, and it's also the first place in this chapter where "convergence" means something other than "the loss's gradient vanished" — there is no loss here, only a mistake counter that provably stops incrementing.
Decision rule (bias folded into θ):
Mistake-driven update rule, applied only when a point is misclassified:
Fold the bias into θ the usual way: append a constant 1 to every feature vector, so x = [x⁽¹⁾, …, x⁽ᵈ⁾, 1] and θ = [w⁽¹⁾, …, w⁽ᵈ⁾, b], making θᵀx = wᵀx + b a single dot product. The Perceptron's prediction is just the SIGN of that score:
Compare this directly to section 2.4.1's logistic regression, which computes the exact same linear score θᵀx and then applies the SIGMOID, producing a real number in (0, 1) read as a probability. The Perceptron applies sign(·) instead — a step function — and that single substitution changes everything downstream: the sigmoid is smooth and differentiable everywhere, so cross-entropy loss built on it has a well-defined gradient at every θ; the sign function is flat (zero derivative) almost everywhere and discontinuous at zero, so there is no useful gradient to descend. The Perceptron cannot be fit by gradient descent — it needs its own, non-calculus learning rule.
That rule: for a labeled point (x_i, y_i) with y_i ∈ {-1,+1}, define its functional margin as y_i(θᵀx_i). This quantity is positive exactly when the point is classified correctly (the sign of θᵀx_i matches y_i) and non-positive exactly when it's misclassified (or lies exactly on the boundary, which is treated as a mistake). The Perceptron scans the data and, on every misclassified point, applies:
Why THIS update, specifically? Look at what it does to that same point's functional margin immediately afterward. Writing θ' = θ + y_i x_i:
Since ‖x_i‖² ≥ 0 always (and is strictly positive for any nonzero point), the update strictly INCREASES that point's functional margin by exactly ‖x_i‖² — it moves the score for that specific point directly toward, and past, the correct side of zero. It's the smallest possible additive correction that pushes precisely the point that failed in precisely the right direction, using that point itself as the correction vector. No other point's margin is touched by this update in a controlled way — some may improve, some may worsen — which is precisely why a single pass isn't enough in general and the algorithm must keep cycling through the data until every point is simultaneously satisfied.
Assume the data {(x_i, y_i)}_{i=1}^n is linearly separable: there exists some unit vector θ* (‖θ*‖ = 1) that classifies every point correctly. Define two quantities that the theorem's bound is built from:
γ is the smallest signed distance (since ‖θ*‖=1) from any point to the separating hyperplane — how much "breathing room" the best separator gives the closest point. R is simply the radius of the smallest ball around the origin containing all the data. Both are properties of the DATA and of one particular separator θ*, fixed before training ever starts.
Claim (Novikoff, 1962): starting from θ₀ = 0, the Perceptron makes at most (R/γ)² mistakes in total, over any order in which misclassified points are presented, before it stops making mistakes entirely.
Proof. Let θ_k denote θ after the k-th mistake has been corrected, so θ_k = θ_{k-1} + y_{i_k}x_{i_k} where (x_{i_k}, y_{i_k}) is whichever point triggered mistake k. The proof sandwiches ‖θ_k‖ between a lower bound that grows LINEARLY in k and an upper bound that grows only as √k — and a quantity that must simultaneously satisfy both cannot let k grow past a fixed ceiling.
Step 1 — lower bound via the margin.
Take the dot product of the update with θ*:
using y_{i_k}(θ*ᵀx_{i_k}) ≥ γ by γ's very definition as the minimum margin over the whole dataset under θ*. Applying this inequality repeatedly from θ₀ = 0 down to θ_k gives:
and since θ* is a unit vector, Cauchy–Schwarz gives θ*ᵀθ_k ≤ ‖θ*‖‖θ_k‖ = ‖θ_k‖. Combining:
— ‖θ_k‖ grows at least linearly in the number of mistakes made so far.
Step 2 — upper bound via the data's scale.
Expand ‖θ_k‖² using the update rule, remembering that mistake k only fires when y_{i_k}(θ_{k-1}ᵀx_{i_k}) ≤ 0:
because the middle term is ≤ 0 by exactly the mistake condition (this is the same identity used in part 1's derivation, now run in the direction that bounds growth rather than showing improvement). Since ‖x_{i_k}‖² ≤ R², applying this repeatedly from θ₀ = 0 gives:
Step 3 — combine.
Squaring the step 1 result and chaining it with the step 2 result:
Dividing both sides by kγ² (valid once a first mistake has occurred, so k ≥ 1):
which holds for every k — in particular for the total number of mistakes made — so the Perceptron can make at most (R/γ)² mistakes in total, ever, regardless of the order points are presented in or how many times the data is cycled through. Since each pass over a finite dataset either makes at least one mistake or terminates with zero, and the mistake budget is finite, the algorithm must reach a pass with zero mistakes — a separating θ — in finitely many steps. ∎
Notice what the bound does NOT depend on: the number of data points n, the dimension d, or the order points are visited in. It depends only on R (how spread out the data is) and γ (how comfortably separable it is) — a wide margin relative to the data's scale means very few mistakes before convergence; a razor-thin margin means the bound (and often the actual mistake count) can be very large.
Every step of the proof above leans on one hypothesis: a separating θ* with strictly positive margin γ exists. If the data is not linearly separable, no such θ* exists at all — γ is not "small", it's UNDEFINED, and the entire sandwich argument collapses at step 1. There is no theorem to fall back on, and in practice the Perceptron can cycle forever: it will keep finding misclassified points (there is always at least one, since no separator exists), keep updating, and the sequence of θ's can revisit the same handful of vectors in an endless loop, never reaching a pass with zero mistakes.
This is the sharpest contrast with logistic regression (section 2.4.1). Cross-entropy loss is defined and finite for EVERY θ, separable data or not, and section 2.2.1's convexity argument (confirmed there via the Hessian) guarantees gradient descent on it makes monotonic progress toward a unique global minimum regardless of separability. On non-separable data that minimum simply isn't a perfect classifier — some points stay misclassified even in the best possible θ — but it IS a well-defined stopping point that gradient descent provably reaches. The Perceptron has no such fallback: its update rule is only ever justified by "fix the current mistake," and with no loss surface underneath it, there's nothing analogous to a minimum for it to settle into when perfect separation is impossible. In practice, non-separable data is handled by capping the number of epochs and keeping the best (or averaged) θ seen along the way — the pocket algorithm and the averaged Perceptron mentioned below — not by waiting for a convergence that Novikoff's theorem never promised.
A linearly-separable toy dataset. The Perceptron cycles through the points in fixed order; the blue line is the current decision boundary theta^T x = 0, and it moves only when the highlighted point is misclassified. The readout tracks the running mistake count and theta. Once a full pass makes zero mistakes, training stops -- exactly the guarantee Novikoff's theorem promises for separable data.
Toggle between a separable and a non-separable version of the same dataset and watch cumulative mistakes over update attempts. On the separable set the curve flattens (converges) well inside the dashed (R/gamma)^2 bound computed from the actual data. On the non-separable set there is no separator at all, so gamma is undefined, no bound exists, and the mistake count keeps climbing until this diagram's iteration cap cuts it off -- the algorithm itself has no stopping rule here.
#include <cmath>
#include <iostream>
#include <vector>
struct Point { double x, y; int label; }; // label in {-1, +1}
// theta = {w1, w2, b}; theta^T x = w1*x + w2*y + b, with bias folded in.
std::vector<double> perceptronFit(const std::vector<Point>& pts, int maxEpochs, int& epochsUsed) {
std::vector<double> theta = {0.0, 0.0, 0.0};
for (int epoch = 0; epoch < maxEpochs; ++epoch) {
int mistakes = 0;
for (const auto& p : pts) {
double score = theta[0] * p.x + theta[1] * p.y + theta[2];
if (p.label * score <= 0) { // misclassified: fix it
theta[0] += p.label * p.x;
theta[1] += p.label * p.y;
theta[2] += p.label;
++mistakes;
}
}
if (mistakes == 0) { epochsUsed = epoch + 1; return theta; } // converged
}
epochsUsed = maxEpochs;
return theta; // hit the cap without a mistake-free pass
}
int main() {
std::vector<Point> pts = {
{-1.8, -1.1, -1}, {-1.2, -0.6, -1}, {-1.6, -1.4, -1}, {-1.0, -0.9, -1},
{1.7, 1.0, 1}, {1.1, 1.4, 1}, {1.5, 0.6, 1}, {1.9, 1.3, 1},
};
int epochsUsed = 0;
auto theta = perceptronFit(pts, 1000, epochsUsed);
std::cout << "theta: [" << theta[0] << ", " << theta[1] << ", " << theta[2] << "]"
<< " converged in " << epochsUsed << " epochs\n";
return 0;
}- Historical role — the Perceptron (1958) was the first trainable artificial neuron, and the direct conceptual ancestor of every unit in a modern multi-layer neural network: a linear score followed by a nonlinearity, learned from mistakes on labeled examples.
- Online / streaming binary classification — the update touches one point at a time and does essentially no work when a prediction is already correct, making it a natural fit for high-throughput streams where a full gradient-descent pass over stored data isn't an option.
- Resource-constrained or embedded classifiers — the update is a single vector addition with no exponentials, logarithms, or matrix operations, which matters when training has to run on very limited hardware.
- Building block for the multi-layer Perceptron — stacking these linear units with nonlinearities between layers, and replacing the mistake-driven rule with backpropagated gradients on a differentiable surrogate, is exactly how the modern feedforward neural network was arrived at historically.
- Assuming the Perceptron always converges — it only converges under the Novikoff theorem's hypothesis (linear separability). Run it on non-separable data expecting a clean stop and it will silently cycle until an epoch cap is hit, often with no warning.
- Processing points in a fixed order every epoch (as the from-scratch code above does for reproducibility) versus shuffling — both converge under separability, but which separating
θis found, and how many mistakes it takes to get there, can differ noticeably between orderings, since the update sequence itself is order-dependent. - Conflating the Perceptron with logistic regression because both look like
g(θᵀx)— one usessignand a discrete mistake-driven rule with no probabilistic meaning at all; the other uses the sigmoid and a smooth, differentiable, probabilistically-grounded loss. They can even converge to different separating boundaries on the same separable dataset. - Reading "converged" as "found the best boundary" — Novikoff guarantees SOME separating
θin finitely many mistakes, not the one with the largest margin (see the note below on maximum-margin classifiers).
Going deeper
The Perceptron finds a separating hyperplane — the first one its mistake-driven walk happens to land on — with no preference for how far that boundary sits from the nearest points on either side. Two different orderings of the same separable dataset can converge to two different valid separators, one with a razor-thin margin and one with a comfortable one, and the Perceptron has no way to tell them apart or prefer the better one. That's precisely the gap the Support Vector Machine closes later in this chapter: it replaces "any separator that stops making mistakes" with an explicit optimization for the MAXIMUM-margin separator. In practice, two variants soften the plain Perceptron's other rough edge — its instability on noisy or barely-non-separable data: the pocket algorithm, which just remembers the best θ seen across all epochs by training-set accuracy, and the voted/averaged Perceptron, which predicts using an average of every θ visited during training rather than only the final one — both are simple modifications of the exact update rule derived above, and both generalize noticeably better in practice.
On non-separable data, the Perceptron can fail to converge at all -- yet logistic regression's gradient descent (section 2.4.1) always keeps making progress, even on the exact same non-separable data. Why the difference?
The Perceptron's update is only ever justified locally: 'this one point is currently misclassified, so fix it' -- there is no global objective underneath it, so when no theta can satisfy every point simultaneously, fixing one point's mistake can easily reintroduce a mistake on another, and the sequence of theta's can cycle forever with no notion of getting closer to anything. Logistic regression's cross-entropy loss, by contrast, is a smooth, convex function (section 2.2.1) defined and finite for every theta, separable or not -- gradient descent always has a well-defined downhill direction to follow and provably converges to that loss's unique global minimum, which on non-separable data is simply the best achievable compromise rather than a perfect classifier. The Perceptron has a mistake counter with no loss surface behind it; logistic regression has an actual objective function it is guaranteed to make monotonic progress on.
Like logistic regression (section 2.4.1), the Perceptron is inherently a binary classifier — its decision rule sign(θᵀx) only ever produces one of two outcomes, with no built-in notion of a third or fourth class. The next lesson, 2.4.4 Multi-class Strategies, covers the composition techniques — one-vs-rest, one-vs-one, error-correcting output codes — needed to build a many-class classifier out of exactly this kind of binary building block, the Perceptron included.