On the sample complexity of PAC learning half-spaces against the uniform distribution

Philip M. Long

doi:https://doi.org/10.1109/72.471352

On the sample complexity of PAC learning half-spaces against the uniform distribution

Philip M. Long · IEEE Transactions on Neural Networks · 1995

We prove an Omega(d/epsilon+1/epsilonlog1/delta) lower bound on the PAC (probably approximately correct) learning sample complexity of learning half-spaces against the uniform distribution on the unit ball in R(d).

Read the paper · More papers on PaperTik