Shape of MSE in polynomial regression

Question

In polynomial regression, an increase in the degree of freedom can cause high variance and low bias. So model overfits on the training set and loses its generalization. On the other hand with a low degree of freedom, the model has low variance and high bias. As a result, the error rate curve on the test set is U-shaped.

But the error rate on the training set should always be descending because the model tries to fit on those data and with a higher degree of freedom, this will be done better. So the plot of MSE on both sets should be like this:

But on my data with sklearn library, I get this one:

What can be the reason for the increase in error rate on the training set with higher degrees of freedom? Why I get a U-shaped curve on the training set just like a test set?

Also, I fit three curves with 7, 15, and 35 degrees. As you can see by increasing the degree of freedom, the curve tends to be more linear in smaller data and just overfits on larger ones. But I can't get why does this happens?

---

Update 1: To check the possibility of overflow in storing coefficient values in float type, I multiplied the values of y by 10^20 in both training and test sets to coefficients not to be so small. As a result, the value of the coefficient did not change and only times 10^20. Also, R^2 doesn't change and the curve has the same shape.

---

Update 2: Also I tried to store data as float128, Again No change in Error rate or coefficients.

Answer 1

Even though this question is a bit older, this answer might still give a hint: the problem most probably is related to the fact that finding higher order polynomials very is often a numerically ill-conditioned problem. For example, algorithms for obtaining polynomial coefficients are based on a least-squares fit and usually use a Vandermonde matrix which contains possibly high powers of the input values. This may result in a system that is numerically very difficult to solve.

If I count correctly, your training datasets consists of 41 records. For constructing a polynomial of order k you would need k+1 data points, or in other words: if, for your data set, you use a polynomial of order 40, your interpolation should in principle exactly pass through all data points and the training error should vanish. However, in the Vandermode matrix you will have input values of your data to the power of ~40! Numerically, this is a terrible thing, and even closed form solutions require to invert the Vandermonde matrix. What you observed in the polynomial fit and then also in the train loss/MSE is the result of this numerically ill-conditioned system.

I would suggest not to use polynomials of such high order. Instead piecewise splines are possible more reliable (but there are plenty of other methods around as well).