Agnostically Learning Halfspaces

We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult agnostic framework of Kearns, Schapire, & Sellie, where a learner is given access to labeled examples drawn from a distribution, without restriction on the labels (e. g. adversarial noise). The algorithm constructs a hypothesis whose error rate on future examples is within an additive /spl epsi/ of the optimal halfspace, in time poly(n) for any constant /spl epsi/ > 0, under the uniform distribution over {-1, 1}/sup n/ or the unit sphere in /spl Ropf//sup n/, as well as under any log-concave distribution over /spl Ropf/ /sup n/. It also agnostically learns Boolean disjunctions in time 2/sup O~(/spl radic/n)/ with respect to any distribution. The new algorithm, essentially L/sub 1/ polynomial regression, is a noise-tolerant arbitrary distribution generalization of the "low degree" Fourier algorithm of Linial, Mansour, & Nisan. We also give a new algorithm for PAC learning halfspaces under the uniform distribution on the unit sphere with the current best bounds on tolerable rate of "malicious noise".

Authors

• Adam Tauman Kalai
• Adam R. Klivans
• Yishay Mansour
• Rocco A. Servedio

Keywords

• Machine learning algorithms
• Error analysis
• Machine learning
• Learning systems
• Optimized production technology
• Polynomials
• Artificial neural networks
• Support vector machines
• Boolean functions
• Engineering profession
• Uniform Distribution
• Polynomial Regression
• Disjunction
• Unit Sphere
• Learning Algorithms
• Least Squares Regression
• Analysis Algorithm
• Adaptive Algorithm
• Presence Of Noise
• Marginal Distribution
• Noise Model
• Time Error
• Orthonormal Basis
• Sign Function
• Real-valued Function
• Error Bounds
• Average Algorithm
• Single Iteration
• Boolean Function
• Concept Of Class
• Hermite Polynomials
• Well-studied Problem
• Sphere Packing