Reliable Learning of Halfspaces under Gaussian Marginals

The problem of learning halfspaces is one of the classical and most well-studied problems in machine learning--going back to the Perceptron algorithm [Ros58]--and has had great impact on many other influential techniques, including SVMs [Vap98] and AdaBoost [FS97]. Here we focus on learning halfspaces from random labeled examples. The computational complexity of this task crucially depends on the choice of the underlying model. For example, in the realizable PAC model (i.e., with clean labels), the problem is known to be efficiently solvable (see, e.g., [MT94]) via a reduction to linear programming. Unfortunately, this method is quite fragile and breaks down in the presence of noisy labels. In the noisy setting, the computational complexity of the problem depends on the choice of noise model and distributional assumptions. In this work, we study the problem of distribution-specific PAC learning of halfspaces, with respect to Gaussian marginals, in the reliable agnostic model of [KKM12]. Formally, we have the following definition.