Grid search and random search

The Hyperparameter Tuning Problem

The Goal: Find hyperparameter configuration $\mathbf{h}^* = \{h_1, h_2, \ldots, h_k\}$ that maximizes validation performance:

\mathbf{h}^* = \arg\max_{\mathbf{h} \in \mathcal{H}} \text{score}_{\text{val}}(\mathbf{h})

where $\mathcal{H}$ is the hyperparameter space.

Why This is Hard:

No gradient information (hyperparameters aren't differentiable w.r.t. validation loss)
Each evaluation requires full model training (expensive)
Space is high-dimensional and combinatorial
Interactions between hyperparameters are non-linear

Grid Search: Exhaustive Exploration

How Grid Search Works

Step-by-step:

Define a grid for each hyperparameter:
- Learning rate: $\alpha \in \{0.001, 0.01, 0.1\}$
- Regularization: $\lambda \in \{0.01, 0.1, 1.0, 10.0\}$
Generate all combinations: $(0.001, 0.01), (0.001, 0.1), \ldots, (0.1, 10.0)$
For each combination:
- Train model with those hyperparameters on training set
- Evaluate on validation set
- Record validation score
Select configuration with best validation score
Retrain on full training+validation data with best config, test on hold-out test set

Computational Cost: If we have 3 values for $\alpha$ , 4 for $\lambda$ , and 5 for max depth:

\text{Total models} = 3 \times 4 \times 5 = 60 \text{ models}

With 5-fold CV, that's $60 \times 5 = 300$ training runs.

Worked example Grid Search Example

Task: Tune SVM with RBF kernel. Hyperparameters: $C$ (regularization), $\gamma$ (kernel coefficient). Grid:

C_values = [0.1, 1, 10, 100]
gamma_values = [0.001, 0.01, 0.1, 1]

Process:

Combination1: $C=0.1, \gamma=0.001$ → Train Val score = 0.82
Combination 2: $C=0.1, \gamma=0.01$ → Train → Val score = 0.85
...
Combination 16: $C=100, \gamma=1$ → Train → Val score = 0.91

Why this step? We're mapping the performance surface. High $C$ with moderate $\gamma$ might overfit. Low $C$ with high $\gamma$ might underfit. We need to try combinations because they interact. Result: Best config is $C=10, \gamma=0.1$ with val score 0.93.

Advantages of Grid Search

Guarantees finding the best configuration in the grid (exhaustive)
Simple to implement and understand
Reproducible (deterministic)
Good when hyperparameters have clear discrete choices (e.g., activation functions: ReLU, tanh, sigmoid)

Limitations of Grid Search

Additional Limitation: Grid search wastes resolution. If you allocate 5 values to learning rate and 5 to batch size, you get 25 combinations. But if learning rate is much more important, you'd want15 values for learning rate and 3 for batch size (still 45 combinations, but better coverage of the important dimension).

Random Search: Efficient Sampling

How Random Search Works

Step-by-step:

Define distributions for each hyperparameter:
- Learning rate: $\alpha \sim \text{LogUniform}(10^{-4}, 10^{-1})$
- Regularization: $\lambda \sim \text{LogUniform}(10^{-3}, 10^{1})$
- Dropout: $p \sim \text{Uniform}(0.1, 0.5)$
Sample $n$ random configurations (e.g., 60 samples)
For each sample:
- Train model with those hyperparameters
- Evaluate on validation set
Select best configuration
(Optional) Zoom in: narrow distributions around best region and sample more

Why Random? Derivation from first principles:

Consider a 2D hyperparameter space where hyperparameter $h_1$ is important and $h_2$ is unimportant.

Grid search with budget of 9 trials:

3 values for $h_1$ : $\{a, b, c\}$
3 values for $h_2$ : $\{x, y, z\}$
Tries: $(a,x), (a,y), (a,z), (b,x), (b,y), (b,z), (c,x), (c,y), (c,z)$
Unique values tried for important $h_1$ : Only 3 values $(a, b, c)$

Random search with budget of 9 trials:

Sample 9 random $(h_1, h_2)$ pairs
Each sample independently choses $h_1$ from continuous distribution
Unique values tried for important $h_1$ : 9 different values (all distinct)

The key insight: Random search gets more coverage in each dimension. For $n$ trials in $k$ dimensions:

Grid with $n^{1/k}$ values per dimension: tries only $n^{1/k}$ unique values per hyperparameter
Random: tries $n$ unique values per hyperparameter (in expectation)

Mathematical justification: If the objective function is:

f(h_1, h_2) = g(h_1) + \epsilon(h_2)

where $g$ is important and $\epsilon$ is noise, then sampling $n$ random points gives $n$ evaluations of different $h_1$ values, whereas a $\sqrt{n} \times \sqrt{n}$ grid only evaluates $\sqrt{n}$ different $h_1$ values.

Worked example Random Search Example

Task: Same SVM tuning problem. Budget: 60 trials (same as grid search $4 \times 4\times 4$ grid). Distributions:

C ~ LogUniform(0.01, 1000)      # Wide range
gamma ~ LogUniform(0.001, 10)   # Wide range

Process:

Trial 1: Sample $C=0.73, \gamma=0.042$ → Train → Score = 0.87
Trial 2: Sample $C=15.2, \gamma=0.0089$ → Train → Score = 0.91
Trial 3: Sample $C=2.1, \gamma=0.15$ → Train → Score = 0.93
...
Trial 60: Sample $C=0.051, \gamma=1.2$ → Train → Score = 0.81

Why this step? Each sample explores a unique point. We're not constrained to a grid, so we can discover that $C=2.1$ works better than $C=1$ or $C=10$ (values we'd try in grid).

