The perceptron convergence proof
Novikoff proved that on linearly separable data the perceptron algorithm stops after a finite number of mistakes.
Why it matters
Learning acquired a guarantee: not that it seems to work, but a bound depending only on the geometry of the data.
The bound is stated through the margin between the classes and the norm of the inputs, and does not depend on the dimension of the space. The proof remains a model of online-learning analysis and was later carried over to support vector machines and other margin-based algorithms.