Commentary on Smoothed Analysis of the Perceptron Algorithm

This paper does not actually prove that the Perceptron Algorithm has polynomial smoothed complexity. In fact, the analysis indicates that the Preceptron Algorithm should have infinite smoothed complexity. This may explain why the Perceptron Algorithm is generally regarded as working poorly in practice.

On the other hand, this paper does prove that it is unlikely that the Perceptron Algorithm will run for too long on a perturbation of any given input instance. However, when one quantifies the tradeoff between "unlikely" and "run too long", one obtains an infinite expectation. The expectation of the square root of the running time is also infinite, but for all lower powers it is polynomial.

Dan Spielman