PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal experimental design: Formulations and computations

Xun Huan, Jayanth Jagalur, Youssef Marzouk

arXiv:2407.16212v2stat.MEcs.NAmath.NAstat.CO

TL;DR

OED addresses how to choose informative data when experiments and measurements can be costly and models may be complex. This survey reviews formulations and computational approaches, including methods for sequential policies. It reports a 1−1/e approximation guarantee for greedy optimization of monotone, nonnegative submodular objectives and identifies open questions in sequential OED.

  • Problem

    Choosing informative data is difficult when experiments are costly and models involve high-dimensional parameters, expensive likelihoods, strong nonlinearities, or non-Gaussian posteriors.

    Source: §1 · pp. 2, 4

  • Method

    The survey synthesizes OED formulations and computational methods, including set-function optimization and sequential policies that adapt experiments to prior outcomes while accounting for future experiments.

    Source: §4.2 · p. 64, §5 · p. 77

  • Results

    For monotone, nonnegative submodular objectives, greedy selection has a 1−1/e approximation guarantee, which cannot generally be improved by another polynomial-time algorithm.

    Source: §4.2.3 · p. 66

  • Takeaways & Limitations

    Sequential OED represents experiment choices as adaptive policies, coordinating each choice with the remaining experiments rather than treating designs only as fixed batches.

    Source: §5 · p. 77

    Beyond the simplest cases, properties of optimal sequential policies and value functions remain little known, limiting characterization of optimality gaps from current representations and network architectures.

    Source: §5.5 · p. 99

Abstract

from arXiv · show

