Learning Halfspaces with Malicious Noise

A. R. Klivans, P. M. Long and R. A. Servedio. Learning Halfspaces with Malicious Noise. JMLR, 10: 2715-2740, 2009.

Abstract
We give new algorithms for learning halfspaces in the challenging malicious noise model, where an adversary may corrupt both the labels and the underlying distribution of examples. Our algorithms can tolerate malicious noise rates exponentially larger than previous work in terms of the dependence on the dimension n, and succeed for the fairly broad class of all isotropic log-concave distributions. We give poly(n, 1/eps)-time algorithms for solving the following problems to accuracy eps:

Learning origin-centered halfspaces in n dimensions with respect to the uniform distribution on the unit ball with malicious noise rate eta = Omega(eps^2/log(n/eps)). (The best previous result was Omega(eps/(n log (n/eps))^(1/4)).)
Learning origin-centered halfspaces with respect to any isotropic log-concave distribution in n dimensions with malicious noise rate eta = Omega(eps^3/log^2(n/eps)). This is the first efficient algorithm for learning under isotropic log-concave distributions in the presence of malicious noise.

We also give a poly(n,1/eps)-time algorithm for learning origin-centered halfspaces under any isotropic log-concave distribution in the presence of adversarial label noise at rate eta = Omega(eps^3/log(1/eps)). In the adversarial label noise setting (or agnostic model), labels can be noisy, but not example points themselves. Previous results could handle eta = Omega(eps) but had running time exponential in an unspecified function of 1/eps. Our analysis crucially exploits both concentration and anti-concentration properties of isotropic log-concave distributions. Our algorithms combine an iterative outlier removal procedure using Principal Component Analysis together with ``smooth'' boosting.