PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient-based stochastic optimization methods in Bayesian experimental design

Xun Huan, Youssef M. Marzouk

arXiv:1212.2228v3stat.COmath.OCstat.ME

TL;DR

Continuous nonlinear Bayesian design seeks experiments that maximize expected information gain, but evaluating that objective can require costly Monte Carlo calculations and gradients. The paper combines polynomial surrogates and infinitesimal perturbation analysis with Robbins-Monro and SAA-BFGS, then compares them for PDE-based sensor placement. Results indicate that sample sizes and their allocation affect solution quality and efficiency, while RM’s frequent, cheaper steps offer finer control over termination time.

  • Problem

    Expected information gain for nonlinear Bayesian design is estimated by Monte Carlo, while computationally intensive forward models and unavailable gradient information complicate optimization.

    Source: §2.3 · p. 7, §3.1 · p. 8

  • Method

    The paper combines polynomial-chaos forward-model surrogates and infinitesimal perturbation analysis with Robbins-Monro and SAA-BFGS optimization.

    Source: §1 · p. 2, §6 · p. 17

  • Results

    Larger sample sizes improved solution quality and could reduce iterations, balanced inner- and outer-loop sampling mattered for computational efficiency, and RM’s cheaper frequent steps provided finer runtime resolution than SAA.

    Source: §6 · p. 18

  • Takeaways & Limitations

    Sample-size allocation and the relative cost of objective evaluations inform algorithm choice, with RM potentially more attractive when evaluations are expensive.

    Source: §6 · p. 18

    Model error is outside this study’s scope, and its impact on optimal experimental design remains future work.

    Source: §5.2.2 · p. 14

Abstract

from arXiv · show

Optimal experimental design (OED) seeks experiments expected to yield the most useful data for some purpose. In practical circumstances where experiments are time-consuming or resource-intensive, OED can yield enormous savings. We pursue OED for nonlinear systems from a Bayesian perspective, with the goal of choosing experiments that are optimal for parameter inference. Our objective in this context is the expected information gain in model parameters, which in general can only be estimated using Monte Carlo methods. Maximizing this objective thus becomes a stochastic optimization problem. This paper develops gradient-based stochastic optimization methods for the design of experiments on a continuous parameter space. Given a Monte Carlo estimator of expected information gain, we use infinitesimal perturbation analysis to derive gradients of this estimator. We are then able to formulate two gradient-based stochastic optimization approaches: (i) Robbins-Monro stochastic approximation, and (ii) sample average approximation combined with a deterministic quasi-Newton method. A polynomial chaos approximation of the forward model accelerates objective and gradient evaluations in both cases. We discuss the implementation of these optimization methods, then conduct an empirical comparison of their performance. To demonstrate design in a nonlinear setting with partial differential equation forward models, we use the problem of sensor placement for source inversion. Numerical results yield useful guidelines on the choice of algorithm and sample sizes, assess the impact of estimator bias, and quantify tradeoffs of computational cost versus solution quality and robustness.

1 Introduction

The paper formulates continuous nonlinear Bayesian experimental design as stochastic optimization because expected information gain generally requires Monte Carlo estimation. It derives gradient-based methods and compares them for PDE-based sensor placement, examining bias, sample sizes, cost, solution quality, and robustness.

1 Introduction

  • Expected information gain for continuous Bayesian parameter inference generally requires Monte Carlo estimation, making design a stochastic optimization problem.The objective is also the mutual information between parameters and observables conditioned on the design.Source: §1 · p. 2
  • Infinitesimal perturbation analysis derives gradients for Robbins-Monro, while sample average approximation uses a deterministic quasi-Newton method; polynomial surrogates accelerate evaluations.The comparison uses sensor placement for source inversion with a PDE forward model.Source: §1 · p. 2
  • The study assesses estimator bias and offers guidance on algorithm and sample-size choices while quantifying computational-cost tradeoffs against solution quality and robustness.These are the stated aims of the numerical comparison, not a claim that one algorithm is universally superior.Source: §1 · p. 2
  • Numerical testing of SAA in general optimization settings was largely unexplored, motivating its assessment alongside stochastic approximation for nonlinear continuous Bayesian design.The authors aim to illustrate algorithm differences and provide selection guidelines, not identify a universally superior approach.Source: §1 · p. 3

