Grid search and random search: Exercises — AI-ML deep dive

Before we begin, one picture fixes the whole vocabulary you need.

Level 1 — Recognition

L1·Q1 — Parameter or hyperparameter?

For each item say parameter (learned during training) or hyperparameter (set before training): (a) the weight $w$ in $y = w x + b$ , (b) the learning rate $α$ , (c) the regularization strength $λ$ , (d) the bias $b$ , (e) the number of trees in a random forest.

Recall Solution

What decides it: ask "does gradient descent update this from data, or did I type it in before training started?"

(a) $w$ — parameter (updated each training step).
(b) $α$ — hyperparameter (you pick it; it controls how $w$ updates).
(c) $λ$ — hyperparameter (see Regularization; you choose how hard to penalize big weights).
(d) $b$ — parameter (learned like $w$ ).
(e) number of trees — hyperparameter (structural choice made before fitting).

L1·Q2 — Count the grid

Learning rate grid $α \in {0.001, 0.01, 0.1}$ (3 values) and regularization grid $λ \in {0.01, 0.1, 1, 10}$ (4 values). Grid search trains one model per combination. How many models?

Recall Solution

Rule: grid search takes the product of the counts — every $α$ paired with every $λ$ . $models = 3 \times 4 = 12.$ Picture a $3 \times 4$ lattice of dots: 12 corners.

L1·Q3 — Grid vs random in one line

A friend says "random search is just grid search with sloppy spacing." State the one true structural difference.

Recall Solution

Grid search puts points on a fixed lattice — the values on each axis are reused across every combination. Random search draws each point independently from a distribution, so (in expectation) every trial uses a fresh, distinct value on every axis. That distinctness is the entire advantage, not "sloppiness."

Level 2 — Application

L2·Q1 — Full grid cost with cross-validation

You tune 3 values of $C$ , 4 of $γ$ , and 5 of max-depth $d$ , using 5-fold cross-validation. How many total training runs?

Recall Solution

Step 1 — combinations: $3 \times 4 \times 5 = 60$ . Step 2 — each combination is trained once per fold, so multiply by folds $k = 5$ : $60 \times 5 = 300 training runs.$ Why fold-multiply? In $k$ -fold CV each configuration is fit $k$ times (each time holding out a different slice), and the reported score is the average — that is what makes the score reliable.

L2·Q2 — Grid step size on a log axis

You want to try $C$ across ${0.01, 0.1, 1, 10, 100}$ . Are these evenly spaced? What kind of spacing is it, and why is that the right choice for $C$ ?

Recall Solution

They are not evenly spaced on a normal ruler ( $0.01$ to $0.1$ is a gap of $0.09$ ; $10$ to $100$ is a gap of $90$ ). They are evenly spaced in multiplication: each is $\times 10$ the previous. This is log-uniform spacing (equal steps in $lo g_{10}$ ). It is right for $C$ because what matters is the order of magnitude: the difference between $0.01$ and $0.1$ matters as much as $10$ vs $100$ . A linear grid would waste almost all its points in the large-number region and never explore small $C$ properly.

L2·Q3 — Reading the grid heat-map

The figure below shows validation scores on a $4 \times 4$ grid over $(lo g_{10} C, lo g_{10} γ)$ . Read off the best cell and its score.

Recall Solution

Scan for the brightest amber cell. It sits at $C = 10$ ( $lo g_{10} C = 1$ ) and $γ = 0.1$ ( $lo g_{10} γ = - 1$ ), with validation score $0.93$ . Why this cell wins: moderate $C$ (not so large it overfits) with moderate $γ$ (kernel neither too wide nor too spiky) balances fit vs generalization — see Overfitting and Underfitting.

Level 3 — Analysis

L3·Q1 — Unique values per axis

You have a budget of $n = 100$ trials in $k = 2$ dimensions. Compare unique values explored per hyperparameter for (a) a square grid, (b) random search.

Recall Solution

(a) Square grid: to get $100$ cells in 2D you use $100 = 10$ values per axis. So each hyperparameter is only ever tried at 10 distinct values (each value reused across a whole row/column). (b) Random search: each of the $100$ trials draws a fresh independent value on each axis, so in expectation 100 distinct values per hyperparameter. General rule: grid gives $n^{1/ k}$ unique values per axis; random gives $n$ . In this case $10$ vs $100$ — a 10× coverage gain on the axis that might actually matter.

