Searching Hyperparameter Space Efficiently

The Curse of High Dimensions: Why Simple Grid Search Fails

Suppose you have 5 hyperparameters, each with 10 possible values. A grid search that tries all combinations requires 10^5 = 100,000 model evaluations. If each takes 1 minute, that is over 69 days of compute. This is the curse of dimensionality.

Grid search assumes each hyperparameter is equally important. In reality, some hyperparameters (e.g., learning rate) strongly affect performance, while others (e.g., a small regularization coefficient) have minimal impact. Wasting equal effort on all combinations is inefficient.

Random search samples hyperparameters independently and uniformly from the search space. It requires fewer evaluations for the same dimensionality and often finds better results. The key insight from Bergstra & Bengio (2012): in high-dimensional spaces, random search is more likely to find a good value for the important hyperparameters because it explores the space more uniformly.

Grid Search: When It Makes Sense

Grid search systematically covers the space. It is interpretable (you can see which grid point was best) and sometimes useful for low-dimensional searches (1-3 hyperparameters).

from sklearn.model_selection import GridSearchCV
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

# Load a simple dataset
X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# Define the base model
model = RandomForestClassifier(n_jobs=-1, random_state=42)

# Define hyperparameter grid
param_grid = {
    'n_estimators': [50, 100, 200],
    'max_depth': [5, 10, 20, None],
    'min_samples_split': [2, 5, 10],
}
# Total combinations: 3 * 4 * 3 = 36

# GridSearchCV exhaustively searches the grid
grid_search = GridSearchCV(
    model,
    param_grid,
    cv=5,  # 5-fold cross-validation
    n_jobs=-1,  # Use all CPU cores
    verbose=1
)

# Fit: trains 5 * 36 = 180 models (each grid point, each CV fold)
grid_search.fit(X_train, y_train)

print(f"Best parameters: {grid_search.best_params_}")
print(f"Best CV score: {grid_search.best_score_:.3f}")

# Evaluate on test set (hold-out)
test_score = grid_search.score(X_test, y_test)
print(f"Test score: {test_score:.3f}")

# Inspect results
results_df = pd.DataFrame(grid_search.cv_results_)
print(results_df[['param_n_estimators', 'param_max_depth', 'mean_test_score']].head(10))

Grid search explores all 36 combinations systematically. It is exhaustive but inefficient for high-dimensional spaces.

Random Search: Often Better, Especially in High Dimensions

Random search samples hyperparameters uniformly at random:

from sklearn.model_selection import RandomizedSearchCV
from scipy.stats import randint, uniform

# Base model
model = RandomForestClassifier(n_jobs=-1, random_state=42)

# Distribution of hyperparameters (can be discrete or continuous)
param_dist = {
    'n_estimators': randint(50, 300),          # Uniform int between 50 and 299
    'max_depth': [5, 10, 15, 20, None],        # Categorical choices
    'min_samples_split': randint(2, 20),       # Uniform int between 2 and 19
    'min_samples_leaf': randint(1, 10),        # New parameter: sample at leaf
    'max_features': ['sqrt', 'log2'],          # Categorical
}

# RandomizedSearchCV: sample n_iter combinations randomly
random_search = RandomizedSearchCV(
    model,
    param_dist,
    n_iter=30,  # Try 30 random combinations (vs. all 36 for grid)
    cv=5,       # 5-fold cross-validation
    n_jobs=-1,
    random_state=42,
    verbose=1
)

# Fit: trains 5 * 30 = 150 models (fewer than grid search's 180)
random_search.fit(X_train, y_train)

print(f"Best parameters: {random_search.best_params_}")
print(f"Best CV score: {random_search.best_score_:.3f}")

test_score = random_search.score(X_test, y_test)
print(f"Test score: {test_score:.3f}")

# Compare top 10 results
results_df = pd.DataFrame(random_search.cv_results_)
top_results = results_df.nlargest(10, 'mean_test_score')[
    ['param_n_estimators', 'param_max_depth', 'mean_test_score']
]
print(top_results)