2 Optimal Bayesian Experimental Design

The section defines Bayesian experimental design through expected information gain and formulates its optimization using Monte Carlo estimates. It presents Robbins-Monro and sample-average methods, then describes how surrogate models and gradient estimators support their use in design.

2.1 Background

  • Expected information gain is the prior-predictive expectation of posterior-to-prior KL divergence, measuring information about parameters from observations at a design.The objective is equivalent to mutual information between parameters and observables conditioned on the design; the paper considers batch, open-loop designs rather than sequential designs.Source: §2.1 · pp. 3–4
  • Because expected utility generally lacks a closed form, nested Monte Carlo estimation makes the design objective stochastic; finite inner sample size M introduces bias.The estimator is asymptotically unbiased, with leading-order bias C(d)/M.Source: §2.1 · p. 4

2.2.1 Robbins-Monro (RM) stochastic approximation

  • Robbins-Monro updates the design using an unbiased stochastic gradient estimate and a gain sequence; the paper uses harmonic steps a_k = β/k.Performance can be sensitive to step-size choice, and this study uses the harmonic sequence for simplicity.Source: §2.2.1 · p. 5

2.2.2 Sample average approximation (SAA)

  • SAA fixes common noise realizations across designs, turning the Monte Carlo objective into a deterministic problem solved here with BFGS.BFGS updates an inverse-Hessian approximation from objective and gradient evaluations; independent replicate runs can characterize variation in solutions.Source: §2.2.2 · pp. 6–7

2.3 Application to optimal design

  • Polynomial surrogates enable tractable objective evaluation and analytical finite-sample gradients for SAA, while infinitesimal perturbation analysis supplies an unbiased gradient estimator for RM.These address the lack of readily available gradient information for the Bayesian design objective.Source: §2.3 · pp. 7–8

3 Polynomial chaos surrogates

Polynomial chaos surrogates address the cost of repeated forward-model evaluations in Bayesian design. The paper constructs expansions over uncertain parameters and design variables, then uses polynomial approximations to accelerate information-gain and gradient calculations.

3.1 Background

  • Repeated forward-model evaluations make Monte Carlo estimation of expected information gain costly, motivating a cheaper surrogate accurate across parameter and design domains.The forward model maps parameters and design variables into data space, and may be evaluated both to sample the likelihood and to evaluate its density.Source: §3.1 · p. 8
  • Polynomial chaos exploits regularity in model outputs and can replace the forward model without reducing its internal physics.The paper uses polynomial expansions to mitigate repeated evaluation costs and later to help compute gradient information.Source: §3.1 · pp. 8–9

3.2 Formulation

  • The expansion is truncated to finite stochastic dimension and polynomial terms; total-order truncation retains terms with |i| ≤ p.Other truncations can retain different numbers of cross terms or account for anisotropy.Source: §3.2 · p. 9
  • A single polynomial chaos expansion jointly represents dependence on parameters and design variables, avoiding construction of a new expansion at every design.Design coordinates are mapped affinely to uniform variables, yielding Legendre polynomial bases and a uniform weight over the design domain.Source: §3.2 · p. 9
  • The paper uses nonintrusive projection to compute polynomial coefficients, reusing the deterministic solver as a black box, and Smolyak sparse quadrature to evaluate projection numerators.The quadrature construction must guard against aliasing; adaptive constituent tensor approximations can exploit weak coupling and anisotropy.Source: §3.2 · p. 10
  • Substituting the polynomial approximation into the likelihood enables fast evaluation of expected information gain.The section then uses the polynomial form to support gradient computation.Source: §3.2 · p. 10

