An upper bound on the sample complexity of PAC learning halfspaces with respect to the uniform distribution

P. M. Long. An upper bound on the sample complexity of PAC learning halfspaces with respect to the uniform distribution. Information Processing Letters, 87(5): 229-234, 2003.

(Available in Postscript and PDF formats.)

Abstract
We establish an upper bound on the number of examples needed for PAC-learning halfspaces with respect to the uniform distribution over the unit ball. The bound matches a known lower bound to within a constant factor.