Bayesian Optimization for HPO

The Expensive Hyperparameter Problem

Evaluating a deep neural network hyperparameter combination (e.g. learning rate, batch size, layer count, weight decay) requires training the model for hours.

• Grid Search: Evaluates a rigid grid. Extremely inefficient ($O(D^k)$ exponential explosion).
• Random Search: Samples points randomly. Better than grid search, but completely ignores past trial results.

Bayesian Optimization (Mockus, 1978) optimizes expensive black-box functions by building a probabilistic model of the function and choosing new parameter trials intelligently using past results.

  Past Hyperparameter Trials ──► [ SURROGATE MODEL (Gaussian Process) ] ──► Mean & Uncertainty
                                                                                  │
                                                                                  ▼
  Next Optimal Trial Point ◄── [ ACQUISITION FUNCTION (EI / UCB) ] ◄──────────────┘

The Two Core Components

┌──────────────────────────┬──────────────────────────┐
│ 1. SURROGATE MODEL       │ 2. ACQUISITION FUNCTION  │
├──────────────────────────┼──────────────────────────┤
│ Probabilistic model      │ Scores potential utility │
│ (Gaussian Process) that  │ of candidate points.     │
│ fits past evaluations to │ Balances Exploration     │
│ output Predicted Mean μ  │ (Uncertainty) vs         │
│ and Uncertainty σ.       │ Exploitation (Best Mean).│
└──────────────────────────┴──────────────────────────┘

1. The Surrogate Model (Gaussian Process)

A Gaussian Process (GP) models a probability distribution over functions.

Given evaluated points $(x_1, y_1), \dots, (x_t, y_t)$:

For any un-evaluated hyperparameter point $x^*$, the Gaussian Process outputs:

1. Predicted Performance Mean $\mu(x^*)$: Expected validation score.
2. Predicted Uncertainty Standard Deviation $\sigma(x^*)$: Confidence boundary around the estimate.

  Validation Performance y
    │                     /───\  ◄── High Uncertainty σ(x) (No past trials here!)
    │      *             /     \
    │     / \           /       \
  0 ┴────*───*─────────*─────────*─────────► Hyperparameter Space x
        Evaluated     Evaluated

2. Acquisition Functions (Exploration vs Exploitation)

How do we pick the single next point $x_{t+1}$ to evaluate?

An Acquisition Function $a(x)$ calculates the value of sampling at point $x$:

Upper Confidence Bound (UCB)

$$a_{\text{UCB}}(x) = \mu(x) + \kappa \cdot \sigma(x)$$

• Exploitation Term $\mu(x)$: Prefers points with high predicted performance.
• Exploration Term $\sigma(x)$: Prefers points with high uncertainty (unexplored regions).
• $\kappa$ (kappa): Controls exploration vs exploitation balance.

Expected Improvement (EI)

Measures the expected amount by which evaluating point $x$ will improve over current best score $y^+$:

$$\text{EI}(x) = \mathbb{E} \left[ \max(0, f(x) - y^+) \right]$$

Production Bayesian Libraries

1. Optuna: Industry standard framework using Tree-structured Parzen Estimators (TPE), supporting automatic trial pruning.
2. Ray Tune / BoTorch: Distributed Bayesian optimization for large-scale GPU cluster tuning.

Say this out loud

Bayesian Optimization efficiently tunes expensive hyperparameter functions using past trial evaluations. It uses a Gaussian Process surrogate model to estimate performance mean and uncertainty across hyperparameter space. Acquisition functions like Expected Improvement balance exploring uncertain parameter regions against exploiting high performing regions, finding optimal parameters in far fewer trials.

Followups to expect

1. What is Tree-structured Parzen Estimator (TPE)? A non parametric Bayesian optimization method used in Optuna that models $p(x \mid y)$ instead of $p(y \mid x)$, scaling better to high dimensional categorical hyperparameters than Gaussian Processes.
2. What is Early Trial Pruning in Optuna? Stopping unpromising hyperparameter trials early (at epoch 5 instead of epoch 100) using median stopping rules to save GPU compute.