You've run the experiment. The model's trained. Practically speaking, the acquisition function is humming along. And then someone asks — "So, how many data points did you actually need to start seeing real signal?
Good question. But in practice? So most papers gloss over it. Most tutorials assume you have infinite budget. You're staring at a blank spreadsheet, a limited compute budget, and a boss who wants results yesterday It's one of those things that adds up..
Here's the uncomfortable truth: there's no universal number. Anyone who tells you "30 points" or "5 times the dimensionality" is selling something — or repeating a heuristic they never stress-tested.
Let's talk about what actually determines the minimum sample size for Bayesian optimization, why the textbook answers fail, and how to think about it when you're the one making the call.
What Is Bayesian Optimization, Really
Bayesian optimization (BO) is a sequential model-based optimization strategy. On top of that, you build a probabilistic surrogate model — usually a Gaussian process — of your objective function. Now, then you use an acquisition function to decide where to sample next. Rinse, repeat Practical, not theoretical..
The surrogate model is the key. On the flip side, it doesn't just predict; it quantifies uncertainty. That uncertainty is what lets BO balance exploration (trying where we're unsure) against exploitation (pushing where we think the optimum lives) Less friction, more output..
But here's the catch: a Gaussian process with three data points is barely a model. That's why it's a guess wearing a tuxedo. The posterior mean reverts to the prior. On the flip side, the uncertainty bands are comically wide. The acquisition function? It's mostly chasing noise.
So the minimum sample size isn't about when BO starts. It's about when the surrogate stops hallucinating.
The cold-start problem
Every BO run has a cold start. Before you have any data, you have a prior. After two? Still mostly prior. After one point, you have a posterior that's barely updated. The model needs enough observations to "lock in" — to let the data overwhelm the prior assumptions about length scales, signal variance, noise levels It's one of those things that adds up..
This is why most practitioners use an initial design: Latin hypercube, Sobol sequence, random sampling. You're not optimizing yet. You're buying the model a fighting chance.
Why It Matters / Why People Care
If you undersample, three things happen — and none of them are subtle.
First, the surrogate model overfits to noise. Consider this: gaussian processes are flexible. Also, with too few points, they'll happily fit a wiggly function through your observations, inventing local optima that don't exist. The acquisition function then chases ghosts.
Second, hyperparameter estimation becomes unstable. On the flip side, length scales, signal variance, noise — these are usually learned by maximizing marginal likelihood. The optimizer picks a random mode. With sparse data, the likelihood surface is flat or multimodal. Your model's behavior becomes arbitrary And that's really what it comes down to..
Third, you waste budget on pure exploration. But the "I have no idea what this function looks like so I'll sample randomly" kind. Not the smart, information-theoretic kind. That's not Bayesian optimization. That's expensive random search.
I've seen teams burn 80% of their evaluation budget just getting the GP to a point where it stops predicting negative values for a strictly positive objective. That's not a modeling failure. That's a sample size failure.
How It Works: What Actually Determines the Minimum
There's no single formula. Consider this: pull the right ones and you need fewer points. But there are levers. Ignore them and you'll need more — sometimes a lot more.
Dimensionality is the obvious one
Each dimension adds volume exponentially. A 2D space with 10 points per dimension needs 100 points for a grid. A 10D space needs 10 billion. BO doesn't need grids — that's the whole point — but the curse of dimensionality still bites The details matter here..
Rough heuristic: you need at least d + 1 points to fit a non-degenerate GP in d dimensions. But "non-degenerate" isn't "useful." In practice, expect to need 10–20× the dimensionality before the model has meaningful signal — if the function is smooth and low-noise.
High-dimensional BO (20+ dims) is a different beast entirely. Standard GPs collapse. Also, you need additive structure, random embeddings, or dropout. The minimum sample size there isn't a number — it's a research project.
Smoothness and length scales
A function that varies slowly (long length scale) is easier to model than one that oscillates wildly. If your objective changes significantly over 1% of the domain, you need dense sampling to capture that. If it's a broad bowl, five well-placed points might sketch the shape That alone is useful..
The Matérn kernel with ν = 5/2 is the workhorse for a reason — it assumes twice-differentiable functions, which matches many real-world objectives. But if your function has discontinuities, sharp ridges, or high-frequency noise? Plus, the GP will smooth right over the features you care about. So you'll need more points. Sometimes dramatically more.
Noise level changes everything
This is the one most people underestimate.
Noiseless observations (simulators, deterministic code) let you interpolate exactly. Worth adding: the GP passes through every point. Ten clean evaluations can give you a decent global picture in 3–5 dimensions.
Add noise — even modest noise — and everything changes. The GP can't interpolate anymore. So it has to regress. Each observation carries less information. You need replication or denser sampling to average out the noise. The signal-to-noise ratio effectively multiplies your required sample size Small thing, real impact..
I've seen cases where going from σ = 0 to σ = 0.And 05×(max−min) doubled the evaluations needed to reach the same regret. Even so, that's not a bug. That's information theory Not complicated — just consistent..
Prior knowledge is a force multiplier
If you know the length scale is roughly 0.Because of that, 2 in normalized space, encode that. If you know the function is monotonic in one dimension, use a monotonic kernel. If you have physics-based constraints, bake them in.
Strong priors can cut the required sample size by 3–5×. Weak priors (wide log-normal on length scales) barely help. The difference between "I think it's smooth" and "I know the length scale is 0.Consider this: 15 ± 0. 03" is the difference between 50 evaluations and 15.
This is why transfer learning and meta-learning for BO are hot topics. If you've optimized similar functions before, you're not starting from zero. You're starting from a posterior that's already seen data.
The acquisition function matters too
Expected Improvement (EI) is greedy. It exploits hard. With few points, it can get stuck in local optima because the model is overconfident.
Upper Confidence Bound (UCB) with a decaying exploration parameter? More reliable to sparse data — but you need to tune the schedule.
Thompson Sampling? Naturally explores more. Often works better in the low-data regime because it samples from the posterior rather than optimizing an acquisition surface that might be pathological.
Entropy Search / Predictive Entropy Search / Max-value Entropy Search? These are information-theoretic. Now, they explicitly value reducing uncertainty about the optimum. Day to day, in theory, they're more sample-efficient. In practice, they're computationally heavier and can be brittle with misspecified models And that's really what it comes down to. Less friction, more output..
If you're data-starved, UCB or Thompson Sampling with a slightly inflated exploration constant is often the pragmatic choice Worth keeping that in mind. Nothing fancy..
Common Mistakes / What Most People Get Wrong
Treating the initial design as optional
"I'll just start with one random point and let BO figure it out."
No. But the first n points are not BO. They're design of experiments. So skipping them doesn't save evaluations — it just makes the first n BO iterations wasteful. The acquisition function has no meaningful uncertainty to work with.
Use a space
…filling design such as a Latin Hypercube, Sobol low‑discrepancy sequence, or a maximin distance set. These designs give the surrogate model a broad view of the input space right from the start, ensuring that the early posterior variance is not concentrated in a tiny region. When the initial points are poorly spread, the GP may become overconfident in unexplored areas, causing the acquisition function to chase mirages and waste evaluations.
Ignoring hyper‑parameter uncertainty
Many practitioners fix the kernel’s length‑scale and variance to point estimates obtained by maximizing the marginal likelihood after a handful of observations. With scarce data, those estimates are noisy, and the resulting posterior can be either too smooth (missing narrow peaks) or too wiggly (chasing noise). A better approach is to place a prior on the hyper‑parameters and integrate them out (e.g., via slice sampling or Hamiltonian Monte Carlo) or to use a strong marginal likelihood optimizer that re‑estimates them after each new batch of points. Even a simple re‑optimization every five iterations can prevent the model from locking into a misleading length‑scale that inflates the required sample size.
Over‑reliance on a single acquisition function
Switching acquisition functions mid‑run is rarely discussed, yet it can be advantageous. Early on, when uncertainty is high, an exploratory criterion like UCB with a large β or Thompson Sampling helps the model discover promising basins. Once a few low‑regret points have been found, shifting to a more exploitative rule such as Expected Improvement or Predictive Entropy Search can fine‑tune the optimum without wasting evaluations on unnecessary exploration. Adaptive schemes that monitor the improvement rate and automatically adjust the exploration‑exploitation balance have been shown to cut the total budget by 10‑20 % in benchmark suites.
Neglecting constraints and conditional dependencies
Real‑world problems often involve inequality constraints (e.g., power limits) or conditional variables (e.g., only evaluating a costly simulator if a cheap surrogate passes a threshold). Treating these as black‑box penalties can distort the GP’s perception of feasibility, leading the optimizer to waste samples in infeasible regions. Incorporating constraints directly into the kernel—using constrained Gaussian processes or warping functions—or employing a separate feasibility classifier that guides the acquisition function preserves evaluation efficiency.
Misinterpreting regret curves
Plotting simple cumulative regret against iteration count can be misleading when the noise level changes or when the objective is re‑scaled mid‑experiment. This is genuinely important to report simple regret (the best observed value so far) alongside cumulative regret, and to normalize both by the known range of the function or by the variance of the noise. This prevents the illusion of progress that is merely due to a shrinking noise estimate rather than genuine improvement in the underlying objective Worth keeping that in mind. Less friction, more output..
Conclusion
Bayesian optimization shines when we treat every component—initial design, surrogate prior, acquisition strategy, and hyper‑parameter handling—as a coordinated experiment rather than a black‑box plug‑and‑play routine. A well‑chosen space‑filling seed gives the GP a honest starting point; informative priors on length scales and monotonicity act as force multipliers that shrink the required budget; thoughtful acquisition choices (UCB, Thompson Sampling, or adaptive hybrids) keep exploration balanced even when data are scarce; and vigilance about hyper‑parameter uncertainty, constraints, and proper regret metrics prevents subtle but costly pitfalls. By respecting these principles, practitioners can turn the theoretical sample‑efficiency of BO into tangible savings—often reducing the number of expensive function evaluations by a factor of three to five or more—while still converging to the true optimum with confidence But it adds up..
