PaperlayerView exact revision on arXiv

Source-linked AI summary

On Nesting Monte Carlo Estimators

Tom Rainforth, Robert Cornish, Hongseok Yang, Andrew Warrington, Frank Wood

arXiv:1709.06181v4stat.COstat.MEstat.ML

TL;DR

Nested expectations prevent conventional Monte Carlo estimation because outer integrands may depend on separately estimated inner expectations. The paper formalizes nested Monte Carlo, derives convergence conditions and rates, identifies naïve-estimation pitfalls, and develops reformulations and applications. It concludes that consistent estimation is possible, with improved rates for reformulated problems and implications for Bayesian experimental design and variational objectives.

  • Problem

    Nested expectations in machine learning and statistics cannot generally be handled by conventional Monte Carlo, motivating analysis of nested estimators and their convergence.

  • Method

    The paper develops a formal framework for nested Monte Carlo, analyzes repeated nesting and continuity requirements, and introduces reformulations that convert some nested problems into single expectations.

  • Results

    The paper establishes convergence conditions and rates, shows that inner and outer sample counts generally must both increase, and reports empirical evidence that the rates occur in practice.

  • Takeaways & Limitations

    The results provide guidelines for avoiding naïve nesting pitfalls and support applications to Bayesian experimental design and variational objectives.

  • Takeaways & Limitations

    The convergence-rate results are upper bounds on worst-case performance, and convergence requires assumptions such as expected continuity of the outer mapping.

Abstract

from arXiv · show

Many problems in machine learning and statistics involve nested expectations and thus do not permit conventional Monte Carlo (MC) estimation. For such problems, one must nest estimators, such that terms in an outer estimator themselves involve calculation of a separate, nested, estimation. We investigate the statistical implications of nesting MC estimators, including cases of multiple levels of nesting, and establish the conditions under which they converge. We derive corresponding rates of convergence and provide empirical evidence that these rates are observed in practice. We further establish a number of pitfalls that can arise from naive nesting of MC estimators, provide guidelines about how these can be avoided, and lay out novel methods for reformulating certain classes of nested expectation problems into single expectations, leading to improved convergence rates. We demonstrate the applicability of our work by using our results to develop a new estimator for discrete Bayesian experimental design problems and derive error bounds for a class of variational objectives.

1 Introduction

The paper studies nested Monte Carlo when outer integrands depend on inner estimators, establishing convergence conditions, rates, pitfalls, and reformulations for applications including Bayesian experimental design and variational inference.

  • Nested expectations arise in applications including portfolio risk management, stochastic control, probabilistic programming, Bayesian experimental design, and variational inference.
  • Nonlinear mappings of inner expectations, such as logarithms, prevent some nested problems from being reformulated as single expectations.
  • Convergence generally requires increasing sample counts in both inner and outer estimators when the outer estimator depends nonlinearly on the inner estimator.
  • For nesting depth D, optimal NMC convergence is O(1/T^(D+2)), while naïve approaches achieve a slower rate.
  • The paper extends prior work by treating multiple nesting levels, broader nonlinear mappings, precise rates, empirical validation, and practical guidance.

2 Problem Formulation

The paper formulates nested Monte Carlo for expectations whose integrands depend on another intractable expectation, estimating inner integrals separately for outer samples and extending this structure to repeated nesting.

  • The formulation considers an intractable integrand λ defined as f(y, γ(y)), where γ(y) is an expectation over another variable.
  • Nested Monte Carlo estimates the inner expectation for each sampled outer value and then applies conventional Monte Carlo to the resulting outer evaluations.
  • Multiple nesting levels arise when evaluating φ(y, z) itself requires computation of an intractable nested expectation.

3 Convergence of Nested Monte Carlo

The section establishes convergence conditions and rates for nested Monte Carlo, including repeated nesting, and identifies how smoothness and allocation affect accuracy. It also shows that naive nesting can remain biased unless inner sample sizes increase.

  • Repeated Nesting and Exact Bounds: For repeated nesting, the paper derives general convergence bounds under Lipschitz assumptions and tighter bounds when all nested functions are continuously differentiable.
  • The NMC estimator converges in mean squared error at O(1/N + 1/M) when f is Lipschitz continuous and the relevant terms are square-integrable.
  • With total budget T = MN, balancing N and M yields rate O(1/√T), while stronger smoothness can yield O(1/T^2/3).
  • Naive NMC estimates are generally biased, so increasing only the outer sample count cannot ensure convergence when the inner sample size remains fixed.
  • Convergence can require an expected-continuity condition weaker than Lipschitz continuity, namely E[(ε_M)_1] → 0 as M → ∞.

