Concept learning using complexity regularization

We apply the method of complexity regularization to learn concepts from large concept classes. The method is shown to automatically find the best balance between the approximation error and the estimation error. In particular, the error probability of the obtained classifier is shown to decrease as 0(√(log n/n)) to the achievable optimum, for large nonparametric classes of distributions, as the sample size n grows. In pattern recognition, or concept learning, the value of a {0,1}-valued random variable Y is to be predicted based upon observing an R^d-valued random variable X