Perceptron Convergence & Its Limits
Novikoff’s theorem and the XOR problem.
Novikoff's theorem says a perceptron makes at most mistakes on separable data. Can any online learner do better? What survives without a separator? How many labelings can one threshold unit realize at all? The answers: the bound is optimal, it degrades gracefully with margin violations, and weights realize exactly half of all labelings of points in general position but a vanishing fraction of Boolean functions. The lesson ends with the perceptron's computational limits and the modern descendants of its analysis.
What you’ll learn
- Prove that no deterministic online learner can guarantee fewer than mistakes on margin- data.
- Derive the Freund–Schapire mistake bound for non-separable data, and state the perceptron cycling theorem.
- Prove Cover's function counting theorem, deduce the capacity of two patterns per weight, and compare it with counts of threshold functions.
- Explain why the perceptron can need exponentially many updates, and relate it to linear programming, noisy halfspace learning and the implicit bias of gradient descent.
Novikoff’s bound is optimal
Present orthogonal inputs. The learner is deterministic, so the adversary can compute each prediction from the history and declare the opposite label:
Whatever labels result, the unit vector separates them with margin at least :
So mistakes are forced, and the perceptron is optimal among dimension-free guarantees. The adversary needs dimensions. In dimension , predicting with the center of gravity of the remaining consistent weight vectors makes only mistakes (each mistake removes a constant fraction of their volume), at a far higher computational cost.
The perceptron widget's 24 blob points have augmented radius and best margin . At most how many updates does Novikoff's theorem allow from ?
Show the answer
81
. The widget's rule needs 8 from . The bound is a worst case over every order and every dataset with this geometry, and orthogonal configurations like the one in the proof attain it.
Without a separator
Give example a private extra coordinate of value : . Lift so that it pays each shortfall: with , a unit vector. Then
In a single pass, example 's private coordinate of is still zero when it arrives, so the lifted perceptron makes exactly the original's predictions. Novikoff applies to the lifted, separable data:
Minimize over : at the numerator is .
Because the bound holds for all at once, the perceptron competes with the best trade-off between margin and violations in hindsight; is a sum of squared hinge losses of the comparator. Run for many epochs, however, the plain perceptron need not settle at all.
How many labelings can one unit realize?
Add a point . A labeling of the first points either is realizable by some with , and then tilting slightly realizes it with both labels of the new point, or it is not, and then only one label of the new point is compatible:
Separators orthogonal to live in a -dimensional subspace, and projecting the points onto it preserves general position, so the second term is :
The binomial formula satisfies the same recursion (Pascal's rule) and initial values. At , symmetry of the binomial coefficients gives exactly half of all labelings:
The separable fraction is 1 for , exactly at , and falls steeply beyond: for large , a random labeling of points is separable with high probability if and with low probability if . This is the classical capacity of a perceptron, two patterns per weight; Gardner (1988) extended the calculation to separation with a margin.
The four corners of the unit square are in general position in the plane. With augmented vectors (), how many of their 16 labelings can one threshold unit realize?
- 16
- 14
- 8
- 12
Show the answer
B. 14
. The two missing labelings are XOR and XNOR.
| Inputs | Boolean functions | Linearly separable | Fraction |
|---|---|---|---|
| 1 | 4 | 4 | 100% |
| 2 | 16 | 14 | 87.5% |
| 3 | 256 | 104 | 40.6% |
| 4 | 65,536 | 1,882 | 2.9% |
Computational limits and modern descendants
Inputs in , augmented with a 1, start at with . Each update adds or subtracts a 0/1 vector, so after updates every coordinate is an integer of size at most :
At convergence, is an integer weight vector that represents the target. Håstad (1994) exhibited threshold functions of inputs (for a power of 2) all of whose integer representations need weights of size about :
So on some separable Boolean targets the perceptron makes exponentially many updates (their margins are exponentially small), while linear programming finds a separator in polynomial time.
Perceptron-style algorithms can still be made efficient. Blum, Frieze, Kannan and Vempala (1998) gave a polynomial-time variant that learns halfspaces under random classification noise, and Dunagan and Vempala (2008) showed that a perceptron with periodic rescaling solves linear programs in polynomial time. Adversarial noise is another story: when a halfspace agrees with a fraction of the examples, finding one that agrees with even is NP-hard (Feldman et al., 2006; Guruswami & Raghavendra, 2009). For Massart noise, where each label is flipped with probability at most chosen by an adversary, Diakonikolas, Gouleakis and Tzamos (2019) gave the first polynomial-time distribution-free learner.
Key takeaways
- An adversary with orthogonal inputs forces that many mistakes on any deterministic learner, so Novikoff's bound is the optimal dimension-free guarantee.
- Without separability, one pass makes at most mistakes for every comparator , by lifting each example into a private dimension; over many epochs the weights stay bounded and eventually cycle.
- Cover: points in general position admit homogeneous linear labelings, exactly half at : the capacity of two patterns per weight.
- Threshold functions are of the Boolean functions (14 of 16, 104 of 256, 1,882 of 65,536).
- Exponentially small margins force exponentially many updates, while LP is polynomial; agnostic halfspace learning is NP-hard, and gradient descent on logistic loss converges slowly toward the max-margin direction.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In dimension , center-of-gravity methods make mistakes. Why doesn't this contradict the lower bound of forced mistakes?
- The lower bound only applies to the perceptron
- The adversary's construction needs at least dimensions; when is smaller, a dimension-dependent bound can be lower
- Center-of-gravity methods are randomized, so lower bounds do not apply
- The two bounds measure different things: updates versus mistakes
Show the answer
B. The adversary's construction needs at least dimensions; when is smaller, a dimension-dependent bound can be lower
The lower bound uses orthogonal inputs, so it holds only when . The perceptron's bound is the best possible guarantee that does not depend on , which is what matters in high or infinite (kernel) dimension.
With , a unit vector separates every example with margin except one, on which . What mistake bound does the Freund–Schapire theorem give for one pass, using this and ?
- 4
- 9
- 16
- No bound: the data are not separable
Show the answer
C. 16
The violating example's shortfall is , so and , against if the data were separable with this margin.
A threshold unit has 50 weights, bias included. For points in general position, at which number of points is a uniformly random labeling separable with probability exactly ?
Show the answer
D.
, so at exactly half of all labelings are realizable: two patterns per weight.
The perceptron always converges on separable data. How can it still need exponentially many updates on targets over ?
- Some threshold functions need integer weights exponentially large in , and each update changes each weight by at most 1, so reaching such weights takes exponentially many updates
- Convergence requires visiting all inputs
- It needs exponentially many epochs only when the learning rate is too small
- It does not: the bound is always polynomial on Boolean inputs
Show the answer
A. Some threshold functions need integer weights exponentially large in , and each update changes each weight by at most 1, so reaching such weights takes exponentially many updates
From with , , and Håstad's functions need weights near . Equivalently, their margins are exponentially small, so is exponentially large.
Further reading
- A. B. J. Novikoff, "On convergence proofs on perceptrons," Proceedings of the Symposium on the Mathematical Theory of Automata 12, 615–622 (1962).
- Y. Freund & R. E. Schapire, "Large margin classification using the perceptron algorithm," Machine Learning 37, 277–296 (1999).
- T. M. Cover, "Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition," IEEE Transactions on Electronic Computers EC-14, 326–334 (1965).
- D. Soudry, E. Hoffer, M. S. Nacson, S. Gunasekar & N. Srebro, "The implicit bias of gradient descent on separable data," Journal of Machine Learning Research 19 (2018).
- S. Shalev-Shwartz & S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, ch. 9 and 21 (Cambridge University Press, 2014).