4 Special Cases

The section identifies settings where nested expectations can recover conventional Monte Carlo rates, either by algebraic reformulation or by exploiting finite support and linear structure. It also extends this result to products of expectations under fixed inner sample sizes.

  • Linear Mappings: When f is linear in its second argument, the nested problem can be rearranged into a single expectation and estimated at the conventional O(1/N) rate.
  • Finite Possible Realizations of y: If y has finitely many possible values, the problem can be split into separate non-nested problems whose estimator has mean squared error rate O(1/N).
  • Products of Expectations: For products of expectations, independent auxiliary variables can transform the expression into a single expectation on an extended space.
  • Products of Expectations: If f is linear, the resulting NMC estimator achieves mean squared error rate O(1/N) with fixed inner sample sizes.
  • For functions of the form f(y, γ(y)) = g(y)γ(y)^α with nonnegative integer α, the paper constructs a standard non-nested Monte Carlo estimator using independent copies.

5 Empirical Verification

Empirical experiments confirm the predicted convergence behavior of nested Monte Carlo across analytic, cancer-treatment, and repeatedly nested problems, while exposing finite-budget allocation effects and bias from fixed inner sample sizes.

  • 5.1 Simple Analytic Model: The analytic model realizes the theoretical convergence rates, but holding M constant makes the estimator converge to an incorrect solution.Finite-budget experiments also show that the asymptotically optimal allocation can be suboptimal at practical sample sizes.
  • 5.1 Simple Analytic Model: O(1/T 2/3) is observed when N ∝M 2, while fixed M achieves O(1/T) error but converges to a biased solution.The best finite-budget allocation changes with T, with the optimal α increasing from about 0.5 at T = 103 to about 0.6 at T = 107.
  • 5.2 Planning Cancer Treatment: The cancer-treatment simulation again verifies the theoretical rates against a ground-truth estimate computed with M = 105 and N = 105.Testing different thresholds identified Ttreat = 0.125 as optimal under the budget.
  • 5.3 Repeated Nesting: In repeated nesting, setting N0 = N1 = N2 yields the expected O(T −1/3) rate, whereas fixing N2 = 5 produces a biased solution.The experiments use total budget T = N0N1N2 and compare multiple allocation strategies.
  • 5.3 Repeated Nesting: For T = 106, finite-budget optimal allocations differ substantially between the original and modified problems and from the asymptotically optimal setup (0.5, 0.5).Bayesian optimization found (α1, α2) = (0.53, 0.36) and (0.38, 0.45) for the two problems, respectively.
  • 5.3 Repeated Nesting: BOPP contour plots show distinct performance variations for the two problem variants, with Gaussian-process approximations judged close to the truth from uncertainty estimates.The plots compare log10 error across different allocations of T = 106.

6 Applications

The paper applies its nested Monte Carlo results to Bayesian experimental design and variational autoencoders, deriving improved estimators and error conclusions. For discrete experimental outcomes, reformulation yields standard Monte Carlo convergence and empirical gains.

  • Bayesian Experimental Design: The paper derives an improved estimator for Bayesian experimental design when experiment outputs are discrete.
  • Bayesian Experimental Design: The naive Bayesian experimental design estimator uses MN samples and converges at O(1/N + 1/M^2).
  • Bayesian Experimental Design: O(1/N) convergence is achieved by the reformulated estimator because the number of possible outcomes C is fixed.The reformulated estimator uses N samples rather than the naive estimator's total of MN samples.
  • Bayesian Experimental Design: Figure 6 reports the theoretical convergence rates and particularly pronounced advantages for the reformulated estimator in the BED problem.
  • Variational Autoencoders: The paper analyzes VAE and IWAE objectives as biased nested estimators of log E[w1,1(θ)].The IWAE sets N = 1, whereas the VAE sets M = 1.
  • Variational Autoencoders: For fixed total sample count T, the lowest MSE bound is achieved by N = 1 and M = T, as in the IWAE.

7 Conclusions

The paper formalizes nested Monte Carlo estimation, establishes convergence and bias results, and identifies practical requirements for consistent estimation. It also shows that certain nonlinear nested problems can be reformulated for faster convergence, while debiasing alternatives have complications.

  • The framework yields consistent estimators for problems that conventional Monte Carlo alone cannot tackle.
  • Under Lipschitz continuity and finite second moments, the mean squared error converges to zero at O(1/N + 1/M).
  • Nonlinear outer mappings generally require both inner and outer sample counts to increase for convergence.
  • Russian roulette and other debiasing techniques may handle some nonlinear cases, but can produce infinite-variance estimates and lack general-purpose nonnegative unbiased factories.

