The Perceptron Algorithm

A perceptron is a linear classifier for binary labels $y \in \{-1, +1\}$. Given an input feature vector $\mathbf{x} \in \mathbb{R}^d$, it computes a score

and predicts $\hat{y} = \text{sign}(f(\mathbf{x}))$. Geometrically, the set $\{\mathbf{x} : \mathbf{w}^\top \mathbf{x} + b = 0\}$ is a hyperplane that partitions $\mathbb{R}^d$ into two half-spaces, one for each class. Learning means choosing $\mathbf{w}$ and $b$ so that every training point falls on the correct side. The key term is linear separability: a dataset $\{(\mathbf{x}_i, y_i)\}_{i=1}^n$ is linearly separable if there exists $(\mathbf{w}^*, b^*)$ such that $y_i (\mathbf{w}^{*\top}\mathbf{x}_i + b^*) > 0$ for every $i$. The perceptron algorithm is designed precisely to search for such a $(\mathbf{w}, b)$, and its convergence guarantee is conditioned on this property holding. What distinguishes the perceptron from the Gradient Descent for Parameter Estimation approach used in linear regression is the mistake-driven nature of its updates. There is no smooth loss function being minimized by computing a gradient over an entire dataset at once; instead the algorithm processes examples one at a time (online), and it only acts when the current hypothesis gets an example wrong. When a mistake occurs on $(\mathbf{x}, y)$, the weight vector is corrected by adding $y\mathbf{x}$ — a step that can be shown to be a special case of gradient descent on a non-smooth hinge-like loss called the perceptron criterion, evaluated at learning rate 1, but its historical and pedagogical presentation is purely combinatorial: correct on success, nudge on failure.

To avoid handling the bias term $b$ separately, a standard trick augments every feature vector with a constant $1$, folding $b$ into $\mathbf{w}$: define $\tilde{\mathbf{x}} = (\mathbf{x}, 1)$ and $\tilde{\mathbf{w}} = (\mathbf{w}, b)$, so $\mathbf{w}^\top\mathbf{x} + b = \tilde{\mathbf{w}}^\top\tilde{\mathbf{x}}$. The pseudocode below assumes this augmentation has already been done, and writes $\mathbf{x}, \mathbf{w}$ for the augmented vectors. The algorithm initializes the weight vector (commonly to zero), then repeatedly scans the training set. For each example, it predicts using the current weights. If the prediction is correct, nothing happens. If it is wrong, the weight vector is updated by adding (or subtracting) the misclassified point, scaled by its true label. The scan repeats over the whole dataset (an "epoch") until a full pass produces zero mistakes, at which point every training point is correctly classified and the algorithm halts. ``` Algorithm: Perceptron Learning (batch-of-epochs form) Input: training set {(x_1, y_1), ..., (x_n, y_n)}, y_i in {-1, +1} x_i already augmented with a constant 1 coordinate Output: weight vector w such that sign(w . x_i) = y_i for all i (if separable) 1. w <- 0 # initialize weights to zero vector 2. mistakes_this_epoch <- +infinity 3. while mistakes_this_epoch > 0: 4. mistakes_this_epoch <- 0 5. for i = 1 to n: # one pass over all examples 6. score <- dot(w, x_i) 7. y_hat <- +1 if score > 0 else -1 # convention: score == 0 counts as a mistake 8. if y_hat != y_i: 9. w <- w + y_i x_i # the mistake-driven update 10. mistakes_this_epoch <- mistakes_this_epoch + 1 11. return w ``` Equivalently, many textbooks present the <strong>online</strong> form: a single infinite stream of examples (possibly repeating), where the algorithm updates immediately on any mistake and the convergence theorem bounds the total number of updates* regardless of the order or repetition of examples. Both forms use exactly the same update rule; the batch-of-epochs form above is just a concrete, terminating way to apply it to a fixed dataset.

Why the update rule makes sense. Suppose $(\mathbf{x}, y)$ is misclassified, meaning $y(\mathbf{w}^\top\mathbf{x}) \le 0$. After the update $\mathbf{w}' = \mathbf{w} + y\mathbf{x}$, recompute the margin on this same point:

Since $\|\mathbf{x}\|^2 \ge 0$, the update always moves the margin on that specific point in the correct direction (strictly positive, unless $\mathbf{x} = \mathbf{0}$). The update does not guarantee that other points stay correctly classified — that is exactly why multiple passes over the data may be needed — but each individual correction is locally sound.

Time complexity. Each weight update and each prediction costs $O(d)$ arithmetic operations, where $d$ is the (augmented) feature dimension. A full epoch over $n$ examples costs $O(nd)$. The number of epochs required is not bounded by a fixed constant in general — it depends on the geometry of the data — but the total number of mistakes (across all epochs, or equivalently across the whole online stream) is bounded by the Perceptron Convergence Theorem below, giving total work $O(Md)$ where $M$ is that mistake bound. Space complexity is $O(d)$ for the weight vector, plus $O(nd)$ to store the dataset itself if working in batch mode.

