Korea Advanced Institute of Science & Technology (KAIST) · HayanMind Inc. · Technical University of Nuremberg (UTN) · Munich Center for Machine Learning (MCML) · Helmholtz Munich
Bayesian Optimization (BO) generally begins with an initialization phase: a batch of
n0 uninformed evaluations. The choice of
n0 remains largely heuristic, and we empirically observe that the total cost (random initial points plus BO iterations needed to find the global optimum) is U-shaped in
n0, i.e., a practitioner wastes resources by selecting either too low or too high a value of
n0. We find this tradeoff persists across MLE, Bayesian MCMC, and exact GP hyperparameters, as well as across acquisition functions. Toward the latter, Thompson Sampling appears an exception, with both total cost and simple regret essentially
n0-agnostic, though higher in our experiments. We attribute this U-shape to the known boundary issue of variance-driven BO: BO burns early budget on corners of the hypercube before turning inward. We demonstrate this effect using a 3D BO trajectory where the exact hyperparameters are known. We conclude with practical recommendations: use multi-step lookahead BO where possible; otherwise use Thompson Sampling when
n0 cannot be tuned, and a generously large
n0 when it can.