Does SMBO always use a Gaussian process?

No. Different implementations use different surrogate models, including models suitable for mixed numerical and categorical settings.

Must the next candidate have the best predicted mean?

No. A selection rule may prefer an uncertain candidate with more potential improvement or information value.

Can the procedure run evaluations in parallel?

Yes, although batch selection should account for pending evaluations and possible redundancy between candidates.

AI Glossary / Probabilistic machine learning / Intermediate

Sequential model-based optimization

Definition

Sequential model-based optimization, or SMBO, is an approach to optimizing an expensive objective by repeatedly fitting a surrogate model, using it to select promising evaluations and updating it with the results. Instead of evaluating every possible setting, the procedure uses accumulated evidence to guide where the next evaluation budget should go.

What it means

Training a model, running a simulator or testing an algorithm configuration can be costly. SMBO learns a cheaper approximation of how settings relate to performance. A selection rule then uses that approximation to identify settings worth testing with the actual expensive procedure.

The word sequential describes the feedback loop: new results influence later choices. It does not forbid batches or parallel evaluations. Bayesian optimization is a prominent model-based approach within this broad setting, while SMBO can also use other surrogate constructions. The surrogate predicts the objective; it does not replace the final need to evaluate the selected configuration credibly.

How it works

Define the search space, objective, evaluation protocol and resource budget. Run an initial set of configurations, then fit a model to their observed outcomes. Depending on the problem, that model may need to handle continuous, categorical and conditionally active settings, as well as noise or incomplete evaluations.

An acquisition or selection criterion scores possible next evaluations. It may favor predicted improvement, uncertainty reduction or a combination reflecting evaluation cost. The chosen configuration is then tested, its result is added to the history and the surrogate is updated. This cycle continues until the budget or stopping rule is reached.

The current preferred configuration, often called the incumbent, should be supported by actual evaluations. With noisy outcomes, comparing configurations fairly may require repeated runs or matched problem instances. Selecting the next experiment and declaring the final best configuration are related but different decisions.

Three practical examples

1. Hyperparameter tuning: select learning rates, regularization strengths or architecture settings using validation performance. Keep the final test set separate from the adaptive search.

2. Algorithm configuration: tune solver choices for a representative set of problem instances. A configuration that works on one convenient instance may fail on the broader workload.

3. Simulator optimization: choose settings for an expensive modeled process. Validate the simulator and constraints separately; optimization can otherwise exploit unrealistic features of the simulation.

Think of it this way

Think of testing recipes while maintaining a notebook that predicts which ingredient changes are promising and which remain uncertain. Each new test updates the notebook and influences the next choice. The analogy concerns informed experimentation. The notebook can be wrong, and a promising prediction is not an observed result.

Worked example

Suppose the objective is a loss to minimize and the best evaluated loss so far is 10. A toy surrogate predicts that candidate A will have loss 8 or 12, each with probability one half. Candidate B will have loss 6 or 16, also with equal probabilities. These discrete predictions are invented to make the selection arithmetic transparent.

A's expected loss is 10, while B's is 11. Selecting only the smaller predicted mean would favor A. But expected improvement uses max(10-loss,0): A has expected improvement 0.5 × 2 + 0.5 × 0 = 1, whereas B has 0.5 × 4 + 0.5 × 0 = 2.

An expected-improvement rule therefore selects B under these assumptions. If the actual evaluation returns 16, the incumbent remains the setting with loss 10 and the new observation updates the surrogate. The choice was a prospective experiment, not a guarantee of improvement. This example uses equal evaluation costs and a noiseless incumbent; practical noisy or cost-sensitive criteria require additional care.

Illustrative case study

Fictional case: Maple Scheduling tunes a solver across a set of scheduling instances. An early search ranks a new configuration above the incumbent after testing it only on easier instances. Reviewers notice that the comparison confounds configuration quality with instance difficulty.

The team uses matched evaluation instances for comparisons, records random seeds and reserves separate instances for final assessment. It reports both search cost and the performance of the selected configuration. This fictional case illustrates a reliable evaluation loop, not a claimed improvement from any particular optimizer.

Common misconceptions and mistakes

SMBO does not eliminate exploration or guarantee the global optimum within a finite budget. A misspecified surrogate or an unsuitable search space can misdirect the search. Strong initial predictions can also become misleading when few observations cover the relevant region.

Repeatedly consulting the test set turns it into part of model selection. Ignoring failed or timed-out evaluations can bias the surrogate toward configurations that completed successfully. Predicted uncertainty also depends on the model and its fitting procedure; it is not automatically a calibrated measure of every kind of uncertainty. Finally, more search can overfit a noisy validation protocol rather than improve generalization.

Business use

Use SMBO when each genuine evaluation is expensive enough for the modeling overhead to be worthwhile. Specify the decision metric and constraints before beginning, including whether the priority is accuracy, runtime, cost or a defined combination. Log configurations and outcomes so the final result can be reproduced.

Compare against sensible baselines such as default settings and a budget-matched random search. Measure the full expense of optimization, including failed runs and surrogate fitting. Before deploying the selected configuration, assess it on representative held-out cases with sufficient repetitions for the problem's variability. Treat the optimizer as part of the experimental process, not an authority on the correct business objective.

Check your understanding

Why did expected improvement favor B despite its worse expected loss?

Answer: B offered a larger possible reduction below the current best loss. Its expected positive improvement was 2 compared with A's 1, under the stipulated predictive distributions.

Related terms

Bayesian optimization
Surrogate model
Expected improvement
acquisition function
algorithm configuration
hyperparameter optimization
incumbent
experimental design

Learn next

Reproduce the expected-improvement calculation, then compare selection by predicted mean with uncertainty-aware criteria. Next study how noisy evaluations and matched-instance comparisons change a practical optimization loop.

Expected improvement

Sources

Hutter, Hoos and Leyton-Brown, Sequential Model-Based Optimization for General Algorithm Configuration: https://www.cs.ubc.ca/~hoos/Publ/HutEtAl11.pdf

The model-selection-evaluation loop and configuration-comparison issues were checked in the original paper. The two-candidate calculation and fictional scheduling case are original illustrations. Independent review consulted the original SMBO framework and Section 4.3 expected-improvement selection.

Previous: Sequential minimal optimization Next: Sequential Monte Carlo