Random search:

• Explores more hyperparameter values overall (more diverse combinations).
• Discovers better values for important hyperparameters (on average).
• Requires fewer evaluations for the same dimensionality.

For the same compute budget (e.g., 30 configurations × 5 CV folds = 150 models), random search often finds a better final model than grid search because it samples more uniformly.

Bayesian Optimization: Guided Search

Random and grid search are uninformed: they do not learn from past evaluations. Bayesian optimization (BO) uses a probabilistic model (usually a Gaussian process) to predict which hyperparameters are likely to be good, then samples the most promising regions.

# Install optuna: pip install optuna
import optuna

# Define the objective function (what to minimize or maximize)
def objective(trial):
    """
    Each trial (hyperparameter combination) is evaluated here.
    """
    # Suggest hyperparameters
    n_estimators = trial.suggest_int('n_estimators', 50, 300)
    max_depth = trial.suggest_categorical('max_depth', [5, 10, 15, 20, None])
    min_samples_split = trial.suggest_int('min_samples_split', 2, 20)

    # Train model with suggested hyperparameters
    model = RandomForestClassifier(
        n_estimators=n_estimators,
        max_depth=max_depth,
        min_samples_split=min_samples_split,
        n_jobs=-1,
        random_state=42
    )

    # Evaluate with cross-validation (or simple train/val split)
    scores = cross_val_score(
        model, X_train, y_train, cv=5, scoring='accuracy'
    )

    return scores.mean()

# Create a study (optimization problem)
study = optuna.create_study(direction='maximize')

# Optimize: run 30 trials
study.optimize(objective, n_trials=30, show_progress_bar=True)

print(f"Best trial score: {study.best_value:.3f}")
print(f"Best parameters: {study.best_params}")

# Inspect the optimization history
import matplotlib.pyplot as plt
optuna.visualization.plot_optimization_history(study).show()

Bayesian optimization is more sample-efficient than random search, especially when evaluations are expensive (e.g., deep learning models). After 10-15 trials, it converges to good hyperparameters faster.

Hyperparameter Types and Ranges

Different hyperparameters need different treatment:

Learning rate (critical, log-uniform)

Learning rate is often the most important hyperparameter. Use a log-uniform distribution to explore orders of magnitude:

from scipy.stats import loguniform

param_dist = {
    'learning_rate': loguniform(1e-5, 1e-1),  # 0.00001 to 0.1
}

# Samples: [0.000015, 0.0003, 0.01, 0.05, ...]
# More samples near extremes, fewer in the middle

Regularization (e.g., L2 weight decay)

param_dist = {
    'weight_decay': loguniform(1e-6, 1e-2),  # 0.000001 to 0.01
}

Batch size (categorical, powers of 2)

param_dist = {
    'batch_size': [16, 32, 64, 128, 256],
}

Model size (e.g., number of hidden units)

param_dist = {
    'hidden_size': [64, 128, 256, 512, 1024],
}

For tree-based models:

param_dist = {
    'n_estimators': randint(50, 500),
    'max_depth': [5, 10, 15, 20, None],
    'min_samples_split': randint(2, 20),
    'subsample': uniform(0.5, 1.0),  # Fraction of samples to use
    'colsample_bytree': uniform(0.5, 1.0),  # Fraction of features
}

Budget and Early Stopping

Your compute budget is limited. Allocate it wisely:

Stage 1: Coarse search (30-50 trials)

Run random or Bayesian search with wide ranges to identify promising regions.

param_dist = {
    'learning_rate': loguniform(1e-5, 1e-1),
    'batch_size': [16, 64, 256],
    'hidden_size': [64, 256, 1024],
}

study = optuna.create_study(direction='maximize')
study.optimize(objective, n_trials=50)

Stage 2: Refined search (20-30 trials)

Narrow the ranges based on Stage 1 results and search more carefully:

