# Why is empirical risk minimization prone to overfitting?

According to Chapter 8 of the book Deep Learning, "..empirical risk minimization is prone to overfitting. models with high capacity can simply memorize the training se." My question why is it so? Models with high capacity can also memorise the training set when we have the true distribution and reduce the true cost function.

• I thought your question can be reduced to this one: is empirical risk minimization more prone to overfitting than the minimization when we use the true cost function if exists? But unfortunately, I don't think the true cost function exists. Since the $p^*$ in $E_{x\sim p^*} [loss(x, M)]$ is generally unknown, we should use this: $E_D [loss(x, \hat M)]=\frac{1}{D}\sum_{x\in D}loss(x,\hat M)$. – Lerner Zhang Jun 30 '19 at 10:35

It's a pretty general question, I'll try to lay out the main ideas in a simple manner. There are a lot of good resources which you can use for further reading, one which I can recommend is Shai Shalev-Schwarz "Understanding Machine Learning" which focuses on the theoretical foundations for machine learning.

Put very simply, the idea in machine learning is to be able to learn (for example, a classifier) given a set of labeled examples ("training set"), and then use that classifier to also classify new data ("test set"). The goal is to do well on the unseen test data - this is known as "generalization".

Probably the most natural way to accomplish the above task is to choose a classifier that performs best on the training data. This is what is known as ERM (empirical risk minimization).

But is that always a good strategy? As it turns out, the answer is no.

Suppose we are given the following training data: points in blue belong to class 1, and points in red belong to class 2. Our goal is to learn a classifier that "separates" them (i.e can classify a new example to one of the classes).

Then, if I were to follow the ERM rule, I would choose the classifier denoted in green: It achieves an accuracy of 100% on the training data (no example is mis-classified).

But is this really what we wanted? We learned a very complex model, but most of the chances are that the data we got was a little noisy. With ERM, we essentially "learned" the noise, instead of ignoring it. If we were now to receive new test data from a similar distribution, we are likely to make mistakes. This is the phenomena of overfitting: We fitted out training data very well (too well), at the cost of performing badly on test data. Essentially, we hurt our ability to generalize!

If, on the other hand, we are willing to not perform perfectly on the training set, than we can actually do better on test data (see the black classifier in the above image). It's a little surprising when you encounter it for the first time.

The transition from the green classifier to something that resembles the black classifier can be achieved by introducing regularization - you've probably encountered the R-ERM (regularized empirical risk minimization), but this is already another subject.

If we know the true distribution, memorizing it won't lead to overfitting.

In the example in the above answer, suppose the true distribution is the black curve plus some noise, we will know that the empirical loss at those overfit points is different from their expected loss, $E_{sample}[L(x,y,\theta)]\neq E_{data}[L(x,y,\theta)]$. Therefore minimizing the "true loss" in this case will not lead to overfitting (if the loss is properly defined).

In most problems we won't know the true distribution, so we often need some techniques (regularization, data augmentation, network structures, etc.) to close the gap between our data/model and the true distribution.

There are already some good answers here explaining the general point, I'll just add two more points:

1. The overfitting of the empirical risk is especially prominent in cases of a small training set. When the data don't contain enough information to learn the underlying pattern, more regularization is needed to fill in the gap.

2. In the specific case of the Deep learning the case is not so clear. Especially with very large nets, it is virtually impossible to find the global minimizer of the loss function, which likely corresponds to the heavily overfitted case. See AISTATS 2015 paper by Choromanska et al. for details [1]. Moreover, there are various interesting works studying the memorization behavior of the deep nets, such as [2] and [3]. Their implication is that even though deep nets have certainly the capacity to overfit terribly, in practice they generalize well even when trained with the unregularized empirical risk.