Efficient Learning of Linear Perceptrons

The resulting combinatorial problem - finding the best agreement half-space over an input sample - is NP hard to approximate to within some constant factor. We suggest a way to circumvent this theoretical bound by introducing a new measure of success for such algorithms. An algorithm is ILmargin successful if the agreement ratio of the half-space it outputs is as good as that of any half-space once training points that are inside the ILmargins of its separating hyper-plane are disregarded. We prove crisp computational complexity results with respect to this success measure: On one hand, for every positive IL, there exist efficient (poly-time) ILmargin successful learning algorithms. On the other hand, we prove that unless P NP, there is no algorithm that runs in time polynomial in the sample size and in 1/ IL that is ILmargin successful for all IL O. 1 Introduction We consider the computational complexity of learning linear perceptrons for arbitrary (Le.