We apply the method of complexity regularization to learn concepts fro
m large concept classes. The method is shown to automatically find a g
ood balance between the approximation error and the estimation error.
In particular, the error probability of tile obtained classifier is sh
own to decrease as O(root logn/n) to the achievable optimum, for large
nonparametric classes of distributions, as the sample size n grows. W
e also show that if the Bayes error probability Is zero and the Bayes
rule is in a known family of decision rules, the error probability is
O(logn/n) for many large families, possibly with infinite VC dimension
.