AutoML Overview

With search spaces potentially containing billions of configurations, how do we find good solutions efficiently? Exhaustive search is impossible; random guessing is inefficient. We need intelligent search strategies that balance exploration (discovering new regions) with exploitation (refining known good regions).

This page covers the major search strategies used in AutoML: random search, grid search, Bayesian optimization, evolutionary methods, and multi-fidelity approaches. You'll understand when to use each and how they work under the hood.

Before sophisticated optimization, practitioners used simple sampling strategies. Understanding their limitations motivates more advanced methods.

Grid Search:

Grid search evaluates all combinations of pre-specified parameter values:

• Learning rate: [0.001, 0.01, 0.1]
• Max depth: [3, 5, 7]
• n_estimators: [50, 100, 200]

Total evaluations: 3 × 3 × 3 = 27 combinations.

Grid Search Limitations:

1. Exponential scaling: Adding parameters or values per parameter explodes the grid
2. Uniform spacing ignores importance: All parameters get equal resolution
3. Wastes budget on unimportant parameters: If only learning rate matters, most evaluations are redundant

Why Random Search Often Beats Grid Search (Bergstra & Bengio, 2012):

The key insight: most hyperparameters don't matter equally. Typically 1-2 parameters dominate performance while others have minimal impact.

With 9 grid points across 2 parameters, grid search tests only 3 unique values per parameter. Random search with 9 samples tests ~9 unique values of the important parameter.

If learning rate dominates and depth doesn't matter:

• Grid search: 3 learning rates tested
• Random search: ~9 learning rates tested

Random search is strictly better when some parameters matter more than others—which is almost always true.

Bayesian Optimization (BO) is the workhorse of modern hyperparameter optimization. Unlike random search, BO learns from previous evaluations to focus on promising regions.

Core Idea:

1. Build a surrogate model that approximates the objective function $f(x)$
2. Use the surrogate to select the next configuration to evaluate via an acquisition function
3. Evaluate the configuration on the true objective
4. Update the surrogate with new observation
5. Repeat until budget exhausted

The surrogate is cheap to query; the true objective (training a model) is expensive. BO trades surrogate queries for expensive evaluations.

Gaussian Process Surrogate:

The classic BO surrogate is a Gaussian Process (GP)—a distribution over functions. Given observations $D = {(x_1, y_1), ..., (x_n, y_n)}$, the GP provides:

• Mean prediction $\mu(x)$: expected performance at configuration $x$
• Uncertainty $\sigma(x)$: how confident we are in the prediction

The GP posterior is: $$p(f(x) | D) = \mathcal{N}(\mu(x), \sigma^2(x))$$

where closed-form formulas exist for $\mu(x)$ and $\sigma^2(x)$ based on the kernel function and observations.

TPE is an alternative to GP-based BO that handles high-dimensional and categorical spaces better. It's the default in Optuna and HyperOpt.

Key Insight:

GPs model $p(y|x)$—the performance given configuration. TPE models the inverse: $p(x|y)$—the configurations that achieve performance $y$.

TPE Approach:

1. Split observations into "good" (top γ quantile) and "bad" (rest)
2. Model $\ell(x) = p(x|y < y^*)$: density of good configurations
3. Model $g(x) = p(x|y \geq y^*)$: density of bad configurations
4. Maximize $\ell(x) / g(x)$: configurations likely good, unlikely bad

This ratio is proportional to Expected Improvement!

Multi-fidelity methods exploit a key observation: bad configurations can be identified early. Instead of fully training every model, we can use cheap early-stopping to filter poor candidates.

Successive Halving:

1. Start with n configurations, each with budget b (e.g., 1 epoch)
2. Evaluate all configurations with budget b
3. Keep top 1/η fraction based on performance
4. Double budget for survivors
5. Repeat until one configuration remains

Hyperband:

Hyperband runs multiple brackets of Successive Halving with different starting configurations and budgets, hedging against the assumption that early performance predicts final performance.

BOHB: Bayesian Optimization + Hyperband

BOHB combines the best of both worlds:

• Use TPE for intelligent configuration sampling (instead of random)
• Use Hyperband for resource allocation and early stopping

Result: Sample-efficient selection + aggressive early stopping = state-of-the-art efficiency.

Key BOHB Insight:

TPE builds density models from completed evaluations at each budget level. Configurations that perform well at low budgets inform higher-budget proposals. The model gradually shifts from exploration to exploitation.

Evolutionary algorithms maintain a population of configurations that evolve over generations through selection, mutation, and crossover. They're particularly effective for NAS and complex structured spaces.

Basic Evolutionary Loop:

1. Initialize: Create random population of configurations
2. Evaluate: Measure fitness (performance) of each individual
3. Select: Choose high-fitness individuals as parents
4. Mutate: Randomly modify selected individuals
5. Crossover: Combine parts of two parents (optional)
6. Replace: Form new generation
7. Repeat: Until convergence or budget exhausted

With many options available, how do you choose? Decision factors include: search space structure, evaluation cost, parallelization needs, and available budget.

What's Next:

With search spaces defined and strategies to explore them, we need to efficiently evaluate candidate configurations. The next page covers evaluation strategies: cross-validation, early stopping, fidelity proxies, and how to make robust decisions from noisy evaluations.