On the sample complexity of PAC learning half-spaces against the uniform distribution.
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).
Long
P M
PM
Res. Triangle Inst., Research Triangle Park, NC.