Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Perceptron Convergence & Its Limits

Novikoff’s theorem and the XOR problem.

Novikoff's theorem says a perceptron makes at most (R/γ)2(R/\gamma)^2 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 dd weights realize exactly half of all labelings of 2d2d 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 ⌊(R/γ)2⌋\lfloor(R/\gamma)^2\rfloor mistakes on margin-γ\gamma 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

DerivationProof
  1. xt=R et,yt=−y^t(t=1,…,k)\mathbf x_t=R\,\mathbf e_t,\qquad y_t=-\hat y_t\qquad(t=1,\dots,k)

    Present orthogonal inputs. The learner is deterministic, so the adversary can compute each prediction from the history and declare the opposite label:

  2. yt u⋅xt=yt⋅yt Rk=Rk ≥ γbecause k≤(R/γ)2y_t\,\mathbf u\cdot\mathbf x_t=y_t\cdot\frac{y_t\,R}{\sqrt k}=\frac{R}{\sqrt k}\ \ge\ \gamma\qquad\text{because }k\le(R/\gamma)^2

    Whatever labels result, the unit vector u=1k∑tytet\mathbf u=\frac1{\sqrt k}\sum_ty_t\mathbf e_t separates them with margin at least γ\gamma:

  3. perceptron: (Rγ)2volume cutting: O(dlog⁡Rγ)\text{perceptron: }\Big(\frac R\gamma\Big)^2\qquad\text{volume cutting: }\order{d\log\frac R\gamma}

    So kk mistakes are forced, and the perceptron is optimal among dimension-free guarantees. The adversary needs kk dimensions. In dimension d≪(R/γ)2d\ll(R/\gamma)^2, predicting with the center of gravity of the remaining consistent weight vectors makes only O(dlog⁡(R/γ))\order{d\log(R/\gamma)} mistakes (each mistake removes a constant fraction of their volume), at a far higher computational cost.

Predict before you look

The perceptron widget's 24 blob points have augmented radius R=1.92R=1.92 and best margin γ=0.213\gamma=0.213. At most how many updates does Novikoff's theorem allow from w=0\mathbf w=0?

Show the answer

81

(1.92/0.213)2≈9.012≈81(1.92/0.213)^2\approx9.01^2\approx81. The widget's rule needs 8 from w=0\mathbf w=0. 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

