Hyperparameter Optimization (HPO)

Grid Search is an exhaustive search method that evaluates every possible combination from a predefined, discrete set of hyperparameter values. It operates by constructing a multi-dimensional grid where each axis represents a hyperparameter and each point is a specific configuration.

• Mechanism: Trains and validates a model for each grid point.
• Guarantee: Will find the best combination within the provided finite set.
• Primary Limitation: Suffers from the curse of dimensionality; search cost grows exponentially with the number of hyperparameters (O(k^n)).

Use Case: Effective only for tuning a very small number (1-3) of hyperparameters due to its computational intensity.

Random Search selects hyperparameter combinations at random from specified distributions (e.g., uniform, log-uniform) for each trial. Proposed by Bergstra and Bengio, it is often significantly more efficient than Grid Search for moderate to high-dimensional spaces.

• Key Insight: For many models, only a few hyperparameters are critically important. Random search explores the entire space more broadly, increasing the probability of finding good values for these key parameters.
• Efficiency: Can find comparable or better configurations than Grid Search with far fewer evaluations, as it doesn't waste budget on exhaustively searching unimportant dimensions.

Best Practice: Define sensible probability distributions (like log_uniform for learning rate) rather than fixed lists to better cover the search space.

Bayesian Optimization (BO) is a sequential model-based optimization (SMBO) technique for global optimization of expensive black-box functions. It builds a probabilistic surrogate model, typically a Gaussian Process (GP), to approximate the objective function (e.g., validation loss).

• Process: 1. Fit the surrogate model to all previously evaluated (hyperparameter, performance) pairs. 2. Use an acquisition function (e.g., Expected Improvement, Upper Confidence Bound) to select the most promising next hyperparameters by balancing exploration and exploitation. 3. Evaluate the chosen configuration, update the model, and repeat.
• Advantage: Highly sample-efficient, making it ideal for HPO where each model training run is costly.

Common Tools: Implemented in libraries like scikit-optimize, BayesianOptimization, and Optuna.

Population-Based Training (PBT) is a hybrid asynchronous algorithm that jointly optimizes model weights and hyperparameters. It maintains a population of models that are trained in parallel.

• Mechanism: Periodically, poorly performing models ("exploit") copy the weights and hyperparameters from top performers. These hyperparameters are then randomly perturbed ("explore") before training continues.
• Key Benefit: It dynamically adjusts hyperparameters during training, allowing schedules (e.g., learning rate decay) to be discovered rather than fixed in advance.
• Distinction: Unlike other HPO methods that treat training as a black box, PBT intertwines optimization with the training process itself.

Use Case: Particularly effective for reinforcement learning and large-scale neural network training where optimal hyperparameters may change over the course of optimization.

Evolutionary Algorithms (EAs) and Genetic Algorithms (GAs) are population-based optimizers inspired by biological evolution. They evolve a population of candidate hyperparameter sets over generations.

• Core Operations:
  • Selection: Choose the best-performing candidates as "parents."
  • Crossover (Recombination): Combine hyperparameters from two parents to create "offspring."
  • Mutation: Randomly alter some hyperparameters in offspring to maintain diversity.
• Fitness: The performance metric (e.g., validation accuracy) acts as the fitness function.
• Strength: Well-suited for complex, non-differentiable, and noisy search spaces. Can escape local minima better than gradient-based methods.

Relation: Population-Based Training (PBT) is a specific form of EA applied concurrently with neural network weight training.

Gradient-Based Optimization treats hyperparameter optimization as a bi-level optimization problem and uses gradients to update hyperparameters. The core idea is to compute the gradient of the validation loss with respect to the hyperparameters (e.g., learning rate, regularization strength) and use it to perform gradient descent.

• Challenge: The validation loss depends on the hyperparameters through the result of the inner loop (model training), which is an iterative, often non-convex, process.
• Solutions:
  • Implicit Differentiation: Uses the implicit function theorem on the optimality conditions of the inner training loop.
  • Unrolled Differentiation: "Unrolls" the training steps as a computational graph and backpropagates through them, which can be memory-intensive.
  • Approximate Gradients: Uses techniques like the Hypergradient method to approximate updates.

Use Case: Most applicable to continuous hyperparameters (like learning rates) where gradients can be meaningfully defined, but less common for discrete architectural choices.

The Multi-Armed Bandit (MAB) problem is a classic formulation of the exploration-exploitation trade-off, relevant to HPO strategies like selecting between different model classes or coarse hyperparameter ranges.

• Core Problem: A gambler faces a row of slot machines (bandits) with unknown payout rates. The goal is to maximize total reward by deciding which machines to play and how often, balancing trying new machines with playing the best-known one.
• Thompson Sampling: A popular MAB solution algorithm. For HPO, it maintains a posterior distribution over the performance of each hyperparameter configuration. It selects a configuration by sampling from each posterior and picking the one with the highest sample, naturally balancing exploration and exploitation.
• Application: Used in Hyperband for early-stopping decisions and in adaptive HPO frameworks.

Gradient-Based Hyperparameter Optimization treats hyperparameters as continuous variables and uses gradient descent to optimize them, differentiating through the entire training process.

• Core Idea: Computes the gradient of the validation loss with respect to the hyperparameters (e.g., learning rate, regularization strength) by unrolling the training steps. This is enabled by techniques like implicit differentiation or the hypergradient method.
• Advantage: Can be very fast for a small number of continuous hyperparameters, as it uses efficient gradient information rather than black-box evaluations.
• Challenge & Limitation: Computationally and memory intensive to unroll many training steps. Not applicable to categorical or architectural hyperparameters. Frameworks like TensorFlow and PyTorch with advanced autodiff enable research in this area.