Learnability and the doubling dimension
–Neural Information Processing Systems
We prove bounds on the sample complexity of PAC learning in terms of the doubling dimension of this metric. These bounds imply known bounds on the sample complexity of learning halfspaces with respect to the uniform distribution that are optimal up to a constant factor.
Neural Information Processing Systems
Dec-31-2007