Correctness — the Perceptron Convergence Theorem. Suppose the training data is linearly separable with margin $\gamma > 0$: there exists a unit vector $\mathbf{w}^*$ ($\|\mathbf{w}^*\| = 1$) such that $y_i(\mathbf{w}^{*\top}\mathbf{x}_i) \ge \gamma$ for all $i$. Let $R = \max_i \|\mathbf{x}_i\|$. Then the perceptron algorithm, started at $\mathbf{w}_0 = \mathbf{0}$, makes at most

mistakes in total, regardless of the order in which examples are presented. Proof sketch. Let $\mathbf{w}_k$ denote the weight vector after the $k$-th mistake, updated on point $(\mathbf{x}, y)$ so $\mathbf{w}_k = \mathbf{w}_{k-1} + y\mathbf{x}$. 1. Lower bound on alignment with $\mathbf{w}^*$. By definition of margin,

Since $\mathbf{w}_0 = \mathbf{0}$, induction gives $\mathbf{w}^{*\top}\mathbf{w}_k \ge k\gamma$. 2. Upper bound on $\|\mathbf{w}_k\|^2$. Since a mistake means $y(\mathbf{w}_{k-1}^\top\mathbf{x}) \le 0$,

Induction gives $\|\mathbf{w}_k\|^2 \le kR^2$. 3. Combine via Cauchy–Schwarz. Since $\|\mathbf{w}^*\| = 1$,

Dividing by $\sqrt{k}\,\gamma$ (assuming $k>0$) gives $\sqrt{k} \le R/\gamma$, i.e. $k \le R^2/\gamma^2$. $\blacksquare$ The elegance of this bound is that it involves no dependence on the dimension $d$ or the number of training points $n$ — only the geometric margin $\gamma$ (how cleanly separable the classes are) and the scale $R$ of the data. This is one of the earliest and cleanest results in learning theory, and it foreshadows the central role that "margin" plays in Support Vector Machines and Maximum Margin, which explicitly maximizes $\gamma$ rather than merely benefiting from its existence.

Tradeoffs and honesty about limits. The theorem is conditional: if the data is not linearly separable, no such $\gamma > 0$ exists, and the algorithm is not guaranteed to terminate — it can cycle indefinitely, flipping between weight vectors that each misclassify some point. The bound $R^2/\gamma^2$ can also be astronomically large if the margin is tiny, so "guaranteed to converge" does not mean "converges quickly" in practice; it is a worst-case combinatorial guarantee, not a rate in the calculus sense. Unlike loss-minimization methods trained via Gradient Descent for Parameter Estimation, the perceptron does not produce a probability estimate or a notion of confidence — its output is a raw sign, and among all separating hyperplanes it finds some one, with no preference for maximizing the margin, which is exactly the gap that SVMs are designed to close.

Consider a tiny 2D dataset (already augmented with a bias coordinate of 1), with learning rate 1 and $\mathbf{w}_0 = (0,0,0)$ in the order $(w_1, w_2, b)$:

We process examples in order A, B, C, D, repeating epochs until a clean pass.

Epoch 1

End of epoch 1: $\mathbf{w} = (1,1,1)$, mistakes = 1 (only on A). Since a mistake occurred, run another epoch.

Epoch 2

Zero mistakes in epoch 2 — the algorithm halts with final weights $\mathbf{w} = (1, 1, 1)$, i.e. decision boundary $x_1 + x_2 + 1 = 0$.

Sanity check against the theorem. Here $R = \max(\sqrt{2}, 2, \sqrt{2}, 2) = 2$. The final hyperplane's unit-normalized normal is $\mathbf{w}^*=(1,1,1)/\sqrt{3}$, giving margins $y_i \mathbf{w}^{*\top}\tilde{\mathbf{x}}_i$ of $3/\sqrt3, 3/\sqrt3, 1/\sqrt3, 1/\sqrt3$ — the smallest is $\gamma = 1/\sqrt{3} \approx 0.577$. The theorem predicts at most $R^2/\gamma^2 = 4/(1/3) = 12$ mistakes; the algorithm needed only 1, consistent with the bound being a (loose) worst-case guarantee rather than a tight prediction.

The perceptron's mistake-bound framework is the seed of online learning theory, which underlies modern large-scale systems that must update models on streaming data — ad click-through prediction, fraud detection, and real-time recommendation, where retraining from scratch on a full dataset is infeasible. Its update rule is the direct ancestor of the stochastic gradient descent updates used to train logistic regression and deep neural networks, connecting cleanly to Gradient Descent for Parameter Estimation. The single-layer perceptron itself is the computational unit — a weighted sum followed by a nonlinearity — that, stacked in layers with differentiable activations, becomes the multi-layer perceptron (MLP), the base building block of modern deep learning architectures. Its inability to solve non-linearly-separable problems like XOR directly motivated both the development of multi-layer networks trained with backpropagation and the max-margin, kernelized approach of Support Vector Machines and Maximum Margin, which explicitly optimizes the margin $\gamma$ that the perceptron's convergence bound merely depends upon.

Ask the tutor: How does the perceptron's mistake bound change if we scale all the input features by a constant factor?