An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution
We show that halfspaces in n dimensions can be PAC-learned with respect to the uniform distribution with accuracy 8 and confidence delta using O(1/epsilon (n + log 1/delta)) examples. (C) 2003 Elsevier B.V. All rights reserved.
sample complexity pac-learning halfspaces machine learning computational complexity