CONCEPT-LEARNING USING COMPLEXITY REGULARIZATION

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 .