Result: Best config is $C=2.1, \gamma=0.15$ with score 0.93. We explored 60 unique $(C, \gamma)$ pairs vs. only 16 unique combinations in grid (if we used4×4 grid).

Advantages of Random Search

More efficient in high dimensions: Tries more unique values per hyperparameter
Handles continuous spaces naturally: No need to discretize
Easy to parallelize: All trials are independent
Can stop anytime: If you have budget for 100 trials but results plateau at 60, you can stop
Better for important/unimportant hyperparameter scenarios: Automatically gets more coverage on dimensions that matter

When to Use Which?

Use Grid Search when:

Few hyperparameters (≤3)
Discrete choices (e.g., optimizer type: 'adam' vs 'sgd')
Small, well-understood search space
You need to report every combination tried (reproducibility requirements)

Use Random Search when:

Many hyperparameters (≥4)
Continuous hyperparameters
Large or unknown search space
You suspect some hyperparameters are more important than others
Computational budget is limited

Practical Implementation Details

Cross-Validation Integration

Both methods should use cross-validation to estimate performance:

For configuration $\mathbf{h}$ :

\text{score}(\mathbf{h}) = \frac{1}{k} \sum_{i=1}^k \text{metric}(\mathbf{h}, \text{fold}_i)

Why? A single train/val split can be lucky or unlucky. CV averages out this variance.

Worked example Grid Search with Cross-Validation

Setup: 3 values for $\alpha$ , 4 values for $\lambda$ , 5-fold CV. Process for one configuration ( $\alpha=0.01, \lambda=0.1$ ):

Fold 1: Train on folds 2,3,4,5 → Validate on fold 1→ Score = 0.85
Fold 2: Train on folds 1,3,4,5 → Validate on fold 2 → Score = 0.87
Fold 3: Train on folds 1,2,4,5 → Validate on fold 3 → Score = 0.83
Fold 4: Train on folds 1,2,3,5 → Validate on fold 4 → Score = 0.86
Fold 5: Train on folds 1,2,3,4 → Validate on fold 5 → Score = 0.84

Average score: $(0.85 + 0.87 + 0.83 + 0.86 + 0.84)/5 = 0.85$

Why this step? This one configuration required 5 training runs. We repeat this for all 12 configurations, giving $12 \times 5 = 60$ total training runs. The averaged score is more reliable than a single split.

Choosing Distributions for Random Search

Log-uniform for hyperparameters spanning orders of magnitude:

h \sim \text{LogUniform}(a, b) \implies \log h \sim \text{Uniform}(\log a, \log b)

Example: Learning rate from $10^{-5}$ to $10^{-1}$ .

Why log-uniform? If we use uniform, we'd sample more values near $10^{-1}$ (the upper end), but the space between $10^{-5}$ and $10^{-4}$ is just as important as between $10^{-2}$ and $10^{-1}$ . Log-uniform gives equal probability to each order of magnitude.

Uniform for bounded hyperparameters: Example: Dropout probability from 0.0 to 0.5.

Integer uniform for discrete counts: Example: Number of hidden units from 50 to 500.

Nested Cross-Validation for Unbiased Evaluation

Common mistake Test Set Leakage Through Hyperparameter Tuning

Wrong approach:

Split data into train and test
Use grid/random search with CV on train set, find best hyperparameters
Report the best CV score as your model's performance Why it feels right: You never trained on the test set directly.