Appendix C Proof of Theorem 2 - “Almost almost sure” convergence

The appendix proves convergence by decomposing nested-estimator error into variance and bias terms and controlling these terms across nesting levels. It derives single- and multiple-nesting bounds under continuity and differentiability assumptions.

  • The proof uses strong-law convergence, Egorov’s theorem, and uniform convergence outside events of arbitrarily small probability.
  • The analysis recursively propagates variance and bias terms through deeper nesting levels, with dominated terms collected as O(ϵ).
  • The error analysis separates variance reduction from bias reduction: outer sample counts reduce variance, while inner sample counts reduce bias.
  • For a single nesting, the finite-sample bound contains terms proportional to 1/N0 and 1/N1.
  • With continuously differentiable mappings, the single-nesting bound instead contains an inner term proportional to 1/N1^2.

Appendix E Proof of Theorem 4 - Convergence Rate for Finite Realisations of y

The appendix proves an O(1/N) convergence rate for the estimator when the outcome variable has finitely many possible realizations. The proof bounds separate probability-estimation and conditional-function-estimation errors.

  • For finite outcome realizations and Lipschitz mappings, the estimator converges at O(1/N).
  • Lipschitz continuity bounds the function-estimation component using Monte Carlo error for each finite outcome.
  • The proof decomposes mean squared error into errors from estimating outcome probabilities and function values.

Appendix F Proof for Theorem 5 - Products of Expectations

Theorem 5 establishes consistency for an NMC estimator when the function is linear, reducing the nested calculation to standard Monte Carlo behavior.

  • For linear f, the estimator converges almost surely to I at mean-square rate O(1/N) for any fixed nested sample sizes.
  • The proof fixes the nested sample sets and uses standard Monte Carlo convergence on an extended sample space.
  • Linearity of f ensures that the expectation of the nested estimator equals the target I.
  • Independence across nested terms allows the estimator’s components to be analyzed separately.

Appendix G Optimizing the Convergence Rates

The appendix optimizes sample allocations for nested estimators by expressing total cost through the product of per-layer sample counts. It shows that balanced allocations recover the best rates, while computational cost is asymptotically dominated by the innermost layer.

  • T = Q_k=0^D N_k counts innermost-layer samples and is an appropriate measure of total computational cost.Each outer sample requires samples at every subsequent layer, producing a product of layer sizes.
  • The asymptotic computational cost is O(T), with nearly all computation spent in the innermost estimator.
  • For the bound O(1/N + 1/M^2), N ∝ M^2 yields convergence rate O(1/T^2/3).
  • Repeated nesting extends these allocation principles across layers, requiring progressively balanced relationships among N_0,...,N_D.The appendix derives corresponding depth-dependent rates and shows that imbalanced terms weaken the bound.
  • Appendix H Additional details pertaining to cancer simulator: The cancer-simulator appendix defines treatment success through a binary simulator outcome and clinician decisions based on estimated success probability.The treatment threshold Ttreat determines whether a patient receives treatment.

H.2 Budget result

The cancer-treatment example selects the treatment-probability threshold where projected expenditure intersects the budget constraint. The reported optimum is Ttreat = 12.5%.

  • A dense search over Ttreat evaluates projected expenditure at each threshold and selects the best value under the budget constraint.
  • Ttreat = 12.5% is the optimal setting, identified by the intersection of predicted expenditure and the budget constraint.The expenditure relationship is non-linear, motivating the use of NMC for this optimization.

Appendix I Bayesian Experimental Design

Bayesian experimental design requires estimating expected information utility, whose marginal-distribution term contains a logarithm of an expectation and is therefore not directly amenable to standard Monte Carlo. The appendix reformulates the discrete-outcome case as a single-expectation estimator, achieving the standard MC rate and improved empirical utility estimation.

  • Bayesian experimental design chooses designs by maximizing expected information gain, equivalently the expected utility under p(y|d).
  • The posterior is rarely available in closed form, and the marginal p(y|d) term becomes nested when its logarithm is evaluated.
  • The estimator samples parameters and outcomes, with importance sampling available when direct likelihood sampling is unavailable.
  • For finite discrete outcomes, the reformulation converts the nested problem into a single MC estimator.
  • O(1/N) MSE is obtained for the reformulated estimator, compared with O(1/T^2/3) for the naïve estimator under N ∝ M^2.
  • The suggested estimator shows significant empirical performance improvements and clearer characterization of expected utility at fixed total budget T = 10^4.
Loading 1709.06181v4…