Sample-Optimal PAC Learning of Halfspaces with Malicious Noise

We study efficient PAC learning of homogeneous halfspaces in R d in the presence of malicious noise of Valiant (1985) . This is a challenging noise model and only until recently has near-optimal noise tolerance bound been established under the mild condition that the unlabeled data distribution is isotropic log-concave. However, it remains unsettled how to obtain the optimal sample complexity simultaneously. In this work, we present a new analysis for the algorithm of Awasthi et al. ( 2017 ) and show that it essentially achieves the near-optimal sample complexity bound of Õ(d), improving the best known result of Õ(d 2 ). Our main ingredient is a novel incorporation of a matrix Chernoff-type inequality to bound the spectrum of an empirical covariance matrix for well-behaved distributions, in conjunction with a careful exploration of the localization schemes of Awasthi et al. (2017) . We further extend the algorithm and analysis to the more general and stronger nasty noise model of Bshouty et al. (2002) , showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in polynomial time under a mild relaxation of the noise model. Assumption 1. The distribution D is isotropic log-concave over R d ; namely, it has zero mean and unit covariance matrix, and the logarithm of its density function is concave. Observe that the family of isotropic log-concave distributions covers prominent distributions such as Gaussian, exponential, and logistic distributions [LV07, Vem10]. In particular, general