L3·Q2 — The low-effective-dimension argument

Suppose the true objective is $f (h_{1}, h_{2}) = g (h_{1}) + ϵ (h_{2})$ where $g$ is important and $ϵ (h_{2})$ is negligible noise. With a $n \times n$ grid vs $n$ random points, how many distinct evaluations of the important function $g$ does each give?

Recall Solution

Because $f$ depends meaningfully only on $h_{1}$ , what matters is how many different $h_{1}$ values you sampled.

Grid: only $n$ distinct $h_{1}$ values → only $n$ useful evaluations of $g$ . The $h_{2}$ axis is wasted since $ϵ$ barely moves the score.
Random: $n$ distinct $h_{1}$ values → $n$ useful evaluations of $g$ . Conclusion: when the objective secretly depends on few dimensions, random search is $n$ -times more informative. This is the reason random search dominates grid in high dimensions.

L3·Q3 — Where grid still wins

Give a concrete scenario where grid search is genuinely the better choice, and justify it.

Recall Solution

Scenario: tuning 2 discrete, categorical hyperparameters — e.g. optimizer $\in {adam, sgd}$ and activation $\in {relu, tanh, sigmoid}$ . Why grid wins here:

Only $2 \times 3 = 6$ combinations — cost is trivial, no dimensionality problem.
Values are discrete with no "in-between" — there is no continuous distribution to sample from, so random search's distinctness advantage evaporates.
Grid is exhaustive and reproducible — you can report every combination, which some publications require.

Level 4 — Synthesis

L4·Q1 — Design a fair comparison

You must compare grid vs random search fairly on an SVM with hyperparameters $C$ and $γ$ . Design the budgets so the comparison is apples-to-apples, and specify the search domain.

Recall Solution

Fairness rule 1 — same total trainings. Give both methods exactly 16 model trainings (a $4 \times 4$ grid = 16). Fairness rule 2 — same search domain. Both must explore the identical rectangle, otherwise you'd be comparing search strategies and domains at once. Fix the domain once: $C \in [0.01, 1000], γ \in [0.001, 10] (log scale on both axes) .$

Grid: place 4 log-spaced points per axis inside that domain: $C \in {0.01, 0.464, 21.5, 1000}$ (geometric steps), $γ \in {0.001, 0.0215, 0.464, 10}$ . These are the log-evenly-spaced endpoints and interior points of the same interval.
Random: draw 16 samples with $C \sim LogUniform (0.01, 1000)$ and $γ \sim LogUniform (0.001, 10)$ — the log-uniform distribution defined above, whose support is exactly that rectangle. Why this is now fair: identical budget (16), identical domain (same rectangle, same log scaling). Any score difference is attributable to strategy alone. Report best validation score and number of distinct $C$ values explored: 16 for random vs only 4 for grid.

L4·Q2 — Probability of hitting a good region

Suppose the top-performing configurations occupy the best 5% of the hyperparameter space. Using random sampling, how many independent trials $n$ do you need so the probability of landing in that good region at least once is $\geq 0.95$ ?

Recall Solution

Setup: each trial independently lands in the good region with probability $p = 0.05$ , so it misses with probability $1 - p = 0.95$ . Miss all $n$ trials: $(0.95)^{n}$ (independence lets us multiply). Hit at least once: $1 - (0.95)^{n}$ . We want $1 - (0.95)^{n} \geq 0.95 ⟺ (0.95)^{n} \leq 0.05.$ Solve: take logs (which turn the exponent into a multiplier): $n \geq \frac{l n 0.05}{l n 0.95} = \frac{- 2.9957}{- 0.05129} \approx 58.4.$ Round up: $n = 59$ trials. This is why "~60 random trials" is a famous rule of thumb — it gives ~95% chance of hitting the best 5% of the space regardless of dimension.

Level 5 — Mastery

L5·Q1 — Full end-to-end budget with nested CV and early stopping

