Hyperparameter Optimization Bayesian Optimization Hyperband

# Hyperparameter Optimization: Bayesian Optimization & Hyperband

## Introduction & Motivation

Hyperparameter optimization: automated search for best hyperparameters. Grid search: exhaustive; exponential in dimensionality. Random search: efficient baseline. Bayesian optimization: probabilistic model guides search. Hyperband: multi-fidelity, early stopping. Applications: AutoML, neural architecture search.

Motivation: Manual tuning tedious, suboptimal. Automated search scales; uses past evaluations.

Applications: Model selection, AutoML, hyperparameter tuning, neural architecture search.

---

## Core Concepts & Theory

### Surrogate Model

Gaussian process (GP) models objective; cheap to evaluate.

### Acquisition Function

Balance exploration vs exploitation; select next point to evaluate.

### Expected Improvement (EI)

Probability of improvement > current best.

---

## Mathematical Formulation

Gaussian Process prior:
$$f(x) \sim GP(\mu(x), k(x, x'))$$

Expected Improvement (EI):
$$EI(x) = \mathbb{E}[\max(f(x) - f(x^*), 0)]$$
$$= \sigma(x) \left[ Z \Phi(Z) + \phi(Z) ight]$$

where Z = (μ - f*) / σ.

Hyperband:
$$n = 5 \cdot 81, r = 1/81 \quad ext{(initial resource)}$$

---

## Advanced Theory & Extensions

### Multi-Objective Optimization

Pareto frontier; accuracy-latency tradeoffs.

### Population-Based Training (PBT)

Evolutionary approach; trains multiple configs in parallel.

### Successive Halving

Eliminate poor configs early; allocate resources adaptively.

---

## Computational Considerations

GP inference: O(n³) where n = evaluations.

Acquisition function: O(n) evaluations.

Hyperband: O(log(R) × R) evaluations total.

---

## Practical Implementation Strategies

### Search Space Definition

Log scale for learning rates, exponential for batch size.

### Warm-Start Prior

Initialize GP with random search results; bootstrap.

### Parallel Evaluation

Multiple configs in parallel; communication overhead.

---

## Benchmark Datasets & Evaluation

MNIST: Standard benchmark; optimal LR ~0.01.

ImageNet: Tuning batch size, learning rate, weight decay.

NAS-Bench: Standardized benchmark for NAS.

Metrics: Wall-clock time, sample efficiency.

---

## Key Challenges & Limitations

### High-Dimensional Spaces

Curse of dimensionality; BO struggles with >10 dims.

### Noisy Evaluations

Stochastic training; variance in results.

### Resource Constraints

Limited compute; must trade exploration-exploitation.

---

## Hyperparameter Tuning

GP kernel: RBF (Radial Basis Function) common.

Acquisition: Expected Improvement (EI) standard.

Budget: 50-500 evaluations for moderate spaces.

---

## Real-World Applications & Case Studies

AutoML (AutoKeras): Bayesian optimization for architecture search.

Hyperparameter Tuning (Optuna): Modern HPO framework.

Neural Architecture Search: Hyperband for NAS.

---

## Integration with Other Methods

HPO + Early Stopping → efficient multi-fidelity optimization.

HPO + Ensemble → optimize ensemble diversity.

---

## Summary & Key Takeaways

Hyperparameter optimization via Bayesian methods and successive halving automates model selection, efficiently exploring high-dimensional spaces with limited budget.

Principles:
1. Surrogate model (GP): cheap to evaluate past data.
2. Acquisition function: balance exploration-exploitation.
3. Expected Improvement: probability of beating current best.
4. Hyperband: multi-fidelity early stopping for efficiency.
5. Parallel evaluation: scale across resources.

---

---

## Appendix: Practical Labs

### Lab 1: Random Search vs Grid Search

import numpy as np
import itertools

def grid_search(param_grid, n_eval=100):
 """Grid search: exhaustive enumeration"""
 # Only evaluate first n_eval points
 all_params = list(itertools.product(*param_grid.values()))
 return all_params[:min(n_eval, len(all_params))]

def random_search(param_ranges, n_eval=100):
 """Random search: sample uniformly"""
 samples = []
 for _ in range(n_eval):
 sample = {k: np.random.uniform(v[0], v[1]) for k, v in param_ranges.items()}
 samples.append(sample)
 return samples

# Test
param_grid_grid = {
 'lr': [0.001, 0.01, 0.1],
 'batch_size': [16, 32, 64],
 'dropout': [0.1, 0.3, 0.5]
}

param_ranges_random = {
 'lr': (0.001, 0.1),
 'batch_size': (16, 64),
 'dropout': (0.1, 0.5)
}

grid_params = grid_search(param_grid_grid, n_eval=100)
random_params = random_search(param_ranges_random, n_eval=100)

print(f"Grid search points: {len(grid_params)}, Random search points: {len(random_params)}")
assert len(grid_params) <= 27, "Grid exhausts all combinations"
assert len(random_params) == 100, "Random search uses full budget"
print("✓ Search strategy comparison working")

if __name__ == "__main__":
 print("Lab 1: Search Strategies - PASSED")

### Lab 2: Gaussian Process Surrogate

import torch
import numpy as np

class SimpleGP:
 def __init__(self, X=None, y=None):
 self.X = X if X is not None else np.array([]).reshape(0, 1)
 self.y = y if y is not None else np.array([])
 
 def predict(self, X_new):
 """Predict mean and uncertainty"""
 if len(self.X) == 0:
 return np.zeros(len(X_new)), np.ones(len(X_new))
 
 # Simplified: distance-based prediction
 distances = np.abs(X_new[:, np.newaxis] - self.X[np.newaxis, :])
 weights = np.exp(-distances)
 
 mean = (weights @ self.y) / (weights.sum(axis=1, keepdims=True) + 1e-8)
 std = np.sqrt(1 - weights.max(axis=1))
 
 return mean, std
 
 def update(self, X_new, y_new):
 """Add new observation"""
 self.X = np.vstack([self.X, X_new])
 self.y = np.concatenate([self.y, y_new])

# Test
gp = SimpleGP()
X_test = np.linspace(0, 1, 50).reshape(-1, 1)

mean, std = gp.predict(X_test)

print(f"Mean shape: {mean.shape}, Std shape: {std.shape}")
assert mean.shape == (50,), "Should predict for all test points"
assert (std >= 0).all(), "Std should be non-negative"
print("✓ GP surrogate working")

if __name__ == "__main__":
 print("Lab 2: GP - PASSED")

### Lab 3: Expected Improvement

import numpy as np
from scipy import stats

def expected_improvement(mean, std, y_best):
 """Compute expected improvement acquisition"""
 # EI = std * (Z * Phi(Z) + phi(Z))
 
 with np.errstate(divide='warn'):
 imp = mean - y_best
 Z = imp / std
 ei = std * (Z * stats.norm.cdf(Z) + stats.norm.pdf(Z))
 ei[std == 0.0] = 0.0
 
 return ei

# Test
mean = np.array([0.5, 0.6, 0.7])
std = np.array([0.1, 0.2, 0.15])
y_best = 0.55

ei = expected_improvement(mean, std, y_best)

print(f"EI values: {ei}")
assert (ei >= 0).all(), "EI should be non-negative"
assert ei.shape == (3,), "Should output EI per point"
print("✓ Expected improvement working")

if __name__ == "__main__":
 print("Lab 3: EI - PASSED")

### Lab 4: Hyperband Resource Allocation

import numpy as np

def hyperband_allocation(R, eta=3):
 """Hyperband resource allocation strategy"""
 # R: max resource, eta: reduction factor
 
 s_max = int(np.log(R) / np.log(eta))
 B = (s_max + 1) * R
 
 allocations = []
 for s in reversed(range(s_max + 1)):
 n = int(np.ceil((B / R) * (eta ** s) / (s + 1)))
 r = int(R * eta ** (-s))
 
 for i in range(int(np.ceil(n / eta ** i))):
 allocations.append({'n': n, 'r': r, 'budget': n * r})
 n = int(n / eta)
 
 return allocations

# Test
allocations = hyperband_allocation(R=81, eta=3)

print(f"Hyperband allocations: {len(allocations)}")
for i, alloc in enumerate(allocations[:3]):
 print(f" Stage {i}: n={alloc['n']}, r={alloc['r']}, budget={alloc['budget']}")
assert len(allocations) > 0, "Should have allocations"
print("✓ Hyperband working")

if __name__ == "__main__":
 print("Lab 4: Hyperband - PASSED")