Learning from mistakes
An online learner sees an input, predicts a label, and then sees the correct label before the next round. The perceptron keeps a vector and predicts the sign of . With labels , use the following rule: start at and update
The nonpositive-margin convention updates even on a tie. If the prediction rule breaks ties in favor of , every actual mistake is an update, although an update on a tie may have predicted correctly. A bound on updates is therefore also a bound on mistakes.
Separation with a positive margin
Definition 5.2.1
(Separation with margin )
A sequence is separated with margin by a unit vector if for every round . The number is the signed distance of from the hyperplane , positive when lies on the side of its label.
Theorem 5.2.2
(Perceptron mistake bound)
Suppose for every round and the sequence is separated with margin by a unit vector . Then the rule performs at most updates, even for an adaptively chosen sequence satisfying these assumptions.
Proof
(Linear progress against square-root growth)
Number only the update rounds and write for the vector after updates. Each update makes progress along :
Here labels update rounds within this proof. On an update, , so
Induction yields . Cauchy–Schwarz and give . For , division and squaring yield . The argument is deterministic: it makes no independence assumption about the sequence.
Proof X-ray
Progress is linear while the norm grows at most as a square root
Each hypothesis feeds exactly one inequality. The margin gives the lower bound , and it is needed on every update round. The update condition makes the cross term in the squared norm nonpositive, and bounds what remains, giving the upper bound . Starting from supplies the base case of that induction. Finally is used once, in Cauchy–Schwarz, to turn the projection into a bound by . Linear growth cannot remain below a square-root upper bound forever; their comparison gives the mistake bound.
Common mistake
(A large raw score is not a large margin)
If a nonzero separator satisfies , use and . A large unnormalized value of alone does not establish a large geometric margin, because scaling changes it. Substituting for in would make the bound arbitrarily small by scaling , which is absurd.
What the bound says and does not say
Worked example 5.2.3
(Reading off the bound)
In , suppose every example has and satisfies . Taking gives , , and at most four updates. This upper bound is not a promise that exactly four updates occur; it holds for every sequence meeting the stated bounds.
Worked example 5.2.4
(A complete run)
Take , , , and cycle through them. With every , so , and , giving at most updates. Start with . Round 1: , so . Round 2: and , so the margin is and . Round 3: , no update. A second cycle gives the margins , , , all positive, so the run stops after updates. The invariants check: and .
Worked example 5.2.5
(A case where the bound is attained)
In one dimension take and for every , with . Then , and the bound is . Since gives margin , the first round updates to . Every later margin equals , so exactly one update occurs and the bound is tight. Note also that the first round of any run starting from always updates, because the initial margin is zero whatever is.
The theorem assumes one separator and one positive margin work for all rounds. A finite separable dataset does have a positive minimum margin after normalizing a fixed strict separator, but an infinite sequence can be strictly classified point by point while having no uniform positive margin. For example, , in one dimension is strictly separated by , yet . The displayed theorem gives no finite numerical bound from that separator; it does not say that this particular sequence forces infinitely many mistakes.
Counterexample mode
Pointwise separation need not give a uniform margin
The margin appears in the denominator for a reason. On a sequence whose points approach the separating hyperplane, a fixed strict separator can have positive signed score on each point while the infimum of those scores is zero. A proof that assumes a single positive cannot replace that assumption by pointwise strict inequalities without further work.
This is a bound on the number of online updates, not automatically a bound on test error under an unknown distribution. To derive a statistical statement one needs a sampling model and a rule for selecting an output predictor.
Common mistake
(Forgetting the threshold term)
The theorem assumes homogeneous hyperplanes through the origin. An affine threshold can be represented by augmenting inputs with a constant coordinate, but the augmented norm bound and the augmented margin must then be recomputed; reusing and from the original inputs is not justified.
Practice and solutions
Quick check
(If and , give an update bound.)
Substitute into .
Solution · Answer
updates at most.
Quick check
(In one dimension let , , . What is under the stated update convention?)
Compute the margin first.
Solution · Answer
The margin is , so the rule updates: .
Quick check
(Why does the proof apply to an adaptive sequence?)
List which properties of the sequence the proof uses.
Solution · Answer
Every step uses only the stated pointwise norm and margin inequalities, which remain valid when each example is chosen after seeing the learner's earlier behavior; no probabilistic independence enters.
Quick check
(Does a bound of ten updates imply a test error at most ten percent?)
Compare what is being counted in each statement.
Solution · Answer
No. An online count and a test-error probability are different quantities. A distributional assumption and an output-selection analysis are needed to connect them.