4 Infinitesimal Perturbation Analysis

Infinitesimal perturbation analysis is used to obtain gradient information for stochastic optimization of expected information gain. Because the finite-sample estimator is biased for the original objective, the paper instead targets a consistent objective for which that estimator is unbiased.

4 Infinitesimal Perturbation Analysis

  • IPA obtains an unbiased gradient estimator by differentiating an unbiased function estimator when regularity conditions permit interchanging differentiation and integration.The stated conditions include continuity and differentiability over the design and random-variable spaces, and noise independent of the design.Source: §4 · pp. 10–11
  • The finite-M estimator is biased for the true expected information gain, so the paper optimizes an alternative objective for which the estimator is unbiased and that converges to the true objective as M increases.The convergence holds for any N > 0.Source: §4 · pp. 10–11
  • For additive Gaussian observation noise, extracting design-independent standard normal noise preserves the expectation form needed for the gradient construction.The observations are generated by scaling the standard normal samples by C and adding them to the model output.Source: §4 · pp. 11–12
  • The same gradient form serves RM and SAA, but RM resamples parameters and noise at each iteration whereas SAA freezes them throughout optimization.With a polynomial forward-model expansion, the required design derivatives can be computed inexpensively.Source: §4 · p. 12

5 Source Inversion Problem

The source-inversion example places a single sensor to infer a contaminant source and compares RM with SAA-BFGS for maximizing expected information gain. In this setting, corners are optimal on average, and RM achieves smaller MSE per computational effort, although its advantage is relatively small.

5.1 Governing equations

  • The study places one sensor in the square domain to infer a source location from five noisy concentration readings, optimizing information gain averaged over source and data uncertainty.The source location has a uniform prior, and the sensor can be placed anywhere in the domain.Source: §5.1 · pp. 12–13

5.2.1 Objective function

  • Increasing M raises finite-sample objective estimates and makes the objective less flat; isotropic diffusion makes corners optimal and the center worst under this domain and noise setting.The authors attribute the corner result to minimizing the average area of posterior annuli around the sensor.Source: §5.2.1 · pp. 13–14

5.2.2 Stochastic optimization results

  • Model error is not treated in this study, which uses a polynomial-chaos surrogate built from a coarser PDE discretization than the one used to simulate data.The authors identify the impact of model error on optimal design as future work.Source: §5.2.2 · p. 14
  • Each SAA sample set creates a different deterministic objective, which can differ sharply from the underlying objective at low N, though many sampled subproblems can still yield reasonably good results.The SAA realizations in this example need not have the underlying objective's symmetry or corner maxima.Source: §5.2.2 · p. 15
  • At N=101, M=2, results are worse than at N=11, M=1001; increasing N and M generally raises mean information gain and lowers its variance, so balanced sampling matters.The variance retains a floor from the high-quality estimator.Source: §5.2.2 · pp. 15, 17
  • Optimality-gap estimates can indicate solution quality for fixed M, but are unsuitable for comparisons across M because each value yields a differently biased objective surface.In the example, solution quality improves with M even as gap estimates appear looser and noisier.Source: §5.2.2 · p. 16
  • SAA-BFGS often finishes in fewer iterations, but each iteration costs more; RM offers finer run-time stopping and is more attractive when objective evaluation is expensive.Increasing sample sizes reduces iteration counts, so added sample cost can grow sublinearly with computational time.Source: §5.2.2 · pp. 16–17
  • RM consistently achieves smaller MSE than SAA-BFGS for a given computational effort, though its advantage is relatively small and may reverse with other algorithm choices or design problems.The authors caution against generalizing this comparison beyond these numerical experiments.Source: §5.2.2 · p. 17

6 Conclusions

The paper uses polynomial chaos surrogates and perturbation analysis to obtain gradient information for stochastic optimization of expected information gain, then compares Robbins–Monro and SAA-BFGS. In source-inversion sensor placement, results favor balanced Monte Carlo resources and suggest an RM advantage, while remaining problem-dependent.

