# Intuition behind training and test MSE when using regression trees

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? 