Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over ℝd × ± 1 whose marginal on ℝd is Gaussian, the goal is to output a hypothesis from a target class F whose 0-1 loss is within ε of that of the best classifier in F. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces under Gaussian marginals. Our algorithm runs in time dO(K2 log(1/ε)/ε2) + (K/ε)^O(K3/ε2.5). Prior to our work, the only known algorithm for K ≥ 2 was brute-force search, with run-time exponential in d. Moreover, the dependence of our run-time on the dimension d matches that of the best known improper learning algorithm, namely d^widetildeO(K2/ε2). For the special case of a single halfspace (K=1), the best previous run-time was dO(1/ε4) + (1/ε)O(1/ε6). Our algorithm improves this to dO(1/ε2) + (1/ε)^O(1/ε2.5). Once again, the dependence on d matches that of the best known improper algorithm, namely dO(1/ε2). Furthermore, the dependence of our run-time on the dimension d is essentially optimal in the statistical query model.