PaperlayerView exact revision on arXiv

Source-linked AI summary

A Generalized Approximate Control Variate Framework for Multifidelity Uncertainty Quantification

Alex A. Gorodetsky, Gianluca Geraci, Mike Eldred, John D. Jakeman

arXiv:1811.04988v3stat.CO

TL;DR

Estimating statistics of expensive high-fidelity simulations by Monte Carlo can be computationally intractable, while lower-fidelity models often have unknown statistics. The paper develops approximate control variate estimators that use multiple models, showing that recursive approaches have a single-model variance-reduction bound while the new approach can converge to the optimal multi-model control variate.

  • Problem

    Monte Carlo estimation can be computationally intractable for expensive simulation models, and existing analyses of control variates with unknown means do not address ensembles of low-fidelity sources.

    Source: §1 · pp. 1–2

  • Method

    The framework constructs approximate control variate estimators without assuming a simplified model dependency structure and derives strategies that converge to the optimal multi-model control variate.

    Source: §1 · p. 2, §3 · p. 9

  • Results

    Recursive MFMC and W-RDiff variance reduction is bounded by that of a single-model control variate, while the proposed approach can converge to the optimal multi-model control variate.

    Source: §2.5 · p. 9, §3 · p. 9

  • Takeaways & Limitations

    The framework and preliminary allocation approach are relevant when high-fidelity evaluations are fixed or impractical to augment, such as legacy data.

    Source: §1 · p. 2

    Robust optimal sample allocation and analysis of variance introduced by estimating the covariance matrix remain future work.

    Source: §5 · p. 23

Abstract

from arXiv · show

We describe and analyze a variance reduction approach for Monte Carlo (MC) sampling that accelerates the estimation of statistics of computationally expensive simulation models using an ensemble of models with lower cost. These lower cost models --- which are typically lower fidelity with unknown statistics --- are used to reduce the variance in statistical estimators relative to a MC estimator with equivalent cost. We derive the conditions under which our proposed approximate control variate framework recovers existing multi-model variance reduction schemes as special cases. We demonstrate that these existing strategies use recursive sampling strategies, and as a result, their maximum possible variance reduction is limited to that of a control variate algorithm that uses only a single low-fidelity model with known mean. This theoretical result holds regardless of the number of low-fidelity models and/or samples used to build the estimator. We then derive new sampling strategies within our framework that circumvent this limitation to make efficient use of all available information sources. In particular, we demonstrate that a significant gap can exist, of orders of magnitude in some cases, between the variance reduction achievable by using a single low-fidelity model and our non-recursive approach. We also present initial sample allocation approaches for exploiting this gap. They yield the greatest benefit when augmenting the high-fidelity model evaluations is impractical because, for instance, they arise from a legacy database. Several analytic examples and an example with a hyperbolic PDE describing elastic wave propagation in heterogeneous media are used to illustrate the main features of the methodology.

1. Introduction.

The paper develops a generalized approximate control variate framework for reducing Monte Carlo variance when lower-fidelity model statistics are unknown. It analyzes limits of recursive multi-model strategies and proposes estimators and sample allocation approaches that use multiple information sources.

1. Introduction.

  • Monte Carlo estimation can be computationally intractable for expensive integrands because estimator variance decreases inversely with sample count.Control variates reduce variance by introducing estimators correlated with the Monte Carlo estimator.Source: §1 · p. 1
  • The framework requires no simplified dependency structure among models and addresses control variates whose statistics are unknown.The paper also proposes a sample allocation strategy for variance reduction under a fixed computational budget.Source: §1 · p. 2
  • The motivating setting includes fixed high-fidelity sample counts, such as evaluations from a legacy database or an impractical-to-repeat simulation campaign.The paper focuses on reducing variance for statistics of the highest-fidelity model, while multilevel methods may also target bias reduction.Source: §1 · p. 2
  • The proposed estimators use correlations among information sources to converge to the optimal multi-model control variate, with improved variance reduction demonstrated theoretically and numerically.The paper presents preliminary optimization-based sample allocation rather than a comprehensive allocation strategy.Source: §1 · p. 2
  • Recursive MFMC and recursive difference estimators are limited to the variance reduction of a control variate using one low-fidelity model.The paper distinguishes this variance-reduction target from mean-squared-error reduction that also addresses bias.Source: §1 · p. 2

2. A unifying approximate control variate framework.

