Hyperparameter Search Game

Predict first: The CV error as a function of k can be bumpy. If k=8 looks better than k=4 and k=16, does that prove k=8 is the global optimum?

Hidden CV landscape

CV scores you have paid to evaluateFull curve, revealed only at the end

Final model

Training datak-NN regression fitted with all data

Your search budget

Evaluations used0 / 8

Best tested k—

Best tested CV MSE—

Global best k🔒

Probe a value of k

Coarse-to-fine idea from the lecture: first probe widely separated values, then refine near a promising region.

Probe #	k	LOOCV MSE

You have 8 CV evaluations. Decide where to spend them.

What should students learn?

Cross-validation lets us compare candidate hyperparameters, but each evaluation can be expensive.

A coarse search such as k = 1, 2, 4, 8, 16, 32 can identify a promising scale. We can then search locally.

A local minimum is not guaranteed to be the global minimum. The point of the search strategy is to spend computation sensibly, not to create a mathematical guarantee.

After choosing k, train the final model with all available training data.