The Mathematics Behind Hyperparameter Search

Model fitting is a solved kind of problem. The loss is differentiable, gradients point downhill, and decades of work have produced optimisers that exploit that structure ruthlessly. Hyperparameter tuning has none of it. You cannot differentiate validation accuracy with respect to max_depth, because the parameter changes the training procedure rather than a term in a formula. You cannot see the surface you are optimising. Each evaluation costs a full training run. And the value you get back is not even the true objective, only a noisy estimate of it.

This is black-box optimisation of an expensive, noisy function, and the strategies people use, grid search, random search, Bayesian optimisation, successive halving, are not arbitrary conventions. Each is a specific answer to a specific mathematical feature of that setting. This article derives them, including the result that explains why random search beats grid search at its own game with sixty evaluations regardless of how many hyperparameters you have, and the result that says most of what you learn from a large search is an illusion.

The problem, stated precisely

Let $\lambda$ be a configuration in the hyperparameter space $\Lambda$, and let $\mathcal{A}_{\lambda}$ be the learning algorithm configured by it. We want:

Four properties of this objective determine everything that follows. It has no gradient, since $\lambda$ enters through the training procedure. It is expensive, since a single evaluation means fitting a model. It is noisy, since what we observe is one draw from the sampling distribution of the validation score rather than the expectation. And $\Lambda$ is mixed, containing continuous quantities like learning rate, integers like depth, and categorical choices like the kernel.

Notice that we cannot even evaluate the objective. We observe:

where f is the expectation we want and $\varepsilon$ is the validation noise from the model validation article. This will matter enormously at the end.

Grid search and the exponent

Grid search picks m values per hyperparameter and evaluates every combination. Over d hyperparameters, the cost is:

The exponent is the whole story. Five values across four hyperparameters is 625 fits; add two more hyperparameters and it is 15,625. At two minutes per fit with five-fold cross-validation, that second search is:

The curse of dimensionality is not a metaphor here, it is a schedule. But cost is not grid search’s real defect, because with enough machines you could pay it. The real defect is that the money buys almost nothing.

Why random search beats grid, and it is not about luck

Bergstra and Bengio’s argument is a projection argument, and once seen it cannot be unseen. Take a grid of $n = m^d$ points and project it onto any single hyperparameter’s axis. How many distinct values of that hyperparameter were actually tried?

Now take n random points and project them onto the same axis:

With a 5-by-5-by-5-by-5 grid you performed 625 experiments and learned about the learning rate at five values. Five. The other 620 fits were repeats of those same five settings under different values of things that may not have mattered.

And typically they do not matter. The empirical fact underpinning the whole argument is that hyperparameter importance is wildly unequal: a handful of settings dominate the response surface and the rest are nearly inert. If only $d_{\text{eff}}$ of the d hyperparameters actually move the score, then the grid explores the important subspace with m points while random search explores it with all n. Grid search spends its budget resolving dimensions that do not vary the objective, and it does so by construction, not by bad luck.

The coverage probability, and the number 60

Random search admits a clean guarantee, and it is the most useful piece of mathematics in this entire topic.

Define the top-q quantile of the configuration space: the set of configurations whose true performance places them in the best q fraction of $\Lambda$. By definition of a quantile, a single uniform random draw lands in that set with probability exactly q. Draw n configurations independently, and the probability that at least one lands in the good set is one minus the probability that all of them miss:

Set $q = 0.05$ and $n = 60$:

Sixty random configurations give a better than 95 percent chance of finding something in the top 5 percent of everything available. Invert the formula to size a search directly:

For $P = 0.95$ and $q = 0.05$, that is $n \approx 59$. For the top 1 percent at the same confidence, $n \approx 299$.

Now the punchline, which is easy to skim past. Look for d in that formula. It is not there. The number of evaluations needed to hit the top q quantile with confidence P does not depend on the dimension of the search space at all. Sixty draws work for two hyperparameters and for twenty. Meanwhile grid search needs $m^d$ and buys less. That asymmetry, dimension-free versus exponential, is the entire case, and it is why the default advice is: use random search, run about 60 evaluations, and stop feeling guilty about not gridding.

The guarantee comes with a caveat worth stating honestly. The top-q quantile is defined over the space you specified, so the result promises a good configuration relative to your ranges. If the optimum lies outside your bounds, no number of draws finds it. Random search protects you from dimension, not from a badly chosen box.

Why the log scale is not a style choice

Suppose you sample a learning rate uniformly from $[10^{-5}, 10^{-1}]$. What fraction of your samples fall below $10^{-2}$?

Ninety percent of your budget lands in the single top decade, and the range from $10^{-5}$ to $10^{-3}$, which spans two full orders of magnitude and contains the answer for most deep learning problems, receives about one percent of your draws. On sixty evaluations, that is fewer than one.

The fix is to reparametrise. Sample the exponent uniformly:

which induces the density on $\lambda$:

Now each decade receives an equal share of the budget: a quarter each across four decades.

The justification is not aesthetic, it is about where the response surface is smooth. Moving a learning rate from 0.001 to 0.002 doubles it and can change training completely; moving from 0.101 to 0.102 changes nothing measurable. The objective is approximately smooth in $\log \lambda$, not in $\lambda$, so the meaningful metric on this axis is the ratio between values rather than their difference. Sampling uniformly in the space where the function is smooth is what puts your evaluations where the function actually varies. The same reasoning applies to regularisation strengths, to C in the SVM article, where $\lambda = 1/(2C)$ makes the scale-not-offset nature explicit, and to anything else whose sensible range spans orders of magnitude.

Bayesian optimisation: using what you have learned

