Timezone: »
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.
Author Information
Phil Long (NEC Labs)
Rocco A Servedio (Columbia University)
More from the Same Authors
-
2014 Poster: Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms »
Siu On Chan · Ilias Diakonikolas · Rocco A Servedio · Xiaorui Sun -
2011 Session: Spotlight Session 6 »
Phil Long -
2011 Session: Oral Session 8 »
Phil Long -
2011 Poster: Algorithms and hardness results for parallel large margin learning »
Rocco A Servedio · Phil Long -
2011 Spotlight: Algorithms and hardness results for parallel large margin learning »
Rocco A Servedio · Phil Long -
2008 Poster: Adaptive Martingale Boosting »
Phil Long · Rocco A Servedio -
2008 Spotlight: Adaptive Martingale Boosting »
Phil Long · Rocco A Servedio -
2007 Spotlight: One-Pass Boosting »
Zafer Barutcuoglu · Phil Long · Rocco A Servedio -
2007 Poster: One-Pass Boosting »
Zafer Barutcuoglu · Phil Long · Rocco A Servedio -
2007 Spotlight: Boosting the Area under the ROC Curve »
Phil Long · Rocco A Servedio -
2007 Poster: Boosting the Area under the ROC Curve »
Phil Long · Rocco A Servedio -
2006 Poster: Learnability and the doubling dimension »
Yi Li · Phil Long -
2006 Spotlight: Learnability and the doubling dimension »
Yi Li · Phil Long -
2006 Poster: Attribute-efficient learning of linear threshold functions under unconcentrated distributions »
Phil Long · Rocco A Servedio