On the sample complexity of PAC learning halfspaces against the uniform distribution

P. M. Long. On the sample complexity of PAC learning halfspaces against the uniform distribution. IEEE Transactions on Neural Networks, 6(6):1556-1559, 1995.

(Available in Postscript and PDF formats.)

Abstract
We prove an Omega((1/eps)(d + log(1/delta))) lower bound on the PAC learning sample complexity of learning halfspaces against the uniform distribution on the unit ball in d dimensions.