Random search has one glaring inefficiency. Draw 59 has no idea what draws 1 through 58 discovered. Every evaluation costs a full training run and its information is thrown away. Bayesian optimisation fixes this by building a model of the objective as it goes.

Place a Gaussian process prior on the unknown function:

After observing $D_n = {(\lambda_i, y_i)}_{i=1}^{n}$, the posterior is again Gaussian at every point, giving a predicted mean and a predicted variance:

The surrogate is cheap to evaluate, so we can search it exhaustively even though we cannot search the real objective at all. The question becomes: given a belief about the objective, where should the next expensive evaluation go?

Answering it requires resolving the exploration-exploitation tension explicitly. Sampling where $\mu_n$ is low exploits current knowledge; sampling where $\sigma_n$ is high explores the unknown. Expected improvement resolves it by a definition rather than a heuristic. Let $f^{*}$ be the best value observed so far and define the improvement:

Because the posterior is Gaussian, the expectation of this quantity has a closed form. With:

the expected improvement is:

where $\Phi$ and $\phi$ are the standard normal CDF and PDF. Read the two terms separately, because the decomposition is the point. The first is large when the predicted mean is well below the incumbent: pure exploitation. The second is large when uncertainty is high, whatever the mean predicts: pure exploration. Nobody balanced them by hand and no trade-off parameter was tuned. Both fell out of taking the expectation of a max, and the balance is a consequence of the definition.

The formula has a property worth noticing. At a point already evaluated, $\sigma_n(\lambda) \to 0$, which sends both terms to zero. Expected improvement is self-avoiding: it will not waste an evaluation where it already knows the answer, and it needs no explicit memory to achieve that.

The honest limits matter as much as the mechanism. Bayesian optimisation is sequential by nature, since choosing the next point requires the previous result, so it parallelises badly, while random search parallelises perfectly across as many machines as you own. The GP itself struggles beyond roughly twenty dimensions. And the surrogate’s own fitting cost only pays off when evaluations are genuinely expensive. The rule follows from the maths rather than taste: Bayesian optimisation when each fit takes hours and you have few machines, random search when fits are cheap or your cluster is wide.

Successive halving: spending the budget, not the draws

A different lever entirely. Everything above assumes each configuration gets a full training run, but most configurations are obviously bad after a fraction of one. Successive halving exploits this. Start with n configurations on a small budget b each, keep the best fraction $1/\eta$, multiply the survivors’ budget by $\eta$, and repeat.

After r rounds:

The product is what makes it work:

Every rung costs the same total, so the scheme evaluates many configurations cheaply and few configurations thoroughly, at the price of one rung’s budget per level. Where random search spends its budget uniformly across n full fits, successive halving spends it in a shape matched to the belief that bad configurations reveal themselves early.

Hyperband layers one more idea on top, running several brackets with different $(n, b)$ trade-offs, because the aggressive setting fails when a configuration is a slow starter and the conservative setting wastes budget when it is not. Running both hedges against not knowing which regime you are in.

The resolution limit nobody mentions

Return to what we can actually observe:

Every score in your search has a standard error s, and you selected the maximum of M of them. The validation article derived the consequence, and it applies here with full force, because hyperparameter tuning is the purest instance of the multiple comparisons problem in all of machine learning:

For the recommended 60-evaluation random search with a typical standard error of 0.02:

Nearly six accuracy points of the winner’s advantage are manufactured by the act of choosing. And the term is monotone in M, so the more diligently you search, the more inflated the reported best. Diligence is taxed.

This implies a resolution limit that is rarely acknowledged. If your top ten configurations sit within 0.01 of each other and s is 0.02, you have not learned which is best. You have learned that ten configurations are indistinguishable and that one of them got lucky. Reporting the winner’s cross-validated score as the model’s performance is reporting $f(\lambda) + \max_j \varepsilon_j$ and calling it f.

Two consequences follow directly. First, the search’s output is a configuration, never a performance estimate; performance comes from data the search never saw, which is what nested cross-validation or a locked test set provides. Second, prefer the simpler configuration among statistical ties, since when the differences are inside the noise, the tiebreak should be something the noise cannot fake, and a shallower tree or a stronger regularisation is a better bet than the specific numbers that happened to win a coin flip.

What the mathematics tells you to do

Use random search over grid search, because grid explores each axis at only m values regardless of budget while random explores it at n, and because the coverage guarantee is free of d while the grid’s cost is exponential in it. Run about 60 evaluations when you want the top 5 percent, and about 300 for the top 1 percent, since $n = \ln(1-P)/\ln(1-q)$ answers the question exactly. Sample learning rates and regularisation strengths log-uniformly, because uniform sampling puts 90 percent of your budget in the top decade of a range whose answer usually lives four decades down. Reach for Bayesian optimisation only when fits are expensive, dimensions are modest, and parallelism is scarce, because its sequential nature is the price of its sample efficiency. Use successive halving when bad configurations are identifiable early, since the constant $nb$ per rung is what buys the extra breadth. And treat the winner’s score as inflated by roughly $s\sqrt{2\ln M}$, always.

The idea beneath all of it is that tuning is an inference problem, not a search problem. You are not looking for a hidden optimum in a static landscape; you are trying to learn about a function through a noisy, expensive channel, with a budget that buys only a handful of samples. Every method here is a different answer to how to spend that budget: random search says spread it, because dimension-free coverage beats exponential cost. Bayesian optimisation says model it, because past evaluations should inform future ones. Hyperband says stage it, because cheap early looks are informative. And the noise term says, quietly, underneath all three, that the last few decimal points you are competing over do not exist.

See you soon.