Hyperparameter Tuning

A hyperparameter is any configuration value fixed before the learning algorithm runs, as opposed to a parameter (weights, biases) updated by gradient descent inside training. Common hyperparameters include the learning rate $\eta$, batch size $B$, weight decay coefficient $\lambda$, dropout rate $p$, number of layers, and momentum coefficients in optimizers like Adam. Hyperparameter tuning is the process of choosing values for these variables to optimize a held-out validation metric — typically validation loss or accuracy, never the test set, since tuning against the test set silently leaks information and inflates reported performance. Formally, tuning is optimization of a function $f(\theta)$ where $\theta \in \Theta$ is a hyperparameter configuration drawn from a configuration space $\Theta$ (a product of intervals, discrete sets, and categorical choices), and $f(\theta)$ is the validation score obtained by training a model with configuration $\theta$ until convergence (or a fixed budget) and evaluating it. This function is a black box: it has no closed form, no accessible gradient with respect to $\theta$, and each evaluation costs minutes to days of compute. This is fundamentally different from the inner optimization problem (minimizing training loss over network weights), which does have gradients and is solved with methods like Adam and Its Variants. The outer problem — search over $\Theta$ — is what this article addresses. Three strategies dominate practice. Grid search discretizes each hyperparameter into a fixed set of values and evaluates every combination in the Cartesian product. Random search samples configurations independently from a specified distribution over $\Theta$ (e.g., log-uniform for learning rate) and evaluates a fixed number of them. Bayesian optimization maintains a probabilistic surrogate model of $f$, fits it to all trials observed so far, and uses an acquisition function to choose the next point that best balances exploring uncertain regions against exploiting regions known to be good. Understanding why the third approach dominates in sample efficiency — and why the second dominates the first — requires understanding how information behaves across dimensions of unequal importance, developed next.

Grid search proceeds by discretizing each hyperparameter axis and enumerating the full product. If hyperparameter $i$ has $k_i$ candidate values, the total number of trials is $\prod_i k_i$ — exponential in the number of hyperparameters. ``` GRID-SEARCH(grids[1..d], train_and_eval):

# grids[i] is a list of k_i candidate values for hyperparameter i best_score := -infinity best_config := null for config in CARTESIAN-PRODUCT(grids[1], ..., grids[d]): score := train_and_eval(config) # trains model, returns validation score if score > best_score: best_score := score best_config := config return best_config, best_score ```

Random search instead samples each configuration independently from a chosen distribution per axis (uniform, log-uniform, categorical) and evaluates a budget of $T$ trials, where $T$ is chosen in advance based on available compute — no exponential blow-up with dimension. ``` RANDOM-SEARCH(distributions[1..d], train_and_eval, T): best_score := -infinity best_config := null for t := 1 to T: config := [SAMPLE(distributions[i]) for i in 1..d] score := train_and_eval(config) if score > best_score: best_score := score best_config := config return best_config, best_score ``` The key reason random search is preferred to grid search at equal budget: in high dimensions, most objective functions are dominated by a small number of important hyperparameters (the effective dimensionality is low). Grid search wastes evaluations by repeating the same values along unimportant axes; random search, by contrast, produces a distinct value on every axis for every trial, so it explores the important axes far more densely for the same total budget. This is a geometric fact about projections of a grid versus a random sample onto a low-dimensional subspace, illustrated below.