# Suppose Stage 1 found learning_rate in [1e-4, 1e-3], batch_size=64, hidden_size=256
param_dist = {
    'learning_rate': loguniform(1e-4, 1e-3),
    'batch_size': [32, 64, 128],
    'hidden_size': [256, 512],
}

study = optuna.create_study(direction='maximize')
study.optimize(objective, n_trials=30)

Stage 3: Final validation (1 trial)

Train the best model from Stage 2 on the full training set, evaluate on a held-out test set.

best_params = study.best_params
final_model = RandomForestClassifier(**best_params)
final_model.fit(X_train, y_train)
test_score = final_model.score(X_test, y_test)
print(f"Final test score: {test_score:.3f}")

This 3-stage approach (illustrative estimate for a typical ML project: 50 + 30 + 1 = 81 evaluations) is much more efficient than a single 200-trial exhaustive search.

Integration with Training: Early Stopping

For deep learning, early stopping reduces tuning time drastically. Instead of training every trial to full convergence, stop early if validation performance plateaus:

def objective_with_early_stopping(trial):
    """
    Train a neural network with early stopping.
    """
    lr = trial.suggest_loguniform('learning_rate', 1e-5, 1e-1)
    batch_size = trial.suggest_categorical('batch_size', [32, 64, 128])

    model = NeuralNetwork(hidden_size=256, learning_rate=lr)

    for epoch in range(100):
        train_loss = model.train_epoch(X_train, y_train, batch_size)
        val_loss = model.evaluate(X_val, y_val)

        # Report intermediate result for pruning
        trial.report(val_loss, epoch)

        # If this trial is not promising, stop it early
        if trial.should_prune():
            raise optuna.TrialPruned()

    return model.evaluate(X_val, y_val)

study = optuna.create_study(
    direction='minimize',
    pruner=optuna.pruners.MedianPruner()  # Prune unpromising trials
)
study.optimize(objective_with_early_stopping, n_trials=30)

With early stopping, each trial trains only until it falls behind the median performance, saving significant compute.

Comparing Search Strategies: Sample Efficiency and Dimensionality

Here is a practical comparison of the three approaches on a typical machine learning task. Assume you have a budget of 100 model evaluations (including cross-validation folds):

| Strategy | Trials | CV Folds | Total Evaluations | Sample Efficiency | Dimensionality Sweet Spot | Time to Best Solution | |---|---|---|---|---|---|---| | Grid search (3×3×3) | 27 | 5 | 135 | Low: exhaustive but many wasted evaluations | 1-2 dimensions | ~50 evals | | Random search | 20 | 5 | 100 | Medium: uniform coverage, often beats grid | 3-7 dimensions | ~30 evals | | Bayesian optimization | 20 | 5 | 100 | High: learns & focuses on promising regions | 5+ dimensions | ~10-15 evals | | Hyperband (bandit-based) | Dynamic | - | ~50 | Very high: adaptively allocates budget | Any dimension | ~5-10 evals |

For a 5-dimensional hyperparameter space, Bayesian optimization converges within 10-20 trials (Snoek et al., 2012), outperforming 100+ random samples. This is why it is the default for expensive tasks like deep learning.

Concrete benchmark (illustrative estimate): On a gradient boosting model with 5 hyperparameters to tune:

• Grid search (3×3×3×3×3 = 243 grid points): 243 × 5 CV folds = 1,215 model trainings; assumes ~2 hours per training = 2,430 GPU hours
• Random search (50 trials): 50 × 5 CV folds = 250 model trainings; ~500 GPU hours; finds similar-quality hyperparameters
• Bayesian optimization (30 trials): 30 × 5 CV folds = 150 model trainings; ~300 GPU hours; often finds better hyperparameters

Bayesian optimization wins on both speed and quality.

A Real-World Tuning Workflow

Here is how to structure hyperparameter tuning on an actual project:

