From Margin to Sparsity

An improvement of Novikoff's perceptron convergence theorem is presented, reinterpreting this mistake bound as a margin dependent sparsity guarantee to give a PAC-style generalisation error bound for the classifier learned by the perceptron learning algorithm.

Abstract

We present an improvement of Noviko's perceptron convergence theorem. Reinterpreting this mistake bound as a margin dependent sparsity guarantee allows us to give a PAC-style generalisation error bound for the classi er learned by the dual perceptron learning algorithm. The bound value crucially depends on the margin a support vector machine would achieve on the same data set using the same kernel. Ironically, the bound yields better guarantees than are currently available for the support vector solution itself.