Reliable Learning of Halfspaces under Gaussian Marginals

We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012).The reliable PAC model captures learning scenarios where one type of error is costlier than the others. We complement our upper bound with a Statistical Query lower bound suggesting that the d {\Omega(\log (1/\alpha))} dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting.