Why does random search over hyperparameters usually beat an exhaustive grid on the same budget?

## The two procedures **Grid search** asks you to enumerate a finite list of candidate values for each hyperparameter and then evaluates every combination — the Cartesian product. Its cost is the product of the list lengths, multiplied by the number of cross-validation folds. **Random search** asks you instead to declare a *distribution* per hyperparameter (uniform over an interval, log-uniform over decades, a categorical choice, an integer range), then draws N independent configurations from that joint distribution and evaluates each one. Its cost is N times the number of folds, and N is a number you pick. ## The counting argument Take a support-ticket triage model where a single fit takes 30 minutes, and a grid of four values for one hyperparameter, five for a second, three for a third and three for a fourth. That is `4*5*3*3 = 180` configurations. Under 5-fold cross-validation each configuration is fit five times, so the search is 900 fits — roughly 450 hours of compute if run serially. For those 900 fits, how many distinct values of the first hyperparameter did you actually try? Four. If that hyperparameter is the only one that matters, you spent 900 fits to measure four points on a curve, each measured 225 times over. A random search with the same 180 trials measures 180 distinct values of it — and, simultaneously, 180 distinct values of every other axis. ## Low effective dimensionality The underlying empirical claim, made by Bergstra and Bengio, is that the validation score as a function of the hyperparameters is dominated by a small subset of them; the remaining axes are close to flat over any sensible range. The dimensionality of the space is high, but its *effective* dimensionality is low — and you usually do not know in advance which axes are the live ones. A grid must commit to a resolution on every axis before it starts, and pays for that resolution multiplicatively. Random search spends every trial informatively on every axis at once. A second, purely probabilistic argument: suppose the top 5% of one hyperparameter's range is the region you need to hit. A single random draw hits it with probability 0.05, so N independent draws hit it with probability `1 - 0.95^N`. At N = 60 that is about 95%. You get a strong coverage guarantee on the important axis without knowing which axis it was. ## Irrelevant hyperparameters This is the sharpest practical difference. Add a fifth hyperparameter with three candidate values to the grid above and the run triples, from 900 fits to 2700, whether or not the new axis does anything. Add it to a random search and the run costs exactly the same 180 trials; you simply also get 180 distinct values of the new axis, which is enough to see that it is flat. ## Other properties worth naming - **Anytime behaviour.** Random trials are exchangeable, so you can stop after any number of them and the best-so-far is a fair draw from the space. A grid interrupted halfway has only explored whichever corner of the space the loop happened to reach first, so the partial result is systematically skewed. - **Parallelism.** Both are embarrassingly parallel — this is not a differentiator, and claiming a grid parallelises better is wrong. - **Reproducibility.** Seed the draws and log every configuration with its score; otherwise a random search is not repeatable and you cannot inspect the response surface afterwards. - **Boundaries.** If the best configuration sits at the edge of a searched range, the range was too narrow, not the search too short. ## When a grid is still the right call - One or two hyperparameters, both known to matter, and a cheap fit — the exhaustive answer is simply better and easier to explain. - A small purely discrete space, for example three candidate distance metrics crossed with four neighbourhood sizes. Twelve combinations are exhaustible, and random sampling over a tiny discrete space wastes trials on duplicate draws. - You want the full response surface for a report or a plot, where the regular lattice is the point. ## What an interviewer is listening for The counting argument stated concretely, the low-effective-dimensionality reason behind it, the fact that the cross-validation folds multiply the cost of every configuration, and the honesty to say that on a two-axis discrete space a grid is fine.