Adaptive sampling - Ciallo Wiki

1 Overview and motivation

Adaptive sampling is a family of strategies for choosing where to collect new data, evaluate a costly function, or query a model. Unlike non-adaptive designs that commit to a predetermined set of sample points, adaptive methods update their selection rule after observing intermediate results. This iterative feedback loop allows the algorithm to concentrate effort where additional information is expected to be most valuable.

1.1 Why sampling needs to adapt

In many tasks, the most informative regions are not known in advance. Early observations can reveal structure (such as smoothness, discontinuities, or changing trends), which in turn changes where further sampling should occur. Adaptation is also useful when budgets are limited: rather than distributing samples uniformly, a method can redirect queries toward areas that improve estimates faster or reduce uncertainty more effectively.

Another motivation is that measurement processes often have variable difficulty across the input domain. Some settings may produce reliable outputs, while others may be noisy or expensive to evaluate. Adaptive sampling can incorporate this heterogeneity, allocating more attention where it is most likely to pay off.

1.2 Fixed vs. adaptive sampling

Fixed sampling chooses a set of points once, before any data are collected. The resulting estimator is designed for that predetermined pattern, which may be adequate when the underlying function is well understood or when the cost of evaluation is uniform.

Adaptive sampling, by contrast, treats the sampling plan as a policy that depends on past data. The policy may vary the next query location based on current posterior uncertainty, expected objective improvement, constraint violations, or performance metrics observed so far. As a result, adaptive methods can better respond to the observed behavior of the system.

1.3 Common goals: accuracy, efficiency, and coverage

Adaptive sampling is typically used to balance several objectives:

Accuracy: reduce error in an estimate (e.g., regression, prediction, or optimization).
Efficiency: achieve a target accuracy with fewer evaluations, or maximize performance under a fixed budget.
Coverage: ensure that the sampled points collectively explore the space enough to avoid blind spots, especially in high-dimensional or irregular domains.

These goals often compete. For example, maximizing uncertainty reduction may lead to scattered exploration, while focusing on likely high-performing regions may under-sample other areas. Many methods therefore incorporate explicit diversity or exploration–exploitation balancing.

2 Foundations and problem setup

Adaptive sampling can be framed broadly as a sequential decision problem: at each iteration, the method selects the next sample location based on a data set accumulated so far. The specific form depends on the measurement model and the quantity being estimated.

2.1 Data, observations, and measurement models

At iteration \(t\), the method has collected data \(\{(x_i, y_i)\}_{i=1}^t\), where \(x_i\) denotes a query location (input, design variable, or experimental setting) and \(y_i\) is the observed response.

A model of how observations relate to latent quantities is central to adaptive sampling, because it determines how uncertainty is computed and how updates are performed.

2.1.1 Deterministic vs. stochastic functions

A common distinction is whether the underlying function is treated as deterministic or stochastic. In deterministic settings, the response can be written as \(y=f(x)\), and uncertainty primarily comes from imperfect modeling or numerical approximation. In stochastic settings, \(y\) includes randomness, typically modeled as \[ y = f(x) + \varepsilon, \] where \(\varepsilon\) captures noise from measurement errors, environmental variability, or intrinsic randomness in the process.

Deterministic and stochastic assumptions influence whether repeated sampling at the same location is meaningful and how posterior uncertainty contracts with additional data.

2.1.2 Noise models and repeat sampling

When observations are noisy, repeat sampling at the same \(x\) can reduce uncertainty about the expected response at that point. Noise-aware models may also distinguish between epistemic uncertainty (due to lack of knowledge about the function) and aleatoric uncertainty (irreducible randomness in the observations). Adaptive rules can then target locations where epistemic uncertainty is high, rather than simply where the observed variance is large.

Noise modeling also affects confidence intervals and information-gain calculations, since the expected reduction in uncertainty depends on assumed noise level and correlation structure.

2.2 Iterative sampling workflow

A typical adaptive sampling algorithm follows a repeated loop: initialize, fit/update a model or compute an estimator, then choose the next point using a decision rule.

2.2.1 Initialization and stopping criteria

Initialization may start from:

