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.