A polynomial-time algorithm for learning noisy linear threshold functions

The authors consider the problem of learning a linear threshold function (a halfspace in n dimensions, also called a “perceptron”). Methods for solving this problem generally fall into two categories. In the absence of noise, this problem can be formulated as a linear program and solved in polynomial time with the ellipsoid algorithm (or interior point methods). On the other hand, simple greedy algorithms such as the perceptron algorithm seem to work well in practice and can be made noise tolerant; but, their running time depends on a separation parameter (which quantifies the amount of “wiggle room” available) and can be exponential in the description length of the input. They show how simple greedy methods can be used to find weak hypotheses (hypotheses that classify noticeably more than half of the examples) in polynomial time, without dependence on any separation parameter. This results in a polynomial-time algorithm for learning linear threshold functions in the PAC model in the presence of random classification noise. The algorithm is based on a new method for removing outliers in data. Specifically, for any set S of points in Rⁿ, each given to b bits of precision, they show that one can remove only a small fraction of S so that in the remaining set T, for every vector v, max_xεT(v·x)²⩽poly(n,b)|T|^-1 Σ_xεT(v·x)². After removing these outliers, they are able to show that a modified version of the perceptron learning algorithm works in polynomial time, even in the presence of random classification noise