This section develops a unifying approximate control variate framework for low-fidelity models with estimated means, accounting for sampling costs and relationships among sample sets. It examines the limits of recursive estimators and motivates ACV strategies designed to converge to optimal control variate performance as low-fidelity data grows.

2.1. Traditional control variate estimation.

  • Traditional control variates combine a high-fidelity estimate with a correlated estimator of a control variate whose mean is known; their variance reduction depends on correlation.The multifidelity setting differs because low-fidelity means are unknown and must be estimated from low-fidelity simulations.Source: §2.1 · p. 3, §2.2 · p. 4

2.2. Approximate control variate estimation.

  • The approximate control variate estimator uses estimated low-fidelity means and sample sets that may overlap, accounting for their additional evaluation cost and deriving optimal weights under a positive-definite covariance condition.For fixed weights, the estimator is unbiased when its high-fidelity, low-fidelity, and estimated-mean components are unbiased.Source: §2.2 · pp. 4–5

2.3. Recursive nested estimators.

  • MFMC uses nested sample sets, with each low-fidelity model’s control-variate estimate sharing samples with higher-fidelity models and its estimated mean using an enriched set [27, 20, 26, 28].The section presents MFMC as a recursive procedure and derives an alternative expression relating its variance reduction to correlations among models.Source: §2.3 · pp. 5–6
  • MFMC’s recursive nested sampling limits its variance reduction to that of the optimal single control variate, regardless of the amount of low-fidelity data used.The authors derive optimal MFMC weights without prior assumptions on model costs or correlation orderings; the bound is established under the stated ordering of correlations, which can be obtained by reordering models.Source: §2.3 · pp. 5–6

2.4. Recursive difference estimators.

  • W-RDiff adds optimal approximate-control-variate weights to the MLMC inner-loop sampling strategy, but recursive difference estimators remain bounded by an optimal single control variate.The classical difference estimator corresponds to fixed control weights αi = −1; using fixed weights can be suboptimal, while the recursive structure limits maximum variance reduction.Source: §2.4 · pp. 7–8

2.5. Summary and example.

  • The example sets Q(ω)=ω^5 and Qi(ω)=ω^(5−i) for i=1,…,4, varying prescribed sample ratios without assuming links to model costs or correlations.The inputs follow a uniform distribution on [0, 1].Source: §2.5 · p. 8
  • The gap between OCV-1 and OCV depends on covariance and correlation, not sample allocation, although exploiting it depends on allocation, model cost, and correlation.Source: §2.5 · p. 9
  • W-RDiff and MFMC variance reduction is bounded by that of OCV-1, as predicted by theory.With high-fidelity samples fixed, the example shows that existing recursive estimators do not achieve the maximum possible variance reduction.Source: §2.5 · p. 9
  • The proposed ACV estimators use Propositions 2.1 and 2.2 to provably converge to OCV as low-fidelity data increases.The recursive approaches cannot recover the full covariance matrix: their sampling patterns yield diagonal covariance for MFMC and tridiagonal covariance for W-RDiff.Source: §3 · p. 9

3. Approximate Control Variates.

The section develops approximate control variates that can converge to the optimal control variate, then extends them to accelerate convergence toward chosen targets and allocate samples under a cost constraint. Its numerical results show these strategies can improve on recursive baselines, while the allocation approach is presented as preliminary.

3.1. Two convergent estimators.

  • With increasing data, ACV-IS and ACV-MF converge in variance reduction to the optimal control variate, unlike recursive W-RDiff and MFMC, which are bounded by OCV-1.In the monomial example, ACV-IS and ACV-MF reach OCV at large sample ratios, though their variance reduction can be below OCV-1 at small ratios.Source: §3.1 · p. 11
  • Recursive estimators are limited to OCV-1, while the framework supports schemes that accelerate convergence to any target up to OCV.The section presents the new algorithm as one example among many possible realizations of the framework.Source: §3.2 · p. 12

3.2. Accelerating the approximate CV.

  • ACV-KL partitions control variates into K for an approximate CV and the remaining models for estimating µL, with the added CV reducing variance in µL.Its first terms form ACV-MF with K control variates; the final term adds a CV scheme to reduce variance in estimating µL.Source: §3.2 · pp. 12–13
  • The ACV-MF sampling strategy is used for ACV-KL; the alternative ACV-IS strategy for estimating µL is not analyzed.The authors describe their choices as representative realizations intended to demonstrate the framework.Source: §3.2 · p. 12
  • ACV-KL can accelerate ACV-MF to any target baseline, outperforming ACV-MF and matching the fully recursive algorithm in the low-ratio region.The best (K, L) combination is problem dependent and can be searched at negligible cost.Source: §3.2 · p. 13

