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.
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.