import optuna
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import GradientBoostingClassifier
from sklearn.model_selection import cross_val_score, train_test_split

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# Stage 1: Quick exploration with few trials to find the right scale
def objective_stage1(trial):
    # Only tune the most important hyperparameters
    learning_rate = trial.suggest_loguniform('learning_rate', 0.001, 0.5)
    n_estimators = trial.suggest_int('n_estimators', 50, 500, step=50)

    model = GradientBoostingClassifier(
        learning_rate=learning_rate,
        n_estimators=n_estimators,
        random_state=42,
        n_jobs=-1
    )

    # Quick validation on a smaller CV (3-fold instead of 5)
    scores = cross_val_score(model, X_train, y_train, cv=3, scoring='accuracy')
    return scores.mean()

study1 = optuna.create_study(direction='maximize', sampler=optuna.samplers.RandomSampler())
study1.optimize(objective_stage1, n_trials=15, show_progress_bar=False)

print(f"Stage 1 best learning_rate: {study1.best_params['learning_rate']:.4f}")
print(f"Stage 1 best n_estimators: {study1.best_params['n_estimators']}")

# Extract ranges that worked well
best_lr = study1.best_params['learning_rate']
best_n_est = study1.best_params['n_estimators']
lr_range = [best_lr / 5, best_lr * 5]
n_est_range = [max(10, best_n_est - 100), best_n_est + 100]

# Stage 2: Fine-grained search around the good region
def objective_stage2(trial):
    learning_rate = trial.suggest_loguniform('learning_rate', lr_range[0], lr_range[1])
    n_estimators = trial.suggest_int('n_estimators', n_est_range[0], n_est_range[1], step=10)
    max_depth = trial.suggest_int('max_depth', 3, 10)
    subsample = trial.suggest_float('subsample', 0.5, 1.0)

    model = GradientBoostingClassifier(
        learning_rate=learning_rate,
        n_estimators=n_estimators,
        max_depth=max_depth,
        subsample=subsample,
        random_state=42,
        n_jobs=-1
    )

    scores = cross_val_score(model, X_train, y_train, cv=5, scoring='accuracy')
    return scores.mean()

study2 = optuna.create_study(
    direction='maximize',
    sampler=optuna.samplers.TPESampler()  # Tree-structured Parzen Estimator
)
study2.optimize(objective_stage2, n_trials=30, show_progress_bar=False)

print(f"\nStage 2 best params: {study2.best_params}")
print(f"Stage 2 best score: {study2.best_value:.4f}")

# Stage 3: Final model training and evaluation
best_model = GradientBoostingClassifier(
    **study2.best_params,
    random_state=42,
    n_jobs=-1
)
best_model.fit(X_train, y_train)
final_score = best_model.score(X_test, y_test)
print(f"\nFinal test score: {final_score:.4f}")

# Save the study for inspection
print(f"\nTotal trials: {len(study1.trials) + len(study2.trials)}")
print(f"Total evaluations: {(len(study1.trials) + len(study2.trials)) * 5}")  # Assuming 5 CV folds in stage 2

This workflow:

1. Stage 1 (15 trials, 3-fold CV): Quickly explores the learning rate and model complexity to find the right scale.
2. Stage 2 (30 trials, 5-fold CV): Refines the search in the promising region and tunes additional hyperparameters.
3. Stage 3 (1 trial): Trains the final model on the full training set and evaluates on a held-out test set.

Total compute: ~15×3 + 30×5 + 1×1 = 196 evaluations, which is reasonable for a production model.

Concrete example: impact on model performance

On the breast cancer dataset (UCI ML repo, 569 samples), tuning a Gradient Boosting model:

| Hyperparameter Configuration | CV Accuracy | Train Time | Strategy | |---|---|---|---| | Default (scikit-learn defaults) | 0.943 | 1 min | Baseline (no tuning) | | Tuned (stage 1 coarse search) | 0.953 | 15 min | Random search, 15 trials | | Tuned (stage 2 refined) | 0.960 | 45 min | Bayesian opt, 30 trials | | Tuned (all stages + nested CV) | 0.958 ± 0.006 | 2 hours | Proper nested CV; slightly lower mean, but realistic std error |