Space-filling designs (e.g., grid or Latin hypercube sampling) to obtain broad coverage.
Problem-informed seeds based on prior knowledge.
Random warm starts with enough points to stabilize initial model estimates.

Stopping criteria can be based on a maximum budget, reaching a target accuracy, meeting a tolerance on improvement, or detecting convergence of the sampling policy or the estimator.

2.2.2 Update step and decision rule

After selecting and observing a new data point, the algorithm updates its internal state, which might include:

Updating regression parameters.
Updating posterior distributions over functions.
Recomputing uncertainty estimates.
Re-evaluating an acquisition function that scores candidate locations.

The next decision is then made by applying the chosen rule to the updated state. This rule can be evaluated over a candidate set (discrete domains) or optimized over a continuous space.

2.3 Notation and evaluation metrics

Notation varies by application, but common components include:

\(x\): input/design variable.
\(y\): observation/response.
\(t\): iteration index.
A predictive model producing \(p(y\mid x, \mathcal{D}_t)\) or point estimates and uncertainty summaries.
A criterion \(a(x)\) used to score how useful sampling at \(x\) would be.

Evaluation metrics depend on the task, such as mean squared error for regression, regret for optimization, calibration error for probabilistic models, or coverage metrics for exploration quality.

3 Acquisition criteria and decision rules

Decision rules determine which candidate location is selected next. Many methods use an acquisition function that quantifies expected usefulness, such as reduction in uncertainty or improvement in performance.

3.1 Uncertainty-based sampling

Uncertainty-based rules select points that maximize some measure of predictive uncertainty, under the intuition that the model is most ignorant where it is least certain.

3.1.1 Variance and confidence intervals

A straightforward approach uses predictive variance:

Choose \(x\) that maximizes the model’s estimated variance of \(y\).
Or use confidence interval width as the score.

Confidence intervals provide a practical way to connect uncertainty to statistical interpretability. However, the usefulness of this strategy depends on having a model whose uncertainty estimates track true error.

3.1.2 Entropy and information gain

Entropy-based criteria generalize variance by focusing on the full predictive distribution. For probabilistic models, an acquisition rule might maximize expected entropy reduction or expected information gain about latent parameters or the function value. These criteria often align with Bayesian decision theory, though they may be computationally more demanding.

Information gain can also incorporate the impact of observation noise, since the amount of learnable information decreases when the measurement is unreliable.

3.2 Improvement-based sampling

Improvement-based rules aim directly at optimizing a target quantity, such as reducing the best observed loss, increasing the probability of achieving a threshold, or enhancing expected objective value.

3.2.1 Expected improvement concepts

Expected improvement evaluates how much better sampling at a candidate \(x\) is likely to be compared with the current best. Under a predictive model, improvement is a random variable, and the method scores points by its expectation.

This approach naturally balances exploration and exploitation: points with high predicted performance yield improvement, while points with high uncertainty can still produce improvement by possibly discovering better outcomes.

3.2.2 Regret and performance-driven rules

In optimization and decision-making, regret measures the gap between the achieved performance and an ideal benchmark. Performance-driven acquisition can aim to minimize expected regret or ensure that the probability of outperforming current best is high.

Such rules are sensitive to the choice of benchmark (e.g., best observed value vs. best predicted value) and to how constraints and noise are handled.

3.3 Diversity and space-filling constraints

Pure uncertainty or pure improvement may produce redundant samples that are too close together, especially when many points appear equally promising. Diversity constraints address this by encouraging spread.

3.3.1 Maximin and coverage objectives

Space-filling objectives can be expressed through distances between sampled points. A maximin criterion selects new points that maximize the minimum distance to existing samples, helping ensure broad coverage and reducing the chance of clustering.

Coverage-oriented designs are common when the goal is to build a global surrogate model that performs well across the entire domain, not only near promising regions.

3.3.2 Balancing exploration vs. exploitation

Exploration–exploitation trade-offs unify many acquisition rules. Exploration seeks information gain in uncertain regions, while exploitation focuses on regions expected to yield strong performance. Balancing can be implemented by combining uncertainty and improvement terms, using explicit exploration parameters, or applying schedules that shift behavior over time.

