Nested cross-validation, and why plain CV leaks hyperparameter choices

The problem, from first principles

A very natural-looking but genuinely wrong pattern: run 04-grid-search's grid_search with k-fold CV as the scoring function, over the whole dataset, then report that search's best_score as "how good this model is." This leaks information: the grid search tried many hyperparameter combinations and kept whichever one scored best on those exact CV folds, so the reported number is optimistically biased — some hyperparameter combination will look good on any particular set of folds purely by chance, especially with a large grid or a small dataset, and reporting the max over many attempts is exactly what "selection bias" means.

From theory to code

Implement nested_cross_validation(input, labels, param_grid, k_outer, k_inner, train_and_predict_fn, score_fn, seed=None). Reuse 01-splitting-and-resampling's k_fold_split and 04-grid-search's grid_search. train_and_predict_fn(params, train_input, train_labels, test_input) -> predictions, score_fn(labels, predictions) -> float.

Constraints

Returns a list of k_outer scores, one per outer fold.
Hyperparameter selection (the inner loop) must only ever see the outer fold's training portion — never the outer test fold.
Each outer fold: select hyperparameters via an inner k-fold search on the outer training data, retrain once on the entire outer training fold with those hyperparameters, then evaluate exactly once on the outer test fold.
seed controls both the outer and inner splits' reproducibility.

Hints

Open one at a time. Each gives away a little more than the last.

Hint 1

The inner k_fold_split must run on outer_train_input/outer_train_labels — the outer training fold only — never on the full dataset. That's the entire difference between this and the naive, leaky approach.

Hint 2

grid_search(param_grid, fit_and_score)["best_params"] where fit_and_score is a closure over that outer fold's training data, running its own inner CV loop and returning the mean inner score — this reuses 04-grid-search unmodified, just fed a fold-scoped scoring function.