PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs

Takashi Goda, Tomohiko Hironaka, Wataru Kitade, Adam Foster

arXiv:2005.08414v3stat.COcs.NAmath.NAstat.ML

TL;DR

Bayesian experimental design requires maximizing expected information gain, whose nested expectation is computationally challenging. The paper combines stochastic gradient optimization with an unbiased antithetic MLMC gradient estimator, and reports convergence in simple and pharmacokinetic experiments.

  • Problem

    Bayesian design requires maximizing expected information gain, but its nested expectation makes standard Monte Carlo cost O(ε^-3) for RMS accuracy ε.

    Source: §1 · p. 2

  • Method

    The authors combine stochastic gradient optimization with an unbiased antithetic MLMC estimator of the expected-information-gain gradient.

    Source: §1 · p. 3, §5 · p. 19

  • Results

    In the simple test, ξt converges to ξ* with mean squared error approximately t^-1.12; in the pharmacokinetic model, MLMC's average converged expected information gain is 4.544.

    Source: §4.1 · p. 14, §4.2 · p. 18

  • Takeaways & Limitations

    Under stated conditions, the estimator has finite expected squared ℓ2-norm and computational cost, supporting stochastic optimization without estimator bias.

    Source: §5 · p. 19

    The choice of MLMC level probabilities remains open; the pharmacokinetic experiments provide no evidence that the expected squared norm converges for the chosen probabilities.

    Source: §4.2 · p. 18

Abstract

from arXiv · show

In this paper we propose an efficient stochastic optimization algorithm to search for Bayesian experimental designs such that the expected information gain is maximized. The gradient of the expected information gain with respect to experimental design parameters is given by a nested expectation, for which the standard Monte Carlo method using a fixed number of inner samples yields a biased estimator. In this paper, applying the idea of randomized multilevel Monte Carlo (MLMC) methods, we introduce an unbiased Monte Carlo estimator for the gradient of the expected information gain with finite expected squared $\ell_2$-norm and finite expected computational cost per sample. Our unbiased estimator can be combined well with stochastic gradient descent algorithms, which results in our proposal of an optimization algorithm to search for an optimal Bayesian experimental design. Numerical experiments confirm that our proposed algorithm works well not only for a simple test problem but also for a more realistic pharmacokinetic problem.

1. Introduction.

Bayesian experimental design seeks setups that maximize information about hidden variables, but its expected information gain involves a computationally challenging nested expectation. This paper uses an unbiased randomized MLMC gradient estimator within stochastic optimization to search for designs.

1. Introduction.

  • For root-mean-square accuracy ε, standard nested Monte Carlo typically costs O(ε^-3), while prior MLMC variants reduce the cost to O(ε^-2) or O(ε^-2(log ε^-1)^2).The paper describes those earlier cost reductions as an intermediate step because design optimization had been left behind.Source: §1 · pp. 2–3
  • The paper applies stochastic gradient descent when design parameters are continuous and the expected information gain is differentiable, using randomized MLMC to estimate its nested-expectation gradient without bias.The estimator supplies random gradient samples at each optimization iteration.Source: §1 · p. 3
  • Unlike the cited approach limited to additive Gaussian noise and biased Monte Carlo gradients, this paper considers a more general forward model and unbiased gradient samples.The paper notes that unbiased samples avoid managing a bias-variance tradeoff in stochastic gradient methods.Source: §1 · p. 3
  • The paper's main contribution is an unbiased gradient estimator shown under conditions to have finite expected squared ℓ2-norm and finite computational cost per sample.The proposed optimization algorithm is tested on a simple problem and a pharmacokinetic problem.Source: §1 · p. 3

2. Stochastic gradient-based optimization.

The expected-information-gain gradient retains a nested expectation, with an inner average over a second parameter draw. Stochastic gradient methods can use rough unbiased samples instead of pointwise-accurate gradients, with convergence guarantees under additional assumptions.

2.1. Gradient of expected information gains.

  • The gradient expression does not require additive Gaussian noise, as the paper's examples also consider multiplicative and mixed noise models.The paper assumes the likelihood can be computed explicitly at unit cost.Source: §2.1 · pp. 4–5
  • Under continuity assumptions on the likelihoods and their gradients, the expected-information-gain gradient has an outer expectation over θ and ϵ and an inner expectation over an independent θ′.The gradient expression is the difference between expected likelihood-score terms, with the second term containing the inner expectation.Source: §2.1 · p. 5

2.2. Basics of stochastic gradient-based optimization.

  • Stochastic gradient optimization needs unbiased gradient samples with finite variance and computational cost, rather than pointwise-accurate gradient estimates.The method uses rough unbiased Monte Carlo estimates at each iteration.Source: §2.2 · pp. 5–6
  • With a convex domain and strongly concave, differentiable objective, the stated stochastic-optimization result gives mean squared error O(1/t) for the design estimate.The update projects onto the feasible domain.Source: §2.2 · p. 6

3. Monte Carlo gradient estimation.

