We describe a simple algorithm that runs in time $\poly(n,1/\gamma,1/\eps)$ and learns an unknown $n$-dimensional $\gamma$-margin halfspace to accuracy $1-\eps$ in the presence of malicious noise, when the noise rate is allowed to be as high as $\Theta(\eps \gamma \sqrt{\log(1/\gamma)}).$ Previous efficient algorithms could only learn to accuracy $\eps$ in the presence of malicious noise of rate at most $\Theta(\eps \gamma).$
Our algorithm does not work by optimizing a convex loss function. We show that no algorithm for learning $\gamma$-margin halfspaces that minimizes a convex proxy for misclassification error can tolerate malicious noise at a rate greater than $\Theta(\eps \gamma)$; this may partially explain why previous algorithms could not achieve the higher noise tolerance of our new algorithm.
pdf.