12:15, Wed 11 Sep 1996, WeH 7220 ^^^^^ Polynomial-time guarantees for the Perceptron Algorithm Avrim Blum Abstract: The Perceptron Algorithm is a simple, well-studied algorithm for learning linear threshold functions. Given a set of linearly- separable positive and negative examples, it converges in a finite number of steps to a correct solution. Unfortunately, it can take exponential time to converge, depending on the amount of "wiggle room" available for a solution. In this work we describe a modified version of the perceptron algorithm which we prove has the following modest guarantee: it still may take exponential time to converge fully, BUT, after a polynomial number of steps, it is guaranteed to have made at least a noticeable amount of progress in the sense that by that time it has correctly classified at least a 1/2 + epsilon fraction of the data ("weak learning"). One might ask what the point of this is since given linearly separable data one can find a solution in polynomial time using linear programming. However, the Perceptron Algorithm has the advantage of noise-tolerance (both empirically and theoretically demonstrated). A specific theoretical result of this work is the first "polynomial time algorithm for learning linear threshold functions in the presence of random classification noise". Does the new algorithm have ideas useful for practice? I don't know. I'd like to try some experiments and would be interested in your suggestions. This is joint work with Alan Frieze, Ravi Kannan, and Santosh Vempala.