6 Conclusions

  • Polynomial chaos approximates the forward model so the nested Monte Carlo objective is tractable and its gradient can be extracted analytically with perturbation analysis.The approximation introduces additional error relative to the original forward model.Source: §6 · pp. 17–18
  • RM showed a consistent performance advantage over SAA-BFGS in the source-inversion study, but the authors caution that this conclusion is problem-dependent.The broader goal is to illustrate algorithm differences and provide selection guidelines, rather than declare one algorithm universally superior.Source: §6 · p. 18
  • Solution quality improved with larger sample sizes, while balancing inner- and outer-loop resources mattered; increasing inner samples alone helped little when outer samples were too few.Larger sample sizes could also yield convergence in fewer iterations.Source: §6 · p. 18
  • SAA can pair with different deterministic optimizers, whereas stochastic approximation specifies each iteration; BFGS suits smooth objective surfaces, while gradient-free methods may suit nonsmooth ones or unavailable gradients.Replicate SAA solutions can inform adaptive outer-loop sample sizing, but optimality-gap estimates are unsuitable for inner-loop sizing because of bias.Source: §6 · p. 18
  • RM's stochastic-gradient steps can perform poorly with high-variance estimates, but increasing outer-loop samples reduced variance in this study.Its frequent, cheaper steps provide finer run-time resolution and more flexibility to stop with little progress lost since the previous iteration.Source: §6 · p. 18
  • The study uses a global polynomial chaos surrogate over parameter and design spaces; local surrogates might improve accuracy, but stochastic-solution sampling error limits potential gains.The authors present local-surrogate exploration as a possible direction, not a demonstrated improvement.Source: §6 · p. 18
  • The work addresses batch or open-loop design, where experiment parameters are chosen before data collection; rigorous sequential or closed-loop design remains future work.Polynomial chaos evaluations can also become expensive at high stochastic dimension and polynomial order, though they remain much cheaper than the original model.Source: §6 · p. 18

8 Figures and Tables

The figures visualize the sensor-placement model, objective and posterior surfaces, and optimization paths; the tables and runtime plot summarize final designs, optimality gaps, iteration counts, and error-versus-time tradeoffs.

Figure 1

  • Figure 1 pairs a modeled concentration trace at the sensor with five noisy measurements for one specified source and sensor configuration.The trace uses source location (0.1, 0.1), strength 2.0, width 0.05, shutoff time 0.3, and sensor location (0.0, 0.0).Source: Figure 1 · p. 20

Figure 2

  • Figure 2 plots independent objective-estimator realizations across the design space; vertical-axis ranges and color scales differ among subfigures.Source: Figure 2 · p. 21

Figure 3

  • Figure 3 compares posterior source-location densities for different sensor placements against the true source location (0.09, 0.22).Source: Figure 3 · p. 22

Figures 4–6

Figures 7–9

Tables 1–2

  • Table 1 charts final search-position histograms from 1,000 independent RM and SAA runs, while Table 2 charts their high-quality expected-information-gain estimates.Table 1 varies N and M; Table 2 evaluates final sensor positions with the estimate using M = 1001 and N = 1001.Source: Table 1 · p. 29, Table 2 · p. 30

Tables 3–4

  • Table 3 presents SAA-BFGS optimality-gap histograms across sample sizes, and Table 4 presents RM and SAA-BFGS iteration-count histograms.Source: Table 3 · p. 31, Table 4 · p. 32

Figure 10

  • Figure 10 plots mean square error against average run time across algorithms and inner- and outer-loop sample sizes, highlighting each method’s optimal front.Source: Figure 10 · p. 33

Appendix: Analytical Derivation of the Unbiased Gradient Estimator

The appendix derives the estimator’s design gradient by differentiating the polynomial-chaos representation and likelihood. It gives the assumptions and recurrence-based derivative evaluation used in that derivation.

Loading 1212.2228v3…