Title :
On the sample complexity of PAC learning half-spaces against the uniform distribution
Author_Institution :
Res. Triangle Inst., Research Triangle Park, NC, USA
fDate :
11/1/1995 12:00:00 AM
Abstract :
We prove an Ω(d/ε+1/εlog1/δ) lower bound on the PAC (probably approximately correct) learning sample complexity of learning half-spaces against the uniform distribution on the unit ball in Rd
Keywords :
computational complexity; learning (artificial intelligence); neural nets; probability; PAC learning; half-spaces; lower bound; probability distribution; probably approximately correct learning; sample complexity; Discrete wavelet transforms; Feedforward neural networks; Information analysis; Information processing; Network synthesis; Neural networks; Notice of Violation; Time frequency analysis; Wavelet analysis; Wavelet transforms;
Journal_Title :
Neural Networks, IEEE Transactions on
