Nested Cross-Validation for fitting methods that use CV themselves

tl;dr: If I am using fitting methods that use CV to set their hyper-parameters, is nested CV actually 3 loops deep?

Imagine you have two very simple OLS candidate models: $Y \sim X$ and $Y \sim X + X^2$ and I want to select the one that predicts best.

So there is a simple CV loop I can use, say K-folds:

loop1:
split the data into K parts
take K-1 parts as training data, last part as testing
for each partitioning
fit models to training data
compute CV error over testing data
average CV errors
choose model with lowest average CV


Now, that selects my model, but it doesn't tell me what the out of prediction error actually is going to be, so I nest that loop in another CV loop:

loop2:
split the data into J parts
take J-1 parts as training data, last part as testing
for each partitioning
perform loop 1 on training
compute CV error of model selected by loop1 on testing data
average out new CV errors


And that average is a fair estimate of out-of-prediction error

Now same problem, but imagine that rather than having to choose between two OLS models, I have to choose whether to use a (gaussian) Kernel regression or Splines to fit $Y \sim X$. Each of these methods requires CV to set their bandiwth or $\lambda$ penalty.

Do I have to change my loop1 in any way? I understand on the fit models to training data line I am actually running a further CV model-selection, but is the general loop unchanged? Am I finding the hyper-parameters on 3 times folded data?

• +1, but I am not sure I understand the difference between your OLS example and your kernel/spline example. If your model has hyperparameters such as $\lambda$ and you want to search for an optimal one using a grid of, say, 50 different $\lambda$ values, then essentially you are comparing 50 different models. This seems to me exactly similar to your initial OLS example, but with 50 models instead of 2. – amoeba Oct 22 '15 at 9:26
• You only ever need two CV's, an outer one to estimate generalization performance of your (optimized) learning method and an inner one to estimate generalization performance of a specific learning method (including hyperparameters). The inner cv is then optimized to find the best the learning method, which may include both optimizing hyperparameters but also choosing which learning algorithm to use (example). – Marc Claesen Oct 22 '15 at 9:34

You only ever need two CV's: an outer one to estimate generalization performance of your (optimized) learning method and an inner one to estimate generalization performance of a specific learning method (including hyperparameters). The inner CV is then optimized to find the best the learning method, which may include both optimizing hyperparameters but also choosing which learning algorithm to use (example).

To make things more clear, suppose the following:

• 5 sets of hyperparameters
• inner CV uses 3 folds
• outer CV uses 2 folds

Then, you are doing the following:

• training $3\times5 = 15$ models in each outer CV iteration to find hyperparameters
• training $2\times3\times5 = 30$ models in total (+ 2 final models with optimized hyperparameters)
• optimizing hyperparameters twice (once per outer fold)
• Thank you! So just to clarify, much like @amoeba said: i am not comparing the CV optimal kernel regression versus CV optimal spline, rather I am running a single CV loop where I am comparing all the candidates kernel regressions and all the candidates splines and then pick the best one among all correct? And that's the inner loop. Just making sure I am not missing a beat. (And thank you for the example, it clarified a lot!) – CarrKnight Oct 23 '15 at 12:55