# Mathematical/Algorithmic definition for overfitting

Is there a mathematical or algorithmic definition of overfitting?

Often provided definitions are the classic 2-D plot of points with a line going through every single point and the validation loss curve suddenly going up.

But is there a mathematically rigorous definition?

Yes there is a (slightly more) rigorous definition:

Given a model with a set of parameters, the model can be said to be overfitting the data if after a certain number of training steps, the training error continues to decrease while the out of sample (test) error starts increasing. In this example out of sample (test/validation) error first decreases in synch with the train error, then it starts increasing around the 90th epoch, that is when overfitting starts

Another way to look at it is in terms of bias and variance. The out of sample error for a model can be decomposed into two components:

• Bias: Error due to the expected value from the estimated model being different from the expected value of the true model.
• Variance: Error due to the model being sensitive to small fluctuations in the data set.

Overfitting occurs when the bias is low, but the variance is high. For a data set $$X$$ where the true (unknown) model is:

$$Y = f(X) + \epsilon$$ - $$\epsilon$$ being the irreducible noise in the data set, with $$E(\epsilon)=0$$ and $$Var(\epsilon) = \sigma_{\epsilon}$$,

and the estimated model is:

$$\hat{Y} = \hat{f}(X)$$,

then the test error (for a test data point $$x_t$$) can be written as:

$$Err(x_t) = \sigma_{\epsilon} + Bias^2 + Variance$$

with $$Bias^2 = E[f(x_t)- \hat{f}(x_t)]^2$$ and $$Variance = E[\hat{f}(x_t)- E[\hat{f}(x_t)]]^2$$

(Strictly speaking this decomposition applies in the regression case, but a similar decomposition works for any loss function, i.e. in the classification case as well).

Both of the above definitions are tied to the model complexity (measured in terms of the numbers of parameters in the model): The higher the complexity of the model the more likely it is for overfitting to occur.

See chapter 7 of Elements of Statistical Learning for a rigorous mathematical treatment of the topic. Bias-Variance tradeoff and Variance (i.e. overfitting) increasing with model complexity. Taken from ESL Chapter 7

• Is it possible for both training and test error to decrease, but the model still overfits? In my mind, divergence of training and test error demonstrates overfitting, but overfitting does not necessarily entail the divergence. For example, a NN that learns to distinguish criminals from non criminals by recognizing the white background of prison photos is overfitting, but the training and test errors are probably not diverging. – yters Jul 3 '19 at 15:10
• @yters in that case, I don't think there would be any sort of way to measure the overfitting that occurs. All you have access to is training and testing data, and if both datasets both exhibit the same feature that the NN takes advantage of (white background), then that's simply a valid feature that should be taken advantage of, and not necessarily overfitting. If you didn't want that feature, then you would have to include variations on it in your data sets. – Calvin Godfrey Jul 3 '19 at 17:23
• @yters your example is what I think of as "social overfitting": Mathematically, the model is not overfitting, but there are some outside social considerations which lead to the predictor not performing well. A more interesting example is some Kaggle competitions and various open data sets like Boston Housing, MNIST, etc...the model itself might not be overfitting (in terms of bias, variance, etc...), but there is a lot of knowledge about the problem in the community in general (results from previous teams and research papers, publicly shared kernels etc...) that lead to overfitting. – Skander H. Jul 3 '19 at 17:33
• @yters (continued) that's why in theory a separate validation data set (besides the test data set) should remain in a "vault" and not used until the final validation. – Skander H. Jul 3 '19 at 17:35
• @CalvinGodfrey here's a more technical example. Let's say I have a binary classification dataset that is evenly split between the two classes, and then add noise to the classification from a fairly unbalanced Bernoulli distribution so the dataset becomes skewed towards one of the classes. I split the dataset into a train and test, and achieve high accuracy on both partly due to the unbalanced distribution. However, the accuracy of the model is not as high on the true dataset classification because the model learned the skewed Bernoulli distribution. – yters Jul 3 '19 at 18:03