DerivationProof by lifting
  1. yt u′⋅xt′=yt u⋅xt+dtZ ≥ γZ,∥xt′∥2≤R2+Δ2y_t\,\mathbf u'\cdot\mathbf x'_t=\frac{y_t\,\mathbf u\cdot\mathbf x_t+d_t}{Z}\ \ge\ \frac\gamma Z,\qquad\norm{\mathbf x'_t}^2\le R^2+\Delta^2

    Give example tt a private extra coordinate of value Δ\Delta: xt′=(xt,Δet)\mathbf x'_t=(\mathbf x_t,\Delta\mathbf e_t). Lift u\mathbf u so that it pays each shortfall: u′=(u,1Δ(y1d1,y2d2,… ))/Z\mathbf u'=\big(\mathbf u,\tfrac1\Delta(y_1d_1,y_2d_2,\dots)\big)/Z with Z=1+D2/Δ2Z=\sqrt{1+D^2/\Delta^2}, a unit vector. Then

  2. M ≤ (R2+Δ2) (1+D2/Δ2)γ2M\ \le\ \frac{(R^2+\Delta^2)\,(1+D^2/\Delta^2)}{\gamma^2}

    In a single pass, example tt's private coordinate of w′\mathbf w' is still zero when it arrives, so the lifted perceptron makes exactly the original's predictions. Novikoff applies to the lifted, separable data:

  3. M ≤ (R+Dγ)2for every u and γ>0M\ \le\ \Big(\frac{R+D}{\gamma}\Big)^2\qquad\text{for every }\mathbf u\text{ and }\gamma>0

    Minimize over Δ\Delta: at Δ2=RD\Delta^2=RD the numerator is (R2+RD)(1+D/R)=(R+D)2(R^2+RD)(1+D/R)=(R+D)^2.

Because the bound holds for all (u,γ)(\mathbf u,\gamma) at once, the perceptron competes with the best trade-off between margin and violations in hindsight; D2D^2 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?

DerivationProof
  1. C(N+1,d)=C(N,d)+#{labelings of N points realizable with w⊥xN+1}C(N+1,d)=C(N,d)+\#\big\{\text{labelings of }N\text{ points realizable with }\mathbf w\perp\mathbf x_{N+1}\big\}

    Add a point xN+1\mathbf x_{N+1}. A labeling of the first NN points either is realizable by some w\mathbf w with w⋅xN+1=0\mathbf w\cdot\mathbf x_{N+1}=0, and then tilting w\mathbf w 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:

  2. C(N+1,d)=C(N,d)+C(N,d−1),C(1,d)=2,C(N,1)=2C(N+1,d)=C(N,d)+C(N,d-1),\qquad C(1,d)=2,\qquad C(N,1)=2

    Separators orthogonal to xN+1\mathbf x_{N+1} live in a (d−1)(d-1)-dimensional subspace, and projecting the NN points onto it preserves general position, so the second term is C(N,d−1)C(N,d-1):

  3. C(2d,d)=2∑k=0d−1(2d−1k)=2⋅22d−2=12⋅22dC(2d,d)=2\sum_{k=0}^{d-1}\binom{2d-1}{k}=2\cdot2^{2d-2}=\tfrac12\cdot2^{2d}

    The binomial formula satisfies the same recursion (Pascal's rule) and initial values. At N=2dN=2d, symmetry of the binomial coefficients gives exactly half of all labelings:

The separable fraction is 1 for N≤dN\le d, exactly 12\tfrac12 at N=2dN=2d, and falls steeply beyond: for large dd, a random labeling of αd\alpha d points is separable with high probability if α<2\alpha<2 and with low probability if α>2\alpha>2. This is the classical capacity of a perceptron, two patterns per weight; Gardner (1988) extended the calculation to separation with a margin.

Check your understanding

The four corners of the unit square are in general position in the plane. With augmented vectors (d=3d=3), how many of their 16 labelings can one threshold unit realize?

  1. 16
  2. 14
  3. 8
  4. 12
Show the answer

B. 14

C(4,3)=2[(30)+(31)+(32)]=2(1+3+3)=14C(4,3)=2\big[\binom30+\binom31+\binom32\big]=2(1+3+3)=14. The two missing labelings are XOR and XNOR.

Inputs nnBoolean functions 22n2^{2^n}Linearly separableFraction
144100%
2161487.5%
325610440.6%
465,5361,8822.9%
Counted by running the perceptron on every function: the separable ones converge and the rest never do. The cube's vertices are not in general position, so Cover's formula would overcount (C(8,4)=128>104C(8,4)=128>104). In general there are 2Θ(n2)2^{\Theta(n^2)} threshold functions among 22n2^{2^n} Boolean functions. Which functions single units miss is proved in A Short History of AI (XOR) and Symbols vs. Connections (parity has order nn).

Computational limits and modern descendants

DerivationFinite is not fast: exponentially many updates
  1. ∥wM∥∞≤M\norm{\mathbf w_M}_\infty\le M

    Inputs in {0,1}n\{0,1\}^n, augmented with a 1, start at w=0\mathbf w=0 with η=1\eta=1. Each update adds or subtracts a 0/1 vector, so after MM updates every coordinate is an integer of size at most MM:

  2. M ≥ ∥wM∥∞ ≥ 2(nlog⁡2n)/2−nM\ \ge\ \norm{\mathbf w_M}_\infty\ \ge\ 2^{(n\log_2n)/2-n}

    At convergence, wM\mathbf w_M is an integer weight vector that represents the target. Håstad (1994) exhibited threshold functions of nn inputs (for nn a power of 2) all of whose integer representations need weights of size about 2(nlog⁡2n)/2−n2^{(n\log_2n)/2-n}:

  3. perceptron: 2Ω(nlog⁡n) updateslinear programming: poly⁡(n) time\text{perceptron: }2^{\Omega(n\log n)}\ \text{updates}\qquad\text{linear programming: }\poly(n)\ \text{time}

    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 1−ε1-\varepsilon fraction of the examples, finding one that agrees with even 12+ε\tfrac12+\varepsilon is NP-hard (Feldman et al., 2006; Guruswami & Raghavendra, 2009). For Massart noise, where each label is flipped with probability at most η<12\eta<\tfrac12 chosen by an adversary, Diakonikolas, Gouleakis and Tzamos (2019) gave the first polynomial-time distribution-free learner.

Key takeaways

  • An adversary with ⌊(R/γ)2⌋\lfloor(R/\gamma)^2\rfloor 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 ((R+D)/γ)2\big((R+D)/\gamma\big)^2 mistakes for every comparator (u,γ)(\mathbf u,\gamma), by lifting each example into a private dimension; over many epochs the weights stay bounded and eventually cycle.
  • Cover: NN points in general position admit 2∑k<d(N−1k)2\sum_{k<d}\binom{N-1}{k} homogeneous linear labelings, exactly half at N=2dN=2d: the capacity of two patterns per weight.
  • Threshold functions are 2Θ(n2)2^{\Theta(n^2)} of the 22n2^{2^n} 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.

Question 1

In dimension dd, center-of-gravity methods make O(dlog⁡(R/γ))\order{d\log(R/\gamma)} mistakes. Why doesn't this contradict the lower bound of ⌊(R/γ)2⌋\lfloor(R/\gamma)^2\rfloor forced mistakes?

  1. The lower bound only applies to the perceptron
  2. The adversary's construction needs at least ⌊(R/γ)2⌋\lfloor(R/\gamma)^2\rfloor dimensions; when dd is smaller, a dimension-dependent bound can be lower
  3. Center-of-gravity methods are randomized, so lower bounds do not apply
  4. The two bounds measure different things: updates versus mistakes
Show the answer

B. The adversary's construction needs at least ⌊(R/γ)2⌋\lfloor(R/\gamma)^2\rfloor dimensions; when dd is smaller, a dimension-dependent bound can be lower

The lower bound uses kk orthogonal inputs, so it holds only when d≥kd\ge k. The perceptron's bound is the best possible guarantee that does not depend on dd, which is what matters in high or infinite (kernel) dimension.

Question 2

With R=1R=1, a unit vector u\mathbf u separates every example with margin γ=0.5\gamma=0.5 except one, on which y u⋅x=−0.5y\,\mathbf u\cdot\mathbf x=-0.5. What mistake bound does the Freund–Schapire theorem give for one pass, using this u\mathbf u and γ\gamma?

  1. 4
  2. 9
  3. 16
  4. No bound: the data are not separable
Show the answer

C. 16

The violating example's shortfall is d=0.5−(−0.5)=1d=0.5-(-0.5)=1, so D=1D=1 and ((R+D)/γ)2=(2/0.5)2=16\big((R+D)/\gamma\big)^2=(2/0.5)^2=16, against 44 if the data were separable with this margin.

Question 3

A threshold unit has 50 weights, bias included. For points in general position, at which number of points NN is a uniformly random labeling separable with probability exactly 12\tfrac12?

  1. N=50N=50
  2. N=250N=2^{50}
  3. N=2,500N=2{,}500
  4. N=100N=100
Show the answer

D. N=100N=100

C(2d,d)=12⋅22dC(2d,d)=\tfrac12\cdot2^{2d}, so at N=2d=100N=2d=100 exactly half of all labelings are realizable: two patterns per weight.

Question 4

The perceptron always converges on separable data. How can it still need exponentially many updates on targets over {0,1}n\{0,1\}^n?

  1. Some threshold functions need integer weights exponentially large in nn, and each update changes each weight by at most 1, so reaching such weights takes exponentially many updates
  2. Convergence requires visiting all 2n2^n inputs
  3. It needs exponentially many epochs only when the learning rate is too small
  4. It does not: the bound (R/γ)2(R/\gamma)^2 is always polynomial on Boolean inputs
Show the answer

A. Some threshold functions need integer weights exponentially large in nn, and each update changes each weight by at most 1, so reaching such weights takes exponentially many updates

From w=0\mathbf w=0 with η=1\eta=1, ∥wM∥∞≤M\norm{\mathbf w_M}_\infty\le M, and Håstad's functions need weights near 2(nlog⁡2n)/2−n2^{(n\log_2n)/2-n}. Equivalently, their margins are exponentially small, so (R/γ)2(R/\gamma)^2 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).