3.3. Sample allocation.

  • The sample-allocation procedure minimizes estimator variance under a cost constraint using numerical optimization, but is offered as a preliminary approach rather than a best formulation.The formulation uses pilot-sample covariance estimates and relaxes integer sample counts to continuous variables before rounding allocations up.Source: §3.3 · p. 15

4. Numerical Experiments.

The experiments compare recursive and non-recursive estimators across analytic models and an elastic-wave simulation, examining how model costs, correlations, weighting, and sample allocation affect variance reduction.

4.1. Model problem.

  • Across the monomial cost tests, recursive estimators perform virtually identically, while ACV-KL provides greater variance reduction and usually beats Monte Carlo when w1 < 0.01.The optimal allocation results show ACV-KL’s advantage when the first control variate costs less than one-hundredth of the truth model.Source: §4.1 · pp. 15–16, Figure 4.1 · p. 16

4.2. A parametric model problem.

  • ACV-KL generally outperforms other estimators across the tested cost ratios and θ1 values, with its advantage greatest where the OCV–OCV-1 variance gap is largest.As the models become cheaper, recursive estimators converge toward OCV-1, while ACV-IS, ACV-MF, and ACV-KL converge toward OCV.Source: §4.2 · p. 17, Figure 4.4 · p. 18

4.2.1. Weighted vs. unweighted estimators.

  • At w = 1000, the weighted recursive difference estimator generally has lower variance than the unweighted αi = −1 alternative and can outperform Monte Carlo in regimes where the unweighted estimator cannot.Source: §4.2.1 · p. 18, Figure 4.6 · p. 19

4.2.2. Estimating control-variate weights.

  • Estimating the covariance matrix with 20 pilot samples reduces efficiency, but weighted schemes generally still outperform the unweighted recursive difference estimator.The experiment used a total cost of 100 and over 5000 repeated estimator realizations; the authors note that the two-step procedure may be sub-optimal.Source: §4.2.2 · pp. 18–19

4.3. Two dimensional elasticity in heterogeneous media.

  • The elastic-wave example uses uncertain material properties and compares estimators across hierarchical and multifidelity model sets built from two numerical fidelities and multiple resolutions.The quantity of interest is average shear stress in a subdomain of the right material.Source: §4.3 · pp. 20–21
  • In the elastic-wave tests, all estimators achieve more than an order-of-magnitude variance reduction for hierarchical models, while ACV approaches outperform recursive methods for less-correlated multifidelity models.ACV-KL does not degrade with more aggressive mesh coarsening, although the tested optimization approach gives inconsistent variance decrease for ACV-MF.Source: §4.3 · pp. 21–22

5. Conclusion.

The conclusion presents non-recursive approximate control variates as a way to use correlations across multiple information sources, beyond the single-model limit of recursive estimators. Their advantage depends on model correlations and costs, while robust allocation and covariance-estimation theory remain future work.

  • ACV estimators can exploit all available correlations and converge to the optimal multi-model control variate, overcoming recursive methods’ single-model limit.The numerical examples report gains both when high-fidelity evaluations increase and when their number is fixed.Source: §5 · pp. 22–23
  • ACV’s advantage is greatest when the OCV–OCV-1 gap is large and diminishes as that gap shrinks; the elastic-wave example also shows robustness to lower-correlation multifidelity hierarchies.The authors report benefits for the monomial test problem and the elastic-equation example.Source: §5 · p. 23
  • Robust optimal sample allocation and analysis of variance introduced by estimating the covariance matrix remain future work for ACV.The authors identify selecting control-variate groups and extending covariance-estimation theory from OCV to ACV as research directions.Source: §5 · p. 23

Appendix A. Proof of Lemma 2.3.

The proof handles nested sampling by partitioning sums into independent sample sets and using their covariance relationships to derive the result.

  • The proof partitions quantities into sums over non-overlapping, independent sample sets before computing covariance terms.Source: Appendix A · p. 23
  • The diagonal variance terms are obtained by adding the variances of independent sums, after which the proof turns to the off-diagonal covariance terms.Source: Appendix A · pp. 23–24
  • For nested samples, the proof identifies which sums share samples with each difference estimator to derive the covariance relationships.Only the first two sums in the cited expression share samples with Δi, and they correspond to samples delegated to Q̂j.Source: Appendix A · p. 24

