In machine learning, I know that there is a bias-variance tradeoff. As model complexity increases, bias decreases, so the test MSE decreases. However, after some threshold, the model begins to overfit, so the model's variance increases, leading to an increase in the test MSE. Overall, the test MSE curve has a U shape.
In my case, my test MSE is increasing monotonically as the model complexity increases. What could this indicate?
Overfitting. It means that your model is not learning anything new while you are adding more complexity, that is your first model is least overfit, but even that may be bad, if your test MSE really does increase from the very start already.
There could be a number of reasons for this: 1) you built your complexity based on your training data which showed you something different than your test data, 2) your model may not be appropriate for your problem, maybe a different one would perform better, 3) your data is not good so no model will be able to learn much from it, 4) your test data is completely different from your training data, could be just random chance or maybe you divided it such (maybe unknowingly).
