The Perceptron Algorithm Is Fast tor Non-Malicious Distributions

Abstract: Within the context of Valiant's protocol for learning, the Perceptron algorithm is shown to learn an arbitrary half-space in time O(r;;) if D, the proba-bility distribution of examples, is taken uniform over the unit sphere sn. Here f is the accuracy parameter. This is surprisingly fast, as "standard " approaches involve solution of a linear programming problem involving O ( 7') constraints in n dimen-sions. A modification of Valiant's distribution independent protocol for learning is proposed in which the distribution and the function to be learned may be cho-sen by adversaries, however these adversaries may not communicate. It is argued that this definition is more reasonable and applicable to real world learning than Valiant's. Under this definition, the Perceptron algorithm is shown to be a distri-bution independent learning algorithm. In an appendix we show that, for uniform distributions, some classes of infinite V-C dimension including convex sets and a class of nested differences of convex sets are learnable. The Percept ron algorithm was proved in the early 1960s[Rosenblatt,1962] t