Agnostically Learning Halfspaces with Margin Errors
Shai Shalev‐Shwartz · 2009
We describe and analyze a new algorithm for agnostically learning halfspaces with respect to the margin error rate. Roughly speaking, this corresponds to the worst-case error rate after each point is perturbed by a noise vector of length at most µ. Margin based analysis is widely used in learning theory and is considered the most successful theoretical explanation for the statistical properties of several learning algorithms, such as Support Vector Machines and AdaBoost. The proposed algorithm can learn n-dimensional halfspaces in time poly(n exp ( 1 1 µ log( µɛ))), for any distribution, where µ is the margin parameter and the error rate of the learned classifier is at most ɛ plus the margin error rate of the optimal halfspace. This improves over the bound poly(n exp( ( 1