The problem: You implicitly "learned" from the validation sets used in CV. By trying many configurations, you overfit to the validation folds. The best CV score is overly optimistic.

Why it fails: The validation sets were used to make decisions (choosing hyperparameters). They're no longer independent of the model.

The fix: Use nested cross-validation:

Outer loop: K-fold CV for performance estimation
Inner loop: Grid/random search with cross-validation for hyperparameter selection

For each outer fold, hyperparameters are selected independently using only that fold's training data.

Nested CV formula for unbiased performance estimate:

\text{score}_{\text{unbiased}} = \frac{1}{K} \sum_{i=1}^K \text{score}_{\text{test}}(\mathbf{h}_i^*)

where $\mathbf{h}_i^*$ is the best configuration found using only outer fold $i$ 's training data.

Comparing Grid and Random Search

Bergstra & Bengio (2012) Theoretical Result

Theorem (informal): For a hyperparameter space where only $k$ out of $d$ dimensions are important, random search with $n$ trials samples $\mathcal{O}(n)$ unique values per important dimension, while grid search with $n$ trials samples $\mathcal{O}(n^{1/d})$ unique values per dimension.

Proof sketch:

Grid search with $n$ trials: allocate $n^{1/d}$ values per dimension → $\mathcal{O}(n^{1/d})$ coverage
Random search: each trial independently samples from each dimension → each dimension gets $\mathcal{O}(n)$ unique samples

Implication: Random search is exponentially more efficient when $d$ is large and $k \ll d$ .

Empirical Comparison

Study: Bergstra & Bengio tested on various ML tasks (neural nets, deep belief networks).

Result: Random search found configurations within 3% of optimal using 2-3× fewer evaluations than grid search.

Why? Most tasks had 1-3 important hyperparameters out of 5-10 total. Random search's better per-dimension coverage dominated.

Connections

Cross-Validation - Used to evaluate each hyperparameter configuration reliably
Overfitting and Underfitting - Hyperparameters control model complexity, affecting bias-variance tradeoff
Regularization - $\lambda$ is a common hyperparameter searched
Learning Rate Scheduling - Learning rate $\alpha$ is often the most important hyperparameter to tune
Bayesian Optimization - More advanced search that builds a surrogate model of the objective
Ensemble Methods - Can reduce need for perfect hyperparameter tuning by averaging models
Training-Validation-Test Split - Framework within which hyperparameter search operates
Early Stopping - Another hyperparameter (patience) that can be tuned

Recall Explain to a 12-Year-Old

Imagine you're trying to find the best settings for a video game character (speed, strength, defense). You have a training mode where you can test different combinations and see your score.

Grid search is like trying every single combination: speed=1 with strength=1, then speed=1 with strength=2, etc. If you have 10 options for each of 3 settings, that's 10×10×10 = 1,000 tests! It takes forever but you'll definitely find the best combination that you tried.

Random search is like closing your eyes and randomly picking settings1,000 times. Sounds silly, but here's the trick: imagine speed matters a lot but defense doesn't matter much. With grid search, you might only try 10 different speeds (because you spread your tests across all settings). But with random search, all 1,000 tests use different random speeds! So you explore the important setting (speed) much better.

The lesson: When some things matter more than others, random trying can actually be smarter than systematic trying. It's like how exploring a new city by wandering randomly sometimes helps you find cool places that weren't on the map!

Flashcards

#flashcards/ai-ml

What are hyperparameters and how do they differ from model parameters? :: Hyperparameters are settings configured before training (learning rate, regularization strength, tree depth) that control the learning process. Model parameters are learned from data during training (weights, biases). Hyperparameters must be chosen, not learned.

What is grid search?

Grid search exhaustively evaluates every combination from a predefined grid of hyperparameter values. For k hyperparameters with n_i values each, it trains ∏n_i models and selects the configuration with the best validation score.

What is random search?

Random search samples hyperparameter combinations randomly from specified distributions (uniform, log-uniform) for n trials. It trains n models with random configurations and selects the best performer.

Why is random search often more efficient than grid search in high dimensions?

For n trials in dimensions, grid search tries only n^(1/d) unique values per hyperparameter, while random search tries approximately n unique values per hyperparameter. When d is large, n^(1/d) becomes very small (e.g., 256^(1/4)=4 vs 256).

When should you use log-uniform distribution for random search?

Use log-uniform for hyperparameters that span multiple orders of magnitude (learning rate: 10^-5 to 10^-1). It ensures equal sampling probability per order of magnitude, preventing bias toward larger values that would occur with uniform sampling.