Appendix B. Proof of Lemma 2.4.

The proof obtains covariance expressions from Proposition 2.2 and uses the diagonal covariance structure to support the stated comparison.

  • The proof derives its result by applying Proposition 2.2 to the covariance expressions.Source: Appendix B · p. 24
  • Equations (A.3) and (A.4) provide the covariance expressions used in the proof.Source: Appendix B · p. 24
  • The proof notes that the covariance is diagonal and invertible, and sets r0 = 1 to enable comparison with a single control variate.Source: Appendix B · p. 24

Appendix C. Proof of Lemma 2.7.

The proof rearranges the w-RDiff estimator to identify independent difference contributions, then obtains its variance by summing those contributions.

  • The proof starts from the w-RDiff estimator’s definition and rearranges it to identify statistically independent difference contributions.Source: Appendix C · p. 25
  • The estimator variance is obtained by summing independent contributions, so all covariance terms are zero.Source: Appendix C · p. 25

Appendix D. Proof of Theorem 3.2.

The proof derives covariance expressions by splitting estimator differences into sums with independent samples, then applies Propositions 2.1 and 2.2 to obtain the result.

  • After recalling the definitions of F(IS) and F(MF), the proof uses Propositions 2.1 and 2.2 with the derived expressions to obtain the stated result.Source: Appendix D · pp. 25–26, Appendix E · p. 26
  • Splitting each Δ_i into independent-sample sums isolates the shared first summation as the source of covariance between Δ_i and Δ_j.The proof also derives diagonal variance terms using the same split.Source: Appendix D · p. 25
  • The proof obtains the off-diagonal covariance from the shared samples, including a term proportional to Cov[Q_i, Q_j].Source: Appendix D · p. 25

Appendix E. Proof of Theorem 3.4.

For ACV-MF, overlapping samples change the off-diagonal covariance derivation, while the diagonal variance and Cov[Q, Δ_i] expressions remain as in ACV-IS.

  • ACV-MF reuses samples for μ̂_i as the first min(r_jN, r_iN) samples of μ̂_j when j ≥ i, changing the off-diagonal covariance expressions.Source: Appendix E · p. 26
  • The proof derives Cov[Δ_i, Δ_j] separately for r_j ≥ r_i and r_j < r_i by splitting the differences into independent-sample sums.When r_j ≥ r_i, covariance comes from the first two summations; the other case uses a different split of Δ_j.Source: Appendix E · p. 26
  • The variance of Δ_i and Cov[Q, Δ_i] retain the same expressions as in ACV-IS, and the theorem follows by applying Propositions 2.1 and 2.2.Source: Appendix E · p. 27

Appendix F. Proof of Theorem 3.6.

The proof establishes that F(IS) and F(MF) converge to the all-ones matrix by checking their diagonal and off-diagonal entries.

  • The proof treats the diagonal entries of F(IS) and F(MF) together because they are shared.Source: Appendix F · p. 27
  • The proof shows that the off-diagonal entries of F(IS) converge to 1.Source: Appendix F · p. 27
  • For F(MF), the off-diagonal convergence follows as min(r_i, r_j) tends to infinity when both r_i and r_j tend to infinity.Source: Appendix F · p. 27

Appendix G. Proof of Theorem 3.8.

The proof organizes covariance calculations into three index regimes, treating the mixed regime by symmetry. It uses sample splittings to compute the covariances and derive the stated result.

Appendix G. Proof of Theorem 3.8.

  • The covariance analysis separates indices into three regimes: both at most K, both greater than K, or one in each group, with the mixed case symmetric.Source: Appendix G · p. 27
  • For i,j ≤ K, the case is identical to ACV-MF for a control-variate estimator with K control variates.Source: Appendix G · p. 27
  • For i,j > K, the proof constructs independent sample splittings and considers both rj > ri and rj < ri.When rj < ri, zj consists of the first rjN samples of zi.Source: Appendix G · pp. 27–28
  • The proof computes the required covariances from the splittings and applies Propositions 2.1 and 2.2 to obtain the result.Source: Appendix G · pp. 27–29

Related papers

Loading 1811.04988v3…