Twenty-four orders, six answers

The theorem bounds the mistakes for every order. It does not claim they are equal.

The outcomes.

The range: 5 to 14 updates, a factor of $2.8$, on byte-identical data. And four distinct hyperplanes, so the algorithm’s output — not merely its runtime — depends on the order the examples happened to arrive in.

Reconciling with the theorem. Here

$R = \max_i \lVert\vec{x}_i\rVert = \lVert(2,1)\rVert = \sqrt5 = 2.2361, \qquad \gamma = 0.3536$

so the bound is

$k \le \left(\frac{2.2361}{0.3536}\right)^2 = 40$

Every one of the 24 orders lands under 40, and the worst — 14 — uses about a third of the allowance. There is no contradiction: I.2.T1 is an upper bound holding uniformly over orders, and a uniform bound must accommodate the worst one. It never claimed the orders agree.

What this costs in practice. Three things follow, and none of them is obvious from the theorem alone.

The solution is not a function of the data. Two researchers running the same algorithm on the same file get different classifiers. Any claim about “the” perceptron solution for a dataset is under-specified until the order is fixed.

The margin achieved is arbitrary. The order giving 5 updates lands on $(-2,2,1)$, with geometric margin $\min_i y_i s_i/\lVert\vec{w}\rVert = 1/(2\sqrt2) = 0.3536$ — which happens to be optimal here. Other orders land on hyperplanes with worse margins. Nothing in the rule prefers the good one.

Shuffling is not a nuisance to be eliminated. It is the reason the algorithm terminates quickly on average, and the reason a single run’s update count is not a measurement of anything about the data. Chapter VIII.4 makes that argument quantitative for training runs generally.

Compare with the set of I.2.B02, where all 24 orders give 2 updates and the same weights. Order-independence happens; it is not guaranteed.