Learning Large-Margin Halfspaces with More Malicious Noise
Abstract
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.
Cite
Text
Long and Servedio. "Learning Large-Margin Halfspaces with More Malicious Noise." Neural Information Processing Systems, 2011.Markdown
[Long and Servedio. "Learning Large-Margin Halfspaces with More Malicious Noise." Neural Information Processing Systems, 2011.](https://mlanthology.org/neurips/2011/long2011neurips-learning/)BibTeX
@inproceedings{long2011neurips-learning,
title = {{Learning Large-Margin Halfspaces with More Malicious Noise}},
author = {Long, Phil and Servedio, Rocco},
booktitle = {Neural Information Processing Systems},
year = {2011},
pages = {91-99},
url = {https://mlanthology.org/neurips/2011/long2011neurips-learning/}
}