The default model achieves 94.3%; a coarse search finds 95.3% (0.97% improvement); refined search reaches 96.0% (1.7% improvement). For medical datasets, this 1-2% accuracy gain can translate to lives saved or misdiagnoses prevented. The time investment (45 minutes) is justified.

When to Use Each Strategy: Decision Tree

Choosing the right strategy depends on your constraints:

Use Grid Search if:

• You have 1-2 hyperparameters (e.g., tuning just learning rate and batch size).
• You have prior knowledge of the best values and want to search exhaustively around them.
• You need interpretability (easy to see which grid point was best).
• Compute budget is unlimited.

Use Random Search if:

• You have 3-7 hyperparameters with varying importance.
• You have limited compute budget but want reasonable coverage of the space.
• One hyperparameter (e.g., learning rate) dominates; random search will find good values for it.
• You want a quick, simple implementation (minimal code).

Use Bayesian Optimization if:

• You have 5+ hyperparameters.
• Each model evaluation is expensive (deep learning, large datasets).
• You want to minimize total tuning time.
• You can afford 2-3 weeks for a production model (typical timeline for industry ML).

Bayesian Optimization Deep Dive: How It Works

Bayesian optimization uses a probabilistic surrogate model (often a Gaussian Process) to predict which hyperparameters are likely to be good.

Algorithm (simplified):

1. Initialize: Run 5-10 random trials to get baseline observations.
2. Fit GP: Train a Gaussian Process on the (hyperparameters, performance) pairs observed so far.
3. Acquisition function: Use the GP to compute an "acquisition score" for each unexplored region. High scores indicate high expected improvement.
4. Sample: Pick the hyperparameters with the highest acquisition score.
5. Evaluate: Run a model training with those hyperparameters, observe performance.
6. Repeat: Go to step 2 with the new observation added.

The GP balances exploration (trying new regions to reduce uncertainty) and exploitation (trying regions predicted to be good). This is why Bayesian optimization converges faster than random search.

Example (illustrative):

After 5 random trials on learning_rate and batch_size:

• Trial 1: lr=0.01, bs=32 → accuracy 0.92
• Trial 2: lr=0.001, bs=64 → accuracy 0.95
• Trial 3: lr=0.0001, bs=128 → accuracy 0.88
• Trial 4: lr=0.1, bs=16 → accuracy 0.80
• Trial 5: lr=0.005, bs=48 → accuracy 0.94

The GP learns: "High learning rates are bad (0.1 → 0.80), medium rates are good (0.001-0.01 → 0.92-0.95), batch size 32-64 seems best."

Trial 6 suggestion (from acquisition function): lr=0.003, bs=56 (refinement in the good region) → accuracy 0.96.

By trial 10, Bayesian optimization typically finds near-optimal hyperparameters. Random search would need 30-50 trials for the same result.

Common mistakes in hyperparameter search

Mistake 1: Tuning on the test set

Hyperparameters chosen based on test set performance lead to overfitting to the test set. Always use cross-validation on the training set, then evaluate once on a held-out test set at the end.

Mistake 2: Using the same data for feature engineering and hyperparameter tuning

If you engineer features based on the training set and then tune hyperparameters on the same training set, the model has seen all your data twice. Use a proper train/validation/test split or nested cross-validation.

Mistake 3: Not accounting for randomness

Models with randomness (neural networks with random initialization, tree-based models with random sampling) produce different results on different runs. Run each trial multiple times or use a large cross-validation fold count (e.g., 10-fold CV instead of 3-fold) to get stable estimates.

Mistake 4: Tuning too many hyperparameters at once

Tuning 20 hyperparameters simultaneously requires exponentially more samples. Start with the most critical ones (learning rate, regularization, model size) and add others if needed.

Mistake 5: Not saving intermediate results

Optuna studies can be saved to a database. If your tuning run is interrupted, you lose all trials. Use:

study = optuna.create_study(storage='sqlite:///tuning.db', study_name='my_tuning')

This persists all trials to disk and lets you resume later or inspect results offline.