Bayesian optimization replaces blind sampling with a model-guided search. It maintains a surrogate model — most commonly a Gaussian process (GP) — over the unknown function $f(\theta)$, using all $(\theta_t, f(\theta_t))$ pairs observed so far. After fitting the GP, every untried point $\theta$ has a predicted mean $\mu(\theta)$ and standard deviation $\sigma(\theta)$ (a posterior belief, not a point estimate). An acquisition function, such as Expected Improvement (EI), converts this belief into a score that favors points that are either likely to beat the current best (exploitation, low $\sigma$, high $\mu$) or highly uncertain (exploration, high $\sigma$). The next trial is chosen by maximizing the acquisition function — a cheap optimization over the surrogate, not over the real expensive objective. ``` BAYES-OPT(objective_space, train_and_eval, T, n_init): D := {} # observed (config, score) pairs for t := 1 to n_init: config := RANDOM-SAMPLE(objective_space) # warm-start with random trials score := train_and_eval(config) D := D union {(config, score)} for t := n_init+1 to T: GP := FIT-GAUSSIAN-PROCESS(D) # posterior mean mu(.), std sigma(.) f_best := max(score for (_, score) in D) config := argmax over config in objective_space of EXPECTED-IMPROVEMENT(GP, config, f_best) score := train_and_eval(config) D := D union {(config*, score)} return argmax (config, score) in D of score ``` where the Expected Improvement acquisition function, in closed form for a GP posterior $\mathcal{N}(\mu(\theta), \sigma(\theta)^2)$, is

with $\Phi, \phi$ the standard normal CDF and PDF, and $\xi \ge 0$ a small exploration margin. Intuitively: EI is large where the predicted mean is high (good exploitation candidate) or the uncertainty is large (good exploration candidate), and exactly zero where the GP is certain the point is worse than the current best.

Grid search complexity. With $d$ hyperparameters and $k_i$ candidate values for the $i$-th, the number of trials is $N = \prod_{i=1}^{d} k_i$, and total cost is $N \cdot C_{\text{train}}$, where $C_{\text{train}}$ is the cost of one training-and-evaluation run. This is exponential in $d$ for fixed $k_i = k$: $N = k^d$. Memory cost is $O(N)$ to store all scores, or $O(1)$ streaming if only the best is kept. Grid search is exhaustive over the specified grid, so within the discretization it is guaranteed to find the best grid point — but the discretization itself may miss the true optimum, and refining the grid to reduce that error multiplies $N$ further.

Random search complexity. With a fixed trial budget $T$ chosen independent of $d$, total cost is $T \cdot C_{\text{train}}$ — no exponential dependence on dimension. The correctness argument for why random search is competitive rests on effective dimensionality: suppose only $d_{\text{eff}} \ll d$ of the hyperparameters materially affect $f$. A grid with $k$ levels per axis places only $k$ distinct values along any single important axis, no matter how large $d$ is, because the grid is a rigid product structure. A random sample of $T$ points, by contrast, has $T$ distinct values (with probability 1, for continuous distributions) projected onto every axis independently. So for the same total budget $N = k^d$ trials, grid search tries only $k$ values of the important axis, while random search with $T = k^d$ trials tries $k^d$ values of that axis — a search that is a factor of $k^{d-1}$ denser along the direction that matters. This is why Bergstra and Bengio's foundational empirical and theoretical analysis showed random search reliably outperforms grid search at equal budget whenever the effective dimensionality is low, which is typical for deep network hyperparameters (learning rate and one or two regularization terms usually dominate; exact batch size or momentum decay often barely matter within a wide range).

Bayesian optimization complexity. Each iteration fits a GP to $t$ observed points, which costs $O(t^3)$ for the Cholesky factorization used in exact GP inference (inverting the $t \times t$ kernel covariance matrix), plus $O(t^2)$ per prediction query. Over $T$ total iterations this GP-fitting overhead is $O(T^4)$ in the worst case (summing $t^3$ over $t=1,\ldots,T$), which becomes the bottleneck only when $T$ is large (hundreds to low thousands) or when $C_{\text{train}}$ is small enough that the surrogate overhead is comparable to actual training cost — in deep learning, $C_{\text{train}}$ (hours of GPU time) almost always dominates this polynomial surrogate cost, which is exactly the regime where Bayesian optimization pays off. The correctness/efficiency argument: EI provably never assigns positive value to a point that is worse than the current best with the GP's own certainty, and it is bounded below by exploitation (it never fully ignores promising regions) while remaining unbounded above wherever uncertainty is large (it never fully stops exploring). Formally, EI is the posterior expectation of the improvement random variable $I(\theta) = \max(0, f(\theta) - f_{\text{best}})$ under the GP, so maximizing it is the Bayes-optimal single-step (myopic) choice given the model — it is not globally optimal over the whole search horizon (that would require solving a much harder sequential decision problem), which is the honest caveat: BO greedily optimizes expected one-step gain, not long-run regret.

