skip to main content


Title: Numerical analysis for inchworm Monte Carlo method: Sign problem and error growth
We consider the numerical analysis of the inchworm Monte Carlo method, which is proposed recently to tackle the numerical sign problem for open quantum systems. We focus on the growth of the numerical error with respect to the simulation time, for which the inchworm Monte Carlo method shows a flatter curve than the direct application of Monte Carlo method to the classical Dyson series. To better understand the underlying mechanism of the inchworm Monte Carlo method, we distinguish two types of exponential error growth, which are known as the numerical sign problem and the error amplification. The former is due to the fast growth of variance in the stochastic method, which can be observed from the Dyson series, and the latter comes from the evolution of the numerical solution. Our analysis demonstrates that the technique of partial resummation can be considered as a tool to balance these two types of error, and the inchworm Monte Carlo method is a successful case where the numerical sign problem is effectively suppressed by such means. We first demonstrate our idea in the context of ordinary differential equations, and then provide complete analysis for the inchworm Monte Carlo method. Several numerical experiments are carried out to verify our theoretical results.  more » « less
Award ID(s):
2012286 2037263 1910571
PAR ID:
10428660
Author(s) / Creator(s):
; ;
Publisher / Repository:
American Mathematical Society
Date Published:
Journal Name:
Mathematics of Computation
Volume:
92
Issue:
341
ISSN:
0025-5718
Page Range / eLocation ID:
1141 to 1209
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Monte Carlo simulations are useful tools for modeling quantum systems, but in some cases they suffer from a sign problem, leading to an exponential slow down in their convergence to a value. While solving the sign problem is generically NP hard, many techniques exist for mitigating the sign problem in specific cases; in particular, the technique of deforming the Monte Carlo simulation's plane of integration onto Lefschetz thimbles (complex hypersurfaces of stationary phase) has seen significant success in the context of quantum field theories. We extend this methodology to spin systems by utilizing spin coherent state path integrals to reexpress the spin system's partition function in terms of continuous variables. Using some toy systems, we demonstrate its effectiveness at lessening the sign problem in this setting, despite the fact that the initial mapping to spin coherent states introduces its own sign problem. The standard formulation of the spin coherent path integral is known to make use of uncontrolled approximations; despite this, for large spins they are typically considered to yield accurate results, so it is somewhat surprising that our results show significant systematic errors. Therefore, possibly of independent interest, our use of Lefschetz thimbles to overcome the intrinsic sign problem in spin coherent state path integral Monte Carlo enables a novel numerical demonstration of a breakdown in the spin coherent path integral. 
    more » « less
  2. We propose an empirical Bayes formulation of the structure learning problem, where the prior specification assumes that all node variables have the same error variance, an assumption known to ensure the identifiability of the underlying causal directed acyclic graph. To facilitate efficient posterior computation, we approximate the posterior probability of each ordering by that of a best directed acyclic graph model, which naturally leads to an order-based Markov chain Monte Carlo algorithm. Strong selection consistency for our model in high-dimensional settings is proved under a condition that allows heterogeneous error variances, and the mixing behaviour of our sampler is theoretically investigated. Furthermore, we propose a new iterative top-down algorithm, which quickly yields an approximate solution to the structure learning problem and can be used to initialize the Markov chain Monte Carlo sampler. We demonstrate that our method outperforms other state-of-the-art algorithms under various simulation settings, and conclude the paper with a single-cell real-data study illustrating practical advantages of the proposed method. 
    more » « less
  3. Summary

    The paper introduces a new local polynomial estimator and develops supporting asymptotic theory for nonparametric regression in the presence of covariate measurement error. We address the measurement error with Cook and Stefanski's simulation–extrapolation (SIMEX) algorithm. Our method improves on previous local polynomial estimators for this problem by using a bandwidth selection procedure that addresses SIMEX's particular estimation method and considers higher degree local polynomial estimators. We illustrate the accuracy of our asymptotic expressions with a Monte Carlo study, compare our method with other estimators with a second set of Monte Carlo simulations and apply our method to a data set from nutritional epidemiology. SIMEX was originally developed for parametric models. Although SIMEX is, in principle, applicable to nonparametric models, a serious problem arises with SIMEX in nonparametric situations. The problem is that smoothing parameter selectors that are developed for data without measurement error are no longer appropriate and can result in considerable undersmoothing. We believe that this is the first paper to address this difficulty.

     
    more » « less
  4. Abstract

    In causal inference problems, one is often tasked with estimating causal effects which are analytically intractable functionals of the data‐generating mechanism. Relevant settings include estimating intention‐to‐treat effects in longitudinal problems with missing data or computing direct and indirect effects in mediation analysis. One approach to computing these effects is to use theg‐formula implemented via Monte Carlo integration; when simulation‐based methods such as the nonparametric bootstrap or Markov chain Monte Carlo are used for inference, Monte Carlo integration must be nested within an already computationally intensive algorithm. We develop a widely‐applicable approach to accelerating this Monte Carlo integration step which greatly reduces the computational burden of existingg‐computation algorithms. We refer to our method as acceleratedg‐computation (AGC). The algorithms we present are similar in spirit to multiple imputation, but require removing within‐imputation variance from the standard error rather than adding it. We illustrate the use of AGC on a mediation analysis problem using a beta regression model and in a longitudinal clinical trial subject to nonignorable missingness using a Bayesian additive regression trees model.

     
    more » « less
  5. Langevin Monte Carlo (LMC) and its stochastic gradient versions are powerful algorithms for sampling from complex high-dimensional distributions. To sample from a distribution with density π(θ) ∝ exp(−U(θ)), LMC iteratively generates the next sample by taking a step in the gradient direction ∇U with added Gaus- sian perturbations. Expectations w.r.t. the target distribution π are estimated by averaging over LMC samples. In ordinary Monte Carlo, it is well known that the estimation error can be substantially reduced by replacing independent random samples by quasi-random samples like low-discrepancy sequences. In this work, we show that the estimation error of LMC can also be reduced by using quasi- random samples. Specifically, we propose to use completely uniformly distributed (CUD) sequences with certain low-discrepancy property to generate the Gaussian perturbations. Under smoothness and convexity conditions, we prove that LMC with a low-discrepancy CUD sequence achieves smaller error than standard LMC. The theoretical analysis is supported by compelling numerical experiments, which demonstrate the effectiveness of our approach. 
    more » « less