The right balance depends on the application: early iterations often benefit from exploration to learn the landscape, whereas later iterations may emphasize refinement near optima.

4 Model-based adaptive sampling

Model-based adaptive sampling uses a statistical or machine learning model to represent unknown relationships and compute posterior uncertainty or predictive distributions.

4.1 Surrogate models

Surrogate models approximate expensive functions, replacing costly evaluations with cheaper predictions. The acquisition rule then leverages the surrogate to decide where to sample next.

4.1.1 Interpolation and regression surrogates

Interpolation surrogates pass exactly through observed data (under certain assumptions), while regression surrogates fit noisy data in a least-squares or regularized sense. The choice affects uncertainty characterization: interpolation often implies zero training error and can underestimate uncertainty in noisy contexts unless noise is explicitly modeled.

Regularized regression can mitigate overfitting and provide smoother behavior that supports more reliable acquisition decisions.

4.1.2 Gaussian processes and posterior inference

Gaussian process models define a prior over functions characterized by a covariance kernel. After observing data, the model yields a posterior mean and variance for any candidate \(x\). These quantities directly feed many uncertainty-based and improvement-based acquisition functions.

Gaussian processes are valued for their principled uncertainty estimates, though computational cost can grow with the number of observations, motivating approximations in large-scale settings.

4.2 Bayesian and sequential frameworks

A Bayesian perspective treats the unknown function or parameters as random variables, updating beliefs as data arrive. This perspective often clarifies how uncertainty enters acquisition rules.

4.2.1 Bayesian updating of beliefs

Bayesian updating computes the posterior \(p(\theta\mid \mathcal{D}_t)\) from a prior and a likelihood model. In function-space models, the posterior can be interpreted as updated beliefs about function values at all inputs.

The resulting posterior is used to predict the response at new points and to quantify uncertainty.

4.2.2 Posterior predictive sampling

Instead of relying only on mean and variance, some methods sample from the posterior predictive distribution. These samples can be used to estimate acquisition metrics, such as probability of improvement or expected improvement under non-Gaussian predictive behavior.

Posterior sampling can improve robustness when predictive distributions are complex, but it may increase computation.

4.3 Model misspecification considerations

Adaptive sampling depends strongly on how well the surrogate or statistical model represents the real system. If the model is misspecified, acquisition functions can target misleading uncertainties.

4.3.1 Robustness checks

Robustness strategies include comparing predictions against held-out data, varying model assumptions, using ensembles of models, or checking sensitivity to kernel choices and priors. When acquisition behavior appears unstable, robustness checks can help detect whether the uncertainty signal is trustworthy.

Another approach is to adopt conservative acquisition rules that reduce the influence of potentially overconfident uncertainty.

4.3.2 Calibration of predictive uncertainty

Uncertainty calibration ensures that predicted intervals match empirical error rates. Calibration can be evaluated with reliability diagrams or coverage tests. If the model’s variance is systematically too small or too large, uncertainty-based acquisition may misallocate samples—requiring calibration methods or alternative uncertainty estimates.

5 Sequential experiment design

Sequential experiment design generalizes adaptive sampling to formal experimental planning, where each measurement may have costs, constraints, and desired optimality properties.

5.1 Adaptive experimental design principles

The central idea is to choose experiment settings to optimize an objective that can depend on the current posterior belief, expected utility, or an information criterion.

5.1.1 Optimality criteria (general form)

Many design criteria can be expressed as maximizing an expected utility:

Maximize expected information.
Minimize expected loss under the current model.
Choose settings that yield the most informative parameter estimates.

In a general form, the next design point is selected to maximize the expected value of a utility function computed under the posterior predictive distribution.

5.1.2 Constraints and feasibility regions

Real experiments often restrict feasible settings due to safety, equipment limitations, or physical bounds. Constraint handling can be built into acquisition by restricting candidates to the feasible region, applying penalties for infeasibility, or modeling constraints explicitly.

Feasibility awareness prevents the method from wasting evaluations on settings that are invalid or non-operational.

5.2 Active learning with adaptive sampling

