  We study efficient PAC learning of homogeneous halfspaces in $\mathbb{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 $\tilde{O}(d)$, improving the best
known result of $\tilde{O}(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.
