Intuition behind training and test MSE when using regression trees

Question

Imagine that we have a supervised learning setting. Training data is given by the input-output pairs $(\mathbf{x}_n, y_n)$ for $n=1,\dotsc,N$ and similarly, the test data $(\mathbf{x'}_n, y'_n)$ for $n=1,\dotsc,N'$. Rather typical setting. Further we can assume that we have $D$ features and that $y_n \in \mathbb{R}$ and $\mathbf{x}_n \in \mathbb{R}^D$. Now, the idea is to employ a recursive binary splitting in order to obtain a nested sequence of regression trees of increasing size.

Now, what would happen if there was NO true relationship between $y$ and $\mathbf{x}$? Say, I currently have a tree of some size $M$, what would happen to training and test MSE if I continued to the tree of size $M+1$? Or if there was a true relationship between $y$ and $\mathbf{x}$ but the relation was not constant (say we don't know how far from constant it is). If I increase the size of the regression tree to $M+1$ in this scenario - can I tell what would happen to training and test MSE?

In general, how does the training and test MSE work in this case? I know that the regression trees are likely to overestimate so in my understanding, if there is a true relation between input and output variables, then when increasing depth of a tree the training MSE should further decrease? But what about the test MSE? Is the MSE curve for that case U-shaped? And how about the case when there is no true relation between inputs and outputs?

Answer 1

Here is my hypothesis:

The training MSE will always decrease with increasing tree depth. Trees are prone to overfitting, and so the test error will increase because each model is highly highly overfit.

I coded something up in python to evaluate this hypothesis for the case where there is not true relationship. Here are the results. Blue is training error, orange is test error. In general, we observe what I thought we would. No surprise there.

I imagine we would see something similar in the case there is a relationship between X and y. Trees are notorious for overfitting, so the general pattern of more depth leading to more overfitting is going to persist.