Technical Report CS-2000-07

Title: Efficient Agnostic Learning of Linear Perceptrons
Authors: Shai Ben-David and Hans Ulrich Simon
Abstract: We introduce an efficient agnostic learning algorithm for the class of half-spaces in $\Re^n$. We make no assumptions whatsoever on the example-generating distribution. Our performance guarantee is that, given any $\eta >0$, our algorithm runs in time polynomial in the sample size and dimension, and outputs a hypothesis half-space that classifies correctly at least the number of points classified correctly with margin $\eta$ by any other half-space. While our algorithm's running time is {\em not} polynomial in $1/\eta$, we prove that unless P$=$NP no such `fully polynomial' approximation scheme exists.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2000
To the main CS technical reports page

Computer science department, Technion