Tradeoffs, honestly stated.

Consider tuning two hyperparameters for an image classifier: learning rate $\eta \in [10^{-4}, 10^{-1}]$ (searched on a log scale) and weight decay $\lambda \in [10^{-5}, 10^{-1}]$ (also log scale). Suppose the true validation accuracy surface has a narrow ridge of good performance around $\eta \approx 3\times10^{-3}$, largely insensitive to $\lambda$ across two orders of magnitude — a realistic effective-dimensionality-1 situation.

Grid search, budget $N = 9$ (3 × 3 grid): $\eta \in \{10^{-4}, 10^{-2.5}, 10^{-1}\}$, $\lambda \in \{10^{-5}, 10^{-3}, 10^{-1}\}$. Only three distinct $\eta$ values are ever tried; none lands near $3\times10^{-3}$, so the best grid point may sit at $\eta = 10^{-2.5} \approx 3.2\times10^{-3}$ by luck, achieving 91.2% validation accuracy — the near-hit is coincidence, not guarantee.

Random search, budget $T = 9$, sampled log-uniformly on both axes:

Nine distinct $\eta$ values were sampled, two of them (trials 2 and 6) land close to the true ridge, and the best result (93.9%) beats grid search's coincidental near-hit — because the density of $\eta$-values tried near the optimum was higher, exactly as the complexity argument predicts.

Bayesian optimization, budget $T = 9$ with $n_{\text{init}} = 3$ random warm-start trials, then GP-guided: after the first 3 random trials establish rough structure (say accuracies of 78%, 84%, 65% at scattered points), the GP posterior mean rises steeply near $\eta \approx 3\times10^{-3}$ and EI concentrates subsequent trials there. By trial 9, Bayesian optimization typically converges to $\eta \approx 3.1\times10^{-3}$, $\lambda \approx 1.5\times10^{-4}$, achieving 94.3% — extracting slightly more signal from the same nine-trial budget by using earlier results to inform later choices, at the cost of having to fit and query a GP after every trial and losing the ability to launch all 9 trials in parallel.

Hyperparameter search connects two distinct lineages: classical statistical experiment design (grid and factorial designs date to Fisher's agricultural field trials) and Bayesian decision theory applied to machine learning model selection, popularized as computational budgets made naive grid search infeasible for deep networks.

Hyperparameter tuning underlies nearly every production deep learning pipeline. Cloud ML platforms (Google Vertex AI, Amazon SageMaker Automatic Model Tuning, Azure ML) expose Bayesian optimization as a managed service specifically for learning rate, regularization, and architecture search. Open-source libraries — Optuna, Ray Tune, Hyperopt, and scikit-optimize — implement random search, tree-structured Parzen estimators, and GP-based Bayesian optimization as interchangeable backends behind a common search API. Large-scale neural architecture search systems combine Bayesian optimization with bandit-based early stopping (Hyperband, BOHB) to prune bad configurations early, saving enormous compute at data-center scale. Recommendation systems, speech models, and vision transformers trained by major labs all report the specific learning-rate schedule, warmup length, and weight decay found via exactly this kind of outer search — the tuning step is often the difference between a paper's headline result and an unremarkable baseline. It also directly foreshadows Transfer Learning and Fine-Tuning, where the search space shrinks (often to just a learning rate and number of unfrozen layers) but the same search machinery — random or Bayesian — is reused around a pretrained backbone.

Ask the tutor: How would you design a hyperparameter search strategy under a strict fixed compute budget when some configurations are far more expensive to train than others?