Section 3 develops Monte Carlo estimators for the nested gradient, replacing biased fixed-inner-sample estimates with a randomized MLMC construction whose antithetic corrections support finite-variance, finite-cost sampling.

3. Monte Carlo gradient estimation.

  • The section introduces two Monte Carlo estimators for the gradient ∇ξU(ξ) = E[ψξ].Source: §3 · p. 6

3.1. Standard Monte Carlo.

  • Although the numerator and denominator estimates are individually unbiased, their ratio-based gradient estimators are biased unless q equals the posterior distribution.Source: §3.1 · p. 7

3.2. Unbiased multilevel Monte Carlo.

  • Randomly selecting level corrections with probabilities wℓ yields an unbiased gradient estimator through the telescoping representation.Source: §3.2 · p. 8

3.2.1. Naive construction.

  • Reusing samples across adjacent levels lowers correction magnitude, but naive correction variance is conjectured to decay no faster than O(2^-ℓ), too slowly for the required condition.Source: §3.2 · p. 8, §3.2.1 · p. 9

3.2.2. Antithetic construction.

  • Antithetic corrections decay faster than naive corrections, allowing weights wℓ ∝ 2^-τℓ, 1 < τ < β, to meet the finite-variance and finite-cost condition.Source: §3.2 · p. 8, §3.2.2 · pp. 10–11

3.3. Unbiased MLMC stochastic optimization.

  • Algorithm 3.1 samples levels with probabilities wℓ, estimates ∇ξU, applies a stochastic-gradient update, and repeats until its stopping criterion is met.Source: §3.3 · p. 11

4. Numerical experiments.

The numerical experiments evaluate the optimization algorithm on a simple test case and a pharmacokinetic design problem. They report convergence toward the test optimum and structured sampling-time designs in the PK model.

4.1. Simple test case.

  • Δψ corrections decayed geometrically in the test case, with estimated β=1.64 at ξ=1.5 and 1.63 at ξ*.Source: §4.1 · p. 13
  • The unbiased MLMC estimate converged toward ξ* with mean squared error approximately t^-1.12, while fixed-M Monte Carlo could stall away from ξ*.Source: §4.1 · p. 14

4.2. Pharmacokinetic model.

  • 3/5/7 versus 3/6/6 sampling times were allocated to the three clusters by stdMC and MLMC, respectively; their cluster centers differed significantly (p≈10^-5).Source: §4.2 · pp. 16–17
  • β was estimated as 0.80, 1.36, and 1.47 at t=0, T/2, and T; when β≤1, no known wℓ choice ensures both finite expected cost and squared norm.Source: §4.2 · pp. 17–18
  • 4.544 for MLMC versus 4.535 for standard Monte Carlo was the average converged expected information gain, while the resulting designs were qualitatively different.Source: §4.2 · p. 18

5. Conclusion.

The paper combines an unbiased multilevel estimator of the expected-information-gain gradient with stochastic gradient optimization to search for Bayesian experimental designs. Numerical experiments show success on a simple test case and a pharmacokinetic problem.

5. Conclusion.

  • The unbiased antithetic multilevel estimator has finite expected squared ℓ2-norm and computational cost per sample under stated conditions, enabling stochastic optimization without the fixed-inner-sample bias.The paper reports that fixed-inner-sample Monte Carlo fails to reach the true optimum in the simple test case.Source: §5 · pp. 18–19
  • In the simple test case, the proposed algorithm finds the true optimal design, while fixed-inner-sample Monte Carlo fails to reach it.The proposed algorithm has the convergence behavior expected under standard stochastic optimization theory with unbiased gradient estimates.Source: §5 · p. 19
  • For the pharmacokinetic problem, the proposed algorithm performs well and gives higher expected information gain and qualitatively different sampling times than the existing standard Monte Carlo estimator.Source: §5 · p. 19

Appendix A. Proof of Theorem 3.1.

The proof bounds the multilevel estimator’s error and establishes finite expected squared norm and computational cost when its stated moment and weight conditions hold.

Appendix A. Proof of Theorem 3.1.

  • The proof follows an argument used for nested expectations and invokes a previously established lemma for its preliminary bound.The cited markers are [17, Lemma 3.9] and [14, Lemma 1].Source: Appendix A · pp. 19–20
  • The proof uses a moment bound for averages of i.i.d. samples, assuming E[|X|^u] < ∞ for u > 2.Source: Appendix A · p. 20
  • Using the same i.i.d. samples from q in the numerator and denominator supports the antithetic bounds used to control the estimator’s terms.The proof notes that its numerator is vector-valued and supplies details for completeness.Source: Appendix A · p. 20
  • The proof’s bound on E[∥∆ψξ,ℓ∥²] decays as 2^-min(u,4)ℓ/2, and choosing wℓ ∝ 2^-τℓ yields finite expected squared norm and computational cost when 1 < τ < β and u > 2.The condition u > 2 ensures β > 1, so the stated interval for τ is available.Source: Appendix A · p. 24

Related papers

Loading 2005.08414v3…