Validation set for early stopping

Question

I learnt about validation for early stopping by taking the course, and I have several questions.

1. Question about validation for early stopping:

   We split the dataset $D$ into a training set $G$ and a test set $T$. The training set $G$ is then split into a validation set $V$ and a smaller training set $G^-$. The trained model on $G^-$ is called $g^-$. The idea of early stopping with a validation set is 'to get a better estimate $\Bbb E_{val}(g^-)$ of a worse quantity $\Bbb E_{out}(g^-)$'.

   My question is after we get a satisfying $\Bbb E_{val}(g^-)$ thus stop training, do we simply forget about the validation set and calculate the $\Bbb E_{out}(g^-)$ on the test set?

2. Question about cross-validation for early stopping:

   I learnt that CV can also be used for early stopping. The key is to treat the training iteration as a hyperparameter, so we just perform a grid search for this hyperparameter with CV as we usually do. At the end of the day, the training iteration that yields the smallest averaged validation error will be chosen.

   Do we actually do this in practice? I think this approach is costly.

Answer 1

For you first question, I would think using CV would be a better choice.
Say you have 10 sets of hyperparameters to try, and set the CV fold to 5. For each set of hyperparameter, you will train 5 models, and have 5 scores on the each of the 5 validation sets. Then you can take the average (I think?) of these 5 validation scores, tag it as the "final score" of this hyperparameter. In this way, you can pick the best hyperparameter set out from 10.

Furthermore, you can use this best hyperparameter set to train on all the data (without test set), and evaluate this model on the test set, just to give you some idea. In this CV way, you avoid fitting a model that is best on a single validation set. In each CV-fold, you can still use early-stopping while training.

For your second question, it should be partially illustrated above. Yes, there are computational cost involved at evaluating the validation scores, but you can probably specify only to check the validation scores every N rounds (or number of trees in the case of boosting trees algorithm)

Answer 2

1. Think of it as of three sets: training, validation/dev, and test set. Training set is used to train the model. Validation set to tune hyper parameters. You use test set to verify the quality of the final result. So yes, in the end you “forget” about the training and validation sets. One exception is that you look at them to check if you’re not overfitting, a discrepancy between training and validation metrics vs test metrics could suggest that.

2. If your algorithm is fast enough or you have enough time, you would use $k$-fold cross-validation for picking hyperparameters. Otherwise, you would use held-out validation set. To find out how many iterations you need, you may simply calculate the validation metrics at each step and pick the best one afterwards. Another approach is to have a hyperparameter telling you when to stop training, e.g. “the improvement in metric between subsequent training steps is larger than $\varepsilon$”, in such case you could decide on the value of $\varepsilon$ using validation set. Notice that in second case you don’t pick the exact number of training steps, but a criteria when to stop training.