The budget problem

That blind spot is fatal when the budget is small. A classic result sharpens the point: Bergstra & Bengio (2012) showed random search beats grid search for hyperparameters — not because randomness is smart, but because real objectives have low effective dimensionality. A 5×5×5 grid spends 125 evaluations but tests only five distinct values of each coordinate; if only one coordinate really matters, 120 evaluations were wasted duplicates. Random search covers every 1-D projection densely. Neither, however, learns anything from the values it observes.

Bayesian optimization’s bet: with evaluations this expensive, it is worth spending real computation between evaluations — fitting a probabilistic model of f and optimizing a decision criterion on it — to make each evaluation count. Here is that bet, measured rather than asserted:

A real GP-EI Bayesian optimizer (implemented in numpy for this page) against random and grid search on the negated Branin function: 30 evaluations, 20 repetitions, shaded bands are ±1 sd. BO’s curve climbs faster and plateaus higher — the entire value proposition in one figure. (Grid’s staircase is an artifact of its fixed visiting order.)

← Optimization when you can query, not differentiate A brief history: 1964 → 1998 → 2012 →