Active learning is a common interpretation of adaptive sampling in machine learning contexts, where queries correspond to obtaining labels or measurements.

5.2.1 Query strategies

Query strategies select which unlabeled instance to label next. Uncertainty sampling, expected model change, and expected error reduction are frequent strategies. The connection to adaptive sampling is direct: the label acquisition is analogous to sampling a new point in an input space.

When models are updated after each label, the policy becomes sequential and adaptive.

5.2.2 Labeling and cost-aware acquisition

Labeling can vary in cost due to time, complexity, or the need for specialized measurement. Cost-aware acquisition incorporates both expected benefit and cost, often using a ratio or a weighted utility. This encourages selecting labels that offer high informational value per unit resource.

5.3 Stopping rules and convergence

Stopping criteria determine when the sequential procedure terminates, balancing computational effort against achieved performance.

5.3.1 Budget-limited stopping

A frequent constraint is a fixed evaluation budget. Under budget limits, the goal becomes maximizing performance after a predetermined number of iterations. In practice, the method may also decide whether to use batch selections to exploit parallel resources.

5.3.2 Tolerance-based stopping

Tolerance-based rules stop when progress becomes sufficiently small, such as when the acquisition function’s maximum falls below a threshold or when changes in the estimated optimum or error proxy are negligible. These rules can prevent unnecessary sampling once the model’s improvement rate has slowed.

Convergence behavior depends on problem structure and modeling assumptions and is therefore application-specific.

6 Computational and practical aspects

Practical performance depends on algorithm engineering: how acquisition is computed, how candidates are generated, and how constraints and numerical issues are handled.

6.1 Implementation details

6.1.1 Batch vs. sequential sampling

Sequential sampling chooses one point at a time. Batch sampling selects multiple points per iteration, which can improve throughput when evaluations are parallelizable. Batch strategies often approximate the sequential policy or use diversity and mutual information to avoid selecting redundant points.

The choice between batch and sequential modes affects both efficiency and the quality of posterior updates.

6.1.2 Numerical stability and scalability

Computational bottlenecks include fitting the surrogate model and optimizing the acquisition function. Numerical stability concerns may arise in matrix operations for probabilistic surrogates, especially with limited data or ill-conditioned kernels.

Scalability solutions include approximate Gaussian process methods, dimensionality reduction for candidate generation, and efficient candidate scoring via gradient-based or heuristic optimization.

6.2 Handling constraints in the sampling space

6.2.1 Bounded domains and restricted regions

Even without explicit constraints, many problems define a bounded input domain. Candidate generation must respect these bounds. Restricted regions can be encoded through hard filtering of candidates, soft penalties, or feasible-set modeling.

This ensures that adaptive sampling does not drift into regions where the model is invalid or where evaluation is impossible.

6.2.2 Incorporating prior knowledge

Prior knowledge can guide initialization, shape priors in Bayesian models, or define regularization terms. Examples include known smoothness, periodicity, monotonicity, or plausible ranges of parameters.

When incorporated carefully, prior knowledge improves sample efficiency by reducing the learning burden on the adaptive process.

6.3 Diagnostics and validation

6.3.1 Back-testing and holdout evaluation

Diagnostics often use holdout sets or cross-validation to evaluate predictive performance over unseen points. Back-testing is useful for assessing whether the adaptive rule would have chosen sensible points earlier, given only past data.

Such evaluations can reveal whether the acquisition-driven sampling strategy leads to genuine improvements or simply exploits model artifacts.

6.3.2 Sensitivity analyses

Sensitivity analysis examines how changes in hyperparameters (e.g., kernel parameters, exploration weights, noise assumptions) affect sampling behavior and outcomes. If results vary widely with minor configuration changes, the method may be fragile or the uncertainty estimates may be unreliable.

7 Applications and illustrative use cases

Adaptive sampling appears across scientific computing and machine learning wherever evaluation is expensive or where the best next measurement depends on interim results.

7.1 Surrogate modeling and simulation-based studies

Surrogate modeling uses adaptive sampling to learn an approximation of an expensive simulator.

7.1.1 Reducing expensive function evaluations

