On Nesting Monte Carlo Estimators

Abstract

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.

arXiv commentTo appear at International Conference on Machine Learning 2018

Cited by in corpus (27)

• Disentangling Disentanglement in Variational Autoencoders
• Decomposing 3D Scenes into Objects via Unsupervised Volume Segmentation
• Tighter Variational Bounds are Not Necessarily Better
• Advances in Variational Inference
• Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs
• A layered multiple importance sampling scheme for focused optimal Bayesian experimental design
• Asymptotic Distributions and Rates of Convergence for Random Forests via Generalized U-statistics
• A Unified Stochastic Gradient Approach to Designing Bayesian-Optimal Experiments
• Improving Transformation Invariance in Contrastive Representation Learning
• Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Design
• Test Distribution-Aware Active Learning: A Principled Approach Against Distribution Shift and Outliers
• Implicit Deep Adaptive Design: Policy-Based Experimental Design without Likelihoods
• Improving VAEs' Robustness to Adversarial Attack
• Compositional uncertainty in deep Gaussian processes
• Nested Reasoning About Autonomous Agents Using Probabilistic Programs
• Variational Inference with Continuously-Indexed Normalizing Flows
• Nesting Probabilistic Programs
• Linked Gaussian Process Emulation for Systems of Computer Models using Matérn Kernels and Adaptive Design
• A Scalable Gradient-Free Method for Bayesian Experimental Design with Implicit Models
• On Signal-to-Noise Ratio Issues in Variational Inference for Deep Gaussian Processes
• Efficient Probabilistic Inference in the Quest for Physics Beyond the Standard Model
• Voice Biometrics Security: Extrapolating False Alarm Rate via Hierarchical Bayesian Modeling of Speaker Verification Scores
• GaussED: A Probabilistic Programming Language for Sequential Experimental Design
• Targeted Active Learning for Bayesian Decision-Making
• An efficient estimation of nested expectations without conditional sampling
• Probabilistic Programs with Stochastic Conditioning
• Efficient Semi-Implicit Variational Inference