Efficient estimation of multiple expectations with the same sample by adaptive importance sampling and control variates

Julien Demange-Chryst, François Bachoc, Jérôme MorioStat. Comput 2023 · OpenReview

TL;DR

This paper introduces a novel adaptive algorithm (ME-aISCV) that efficiently estimates multiple expectations from a single sample, significantly outperforming standard Monte Carlo methods. It achieves this by adaptively refining importance sampling distributions and control variates, making it a powerful tool for complex uncertainty quantification tasks like sensitivity analysis.

What Problem Does This Paper Address?

Many problems in fields like finance and engineering require estimating multiple expected values simultaneously. Standard Monte Carlo methods, which estimate each expectation independently using separate samples, can become computationally prohibitive when dealing with many expectations or expensive-to-evaluate models. This paper tackles the challenge of efficiently estimating multiple expectations from a single sample, aiming to reduce computational cost and improve accuracy, especially when these expectations are related or when the underlying model is complex.

Methods

The core of the paper is the ME-aISCV (Multiple Expectations - adaptive Importance Sampling and Control Variates) algorithm. It builds upon two established variance reduction techniques:

  • Importance Sampling (IS): This technique involves drawing samples from a modified probability distribution (the "importance distribution") that is more likely to yield relevant outcomes, thereby reducing the variance of the estimator.
  • Control Variates (CV): This method uses auxiliary variables (control functions) whose expected values are known to reduce the variance of the primary estimator.

The novelty lies in the adaptive nature of ME-aISCV. It iteratively refines:

  1. Importance Sampling Distributions: The algorithm learns and updates the probability distributions from which samples are drawn for each expectation.
  2. Control Parameters: It optimizes the parameters associated with the control variates.
  3. Mixture Distribution: It constructs a mixture of these refined distributions to serve as the final sampling distribution.

A key innovation is a quantitative stopping criterion that balances the improvement in estimation accuracy with the remaining computational budget. Once the algorithm converges, a final independent sample is drawn from the learned distribution to obtain unbiased estimates.

Datasets

Not discussed in the paper. The paper focuses on methodology and uses synthetic examples and a real-world engineering problem for evaluation.

Key Insights and Ideas

  • Optimal Estimators are Intractable: The paper first demonstrates that theoretically optimal estimators combining IS and CV exist but require knowledge of the very expectations they aim to estimate, making them impractical. This motivates the search for adaptive approximations.
  • Adaptive Learning is Crucial: The ME-aISCV algorithm's success hinges on its ability to adaptively learn the best importance sampling distributions and control variates for the specific set of expectations being estimated.
  • Synergy of IS and CV: Combining IS and CV proves more powerful than either technique alone, especially when dealing with multiple, potentially related, expectations.
  • Stopping Criterion Balances Accuracy and Budget: The proposed stopping criterion is a clever way to avoid unnecessary computation by assessing if further refinement is likely to yield significant gains, thus optimizing the use of the available computational budget.
  • Unified Framework for Diverse Problems: The algorithm is shown to be applicable to various scenarios, including estimating moments of distributions and performing sensitivity analyses (Sobol' indices, input parameter uncertainty).

Key Results

  • Significant Variance Reduction: The ME-aISCV algorithm consistently achieved substantial variance reduction compared to standard Monte Carlo methods and even existing standard methods for specific tasks like Sobol' index estimation. For instance, in estimating moments of the Gaussian distribution, the criterion to minimize was reduced by about $10^4$.
  • Improved Accuracy in Sensitivity Analysis: In the cantilever beam example, ME-aISCV provided significantly better Sobol' index estimations, with boxplots centered on reference values and much smaller spreads. Individual variances were divided by approximately 10.
  • Efficient Handling of Many Expectations: The algorithm demonstrated its capability to efficiently estimate a large number of expectations (e.g., 100 expectations for the cantilever beam problem with input parameter uncertainty) simultaneously, outperforming naive Monte Carlo and mixture-based approaches.

Limitations and Future Work

  • Curse of Dimensionality: The paper acknowledges that using non-parametric IS auxiliary distributions, while offering more flexibility, faces challenges with high-dimensional problems.
  • Adaptive Weighting: The authors suggest that adaptively updating the weights assigned to each expectation during the algorithm's execution could be a valuable improvement.
  • Small Failure Probabilities: The algorithm could be adapted to estimate small failure probabilities by employing adaptive parametric IS to solve the cross-entropy problem.
  • Dependent Inputs: Extending the method to handle dependent input variables for sensitivity analysis (e.g., Shapley effects) remains a challenge, requiring the development of optimal IS distributions in the original input space.

Summary updated

Abstract

Some classical uncertainty quantification problems require the estimation of multiple expectations. Estimating all of them accurately is crucial and can have a major impact on the analysis to perform, and standard existing Monte Carlo methods can be costly to do so. We propose here a new procedure based on importance sampling and control variates for estimating more efficiently multiple expectations with the same sample. We first show that there exists a family of optimal estimators combining both importance sampling and control variates, which however cannot be used in practice because they require the knowledge of the values of the expectations to estimate. Motivated by the form of these optimal estimators and some interesting properties, we therefore propose an adaptive algorithm. The general idea is to adaptively update the parameters of the estimators for approaching the optimal ones. We suggest then a quantitative stopping criterion that exploits the trade-off between approaching these optimal parameters and having a sufficient budget left. This left budget is then used to draw a new independent sample from the final sampling distribution, allowing to get unbiased estimators of the expectations. We show how to apply our procedure to sensitivity analysis, by estimating Sobol’ indices and quantifying the impact of the input distributions. Finally, realistic test cases show the practical interest of the proposed algorithm, and its significant improvement over estimating the expectations separately.
BibTeX
@inproceedings{demangechryst2023efficient,
  author = {Julien Demange-Chryst and François Bachoc and Jérôme Morio},
  title = {{Efficient estimation of multiple expectations with the same sample by adaptive importance sampling and control variates}},
  booktitle = {Stat. Comput},
  year = {2023},
  url = {https://openreview.net/forum?id=SPNmCQMS0A},
}
Figure