The test set values increase over iterations signaling overfitting, but why is the training set deviance continuing to drop at the same time? This seems to indicate to me that the training set is continuing to get better over iterations but the test set only worsens, there is also a large gap in the starting points of the deviance between the test and training sets. Any clues as to where to look for causes would be helpful.
This is exactly what it means to overfit!
In many scenarios, you can make the training performance arbitrarily great, perhaps going as far as playing connect-the-dots. This is analogous to your training set curve decreasing. However, as you fit too tightly, you stop modeling the trend (signal) and start modeling coincidences in the training data that will not be present in the test data (noise).
Instead of looking at the deviance plot for training and test data we could also take a look at some plots of actual fits.
Below is an example of fitting with a polynomial. From left to right the number of terms in the polynomial model is increased.
What you can see is that as we go to the right, and as the number of terms used to fit are increased, then...
The training data error will continuously improve (get smaller) and the fitted line will be a better fit with the training data.
But this is not the same for the validation/test data error. Initially the error improves in the same way as with the training data, but further on the error will increase and get worse.
This is because the lower training data error is not necessarily a sign that the model captures the deterministic part of the model. Instead, at some point if the model becomes too flexible, then it becomes too sensitive to fitting the random part of the training data.