What is nested cross-validation and why is it necessary?

Nested CV has an outer loop (K-fold CV for performance estimation) and inner loop (hyperparameter search with CV). It prevents test set leakage that occurs when reporting the best CV score from hyperparameter tuning, which is overly optimistic because validation sets influenced the model selection decision.

What is the computational cost of grid search with3 hyperparameters having 4, 5, and 6 values respectively with 5-fold CV?

Total models = 4 × 5 × 6 = 120configurations. With 5-fold CV: 120 × 5 = 600 training runs.

Why does grid search waste resolution in hyperparameter space?

Grid search allocates equal numbers of values to all hyperparameters regardless of importance. If learning rate is critical but batch size isn't, allocating 5 values to each wastes resolution on batch size. Better to allocate 15 values to learning rate and 3 to batch size.

What is the main advantage of grid search over random search?

Grid search guarantees finding the best configuration within the defined grid (exhaustive). It's deterministic and reproducible. Good for small discrete spaces (≤3 hyperparameters) with clear choices.

How many unique values does random search sample for an important hyperparameter with 100 trials?

Approximately 100 unique values (each trial independently samples). Compare to grid search with 100 trials in 4D space: only 100^(1/4) ≈ 3.16 values per dimension.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Jab ap ek machine learning model train karte ho, to bahut sare settings hote hain jo apko pehle se decide karni padti hain—jaise learning rate, regularization strength, ya tree depth. Yeh hyperparameters kehlate hain, aur inhe data se nahi seekha ja sakta, apko khud choose karna padta hai. Problem yeh hai ki agar aapne galat hyperparameters choose kar liye, to aapka model ya to underfit karega (kuch bhi nahi seekhega) ya overfit karega (training data ko ratt lega par nayi data pe fail karega).

To sahi hyperparameters dhoondhne ke liye do popular tarike hain: Grid Search aur Random Search. Grid search bilkul systematic hai—ap harek combination ko try karte ho. Suppose aapke pas 3 values hain learning rate ke liye aur 4 values hain regularization ke liye, to grid search 3×4=12 models train karega aur sabse best wala chun lega. Yeh guaranteed hai ki aapko best combination mil jayega jo aapne define kiya tha, lekin problem yeh hai ki jaise hi aap zyada hyperparameters add karte ho, combinations exponentially badh jate hain. Agar 5 hyperparameters hain aur har ek ke 5 values hain, to 5^5 = 3,125 models train karne padenge. Yeh bahut time-consuming aur expensive ho jata hai.

Random search ek smarter approach hai jab bahut sare hyperparameters ho. Isme ap systematic grid ki jagah randomly combinations sample karte ho. Matlabagar aapko 100 trials ka budget hai, to ap 100 random configurations try karoge. Surprisingly, yeh zyada efficient hota hai kyunki agar kuch hyperparameters important hain aur kuch nahi, to random search automatically important walon kozyada explore kar leta hai. Grid search meagar aapne 100 trials ko 4dimensions me divide kiya (10×10×10×10 ka kuch grid), to har dimension me sirf 10 unique values try hoti hain. Lekin random search me har trial unique hota hai, to apko har important hyperparameter ke liye 100 different values mil jate hain. Research studies (Bergstra & Bengio 2012) ne dikhaya hai ki random search aksar grid search se 2-3 guna kam trials me best configuration dhoodh leta hai jab dimensions zyada ho.

Practical advice: Agar aapke pas 3 ya usse kam hyperparameters hain aur discrete choices hain (jaise optimizer type: Adam ya SGD), to grid search thek hai. Lekin agar 4 ya zyada hyperparameters hain, continuous values hain (jaise learning rate 0.001 se 0.1 tak), ya apko nahi pata ki kaun sa hyperparameter kitna important hai, to random search use karo. Aur hamesha cross-validation ke sath search karo taki ek lucky/unlucky split ki wajah se aapka result biased na ho. Yeh tuning process model development ka critical part hai kyunki best hyperparameters ka matlab hai best performance aur production me success.

The Hyperparameter Tuning Problem

Grid Search: Exhaustive Exploration

How Grid Search Works

Advantages of Grid Search

Limitations of Grid Search

Random Search: Efficient Sampling

How Random Search Works

Advantages of Random Search

When to Use Which?

Practical Implementation Details

Cross-Validation Integration

Choosing Distributions for Random Search

Nested Cross-Validation for Unbiased Evaluation

Comparing Grid and Random Search

Bergstra & Bengio (2012) Theoretical Result

Empirical Comparison

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Model Evaluation & Selection

Connections