Communicated by Vladimir Vapnik Empirical Risk Minimization versus Maximum-Likelihood Estimation: A Case Study

We study the interaction between input distributions, learning algo-rithms, and finite sample sizes in the case of learning classification tasks. Focusing on the case of normal input distributions, we use sta-tistical mechanics techniques to calculate the empirical and expected (or generalization) errors for several well-known algorithms learning the weights of a single-layer perceptron. In the case of spherically symmetric distributions within each class we find that the simple Hebb rule, corresponding to maximum-likelihood parameter estimation, out-performs the other more complex algorithms, based on error minimiza-tion. Moreover, we show that in the regime where the overlap between the classes is large, algorithms with low empirical error do worse in terms of generalization, a phenomenon known as overtraining. The problem of pattern recognition can formally be stated as follows (Vapnik 1982): in a certain environment that is characterized by a proba