In engineering and scientific simulations, running a full high-fidelity model can be costly. Adaptive sampling can concentrate evaluations in regions that most affect the predicted quantity of interest, such as regions where constraints are violated or where the response varies rapidly.

The result is often a surrogate that achieves desired accuracy with fewer simulation runs than uniform sampling.

7.2 Hyperparameter tuning and resource allocation

Hyperparameter optimization can be treated as an adaptive sampling problem: each configuration is a “sample,” and the validation score is the observation.

Model-based tuning methods fit a surrogate over the hyperparameter space and use acquisition rules to propose the next candidate. As data accumulate, the search focuses on promising regions while still exploring uncertain settings, which can be especially beneficial when each training run is expensive.

Resource allocation may also include early stopping: partially trained models provide intermediate signals that can affect subsequent decisions.

7.3 Scientific measurement and sensor placement

In physical sciences, adaptive sampling can guide where to measure next, such as selecting sensor locations or experimental settings that maximize informativeness.

7.3.1 Targeting informative locations

When measurement campaigns are limited, adaptive methods can choose locations that reduce uncertainty about spatial fields, improve parameter identifiability, or detect anomalies. By using a model of how the observed quantity varies across space, the method can prioritize regions expected to yield the greatest learning.

8 Theory and guarantees (high-level)

Theoretical analysis of adaptive sampling addresses questions like whether the method converges, how fast uncertainty decreases, and under what assumptions it is efficient. Results depend strongly on the model class, noise conditions, and the acquisition rule.

8.1 Conditions for consistency

Consistency refers to whether the estimator converges to the true underlying quantity as the number of samples grows. For adaptive sampling, consistency typically requires that:

The sampling policy does not neglect important regions indefinitely.
The surrogate/model class is sufficiently expressive for the true function.
Uncertainty estimates used by the acquisition rule behave appropriately under the assumed data-generating process.

When these conditions hold, adaptive sampling can inherit favorable convergence properties from the underlying statistical model.

8.2 Sample complexity and efficiency perspectives

Sample complexity describes how many evaluations are needed to reach an error tolerance. Adaptive methods often aim to reduce sample complexity relative to non-adaptive baselines by focusing on informative points.

Efficiency perspectives consider trade-offs: computational overhead for acquisition optimization and model updates versus savings from fewer expensive evaluations. In many settings, the net gain depends on which part of the pipeline dominates cost.

8.3 Trade-offs and limitations

Limitations commonly include:

Model mismatch: incorrect uncertainty can misguide exploration.
Computational burden: acquisition optimization can be costly, especially in high-dimensional spaces.
High-dimensional challenges: distance measures and surrogate modeling may degrade as dimensionality grows.
Noisy or adversarial environments: noise can obscure the true signal, leading to inefficient sampling.

These limitations motivate robust modeling, calibrated uncertainty, and hybrid strategies that combine exploration heuristics with model-based scoring.

Adaptive sampling is connected to several well-known frameworks. The terminology varies across communities, but the shared principle is sequential decision-making based on accumulated information.

9.1 Active learning vs. adaptive sampling

Active learning typically emphasizes selecting which data points to label in order to train a predictive model effectively. Adaptive sampling is a broader term that includes selecting where and what to measure, which can involve labeling, function evaluations, or experimental observations.

In many practical systems, active learning and adaptive sampling are effectively the same mechanism viewed through different lenses.

9.2 Bayesian optimization connections

Bayesian optimization is a prominent instance of model-based adaptive sampling for optimizing expensive black-box objectives. It uses a surrogate model—often Gaussian processes—to compute acquisition functions like expected improvement or probability of improvement.

While Bayesian optimization focuses on finding optima, adaptive sampling also applies to broader estimation tasks beyond optimization.

9.3 Sequential Monte Carlo and adaptive resampling (conceptual link)

Sequential Monte Carlo (SMC) techniques use iterative sampling to approximate distributions, often with resampling steps that depend on current particle weights. Although SMC’s primary goal is approximating probability distributions rather than selecting new experimental points in an input space, the conceptual link is the adaptive use of intermediate information to guide future sampling steps.

This connection highlights a common theme: sequential procedures that adapt their behavior based on observed intermediate states.