Questions of `how best to acquire data' are essential to modeling and prediction in the natural and social sciences, engineering applications, and beyond. Optimal experimental design (OED) formalizes these questions and creates computational methods to answer them. This article presents a systematic survey of modern OED, from its foundations in classical design theory to current research involving OED for complex models. We begin by reviewing criteria used to formulate an OED problem and thus to encode the goal of performing an experiment. We emphasize the flexibility of the Bayesian and decision-theoretic approach, which encompasses information-based criteria that are well-suited to nonlinear and non-Gaussian statistical models. We then discuss methods for estimating or bounding the values of these design criteria; this endeavor can be quite challenging due to strong nonlinearities, high parameter dimension, large per-sample costs, or settings where the model is implicit. A complementary set of computational issues involves optimization methods used to find a design; we discuss such methods in the discrete (combinatorial) setting of observation selection and in settings where an exact design can be continuously parameterized. Finally we present emerging methods for sequential OED that build non-myopic design policies, rather than explicit designs; these methods naturally adapt to the outcomes of past experiments in proposing new experiments, while seeking coordination among all experiments to be performed. Throughout, we highlight important open questions and challenges.

1. Introduction

Optimal experimental design (OED) formalizes how to acquire data efficiently by selecting experiments against model-based goals. This survey connects classical design theory with computational methods for complex and sequential settings.

1. Introduction

  • OED formalizes choices about what, where, when, and how precisely to measure by defining criteria for useful data before acquisition.The model is used to simulate candidate experiments and assess how their results may improve models and predictions.Source: §1 · p. 2
  • OED spans laboratory experiments, simulations, sensor networks, and applications from clinical trials and regression to inverse problems and complex scientific models.The article notes applications in fields including astronomy, systems biology, aeroelasticity, reliability testing, and nuclear physics.Source: §1 · p. 3
  • The survey traces modern OED from early agricultural design concepts and mid-century design criteria to Bayesian information-based approaches made practical by computing advances.The historical account includes balance, orthogonality, blocking, aliasing, and alphabetic optimality terminology.Source: §1 · pp. 3–4
  • Modern OED addresses complex models with high-dimensional parameters, costly likelihoods, strong nonlinearity, non-Gaussian posteriors, and time-evolving processes.Combinatorial optimization and machine-learning tools also contribute methods for selecting candidate experiments and evaluating complex criteria.Source: §1 · p. 4

1.1. Scope and organization of this article

  • The survey covers design criteria, numerical estimation or bounding, continuous and combinatorial optimization, and sequential policies that adapt to prior outcomes while coordinating future experiments.It concludes by identifying open questions and opportunities for future work.Source: §1.1 · pp. 5–6

2. Optimal design criteria

OED criteria turn the goal of an experiment into a quantitative objective to optimize. Their formulation requires a statistical model of observations, while Bayesian methods can incorporate prior knowledge into design.

2. Optimal design criteria

  • A design criterion quantifies what makes a candidate experiment good, and its optimization identifies a design suited to the chosen goal.The section surveys criteria ranging from specific settings to general formulations.Source: §2 · p. 6
  • A statistical model represents the probability distribution of observations as a function of unknown parameters and the controllable design.It predicts candidate-experiment outcomes and connects them to the estimation or prediction task motivating data acquisition.Source: §2 · pp. 6–7
  • In Bayesian OED, the prior and posterior represent knowledge before and after observing data, and prior information can shape criteria, especially for nonlinear designs.The marginal observation density is the prior predictive distribution; the Bayesian approach is also presented as natural for decision-theoretic reasons.Source: §2 · p. 7

2.1. Design criteria for the linear-Gaussian setting

Design criteria in linear-Gaussian models are often explicit and tractable, with classical and Bayesian variants encoding different goals. The section also treats design measures and the challenges that arise when model behavior is nonlinear in unknown parameters.

2.1. Design criteria for the linear-Gaussian setting

  • Linear-Gaussian design criteria are often explicit and tractable, and can serve as building blocks for nonlinear design approaches.Applications include linear regression and linear inverse problems such as deconvolution, tomography, and source inversion.Source: §2.1 · p. 8

2.1.1. Classical alphabetic optimality

  • Classical alphabetic criteria scalarize the Fisher information matrix to encode goals such as reducing parameter-estimation variance or prediction variance.A-optimality minimizes average parameter variance, E-optimality controls the worst-direction variance, and G-optimality minimizes maximum prediction variance.Source: §2.1.1 · pp. 8–9

2.1.2. Bayesian alphabetic optimality

  • Bayesian alphabetic criteria optimize posterior covariance, so prior information and its balance with likelihood information can affect the chosen design.With a full-rank prior covariance, these criteria do not require an invertible Fisher information matrix and suit designs with fewer than p support points and ill-posed inverse problems.Source: §2.1.2 · pp. 10–11

2.1.3. Designs as probability measures

  • Representing a design as a probability measure unifies discrete and continuous observation choices, while exact designs impose quantized weights.For classical linear criteria, an optimal design exists with at most p(p+1)/2 support points under stated conditions; nonlinear criteria generally lack such upper bounds.Source: §2.1.3 · pp. 11–12

2.1.4. Challenges of nonlinear design

  • In nonlinear models, parameter-dependent Fisher information makes criterion evaluation uncertain; local designs can ignore that uncertainty and depend sharply on the chosen reference parameter.Minimax criteria target worst-case parameter values but can be difficult to optimize; averaging local criteria over a prior is common, though Fisher-information-only formulations are pseudo-Bayesian.Source: §2.1.4 · pp. 13–14
  • A Gaussian approximation criterion for nonlinear design can be far from the precision matrix of the posterior produced by realized data.Such criteria are best viewed as approximations to expected utility from a more principled decision-theoretic formulation.Source: §2.1.4 · p. 14

2.2. Decision- and information-theoretic formulations

The decision-theoretic formulation chooses design criteria by encoding an experiment’s purpose in a utility and averaging over uncertainty. The section extends information gain from parameter inference to other targets and decision goals, while noting computational and modeling qualifications.

2.2. Decision- and information-theoretic formulations

  • Decision-theoretic OED maximizes expected utility, averaging a purpose-specific utility over uncertain outcomes and parameters.The design is chosen before the outcome is known, so the utility is averaged over the joint prior distribution of observations and parameters.Source: §2.2 · pp. 14–15

2.2.1. Expected information gain in parameters

  • Expected information gain (EIG) averages the KL divergence from prior to posterior; it is nonnegative, equals mutual information, and is zero when parameters and observations are independent.Its entropy interpretation is the average reduction in uncertainty from prior to posterior.Source: §2.2.1 · pp. 15–16
  • EIG is invariant to bijective parameter transformations and requires neither linearity nor Gaussianity, while in linear-Gaussian models it reduces to Bayesian D-optimality.When observational error covariance is design-independent, maximizing EIG also maximizes the log-determinant of marginal observation covariance.Source: §2.2.1 · p. 17

2.2.2. Other utility functions

  • For information gain in a parameter subset, uncertainty in the remaining parameters must still be integrated out, adding an integration over the nuisance block.This criterion is mutual information between observations and the parameters of interest, conditional on the design.Source: §2.2.2 · pp. 17–18
  • Goal-oriented EIG targets a function Z = Ψ(Θ), but generic cases require estimating otherwise inaccessible target and marginal densities; bijective Ψ preserves EIG, while non-bijective Ψ lowers it.Linear Ψ with Gaussian priors is one stated case where some computations become more tractable.Source: §2.2.2 · pp. 18–19
  • Sensor-placement optima for future predicted concentrations can differ markedly from parameter-EIG optima; Figure 2.1 contrasts these objectives.The parameter-EIG optimum is nonunique and lies roughly 0.2 units from the domain center, with slight asymmetry from advection.Source: §2.2.2 · p. 19, Figure 2.1 · p. 20
  • Other information targets include future predictions and model indicators; the latter averages over model-specific prior predictives and assumes the true model is among those considered.For random quantities of interest, the conditional density can smooth density estimates and lift the restriction q ≤ p.Source: §2.2.2 · pp. 19, 21
  • Alternatives include posterior-mean quadratic loss and posterior-covariance utilities; valid information measures also return zero for uninformative experiments and respect sufficiency ordering.In linear-Gaussian models, quadratic loss on the posterior mean recovers Bayesian A-optimality; covariance criteria can be intended for nonlinear or non-Gaussian cases but remain computationally demanding.Source: §2.2.2 · pp. 21–23

2.3. Design criteria for infinite-dimensional problems

The section surveys design criteria for infinite-dimensional models, especially Bayesian inverse problems and Gaussian-process regression. It describes tractable criteria and approximations alongside computational challenges and open boundaries.

2.3. Design criteria for infinite-dimensional problems

  • Infinite-dimensional models treat parameters as functions, arise in inverse problems and nonparametric inference, and motivate well-defined Bayesian formulations with discretization-invariant algorithms.For PDE inverse problems, the unknown may be an initial condition, source, boundary condition, or heterogeneous coefficient.Source: §2.3 · p. 23, §2.3.1 · p. 23

2.3.1. Inverse problems in the Bayesian setting

  • For Gaussian-prior inverse problems, linear forward operators support Bayesian A-optimality by minimizing posterior-covariance trace; an EIG-based objective supplies a D-optimality analogue.The ordinary log-determinant of the infinite-dimensional posterior covariance is not meaningful because its eigenvalues accumulate at zero.Source: §2.3.1 · pp. 23–25
  • Infinite-dimensional inverse-problem design is computationally challenging because discretization dimension and forward-operator costs are high; low-rank Hessian structure and randomized linear algebra can help.The EIG expression in the linear-Gaussian case uses a log-determinant involving the prior-preconditioned Hessian.Source: §2.3.1 · p. 25
  • For nonlinear forward operators, full infinite-dimensional EIG has not been used as a design criterion to the authors’ knowledge, so simpler risk and covariance criteria or approximations are used.Posterior covariance is difficult to approximate; a Laplace approximation at the MAP point is reasonable when the posterior is close to Gaussian.Source: §2.3.1 · p. 25

2.3.2. Gaussian process regression

  • In GP regression, maximum-entropy sampling selects observed sites to maximize their joint entropy, but the resulting subset-selection problem is NP-hard and greedy predictive-variance selection can be far from optimal.The section also relates GP regression to function-space inverse problems and uses posterior predictive variance as a design quantity.Source: §2.3.2 · pp. 26–27
  • GP design also uses submodular mutual-information objectives and integrated predictive variance; greedy MI tends to work better than greedy entropy, while full-batch variance designs generally perform better than sequential batches.Integrated variance is also called IMSE, IMSPE, or IVAR, and is the trace of the posterior covariance operator.Source: §2.3.2 · pp. 27–28
  • Many GP design methods assume fixed covariance hyperparameters, although learning them can change predictive uncertainty and motivates designs that interleave hyperparameter learning with prediction.Fully Bayesian hyperparameter inference is computationally demanding, and the authors know of no method that completely realizes joint EIG-based design for the process and hyperparameters.Source: §2.3.2 · pp. 29–30
  • When GP hyperparameters are uncertain, sequential policies can use observed outcomes to update covariance parameters and adapt later designs; non-myopic policies can balance hyperparameter learning with prediction.The survey cites both myopic approaches using MCMC marginalization and a non-myopic approximation to sequential maximum-entropy sampling.Source: §2.3.2 · p. 30

2.4. Related problems and their distinctions

Several design and data-selection methods overlap with OED, but differ in what they optimize, when choices are made, or whether they use an explicit statistical model. The section distinguishes space-filling design, active learning, Bayesian optimization, and data summarization on these grounds.

Space-filling and other non-model based designs

  • Space-filling designs spread points across the design domain without exploiting a response model, while OED uses model-based criteria.Maximin and minimax distance are common objectives; Latin hypercube and related methods address projection properties.Source: §2.4 · p. 31
  • Space-filling criteria can maximize design-point entropy or minimize discrepancy, but these are not the maximum-entropy sampling criteria used in model-based design.The entropy here is that of the empirical distribution of points on the design domain.Source: §2.4 · p. 31
  • Factorial, blocking, fractional, and composite designs are additional standard strategies that do not rely on a statistical response model.The section frames these alongside other non-model-based design strategies.Source: §2.4 · p. 31

Active learning

  • Active learning selects data to label sequentially and often greedily, whereas OED can target parameter inference as well as prediction.Active-learning selection may use uncertainty sampling, committee disagreement, or expected reduction in predictive uncertainty; some methods rely on heuristics rather than explicit criteria.Source: §2.4 · pp. 32–33

Bayesian optimization

  • Bayesian optimization chooses sequential evaluation points to maximize a black-box objective, unlike OED designs that target learning or prediction.Its acquisition functions typically balance exploration and exploitation and are generally myopic.Source: §2.4 · p. 33

Data summarization

  • Coresets choose a small weighted subset after data are observed, whereas OED must choose a design before observing its outcomes.Coresets seek to preserve the likelihood or posterior of the realized full dataset.Source: §2.4 · p. 34

3. Numerical approximation of design criteria

Evaluating design criteria is a central computational challenge: information-theoretic objectives are flexible for complex nonlinear models but can be difficult to approximate, especially when model evaluations are costly or inaccessible.

3. Numerical approximation of design criteria

  • Information-theoretic design criteria can be challenging to evaluate even when parameter dimension is low.The section surveys nested Monte Carlo, tractable-family density approximations, and variational bounds as approaches to approximation.Source: §3 · p. 34
  • Closed-form expressions generally make standard alphabetic criteria for linear models easier to evaluate, though high- or infinite-dimensional parameters can make them costly.Dimension-reduction methods are discussed for that setting.Source: §3 · p. 34
  • Methods differ in whether they require likelihood evaluations, which may be unavailable in implicit-model settings.The section considers applicability across standard and implicit Bayesian models.Source: §3 · p. 34

3.1. Nested Monte Carlo estimators

Nested Monte Carlo estimates expected information gain by sampling from the joint prior and observations, then estimating the evidence within an inner loop. Its finite-budget bias, computational cost, and design-dependent errors motivate importance sampling, multilevel schemes, and other approximations.

3.1. Nested Monte Carlo estimators

  • Vanilla NMC estimates expected utility using prior-and-observation samples and estimates the evidence separately for each observation.It requires prior sampling, model sampling, and likelihood evaluation; finite-inner-sample estimates are biased, though asymptotically unbiased and consistent.Source: §3.1 · pp. 34–36
  • MSE decreases at the optimal NMC rate O(W^-2/3), slower than standard Monte Carlo, requiring O(ε^-3) work for MSE ε^2.The optimal inner-to-outer sample-size ratio scales as O(W^-1/3).Source: §3.1 · p. 36
  • Importance-sampling biasing distributions can reduce NMC bias and variance, but do not change its convergence rates.Laplace-based sampling can require gradients and Hessian approximations, and Gaussian biasing may be unstable for strongly non-Gaussian or heavy-tailed posteriors.Source: §3.1 · p. 37
  • Derivative-free multiple importance sampling reuses earlier inner-loop samples to tailor evidence estimation and can substantially reduce EIG-estimate bias and variance.Outer-loop samples are ordered from largest to smallest prior density to maximize information reuse.Source: §3.1 · p. 37
  • O(ε^-2) computational complexity achieves MSE ε^2 with multilevel Monte Carlo, improving on standard NMC’s O(ε^-3) complexity.Antithetic coupling reduces variance; importance sampling can further reduce error constants.Source: §3.1 · p. 38
  • Some faster EIG approximations are inconsistent, and their error can be large with few repeated trials or non-Gaussian posteriors.The approximation discussed by Long et al. has error bounded in probability by O(1/N_tr), with posterior concentration controlling integral-approximation error.Source: §3.1 · pp. 38–39
  • Surrogate forward models yield consistent estimates of an approximate EIG, while closeness of Gaussian-likelihood forward maps uniformly controls approximate-EIG error across designs.Surrogates can replace costly PDE or integral-equation solutions.Source: §3.1 · p. 39
  • Figure 3.1 shows vanilla NMC bias obscuring the true EIG maximum, while multiple importance sampling fares better without guaranteeing stable maxima at finite samples.The bias varies with design and is largest where posterior concentration is maximized, so EIG approximation must be coordinated with optimization.Source: §3.1 · pp. 39–40, Figure 3.1 · p. 40

3.2. Mutual information bounds via density approximations

This section bounds mutual information by approximating either the marginal observation density or the posterior density, then tightens the bounds through density estimation. Transport maps provide flexible approximations, including conditional-density representations useful in implicit and goal-oriented OED.

3.2. Mutual information bounds via density approximations

  • Approximating the marginal observation density yields an upper EIG bound, while approximating the posterior yields a lower bound.The expectations defining both bounds remain under the true joint distribution.Source: §3.2 · p. 41
  • Posterior-density lower bounds can apply to implicit models without likelihood evaluation, but approximating both prior and posterior marginals need not preserve a bound.The approach also bounds expected marginal information gain by estimating a marginal posterior.Source: §3.2 · pp. 41, 45, 46
  • Fitting the variational density family by tightening either bound is equivalent to maximum-likelihood density estimation.The chosen family may include simple Gaussian or uniform densities tailored to the design problem.Source: §3.2 · p. 42
  • Transport-based density estimation learns invertible maps that transform target distributions to tractable reference distributions.Normalizing flows are one parameterization; monotone triangular maps and other representations are also described.Source: §3.2 · pp. 42–43
  • Block-triangular transport components can represent the observation marginal and posterior separately, enabling the density needed for a chosen bound to be learned on its own.The reference distribution is product-factorized, and the map components capture the evidence and posterior, respectively.Source: §3.2 · pp. 43–44
  • Figure 3.2 shows variational upper and lower EIG bounds sandwiching the true EIG as sample size increases.The plotted estimates use separate batches for map learning and outer-expectation estimation.Source: §3.2 · p. 44, Figure 3.2 · p. 45
  • Goal-oriented OED can use density estimation when the joint distribution of quantities of interest and observations can be simulated, even if the relevant density ratios are unavailable.The passage describes using two block-triangular maps for the density approximations.Source: §3.2 · p. 46
  • Transport-map approximations can also be constructed directly from unnormalized joint-density evaluations rather than by tightening a variational bound.The resulting map-approximation error in EIG can still be analyzed.Source: §3.2 · p. 46

3.3. More general variational bounds for mutual information

Section 3.3 surveys variational and multi-sample approaches to bounding mutual information, highlighting their differing tightness, variance, and likelihood requirements. It also discusses estimating these bounds and optimizing them alongside experimental designs.

3.3. More general variational bounds for mutual information

  • More general variational bounds extend beyond density and invertible-transport approximations to broader function classes for mutual information.The section also recalls k-nearest-neighbor estimation, which is known to scale poorly with dimension, and entropy-based lower bounds.Source: §3.3 · p. 47, §3.3.1 · p. 47

3.3.1. Variational lower bounds and approximate density ratios

  • TUBA approximates the posterior-to-prior density ratio, and its lower bound is tightened by maximizing over the critic f and function a.The critic and a may depend on the design; Monte Carlo can estimate bounds and their gradients, while neural-network estimator properties remain incompletely understood.Source: §3.3.1 · p. 48
  • Variational-bound estimators can have high variance, and finite-sample MINE estimation yields a positively biased estimate whose mean is neither an upper nor lower bound on mutual information.The nested expectation in MINE leads in practice to nested Monte Carlo estimation with finite-inner-loop bias.Source: §3.3.1 · p. 49

3.3.2. Multi-sample lower bounds

  • PCE and InfoNCE are multi-sample mutual-information lower bounds, but their values cannot exceed log M, so they cannot be tight when mutual information exceeds log M.PCE becomes tight as M grows; ACE is tight at finite M when its biasing distribution is the posterior, and otherwise becomes tight as M grows.Source: §3.3.2 · p. 50
  • Reusing each sample pair in turn as the data-generating sample yields an InfoNCE estimator whose expectation is a lower bound and is also capped by log M.With a tractable likelihood, the optimal critic can be the log-likelihood; the resulting sample-reuse estimator can reduce expensive model evaluations from O(NM) to O(M) in the stated cost setting.Source: §3.3.2 · p. 51

3.3.3. Deploying variational bounds

  • Deploying variational bounds uses gradient estimates to optimize variational parameters and the design together, while the relative merits of different bounds remain under study.Multi-sample bounds generally have lower Monte Carlo variance than TUBA, NWJ, and DV, but finite contrastive sample sizes limit tightness at high mutual information.Source: §3.3.3 · p. 52

3.4. Low-dimensional structure

Section 3.4 uses low-dimensional structure to reduce the cost of mutual-information approximations, through parameter and data subspaces. It develops spectral methods for linear-Gaussian models and diagnostic-matrix bounds for nonlinear models, with different guarantees and limitations.

3.4.1. Linear models

  • In linear-Gaussian models, mutual information can be approximated from leading generalized eigenvalues, whose decay indicates intrinsic dimension and supports optimal low-dimensional projections of parameters, data, or both.The parameter-space and data-space spectral structures are dual in this setting.Source: §3.4.1 · pp. 53–55
  • The equivalence among projected models and the strict duality between parameter and observation reduction are specific to the linear-Gaussian setting.Source: §3.4.1 · p. 56
  • Goal-oriented linear reduction targets information about Z=A^TΘ; its generalized eigenvalues can decay faster than the parameter-inference spectrum, enabling more efficient approximation.The resulting eigenproblems balance the forward operator, noise and prior covariances, and the prediction goal.Source: §3.4.1 · pp. 56–57

3.4.2. Nonlinear models

  • Nonlinear projection-error bounds require a subspace logarithmic Sobolev inequality and are generally not tight; their eigenvalue-tail sums differ from exact log(1+λ_i) truncation errors.The stated sufficient conditions include convex support and a log-density that is a bounded perturbation of a strongly convex function; distributions with exponential tails are excluded.Source: §3.4.2 · pp. 58–60
  • For nonlinear models, dominant eigenspaces of diagnostic matrices guide parameter and data projections, after which existing methods can estimate or bound projected mutual information.The projected mutual information is no greater than the full mutual information; fast diagnostic-eigenvalue decay gives more opportunity for dimension reduction with controlled error.Source: §3.4.2 · pp. 58–59

4. Design optimization methods

This section surveys OED optimization methods for discrete selection and real-valued exact designs, including how design structure and objective properties shape available methods and guarantees. For real-valued designs, it covers Monte Carlo expected-utility estimation and its effects on method choice, alongside derivative-free and gradient-based approaches, unbiased EIG gradient estimators, and methods for tightening EIG bounds during optimization.

4.1.1. Local search and exchange algorithms

  • Local-search exchange methods improve exact linear designs by replacing selected points; Fedorov’s method has approximation guarantees, with performance depending on design criteria and conditions.Madan et al. (2019) show asymptotic optimality when n/p is large, but A-optimality can have arbitrarily bad local optima; Lau and Zhou (2022) give further guarantees, including for A-optimality when a near-optimal solution has a well-conditioned design matrix.Source: §4.1.1 · pp. 61–62

4.1.2. Continuous convex relaxation approaches

  • Convex relaxations replace the intractable integer linear-design problem with a convex program, then round its fractional solution to an integer design.Constraints can encode cardinality, selection without replacement, and costs; rounding algorithms provide approximate D-, A-, and E-optimal designs, with methods also addressing knapsack, partition, and matroid constraints.Source: §4.1.2 · pp. 62–63

4.1.3. Sequential algorithms for finding optimal designs

  • Sequential forward-addition and backward-deletion procedures use greedy choices to build or reduce linear designs, but their guarantees can depend on the initialization.Running the procedure from multiple initial designs can mitigate this dependence; resulting designs may also be improved with non-sequential methods.Source: §4.1.3 · p. 63

4.2.1. Background

  • Set-function optimization captures discrete OED objectives, with submodularity expressing diminishing returns and curvature and ratio measures characterizing deviations from modularity.The section uses these properties to analyze algorithms for design criteria, including nonlinear designs.Source: §4.2 · p. 64, §4.2.1 · pp. 64–65

4.2.2. Set function attributes of design criteria

  • The log-determinant D-optimality criterion is submodular, whereas A-optimality is generally not; mutual information is submodular under conditionally independent observations, even for non-Gaussian distributions.With correlated noise in Bayesian inverse problems, the information objective is non-submodular; for linear inverse problems, its deviation can be bounded using submodularity and supermodularity ratios.Source: §4.2.2 · pp. 65–66

4.2.3. Greedy algorithms for cardinality-constrained designs

  • For monotone, non-negative submodular objectives with a cardinality constraint, greedy selection achieves a 1 − 1/e approximation guarantee.Curvature and submodularity-ratio bounds refine guarantees for broader objectives; stochastic greedy achieves an expected (1 − 1/e − ε) guarantee with function evaluations independent of the cardinality constraint.Source: §4.2.3 · pp. 66–67

4.2.4. Beyond greedy: algorithms for more general design problems

  • For cost-constrained submodular design, standard or cost-benefit greedy achieves at least (1 − 1/e)/2 of optimum, while richer constraints and non-monotone objectives require other methods.A more involved enumeration method achieves 1 − 1/e for knapsack constraints; multilinear extensions support continuous optimization followed by rounding for broader constraint classes.Source: §4.2.4 · pp. 67–68

4.3. Optimizing real-valued design variables

  • For exact designs with a prescribed number of experiments, real-valued coordinates such as sensor locations or measurement times enable continuous optimization, avoiding discretizations whose candidate count grows exponentially with design dimension.The design is parameterized by the coordinates of its support points, making gradients with respect to the design straightforward to define.Source: §4.3 · pp. 68–69
  • Expected utility is often estimated by Monte Carlo, and optimizing the estimator’s expectation assumes it is unbiased or its bias is acceptably small.When that assumption fails, as with EIG estimators, the estimated objective can depart from the true design objective.Source: §4.3 · pp. 69–70

4.3.1. Derivative-free methods

  • SPSA estimates a gradient with two objective realizations per iteration, independent of design dimension, while Kiefer–Wolfowitz requires 2D evaluations.Other derivative-free options include Bayesian optimization for moderately dimensional, expensive noisy objectives, local model-based methods with convergence guarantees, and direct search methods.Source: §4.3.1 · pp. 70–72

4.3.2. Gradient-based methods

  • Reparameterization can yield unbiased gradient estimates for Robbins–Monro, which converges under suitable conditions, while sample-average approximation fixes randomness to create a deterministic optimization problem.Robbins–Monro converges almost surely to a global optimum for convex problems or to a first-order critical set in certain non-convex problems; sample-average approximation can use standard deterministic algorithms.Source: §4.3.2 · pp. 73–74

4.3.3. Unbiased EIG gradient estimators

  • For EIG, Goda et al. (2022) use random truncation to obtain an unbiased nested-Monte-Carlo gradient, while Ao and Li (2024) obtain an unbiased estimator with exact inner posterior samples.Finite-length MCMC chains introduce bias in Ao and Li’s estimator, but the authors demonstrate empirically that it can be made negligible.Source: §4.3.3 · pp. 74–75

4.3.4. Simultaneous bound tightening and design optimization

  • Simultaneously maximizing a variational EIG lower bound over its parameters and the design tightens the bound while seeking a design that maximizes true EIG.Zheng et al. (2020) adaptively refine lower and upper EIG bounds by increasing inner-loop sample size, achieving regret-style guarantees.Source: §4.3.4 · pp. 75–76

5. Sequential optimal experimental design

Sequential OED plans experiments in sequence, using earlier outcomes to inform later designs. Its policy-based formulation combines feedback with lookahead across the remaining experiments, unlike greedy procedures or static batch designs.

5. Sequential optimal experimental design

  • Greedy design selects the next experiment without looking ahead, while batch design coordinates experiments without adapting to new observations.Greedy procedures are simple and flexible when the total number of experiments is unknown.Source: §5 · p. 76
  • Sequential OED chooses each design with all remaining experiments in view and uses policies to adapt designs to the current information state.The formulation generalizes both greedy and batch design.Source: §5 · p. 77
  • Fully Bayesian sequential OED remains challenging to solve generally, and prior advances often focus on discrete settings or omit Bayesian information-theoretic criteria.The survey highlights dynamic programming, reinforcement learning, and information bounds as recent approaches.Source: §5 · p. 77

5.1. Background

  • The background formulation assumes a known, fixed number of experiments, updates the posterior after each outcome, and allows experiment types and dimensions to vary.The likelihood may depend on the history of earlier designs and observations, though conditional independence can simplify it.Source: §5.1 · pp. 77–78

5.2. Formulation as a Markov decision process

The section formulates sequential experimental design as a finite-horizon Markov decision process. Its state supports adaptive choices, while transitions encode Bayesian updating and rewards encode the value of experiments.

5.2. Formulation as a Markov decision process

  • The MDP state combines a belief about uncertain parameters with any relevant physical state, preserving information needed for future design decisions.The belief state is the posterior given prior designs and observations; physical state can track relevant history-dependent features.Source: §5.2 · pp. 78–79
  • A policy maps the current state at each stage to a design, and the policy function may differ across experiments in a finite sequence.The formulation focuses on deterministic policies, though stochastic policies are also possible.Source: §5.2 · p. 79
  • After an experiment, transition dynamics update the state using its design and observed outcome, typically through Bayesian inference.The transition kernel is generally intractable to evaluate directly but can be simulated from the prior predictive distribution.Source: §5.2 · p. 79
  • Figure 5.1 traces the sequence from initial state through policy-selected designs, observations, state updates, and a terminal reward.It distinguishes the reward after each experiment from the reward after the final state is reached.Source: Figure 5.1 · p. 80
  • Immediate rewards can represent experimental cost or information gain, while terminal rewards capture value assessed after all experiments.The reward functions can use the range of optimal-design utilities discussed earlier.Source: §5.2 · p. 80

5.3. Problem statement

The problem statement seeks a policy that maximizes expected utility over a finite sequence of experiments, subject to design and state-transition constraints. The formulation is computationally demanding because each transition embeds Bayesian inference.

5.3. Problem statement

  • Sequential OED seeks a design policy that maximizes expected utility subject to valid design choices and state transitions at each stage.The policy selects designs from the stage-specific action spaces, and the next state follows the transition function.Source: §5.3 · p. 80
  • Expected utility is the MDP expected return, with an optional discount factor reducing the weight of rewards from later stages.An expectation over the initial state can also be used if that state is unknown.Source: §5.3 · pp. 80–81
  • Solving the problem can be costly because each transition embeds Bayesian inference, especially with nonlinear, non-Gaussian models and computationally intensive likelihoods.The formulation has finite horizon and continuous action and observation spaces.Source: §5.3 · p. 81

5.4. Solution approaches

This section surveys computational approaches for constructing sequential OED policies, including value-function and policy-gradient methods that combine planning with adaptation, and information-bound methods for maximizing expected information gain, including for implicit models. It also covers alternative reward formulations and their computational tradeoffs.

5.4. Solution approaches

  • Terminal and incremental reward formulations yield equal expected utility for any policy, while terminal rewards require fewer KL calculations but delay feedback.Incremental rewards can include terms such as design costs without changing their correspondence to total expected information gain; greedy design requires more intermediate posterior and KL calculations than the sOED terminal formulation.Source: §5.4 · pp. 82–83

5.4.1. Approximate dynamic programming (ADP-sOED)

  • ADP-sOED approximates optimal V-functions satisfying Bellman equations, but is computationally expensive because evaluating its implicit policy requires stochastic optimization.It uses approximate value iteration with posterior representations such as adaptive grids or triangular transport maps, and can refine trajectory samples during training.Source: §5.4.1 · pp. 83, 85

5.4.2. Actor-critic policy gradient (PG-sOED)

  • PG-sOED explicitly parameterizes the policy and learns it with an actor-critic gradient method that avoids likelihood or simulator gradients with respect to designs.Its information-based rewards are computed by numerical quadrature, which is practical only for low-dimensional parameters (e.g., p ≤ 4).Source: §5.4.2 · pp. 85, 87
  • Both ADP-sOED and PG-sOED reach the benchmark’s optimal design set, with utilities near the analytic optimum.The reported values are U(π* ADP) ≈ 0.775, U(π* PG) ≈ 0.775, and U(π*) ≈ 0.783.Source: Figure 5.3 · p. 89, §5.4.2 · p. 89
  • PG-sOED is orders of magnitude faster than ADP-sOED, especially at testing, because it evaluates the explicit policy with one network pass rather than stochastic optimization.The timing comparison is for the linear-Gaussian benchmark; ADP-sOED’s policy is implicit in its value functions, whereas PG-sOED’s policy is explicit.Source: §5.4.2 · p. 89, Table 5.1 · p. 90
  • PG-sOED achieved the highest expected reward, U(𝜋PG) ≈ 3.435 versus greedy’s U(𝜋∗greedy) ≈ 3.057, combining planning ahead with adaptation to new measurements.The expected rewards were assessed over 104 trajectories; batch design can plan ahead but cannot adapt to new measurements, while greedy design tends to chase the latest source-location estimate.Source: §5.4.2 · p. 90, Figure 5.6 · p. 92

5.4.3. Methods that leverage information bounds

  • DAD uses a sequential prior contrastive estimator (sPCE) to lower-bound EIG and optimize a DNN-based policy offline.Including the data-generating parameter in the evidence estimate makes the bound tight as M→∞; Monte Carlo sampling produces a negatively biased estimator.Source: §5.4.3 · pp. 91, 93
  • Blau et al. (2022) combine the sPCE bound with randomized ensembled double Q-learning to learn stochastic policies for discrete design spaces.Source: §5.4.3 · p. 93
  • iDAD uses critic-based likelihood-free lower bounds to optimize a policy and EIG bound jointly, but requires simulator derivatives with respect to current and previous designs and outcomes.Its bounds can be tight with an optimal critic and as M→∞.Source: §5.4.3 · p. 94
  • vsOED generalizes sequential design objectives to multiple models, nuisance parameters, predictive quantities of interest, and implicit likelihoods (Shen et al., 2023).Its one-point rewards preserve expected utility for any policy, while variational approximations make the resulting objective a lower bound on EIG.Source: §5.4.3 · pp. 95–97
  • vsOED optimizes its variational lower bound with an actor-critic approach and, unlike DAD and iDAD, requires neither explicit likelihoods nor gradients of the likelihood or simulator.The Q-network enables this gradient-free access to the likelihood or simulator derivatives.Source: §5.4.3 · p. 97

5.5. Open questions in sequential optimal design

Sequential OED still needs more scalable state representations, stronger computational methods, and better foundations for approximating policies and value functions. The section also calls for richer sequential formulations and ways to weigh their benefits against computational costs.

State representations

  • Tracking the information sequence I_k grows linearly with completed experiments, while zero-padding variable-length inputs becomes less efficient as the design horizon increases.I_k also carries information beyond what is needed for Bayesian updating because multiple sequences can yield the same posterior.Source: §5.5 · pp. 97–98

Scalable methods

  • Sequential OED needs more scalable methods for computationally intensive models, high-dimensional parameters and data, and complex design objectives.Current demonstrations remain confined to relatively simple formulations and models.Source: §5.5 · pp. 98–99

Approximation theory

  • Little is known about optimal-policy and value-function properties beyond simple cases, limiting understanding of approximation error and performance guarantees.The section calls for numerical analysis, approximation theory, and stronger convergence guarantees for Bayesian sequential-design reinforcement learning.Source: §5.5 · p. 99

Sequential formulations

  • Further work should explore optimal stopping, interleaved batch and sequential designs, and policies robust to changes in the design horizon.Source: §5.5 · p. 99

Choosing a strategy

  • Because sequential OED is generally more computationally demanding than batch or greedy designs, the section advocates estimating feedback and lookahead benefits before solving the problem.Those potential benefits should be balanced against computational costs.Source: §5.5 · p. 99

6. Outlook

The outlook identifies open questions spanning OED criteria, computation, optimization, and sequential design. It also highlights model misspecification, risk-aware criteria, and practical issues in applying and validating designs.

6. Outlook

  • OED research continues on expressive design criteria, efficient criterion estimation, optimization guarantees, and sequential-design formulations and algorithms.Source: §6 · pp. 99–100

6.1. Model misspecification

  • OED depends on statistical models that may fail to capture the actual data-generating distribution; one response is to augment noise models or add nuisance parameters.The article describes these as partial solutions when a better model can be constructed.Source: §6.1 · p. 100
  • Robust OED remains an open area, including robustness to likelihoods and forward operators, choices of ambiguity-set radius, and settings where a better model is infeasible.Source: §6.1 · pp. 101–102

6.2. Risk-aware design criteria

  • Risk-aware OED extends beyond expected utility to characterize or control low-utility outcomes; explored approaches include variance-penalized expected utility for nonlinear OED.The article also describes demonstrations of this approach in sequential OED.Source: §6.2 · pp. 103–104
  • R-optimality minimizes the CVaR of predictive variance across inputs, targeting the upper tail rather than only worst-case or average variance.The criterion has a computable gradient or subgradient to facilitate design optimization.Source: §6.2 · pp. 104–105

6.3. OED in practice

  • Practical OED models can include experiment failure and discrepancies between intended and realized designs as components of the statistical model or utility.Source: §6.3 · p. 105
  • Sequential plans may be disrupted by changing environments, shortened horizons, shifting feasible designs, or altered experiment timing; validation also remains challenging.Simulation-based checks reveal internal inconsistencies, while external validation faces the inability to sample from the prior in real experiments.Source: §6.3 · pp. 105–106
  • Encoding real-world constraints, suitable priors, and expert knowledge in OED formulations may improve practitioners’ trust and encourage adoption.Source: §6.3 · pp. 106–107
Loading 2407.16212v2…