# Should one choose best hypothesis among different inilizations based on lowest training error or lowest cross-validation criterion?

Recall that in standard hold-out cross validation we do the following (re-phrased from Andrew Ng's notes CS229 part VII):

1. Split the whole data set $S$ randomly into two parts $S_{train}$ and $S_{cv}$. Where $S_{cv}$ is the hold-out cross validation set
2. Train each model $M_{i}$ on $S_{train}$ only, to get some hypothesis $h_{i}$. i.e. $h_{i} = arg\min_{h \in M_{i}} \mathcal{\hat{E}}_{S_{train}}(h)$, or basically, the training/learning algorithm $\mathcal{L}$ chooses some hypothesis only from the set $M_{i}$ trained on only $S_{train}$, $h_{i} \in \mathcal{L}(M_{i}, S_{train} )$.
3. Select and output the hypothesis $\hat{h}_{cv}$ that had the smallest error $\mathcal{\hat{E} }_{S_{cv}}(h_i)$ on the hold out cross validation set i.e. $\hat{h}_{cv} \in arg\min_{h \in \{h_1, ..., h_M \}} \mathcal{\hat{E}}_{S_{cv}}(h)$

where $\mathcal{\hat{E}}_{S}(h)$ is the empirical error on the set of examples $S$.

This method makes sense to me however, it hides some of the details of different type of training methods and optimization procedures. For example, consider a learning method (like gradient descent) that has different (potentially random) initializations. In this case one could just simply select the initialization that resulted in the lowest cross-validation error. Is it ok to use that criterion even though one will use the cross-validation set again to select the best model $M_i$? The issue is that is seems that the procedure "saw" the cross-validation set twice (in training, when choosing the best initialization, and in validation).

For example, consider a learning algorithm $\mathcal{L}(M_{i}, S_{train} )$ that depends on the initialization (which might be unavoidable for training algorithms like GD or SGD on non-convex functions, like NN or CNN). Once we have the set of predictor function/hypothesis that $\mathcal{L}$ produced by each initialization trained on the training set, do we choose the trained model that resulted from a specific initialization (and from a specific model $M_i$) that performed the lowest training error or the lowest cross-validation error? Usually in training one should keep the validation set and the training set completely separate, however it seems to me a little strange to choose amongst these hypothesis that had variability in the training with the one with the lowest cross validation set. Which one is the correct one to use? If one assumed that ERM works (and believes the theoretical guarantees of ERM as data sets get large) it seems to me that one should use the initialization that uses lowest training error.

Appendix to make it super precise what I mean. The two algorithms that I am comparing are:

Method 1:

1. Split the whole data set $S$ randomly into two parts $S_{train}$ and $S_{cv}$. Where $S_{cv}$ is the hold-out cross validation set.
2. Train each model $M_{i}$ on $S_{train}$ with $T$ different initializations $init_t$ and collect each of these hypothesis in set $\mathcal{H}_{M_{i},T}$. i.e. $\mathcal{H}_{M_{i},T} = \{ h_j \mid h_j = \mathcal{L}(M_{i}, S_{train}, init_t ), t=1,...,T\}$
3. For each $\mathcal{H}_{M_{i},T}$ (the set of hypothesis outputted by training on $S_{train}$ for different iterations) select the hypothesis that is going to represent model $M_i$ as $h^{(cv)}_i = arg\min_{h \in \mathcal{H}_{M_{i},T}} \mathcal{\hat{E}}_{S_{cv}}(h)$.
4. Select and output the hypothesis $\hat{h}_{cv}$ that has the smallest error $\mathcal{\hat{E} }_{S_{cv}}(h_i)$ on the hold out cross validation set i.e. $\hat{h}_{cv} \in arg\min_{h \in \{h^{(cv)}_1, ..., h^{(cv)}_M \}} \mathcal{\hat{E}}_{S_{cv}}(h)$.

OR

Method 2:

1. Split the whole data set $S$ randomly into two parts $S_{train}$ and $S_{cv}$. Where $S_{cv}$ is the hold-out cross validation set.
2. Train each model $M_{i}$ on $S_{train}$ with $T$ different initializations $init_t$ and collect each of these hypothesis in set $\mathcal{H}_{M_{i},T}$. i.e. $\mathcal{H}_{M_{i},T} = \{ h_j \mid h_j = \mathcal{L}(M_{i}, S_{train}, init_t ), t=1,...,T\}$
3. For each $\mathcal{H}_{M_{i},T}$ (the set of hypothesis outputted by training on $S_train$ for different iterations) select the hypothesis that is going to represent model $M_i$ as $h^{(train)}_i = arg\min_{h \in \mathcal{H}_{M_{i},T}} \mathcal{\hat{E}}_{S_{train}}(h)$.
4. Select and output the hypothesis $\hat{h}_{cv}$ that has the smallest error $\mathcal{\hat{E} }_{S_{cv}}(h_i)$ on the hold out cross validation set i.e. $\hat{h}_{cv} \in arg\min_{h \in \{h^{(train)}_1, ..., h^{(train)}_M \}} \mathcal{\hat{E}}_{S_{cv}}(h)$.

It seems to me that method 1 is actually better at choosing a model that generalizes better, however, whatever number it reports as $\mathcal{\hat{E}}_{S_{cv}}(h)$ seems completely unreliable, since $h$ was chosen seeing the cross-validation set. However, method 2 avoids this problem completely by choosing the hypothesis that minimizes the training set. If has enough data to further split it and have a test set, I'd probably argue that method 1 is better. Otherwise, I'd use method 2. is this correct? Or should we always choose the predictor that minimizes the training error no matter what (since usually, this is the cost that we have provable bounds that its close to the generalization error). Or maybe both are wrong and there is a 3rd algorithm that I am not considering? (I am on purposely ignoring k-fold like methods, but maybe I shouldn't?)

Other two options that occurred to me:

1) We could combine all the hypothesis outputted per iteration using bagging (or something like boosting) and then for each model test how good this combined model does on the CV.

2) for all iterations and all models, just choose the one with smallest CV.