You tune 4 hyperparameters at values ${4, 3, 3, 2}$ using grid search. You use nested cross-validation: an outer loop of $O = 5$ folds gives an honest performance estimate, and inside each outer fold an inner loop of $I = 3$ folds is used to pick the best configuration. Each training would take up to 100 epochs but Early Stopping cuts it to an average of 40 epochs. If one epoch costs 2 seconds, estimate total wall-clock time (assume serial execution).

Recall Solution

Why nested CV multiplies by both loops: for each of the $O$ outer folds we run a whole grid search scored by $I$ -fold inner CV, then retrain the chosen config. The inner search dominates the count, so we budget $O \times (combinations \times I)$ . Step 1 — combinations: $4 \times 3 \times 3 \times 2 = 72$ . Step 2 — inner trainings per outer fold: each combination trained $I = 3$ times → $72 \times 3 = 216$ . Step 3 — times outer folds: $216 \times O = 216 \times 5 = 1, 080$ trainings. Step 4 — epochs per training with early stopping: $40$ . Total epochs $= 1, 080 \times 40 = 43, 200$ . Step 5 — time: $43, 200 \times 2 s = 86, 400 s = 24$ hours. Contrast with a single (non-nested) 5-fold loop: that would be $72 \times 5 \times 40 \times 2 = 28, 800$ s $= 8$ h. Nested CV costs the extra outer/inner factor ( $1080$ vs $360$ trainings) but buys a leakage-free performance estimate.

L5·Q2 — Random vs grid, decide with numbers

You have 8 continuous hyperparameters and a budget of $256$ trials. (a) How many unique values per hyperparameter would a full grid give? (b) What does random search give? (c) State your recommendation and why.

Recall Solution

(a) Grid: $k = 8$ , so values per axis $= n^{1/ k} = 25 6^{1/8}$ . Since $256 = 2^{8}$ , this is $2^{8/8} = 2$ . Only 2 values per hyperparameter — barely "low vs high." Useless resolution. (b) Random: $256$ distinct values per hyperparameter (in expectation) — every trial a fresh value on every axis. (c) Recommendation: random search. At 8 continuous dimensions a grid collapses to a 2-level cube that cannot resolve any curve, while random search still explores 256 distinct settings per axis. If evaluations are very expensive, escalate to Bayesian Optimization, which learns where to sample next.

L5·Q3 — Synthesis: full tuning pipeline

Sketch (in words) a correct, leakage-free tuning pipeline that uses random search, cross-validation, and a final honest test estimate. Name each safeguard.

Recall Solution

Split data into a train+validation pool and an untouched test set (Training-Validation-Test Split). The test set is locked away and touched exactly once, at the very end.
Random search over the sampling distributions on the train+val pool — e.g. $C \sim LogUniform (0.01, 1000)$ , $γ \sim LogUniform (0.001, 10)$ , dropout $p \sim Uniform (0.1, 0.5)$ .
For each sampled configuration, score it with $k$ -fold cross-validation inside the pool (Cross-Validation): fit on $k - 1$ folds, validate on the held-out fold, average the $k$ scores for a stable estimate.
Select the configuration with the best mean CV score. (Optionally zoom in: narrow the distributions around this best region and sample again.)
Retrain that single best config on the entire train+val pool, so the final model uses all non-test data.
Evaluate once on the locked test set → this is your honest generalization estimate; do not tune anything after seeing it. Safeguards named: the locked test set prevents selection leakage (hyperparameters were never chosen using test data); cross-validation prevents lucky-split bias (one unlucky validation split can't dominate the average); retraining on the full pool uses all available data before the final report. For an even more honest estimate of the whole procedure, wrap steps 2–5 in an outer CV loop (the nested CV of L5·Q1). Optionally combine several strong configs via Ensemble Methods.

Recall One-line self-test

Random search's core advantage over grid ::: it explores $n$ distinct values per hyperparameter vs grid's $n^{1/ k}$ , so it wins when the objective depends on few of many dimensions. Total training runs for grid with $\prod_{i} n_{i}$ combos and $k$ -fold CV ::: $(\prod_{i} n_{i}) \times k$ . Random trials for ~95% chance of hitting the best 5% region ::: about 59 (the "~60 trials" rule).