Multi-fidelity Monte Carlo: a pseudo-marginal approach
Authors: Diana Cai
Ryan P Adams
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-fidelity modeling
Markov Chain Monte Carlo
multi-fidelity MCMC
pseudo-marginal MCMC

Abstract: Markov chain Monte Carlo (MCMC) is an established approach for uncertainty quantification and propagation in scientific applications.  A key challenge in applying MCMC to scientific domains is computation: the target density of interest is often a function of expensive computations, such as a high-fidelity physical simulation, an intractable integral, or a slowly-converging iterative algorithm.  Thus, using an MCMC algorithms with an expensive target density becomes impractical, as these expensive computations need  to be evaluated at each iteration of the algorithm.  In practice, these computations often approximated via a cheaper, low-fidelity computation, leading to bias in the resulting target density.  Multi-fidelity MCMC algorithms combine models of varying fidelities in order to obtain an approximate target density with lower computational cost.  In this paper, we describe a class of asymptotically exact multi-fidelity MCMC algorithms for the setting where a sequence of models of increasing fidelity can be computed that approximates the expensive target density of interest.  We take a pseudo-marginal MCMC approach for multi-fidelity inference that utilizes a cheaper, randomized-fidelity unbiased estimator of the target fidelity constructed via  random truncation of a telescoping series of the low-fidelity sequence of models.  Finally, we discuss and evaluate the proposed multi-fidelity MCMC approach on several applications, including log-Gaussian Cox process modeling, Bayesian ODE system identification, PDE-constrained optimization, and Gaussian process parameter inference.

Multi-fidelity Monte Carlo: a pseudo-marginal approach
Diana Cai
Ryan Adams
Department of Computer Science Princeton University dcai @cs. princeton. edu
Department of Computer Science
Princeton University
rpa@princeton.edt
Abstract
Markov chain Monte Carlo (MCMC) is an established approach for uncertainty quantification and propagation in scientific applications. key challenge in apply- ing MCMC to scientific domains is computation: the target density of interest is often function of expensive computations, such as high-fidelity physical sim- ulation, an intractable integral, or slowly-converging iterative algorithm. Thus, using MCMC algorithms with an expensive target density becomes impracti- cal, as these expensive computations need to be evaluated at each iteration of the algorithm. practice, these computations often approximated via cheaper, low- fidelity computation, leading to bias in the resulting target density. Multi-fidelity MCMC algorithms combine models of varying fidelities in order to obtain an ap- proximate target density with lower computational cost. In this paper, describe a class of asymptotically exact multi-fidelity MCMC algorithms for the setting where sequence of models of increasing fidelity can be computed that approxi- mates the expensive target density of interest. We take a pseudo-mane marginal MCMC inference that utilizes cheaper, randomized-fided
approach for multi-fidellin unbiased estimator of the target fidelity constructed via random truncation of a telescoping series of the low-fidelity sequence of models. Finally, diseuss and evaluate the proposed multi-fidelity MCMC approach on several applications, in- cluding log- Gagssin Cox process modeling, Bayesian ODE system identification, PDE-constrained optimization, and Gaussian process parameter inference.
Introduction
Simulation and computational modeling play key role in science, enginecring, economics, and many other areas. When these models are high-quality and accurate, they are important for scientific discovery, design, and data-driven decision making. However, the ability to accurately model complex physical phenomena often comes with a significant cost-many models involve expensive computations that then need to be evaluated repeatedly in, for instance, sampling optimization algorithm. Examples of model classes with expensive computations include intractable integrals or sums, expensive quantum simulations [43], expensive numerical simulations arising from partial differential equations (PDEs) [38] and large systems of ordinary equations (ODEs).
In many situations, one has the ability to trade off computational cost against fidelity accuracy in the result. Such a tradcoff might arise from the choice of discretization or the number basis functions when solving PDE, the number of quadrature points when estimating integral. It often possible to leverage nower-fidelity models to help accelerate high-quality solutions, e.g., by using multigrid methods [23] for spatial discretizations. More generally, multi-fidelity methods combine multiple models varying cost and fidelity to accelerate computational algorithms and have been applied to solving inverse problems [11, 24, 38], trust region optimization [1. 15. 31, 39], Bayesian optimization [8, 21, 27, 28, 41, 45], Bayesian quadrature [17, 46), and sequential learning [22, 35).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

0.25
population size
120
0.05
dt 0.001
AxI
TM
x
1900
1905
1910
1915
1920
year (t)
(a) Trapezoid rule with 21: trapezoids (A: = 1,2,3) (b) Lokta-Volterra ODE solutions, dt = 1/k
Figure 1:
Examples of low-fidelity sequences of models. (a) Sequence trapezoid quadrature estimates Ix. where Is is the trapzoid rule with 2k trapezoids. (b) Lokta-Voltern Volterra ODE solutions for prey u(t) (bluc) and predator (t) (red) using Euler's method with step size dt.
One critically important tool for scientific and engineering computation is Markov chain Monte Carlo (MCMC), which widely used for uncertainty quantification, optimization, and integration. MCMC methods are recipes for constructing a Markov chain with some desired target distribution as the limiting distribution. Pseudo-random numbers used to simulate transitions of the Markov chain in order to produce samples from the target distribution. However, MCMC often becomes impractical for high-fidelity models, where single step of the Markov chain may, for instance, involve numerical simulation that takes hours or days to complete. Multi-fidelityy methods for MCMC focus on constructing Markov chain transition operators that are sometimes able use inexpensive low- fidelity evaluations instead of expensive high-fidelity evaluations. The goal is to increase the effective number of samples generated by the algorithm, given constrained computational budget. A large focus of the multi-fidelity MCMC literature is on two-stage Metropolis-Haatings (M-H) methods [10, 1 14], which use single low-fidelity model for early rejection of proposed sample, thereby often short-circuiting the evaluation of the expensive, high-fidelity model.
However, there are several limitations of two-stage multi-fidelity Monte Carlo. First, in many applications. a hierarchy of cheaper, low-fidelity models is available; for instance, in the case of integration, k-point quadrature estimates form hierarchy of low-fidelity models, and in the case of PDE, varying the discretization. Thus, the two-stage approach does not fully utilize the availability of a hierarchy of fidelities and may be more suitable for settings where the high- and low-fide oow-iieeity models are not hierarchically related, e.g., semi-empirical methods vs. Hartree- Fock in computational chemistry. In addition, in such applications, there often a limiting model of interest, such continuous function that the low-fidelity discretizations approximate. Two-stage MCMC does not asymptotically sample from this limiting target density and will at best sample from an approximation of the biased, high-fidelity posterior. Finally, the two-stage method is unnatural to generalize to more sophisticated MCMC algorithms such as slice sampling and Hamiltonian Monte Carlo (HMC).
We propose a class of multi-fidelity MCMC methods designed for applications with a hierarchy of low-fidelity models available. More specifically, we assume access to a sequence of low-fidelity models that converge to a perffettfidelityy model in the limit. Within an MCMC algorithm, we can approximate the perfect-fidelity target density with an unbiased estimator constructed from randomized truncation of the infinite telescoping series of low-fidelity target densities. This class sosuudo-maggin MCMC (PM-MCMC) algorithm-
of multi-fidelity MCMC an example unbiased estimator essentially guarantees that the algorithm is asymptotically exact in that the limiting distribution recovers the perfect-fidelity target distribution its marginal distribution. Our approach auxiliary random variable that is evolved separately from
introduces the fidelity of model the target variable according to its own conditional target distribution; this technique can be used in conjunction with any suitable MCMC update that leaves the conditional update for the target variable of interest invariant, such as M-H, slice sampling, elliptical slice sampling, or Hamiltonian Monte Carlo. We apply the pseudo- pseudo-marginal marginal multi-fidelic MCMC approach several problems, including log-Gau Gaussian Cox process modeling, Bayesian ODE system identification, PDE-constrained optimization, and Gaussian process parameter inference.
Related work. Multitfidelity MCMC methods are commonly applied in two-stage procedure, where the goal is to reduce the computational cost of using single expensive high-fidelit, model by

---

using a cheap low-fidelity model as a low-pass filter for a delayed acceptance/rejection algorithm [10. 11, 14]: see Peherstorfer et al. [36] for a survey, Higdon et al. [24] propose coupling high- fidelity Markov chain with a low-fidelity Markov chain via product chain. In constrast, our approach aims to sample from a "perfect-fidelity" target density while reducing computational cost; two-stage MCMC algorithms result in biased estimates with respect to this target density. A related class of methods is multilevel Monte Carlo [13, 18, 19, 44], which uses a hierarchy of multi-fidelity models for Monte Carlo estimation by expressing the expectation of high-fidelitt model as a telescoping sum of low-fidelity models. Dodwell et al. [13] use the M-H algorithm to form the multilevel Monte Carlo estimates, simulating from a separate Markov chain for each level of the telescoping sum. In practice multilevel Monte carlo requires choosing a finite number of fidelities, inducing bias in the estimator with respect to the (limiting) perfect-fidelit fidelity model. In contrast, our method uses randomized fidelity within a single Markov chain with the perfect-fidelity model as the target.
Our approach applies pseudo-marginal MCMC to multi-fidelity problems. There is rich literature developing aeeudo-maggine MCMC methods [2, 6] for so-called "doubly-inrractalee" likelihoods, which are likelihoods that are intractable to evaluate. Several approaches in the marggnaa MCMC literature are particular relevant to our work. The first are the PM-MCMC methods introduced by Lyne et al. [30], which describes class of pseudo-marginal M-H methods that use Russian roulette estimators to obtain unbiased estimators of the likelihood. However, this method samples the variable of interest jointly with the auxillary randomness, which often leads to sticking.
Alternatively, several methods have considered sampling the randomness separately. The idea of clamping random numbers is explored in depth by Andrieu et al. [3] and Murray and Graham [33]: the latter applies to this ggeudo-marging slice sampling. In particular, our approach applies these ideas to the specific setting of multi- multi-fidelity models, where the random fidelity is treated as an auxillary variable. Finally, while our approach applies to doubly-intractable problems, we are also motivated by a larger class of multi-fidelity problems studied in the computational sciences that may not even be inference problems, such as quantum simulations and PDE-constrained optimization.
2 Multi-fidelity MCMC
Monte Carlo methods approximate integrals and sums that can be expressed an expectation:
R (h(0)) ( ((0)=(0))))) R T EEMO))
where
000) n,
and where т. O + R4 is the target density that may only be known up to a constant, h(0) is a function of interest, and {0(t)] are samples from т. Markov chain Monte Carlo methods are then used to generate samples g(t) from π by simulating from a Markov chain with target и.
In many settings, pointwise evaluations of the target function t (0) are expensive or even intractable; from here on we will assume that the goal is to compute statistics of quantity of interest h(0) with respect to perfect-fideling target density oo (0). In practice, the estimate in Equation (1) is instead estimated using a cheaper, low-fidelity density (0), where l E N == {1, ......... .). consider settings where there is sequence of low-fidelity densities available that converge to the
In particular, we
target, i.e., TT& k=3 xo (f). We assume that as increases, the model becomes higher in fidelity (with respect to ) but more costly to evaluate, increasing in expense super-linearly with k.
For instance, Too could represent a target density that depends on an intractable integral, the solution of PDF, the solution of a large system of ODEs, the solution of large system of linear equations, or the minimizer of a function. Thus, a typical evaluation of Too requires an approximation at a fidelity A with tolerable level of bias for a given computational budget. Here increasing k could correspond to finer discretizations of differential equations, increasing numbers of quadrature points, or performing a larger number of iterations in linear solver or optimization routine.
In the multi-fidelity setting, the goal is to combine several models of varying fidelity within an MCMC algorithm to reduce the computational cost of estimating Equation (1). In this paper, we describe a class of MCMC algorithms that leverages the sequence of low-fidelity models T&. Our strategy for multi-fidelity MCMC (MF-MCMC) will be to construct an unbiased estimator of noo (0) using random choices of the fidelity K and then to include K in the Markov chain as an auxiliary variable. By carefully constructing such Markov chain, it will be possible to asymptotically estimate the
3

---

functional in Equation (1) as though the samples were taken from the perfect-ideelity model: each step of the Markov chain will nevertheless only require a finite amount of computation. Finally, our approach allows us to essentially plug in any valid MCMC algorithm, and we apply this strategy to develop multi-fidelin fideliifi variants of number of MCMC algorithms, such as M-H and slice sampling.
2.1 Pseudo-marginal MCMC for the multi-fidelity setting
Sseudo-marginal MCMC [2. 6] is class of auxillary-variable MCMC algorithms that replaces the target density (0) with an estimator (0) that is function of a random variable. If the estimator is nonnegative and unbiased, i.e., for all @ E O, =()) 2 0 and [()] x (0), then MCMC transitions that use the estimator still have (0) as their invariant distribution. This property is sometimes referred to as "exact-approximate" MCMC as the transitions are approximate but the limiting distribution is exact. Estimators can be constructed from a variety of methods, including particle filtering [2]; our approach will use randomized series truncations, which has been consider in pseudo marggnall MCMC methods such as Lyne et al. [30], Georgoulas et al. [16]. and Biron-Latted et al. [7].
We now apply the pseudo-marge estimator arises from a random choice of the fidelity K E N that is governed by a distribution j on N. We denote the estimator using Rx (0) to make the dependence on the random fidelity K explicit. The estimator is constructed such that it unbiased with respect to jr, i.e.
approach to the multi-fidelity setting. Here the target density
(k))+x = πl (0).
(0).
The distribution y is also constructed by the user: ideally, the estimator मx (0) will prefer smaller values of K while having sufficiently low variance as to allow the Markov chain to mix effectively. Thus the simulations can be run at inexpensive low-fidelities, while the estimates will be as though the crffect-fidelity model were being used.
The standard gseudo-marging MCMC approach is to construct Markov chain that has the following joint density as its stationary distribution:
T(0, ((K)xx(0))
Observe that while Equation (3) does not depend on the perfect-fidelity target density Too it returns the desired marginal Too via Equation (2). As a concrete example, aseudo-marging M-H algorithm generates a new state and fidelity K" jointly using v(0':)) as the proposal for 0', q (K'; K) = (KK)) as the proposal distribution for the fidelity, and accepts/rejects the state according to
(6', (0))(0;; 0¹ (K)q K*) a
* (or (0')
(4)
())(") ()((())))))(K)))))
#x (x(0)g(0(:0)
where the equality holds since the distribution terms for K and K' cancel. Note that the right-hand side of Equation (4) is the standard M-H ratio but that the target density a is replaced with the estimator fx.
However, standard greudo-marginal MCMC using joint proposals of the state and fidelity can "get stuck" when the estimator is noisy and fail to accept new states. Thus, we apply the approach in Murray and Graham [33] that augments the Markov chain to include the randomness of the estimator via a separate update; here the randomness of the estimator arises from the fidelity K. Concretely, we construct a Markov chain that simulates from Equation (3) by alternating sampling between the conditional target densities n (0) and π (0]K) (steps 5 and 6 of Algorithm 1, respectively). We refer to this strategy as multi-fidelity MCMC (MF-MCMC), since by conditioning on K = k, the update for the state 0 becomes standard deterministic update applied to a low-fidelity model nu (0), and any appropriate MCMC update can be used here, making it straightforward to use complex MCMC methods, such as slice sampling and HMC. Similarly, any suitable MCMC update for the fidelity K can be used using the conditional target T (K(()
Many techniques can be used to construct an unbiased estimator of Too with randomness K; we describe a general approach in the next section. However, it is generally difficult to guarantee the estimator is nonnegative, as required by pseudo-marginal MCMC. One technique considered by Lin et al. [29] and Lyne et al. [30] is to instead sample from the target distribution induced by the absolute value of the estimator and applying a sign-correction to the final Monte Carlo estimate in

---

Equation (I), an approach borrowed from the quantum Monte Carlo literature where it is necessary for modeling fermionic particles. This approach has been applied to the M-H algorithm, but we note that this general approach can be applied much more broadly, as we do in this work.
In problems where the estimator may be negative, we sample from the conditional target distributions using the absolute value of the estimator | (0), and we denote these conditionals with म (K 10) oc u(K) | (0) and [0 k) (0). The estimate in Equation (1) is then corrected using the signs (0, k) of evaluations of (0),
/ h(()) T(0) dB
EL h0 K(O) Ir. Ei10((00) KW)
(5)
where ((00),))) HT are the sampled values from the joint distribution #0, K) xc [ (K)
Importantly, the sign-corrected estimate still asymptotically leads to the desired estimate of the functional of interest. Let (0, k)) denote the sign of the estimator such that # (0) a0, k) | (0).
The estimator IT in Equation (5) formed using a Monte Carlo estimate of the functional after expanding it into its joint distribution, i.c.,
/ 110)===0))
J2 1()) () k)d0 JE (0, A k)d0
Σ (O)))()))())000
The full multi-fidelity MCMC algorithm with sign correction summarized in Algorithm 1. We note that while the Markov chain no longer converges to target with the marginal Toc. the final estimate after gegn-correction-wiile is the downstream goal of interest-convergee to the quantity of interest due to Equation (6). While this may seem limiting if one is interested in the posterior itself, useful unbiased posterior summaries may be still be obtained via the functional, such as the posterior mean, variance, quantiles, and histograms that may be used to visualize marginal distributions.
3 Unbiased low-fidelity estimators via randomized truncations
In this section, we discuss how construct an unbiased estimator of T (+),, given a sequence of low-fidelity likelihoods with the property Tu Txx(0) (0) + (f) as k + co. This estimator has the property that it requíres finite amount of computation with probability one, and it also has a tunable amount of expected computation per estimate, i.e., it uses low-fidelin density evaluations to estimate the perfect-fidelity target density. The central idea of this estimator has been used for decades, going back to John von Neumann and Stanislaw Ulam. More recently it has found use in applications of inference and optimization related work such as Glynn and Rhee [20], Lyne et al. [30], Beatson and Adams [5], and Jacob et al. [26].
First note that we can express the perfect-fidelity model as a telescoping sum of low-fidelity models: let To (0) = 0 and write
20
oo (8) Σ (((
10).
The estimator म is then constructed by taking random truncation K μ of the infinite telescoping series. The sampled terms in the sum are then reweighted to ensure the estimator remains unbiased:
K
म (0)
(0))
(8)
Two approaches are commonly used to ensure that the resulting estimator is unbiased: weighted single-term estimators and Russian roulette estimators. The single-term estimator [30] is constructed
by importance sampling term from the series in Equation (7): the truncation level is drawn as K ~ μ, and the K Kthh term is used to form the estimate
nx (8) 1a( (Txx kk x
Thus, the weight in Equation (8) is WA,K = (uk)) k). the Russian roulette es- timator, the remaining terms in the estimator reweighted by their survival probabilities,
5

---

Algorithm 1 Multi-fidelity Monte Carlo with sign-correction
1: Input: Initial state and fidelity K, truncation distribution
2: for t = II....,T do
3: Given current K and 0, form estimator *x = Σk K (0) T 1k))
4: Save sign o o0, K) sign(*x(())
5: Update fidelity K leaving invariant the target conditional
म (K]0) (*)) (0)
6: Update state 0 leaving invariant the target conditional
K = k) x |+)(
7: end for
8: Output: Samples {(A()) {(()) and estimate I = -E o()((())))) / (Ei=, o(1)
Le., WE,K = (1 - Σ I ((K))))((K3 2 k). The distribution μ controls the number of terms in
the estimator, and a good proposal distribution should match the tails of the sequence of low-fidelity densities [5, 30, 37].
The ability to use cheaper models is a key feature of multi-fidelity inference, and the low-fidelity estimator provides means to reduce the computational cost of multi-fidelity Monte Carlo. However, these estimators are an example of a class of methods that explores compute-variance tradeoff: computationally cheaper estimates leads to high variability. The resulting increase in variance slows down the convergence of the MCMC procedure and could lead to an overall less efficient method due to reduced effective sample size.
4 Summary of the multi-fidelity MCMC recipe
Here we summarize the recipe for constructing multi-fidelity Markov chain Monte Carlo algorithm.
First, identify a sequence of prreeasingffielliie target densities with the property that their limit is the desired pperfectfidelity" density. Low-fidelity densities should be cheap with the cost rapidly increasing within the sequence. In the context of Bayesian inference, may appropriate the multi-ffdelii aspects on the likelihood term and construct the target densities via, e.g., TV (0; D) x To( (0; D). where Th is the prior, L2 is low-fieeliyy likelihood, and DD is the set observations. This likelihood based version is what we use in several of the experiments.
focus
Next, introduce truncation distribution μ on N. This truncation distribution should be chosen to balance between expected cost and variance of the resulting estimator; our overall goal is to mostly use cheap low-fidelity densities, but high-variance estimators will presumably damage the mixing time and/or the asymptotic variance.
Initialize the Markov chain with reasonable choice for 0 and draw of K from the distribution Each step of the Markov chain simulation consists of an update to 9 given K and an update of K given 0. The update of 0 given K can be performed using any standard MCMC algorithm, e.g., M-H, slice sampling, or HMC, applied to the low-fidelity estimator. It is important to use the absolute value of the estimator and keep track of its sign. The update of K given 0 is also flexible, but it is reasonable to construct the update so that only a few K are considered in each step, as each of those fidelities will need to be evaluated. By default, we consider a simple random walk on the positive integers for our experiments. After running a sufficient number of steps of the Markov chain, use the sign corrected-estimator in Equation (5) to compute the expectation of the function (0)..
5 Experiments
In all experiments, we use a random-walk M-H update to sample from the conditional K00, and truncation distribution μ u(K) geometric(KK; (o). Additional experimental details are in Appendix F.

---

K- 1003 K= 100
0.055
Postorter standard civistion
15%
5F K-1000
... TSK-100
0-0
1-10000
MF 0.05
deniity
density
30-1
3.5
1.0
30
15"
Number cost-edjusted licelihood eveluctions
(a) Two-stage MH
(b) Multi-fidelity MH
(c) MH sampler estimate
180
y- 0:05
Pusterior standard desision
10
K0 SF K- 100
v 001
X-=
ym 0.3
30
0.05
deraty
dersty
20
10
0.5
1.0
3.5
1.0
1.5
10'
10'
10
10"
10"
Number of cost adjusted likelinod evallations
(d) Single-fidelity slice
(c) Multi-fidelity slice
(f) Slice sampler estimate vs cost
Figure 2: Conjugate Gaussian model. Left: Histograms for M-H (a.b) and slice sampling (d,e). Right:
Comparison of posterior standard deviation estimate vs computation for M-H (c) and slice sampling (d) methods. Average posterior mean computed over 4 different chains.
5.1 Toy conjugate Gaussian models
In order to understand the behavior of MF-MCMC on a simple example of Bayesian inference, we first examine an example where the computational cost of evaluating the sequence of low-fidelity
likelihoods does not increase with k. Consider a perfect-fideltty likelihood (0) = -< 0, xo) and low- wwwfiideitty likelihood (+) ((;; 0, ox). where of - o² The prior is (o)) = (6 1). and so a closed-form posterior density can be computed. Here we consider the sequence o 1+2/k2 and d² = 1. In Figure 2 we compare the results single-fidelit, and fultii-ideeiity M-H and slice sampling well the two-stage M-H algorithm summarized in Appendix C.4. We consider two-stage M-H settings with high and low fidelities of {I+HF XLF) = { {1000, 10) and (I#HP [ (100, 5]. The histograms show the bias of each method after simulating 10,000 samples, and the solid gray curve denotes the exact posterior density. We also compute a measure of total cost and running average of the estimate the posterior standard deviation functional, where the dotted black line denotes the true value. The number of cost-adjusted likelihoods was computed by upweighting each likelihood evaluation by the fidelity. Here the multi multi-fidelity methods typically converge similar value as the single high-fidelit methods but in fewer cost-adjusted likelihood evaluations.
5.2 Log-Gaussian Cox processes
We examine an application of MF-MCMC the log Gaussian Cox process (LGCP) model [32], where the perfect-fidelity model is a function of an integral and the lower-fidelity sequence of models arises from k-point quadrature estimates. Let log GP rz). where ke(2,, x²) exp (- 7 | x 112) and where & is lengthseale hyperparameter. Consider an inhomogenous Poisson process on X R with intensity X(x) ed()) Given random set of points {Xn)) the perfect-fidelity likelihood is
N
Lx( = exp
II ==1
(X.))
(10)
Typically, inference in the LGCP uses grid-based approximation of Equation (10), where the
points are binned into counts and modeled with a Poisson likelihood [12, 34, 42], resulting in biased posterior. Because the likelihood depends on a high-dimensional latent Gaussian vector, we perform inference for f using the elliptical slice sampling (ESS) algorithm (see Appendix C.3). We approximate the integral Equation (10) with a trapezoidal quadrature rule J, where the number of quadrature points is linear function of k.
7

---

Posterion mean of rate
SF-E5S < 100
SF SFESS k 1000
10"
1=
100 k-
MF-ESS
188 80
10
10"
10
10
101²
3950
Number of cost adjusted likelihodd evalustions
Figure 3: Coal mining disasters Left: Posterior mean of the rate function at the observed data points. Right: Posterior of the rate function at ' 1862 computation.
SF di - 1 10-3
SF dt= 1 10 MF-E5E
population
1900
1805
1910 it
1915
1920
(a) Sampled posterior trajectories under fixed computational budget
SF dt 1 10-5
Posterior meat
10a
mean
10-1
MP-ESS
0x
4x10-
10
10'
107
Wellclock (5)
Wellclock (9)
6 6x10-2
mean
Posterior
4x10-
10a
3x10
9x00
8x-10-1
Wallclock (s)
Wallclock (5)
(b) Posterior mean estimate computational cost
Figure 4: Lokta-Volterra system parameter identification. The fidelity represents (a function of) the step size dt of the ODE solver.
We apply multi-fidelity and single-fidelity ESS algorithms coal mining disasters data set (Carlin et al. (9)). The data contain the dates of 191 coal mine explosions that killed ten or more men in Britain between March 15, 1851 and March 22, 1962. Figure 3 (left) shows the estimated mean intensity and standard deviation on coal mining disasters data between one run of multi-fidelity ESS and single-fidelity ESS with 10, 100, 1000 quadrature points. In this plot, the high- (k 1000) and multi-fidelity posterior mean and standard deviation estimates match well, and the bias in the lowest fidelity (k 10) estimate is apparent. We also computed the cost- cost-adjusted number of likelihood evaluations performed in each iteration of MF-ESS and SF-ESS. Figure 3 (right) shows the average estimated mean intensity the time step 1862 on the three models against the average cost-adjusted number of likelihood evaluations per iteration. We observe that the multi multi-fidelity and high-fidelity estimates are close after many iterations of sampling, but that the multi-fideliy estimate converges with less computation.
5.3 Bayesian ODE system identification
We now apply the MF-MCMC approach to Bayesian system identification for the Lotka-Von Volterra ODE. Let u(t) 2 0 represent the population size of the prey species at time and u(t) 2 0 represent the population size of the predator species. The dynamics of the two species given parameters a, 1,8 2 0 are given by pair of first-order ODEs:
d
(a - Be)u au Buv,
= (-7- -u.v -yv -uv.
(11)
dt
dt

---

10"1 4x=1xx 10
5x
10
MF Yo 0.225
10
MF Yo 0.1
10"
10A
30
Wallclock 1s1
Wallclock (s)
Figure 5: PDE-constrained optimization with linear heat equation. Estimate for a (left) and / (right) vs computation. The black dotted lines denote the true values of 3.
System identification solves the inverse problem by estimating the parameters of the ODE system 0 == (a, 7,7, 6). Taking a Bayesian approach, we specify a noise model for the observed data and priors the parameters, and we assume that the initial conditions are known and fix a = 0.25.
MCMC to infer a distribution over the solution. For simplicity,
(0) be the solutions to the Lotka- Volterra differential equations at times fi....,ty given the initial conditions and the system parame- ters 0 = (a, 3, 7. Suppose we have observations arising from log(y,) log(2n) (nn) En. where c N(0, I² ). The low-fidelity likelihood a function numerical solution of the ODE using a time step of size dt (Equation (F.3)). We compared the performance of multi-fidelie
Define 2n
(u(tn); v(t,)) and let 21 20))......
elliptical slice
sampler to single-fidelity ellipitical slice samplers with step size dt = 1 x 10-5, 1 x 10 For the considered both an Euler solver and an 4th-order Runge- Kutta solver (Figure F.I).
ODE solver, Figure 4a shows 200 trajectories corresponding to parameters sampled from the posterior distributions under each method using the Euler solver. Figure 4b shows posterior mean estimates for each system parameter. We observe that the estimates from the multi-fidelity slice sampler approach the estimates reported by Howard [25] (black dotted lines) in less time than the single-fidelity samplers.
5.4 PDE-constrained optimization
We now consider global optimization of PDE-constrained objective, where expensive physical simulation is run repeatedly in an outer loop problem. A common approach for global optimization is simulated annealing, which has been applied to constrained global optimization [40]. Consider model for heat flow in a thin rod of length with spatial coordinates x [0, LJ. Let (2x, represent the temperature in the rod at position and time t, and let represent desired target temperature. The goal is to minimize loss function subject to u satisfying a linear heat equation. This objective along with initial condition and homogenous boundary conditions can be summarized as:
minimize, ||u
1
du
8P
subject
23
(12)
Or?
u (x, 0) = sin (Tx/2),
(0, t) u(L,t) =0 x x 1), e [0,T],
where a, are the system parameters. The goal is to find (a, 3) that minimizes the objective and satisfies the constraints. To solve the PDE, we discretize the domain into grid of size Ar and represent the second derivative using the central difference formula. This induces a system ODEs that we solve numerically using a Tsitouras 5/4 Runge- Kutta method, setting At = 0.4Ar² so as to satisfy CFL stability condition. Here the fidelity the problem is given by the size of the spatial discretization Az, which in turn controls At. We compared against two single-fidelity discretizations of the spatial coordinate, where Az x 10 3 x 12-2, The results are Figure 5, where we plot two of the MF results with To = 0.1, 0.25. In these examples, the multi-fidelity estimates converge faster than the finll-fidelity estimates in wallclock time.
5.5 Gaussian process regression parameter inference
Let X E ND and consider Gaussian process regression model with a squared exponential kernel:
~ GP(O,ko), y f(x) +c, e~ N((, ko(x, = exp (- (-2ge
1
20² ||
x 113 (13)

---

0.12
0.00
0.08
*x100
HF MH Yo -
HF- MF-MI
0.04
0.04
LF-HH
HF-MH
LF-MH
0.00
MF
30
35
40
50
55
30
35
50
10
10P
167
10"
155
10"
Number cost-edj.sted likelhood evalutions
(a) Histograms of high, low, two-stage, and multi-fidelit
(b) Posterior mean estimate computation
Figure 6: Parameter inference in Gaussian process regression model. Left: The posterior distribution of the
parameter 0. Right: The posterior mean estimate computional cost.
where we assume of is known. Let Eg == (ko (Zi, Try ( [
In many applications of Gaussian process modeling, one is interested in integrating out the parameters I using MCMC. Computing the posterior x( is expensive because each evaluation of the likelihood p(y X, 0) = N 0, Eg + o involves computing determinant and solving linear system with respect the matrix Eg ogL, which has an O(N3) computational cost associated with standard methods ge.g., Cholesky decomposition). For simplicity, we will only consider the fidelity of solution the linear system, but we note that the determinant can considered using the approach described in Potapczynski et al. [37]. Additional derivations and details are in Appendix F.5.
We generate synthetic data from the GP model with N 100, o 1, and lengthscale 8 45. For the GP model, we use a log Normal prior on 0 given above in Equation (F.5) with parameters Po 3.8, / 0.03. In Figure 6, we compare these approaches using single-fidelity, multi-fidelit fideliiyyytyy and two-stage M-H samplers. The low-fidelity likelihood sequence was constructed by computing the solution the linear system using a preconditioned conjugate gradient solver with steps. The single-fidelity likelihoods were high-fidelity likelihood (k: N) and a low-fidelity likelihood (k: = KN < N), and the multi-fidelity M-H samplers used to = 0.1. The two-stage M-H approach used high and low fidelities of & {100, 5}. For all methods. we use M-H sampler with T 50000 iterations. In the histograms, we observe that the high- rideliiyyttty, multi-fidellin and two-stage approaches tend to lead to similar posteriors, while the low-fidelity sampler has more noticable bias with respect to the
histogram. The estimate produced by the multi-fidelity samplers converged in fewer cost-adjusted likelihood evaluations than the high-fidelity and two-stage approaches.
6 Discussion and future work
In this work, we introduced a class of multi-fidelity MCMC that uses a low-fidelity unbiased estimator reduce the computational cost of sampling while still maintaining the desired limiting target distribution of the Markov chain. In particular, we have demonstrated the use of our framework on more advanced MCMC algorithms beyond M-H, such as slice sampling, and to additional settings such as optimization. Our results show a reduction in computation while producing accurate solutions in comparison with high-fidelity models when it is possible construct a target estimator that is not too noisy. Many future directions remain. First, applying MF-MCMC to large-scale expensive applications has many computational challenges. Making the method more robust to specialized problems is important, especially if the estimator is heavy-tailed. Thus, constructing good proposal distributions matching properties of the low-fidelity target sequence crucial, especially for application to high-dimensiioal problems. In addition, we have thus far focused target densities where there is a single computation whose fidelity varied. However, in many settings, there may be target densities with multiple computations that converge at different rates, for example, if the target density includes both an intractable integral and a solution of a linear system. Our framework can be extended to that setting by adjusting the proposal distribution, and it is useful to understand how these rates impact the convergence properties of the sampler.
Acknowledgments and Disclosure of Funding
This work was partially supported by NSF grants IIS-2007278 and OAC-2118201. D. Cai was supported in part by Google Ph.D. Fellowship in Machine Learning.
10

---

References
[1] N. M. Alexandrov, J. E. Dennis, R. M. Lewis, and V. Torczon. A trust-region framework for managing the use of approximation models in optimization. Structural optimization, 15(1): 16-23, 1998.
[2] C. Andrieu and G. O. Roberts. The maruda-marginal approach for efficient Monte Carlo computations. The Annals of Statistics, 37(2)697-725,, 2009.
[3] C. Andrieu, A. Doucet, and R. Holenstein. Discussion of "Particle Markov chain Monte Carlo methods". Journal of the Royal Statistical Society: Series B (Statistical Methodology), 72(3): 269-342, 2010.
[4] E. Arian, M. Fahl, and W. Sachs. Trust-region proper orthogonal decomposition for flow control. In IEEE Conference on Decision and Control, 2000.
[5] A. Beatson and R. P. Adams. Efficient optimization of loops and limits with randomized telescoping sums. In International Conference on Machine Learning, pages 534-543. PMLR, 2019.
[6] M. A. Beaumont. Estimation of population growth or decline in genetically monitored popula- tions. Genetics, 164(3):1399-1166 2003.
[7] M. Biron-Lattes, A. Bouchard-Côté, and T. Campbell. Pscudo-marginal inference for CTMCs on infinite spaces via monotonic likelihood approximations. Journal of Computational and Graphical Statistics, 2022.
[8] L. Brevault, M. Balesdent, and A. Hebbal. Overview of Gaussian process based multi-fidelity techniques with variable relationship between fidelities. arXiv preprint arXiv:2006.16728, 2020.
[9] B. Carlin, A. E. Gelfand, and A. F. Smith. Hierarchical Bayesian analysis of changepoint problems. Journal of the Royal Statistical Society: Series C (Applied Statistics), 41(2):389-405, 1992.
[10] A. Christen and C. Fox. Markov chain Monte Carlo using an approximation. Journal of Computational and Graphical Statistics, 14(4):795-88 7900100, 2005.
[11] T. Cui, Y. M. Marzouk, and K. E. Willcox. Data-driven model reduction for the Bayesian solution of inverse problems. International Journal for Numerical Methods Engineering, 102 (5):966-990) 2015.
[12] J. Diggle, P. Moraga, B. Rowlingson, and B. M. Taylor. Spatial and spatio-temporal log- Gaussian Cox processes: extending the geostatistical paradigm. Statistical Science, 28(4): 542-563, 2013.
[13] T. Dodwell, C. Ketelsen, R. Scheichl, and A. L. Teckentrup. A hierarchical multilevel Markov chain Monte Carlo algorithm with applications uncertainty quantification in subsurface flow. SIAM/ASA Journal on Uncertainty Quantification, (():1075--118, 2015.
[14] Y. Efendiev, T. Hou, and W. Luo. Preconditioning Markov chain Monte Carlo simulations using coarse-scale models. SIAM Journal on Scientific Computing, 28(2):776-803, 2006.
[15] M. Fahl and E. Sachs. Reduced order modelling approaches PDE optimization based on proper orthogonal decomposition. In Large-scale PDEE-constrained Optimization, pages 268-280. Springer, 2003.
[16] A. Georgoulas, J. Hillston, and G. Sanguinetti. Unbiased Bayesian inference for population Markov jump processes via random truncations. Statistics and Computing, 2711) 2017.
[17] A. Gessner, J. Gonzalez, and M. Mahsereci. Active multi-information source Bayesian quadra- ture. In Uncertainty in Artificial Intelligence, pages 712-721. PMLR, 2020.
[18] M. Giles. Multilevel Monte Carlo path simulation. Operations Research, 56(3):607-617, 2008.

---

[19] M. B. Giles. Multilevel Monte Carlo methods. Monte Carlo and Quasi-Monte Carlo Methods, pages 83-103, 2013.
[20] P. W. Glynn and C.-h. Rhee. Exact estimation for Markov chain equilibrium expectations. Journal of Applied Probability, 51(A)::377339, 2014.
[21] R. B. Gramacy and H. K. Lee. Adaptive design and analysis of supercomputer experiments. Technometrics, 5 51(2)130-144, 2009.
[22] G. W. Gundersen, D. Cai, C. Zhou, B. E. Engelhardt, and R. P. Adams. Active multi-fidelity Bayesian online changepoint detection. In Uncertainty in Artificial Intelligence, pages 1916- 1926. PMLR, 2021.
[23] W. Hackbusch. Multi grid methods and applications, volume 4. Springer Science & Business Media, 2013.
[24] D. Higdon, H. Lee, and Z. Bi. A Bayesian approach to characterizing uncertainty in inverse problems using coarse and fine-scale information. IEEE Transactions on Signal Processing, 50 (2):389-399) 2002.
[25] Howard. Modeling basies. Lecture Notes for Math 442, 2009.
[26] P. E. Jacob, J. O'Leary, and Y. F. Atchadé. Unbiased Markov chain Monte Carlo methods with couplings. Journal of the Royal Statistical Society: Series (Statistical Methodology), 82(3): 543-600, 2020.
[27] D. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455-49) 1998.
[28] S. Li, W. Xing, R. Kirby, and S. Zhe. Multi-fidelity Bayesian optimization via deep neural networks. Advances in Neural Information Processing Systems, 33:8521-8531, 2020.
[29] L. Lin, K. Liu, and J. Sloan. A noisy Monte Carlo algorithm. Physical Review D, 61(7):074505, 2000.
[30] A.-M. Lyne, M. Girolami, Y. Atchadé, H. Strathmann, and D. Simpson. On Russian roulette estimates for Bayesian inference with doubly-intractable likelihoods. Statistical Science, 30(4): 443 467, 2015.
[31] A. March and K. Willcox. Constrained multifidelity optimization using model calibration. Structural and Multidisciplinary Optimization, 46(1):93-109, 2012.
[32] Møller, A. Syversveen, and R. Waagepetersen. Log Gaussian Cox processes. Scandina- vian Journal of Statistics, 25(3):451-482 1998.
[33] I. Murray and M. Graham. Decudo-arggnnal slice sampling. In Artificial Intelligence and Statistics, pages 911-919. PMLR, 2016.
[34] I. Murray, R. Adams, and D. MacKay. Elliptical slice sampling. In Artificial Intelligence and Statistics, pages 541-548. PMLR, 2010.
[35] A. Palizhati, S. B. Torrisi, M. Aykol, S. K. Suram, J. S. Hummelshoj, and J. H. Montoya. Agents for sequential learning using multiple-fidelity data. Scientific Reports, 12(1):1-13, 2022.
[36] B. Peherstorfer, K. Willcox, and M. Gunzburger. Survey of multifidelity methods in uncertainty propagation, inference, and optimization. SIAM Review, 60(3):550-591, 2018.
[37] A. Potapczynski, L. Wu, D. Biderman, G. Pleiss, and J. P. Cunningham. Bias-free scalable Gaussian processes via randomized truncations. In International Conference on Machine Learning, pages 8609-8619, PMLR, 2021.
[38] M. Raissi, P. Perdikaris, and G. F. Karniadakis. Inferring solutions of differential equations using noisy multi-fidelity data. Journal of Computational Physics, 335:736-7465 2017.
12

---

[39] T. Robinson, M. S. Eldred, K. E. Willcox, and R. Haimes. Surrogate- optimization using multifidelity models with variable parameterization and corrected space mapping. AlAA journal. 46(1 1:28144-8222, 2008.
[40] H. E. Romeijn and R. L. Smith. Simulated annealing for constrained global optimization. Journal of Global Optimization, 5(2):101-126, 1994.
[41] J. Song, Y. Chen, and Y. Yue. A general framework for multi-fidelitg Bayesian optimization with gaussian processes. In The 22nd International Conference Artificial Intelligence and Statistics, pages 3158-3167. PMLR, 2019.
[42] M. Teng, F. Nathoo, and T. D. Johnson. Bayesian computation for Log- Gogg-Gussian Cox processes: A comparative analysis of methods. Journal of Statistical Computation and Simulation, 87(11): 2227-2252, 2017.
[43] M. Troyer and U.-J. Wiese. Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations. Physical Review Letters, 94(17): 70201, 2005.
[44] D. Warne, T. Prescott, R. E. Baker, and M. J. Simpson. Multifidelity multilevel Monte Carlo to accelerate approximate Bayesian parameter inference for partially observed stochastic processes, arXiv preprint (rXxv:2210.140855 2021.
[45] Wu, S. Dascano-Palmerinn P. I. Frazier, and A. G. Wilson. Practical multi-fidelity Bayesian optimization for hyperparameter tuning. In Uncertainty in Artificial Intelligence, pages 788-798. PMLR, 2020.
[46] X. Xi, F-X. Briol, and M. Girolami. Bayesian quadrature for multiple related integrals. In International Conference on Machine Learning, pages 5373-5382. PMLR, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss this in the discussion section.
(c) Did you discuss any potential negative socictal impacts of your work? [Yes] We include section in Appendix G
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We provide details in Appendix
(b) Did you include complete proofs of all theoretical results? [Yes] We provide details in Appendix E
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as URL)? [Yes] See Appendix
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Yes, see Appendix F for full details.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The plots are generated over multiple random seeds.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix F
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
13

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "jWRKQ3FVDUd", "reviewer": "Reviewer_ga3Z", "summary": "The paper process an alternative approach to what it terms \"multi-fidelity\" Monte Carlo in which a sequence of estimators of increasing cost and quality (in the sense of approximating some, typically intractable, limiting model) are available. The main innovation of the proposal is to define, explicitly, a target distribution on an augmented space including both a fidelity index parameter and the model parameters of interest. Having done this it is possible to run a Markov chain which targets a distribution over the joint space in order to extract the marginal of interest.", "questions": "1: Under what conditions does the proposed approach give rise to estimators of finite variance and with finite expected cost?\n\nAs written (5) in the case of single-term estimators (which I specialise to here simply because they simplify the presentation) combined with the sign correction described in line 160 gives a target distribution over k, \\theta proportional to\n\n\\mu(k) * |\\pi_k(\\theta) - \\pi_{k-1}(\\theta)| / \\mu_k\n\nwhose marginal distribution of k is consequently determined entirely by the normalizing constant of |\\pi_k - \\pi_{k-1}| and is well defined only if these normalizing constants are summable -- and, indeed, seems independent of the choice of \\mu although the situation is more complex in the Russian Roulette setting favoured in the experiments. Is that correct? If so some discussion seems appropriate, the manuscript reads as though \\mu is the marginal distribution of K under the target distribution but that seems not to be the case unless I'm misunderstanding.\n\n2: Evaluating (5) seemingly requires that one has access to the normalized \"posterior\" associated with each fidelity approximation: if one substituted unnormalized quantities in here then the argument doesn't seem to continue to hold. If one took the single term estimator and used unnormalized forms of the individual terms then the weighting described in Q1 would be different, typically, in different terms and so you'd end up with a target that does not have \\pi_\\infty as a marginal. Is that correct? How is that dealt with in practice?\n\n2: Is the fact that one sees good performance in experiments due to the fact that the target distribution has light enough tails in k to keep the cost under control but heavy enough ones to keep the estimator variance finite in the examples studied, or is it just a consequence of the fact that the Markov chain hasn't run for long enough to start a long excursion into a region of the space for which \n\n3: It would be helpful to state explicitly the target distribution of the Markov chain somewhere prominent in the manuscript, it took me quite some time to (I think) understand what's going on and I think the readership could be expanded somewhat if this was made clearer. That is, the |\\hat\\pi_k(theta)| which appears in the target might profitably be expanded to illustrate how the complications with normalizing constants are addressed.\n\nTypos etc.:\nl99: \"that may not even inference problems, such as quantum simulations and PDE-constrained optimization problems.\" is missing a verb: \"be\" I think.\nl180: \"I(N=n)\" should this read \"I(K=k)\"?\n", "limitations": "Appendix G touches on societal implications but given the nature of the paper I'm not sure that it adds much to the manuscript; no more seems required.\n\nSome of my questions hint at what seem to me to be limitations which have not been discussed, but it is possible that I have misunderstood.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Seemingly, the proposed approach addresses some of the issues which arise when implementing methods based around telesoping sums in practice, particularly that it is often impossible to define a distribution over the index parameter which gives rise simultaneously to finite variance and finite expected running cost. There are some details that I haven't found completely transparent but I think I've managed to understand the main ideas.\n\n(2) looks different to the usual description of multi-fidelity models at first glance, but this turns out to be because the $\\hat\\pi_k$ here is not a probability but rather than estimator of the form in (5) which is signed and will not typically integrate to 1. This is perhaps a little confusing and could be clarified. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fe8eMmsrCgE", "reviewer": "Reviewer_xJ5d", "summary": "“Multi-fidelity Monte Carlo: a pseudo-marginal approach” presents an approach to MCMC that converges faster than many common alternatives. It presents an unbiased estimator for multi-fidelity settings that can be used to construct an MCMC algorithm. The only requirement is that the problem can be written as a sequence of increasing-fidelity target densities. \n\nThe authors then show their approach in 5 different experiments on different problems requiring different solution approaches, thereby demonstrating the flexibility of their method. In all cases, the multi-fidelity approach converges much faster than a high-fidelity approach but always finds a solution that is similar in quality to the alternatives. In these experiments, the multi-fidelity approach seems strictly superior to its alternatives. \n\n*UPDATE*: thanks for addressing all of my concerns. I still vote to accept the paper. Furthermore, I feel like the concerns of other reviewers were well addressed or only minor compared to the benefits of the paper and they thus did not reduce my score.\n", "questions": "Please note that I prefer honest answers over answers that prefer the method in the best possible light. If there is a limitation, I’d rather have that stated in the paper and it will not reduce my score. \n- Scale: The five experiments you show demonstrate the method can be applied to a host of problems. However, all problems seem like very low-dimensional problems to me (e.g. less than 5D). I would be interested in whether the method also scales to higher-dimensional problems. If the efficiency gains seen in lower dimensions would translate to higher dimensions this would be a major upside of the method and should be worked out. In case it doesn’t scale, it would be interesting to understand why. \n- Space of applications: Your method can be applied to all problems that can be phrased as a sequence of increasing-fidelity densities. You already demonstrate that this includes a wide variety of problems in your experiments but I’m not sure how many problems can be phrased like that. Two sentences on which kind of problems this entails would be helpful to me and readers who are new to the field. \n- Complexity of application: If I understand correctly, you have to a) find a way to write your problem as a sequence of increasing-fidelity densities, then b) introduce a proposal distribution and c) use equation (3) to compute the expectation. This seems like a very simple procedure that can be applied easily without much new derivation or background knowledge that would only change a few lines of code from a high-fidelity implementation. My question is then: is it really that simple? If that is the case, this could be a major strength of the method and should be emphasized. \n", "limitations": "The paper discusses some limitations implicitly by pointing out the assumptions of the method. It also explicitly points out some limitations in the conclusion and future work section. I think it is good that the authors explicitly state the limitations.\n\nI will use the rest of the section to make some high-level remarks. \n- I would increase my score if the reviewers provide good answers to the questions detailed above. More concretely this means:\n- a) Provide clarity on whether the method scales to larger settings. In case it doesn’t I would be interested in hypotheses on why it doesn’t. \n- b) More clarity on the space of applications. Two sentences listing different possibilities or a general idea of how many problems can be phrased for your method to work are sufficient.\n- c) A general idea of the complexity of the method. Very non-technical answers such as “it requires 5 lines of code to change a high-fidelity method to a multi-fidelity method” or “We expect it would take a subject-matter expert X hours to change their algorithm to multi-fidelity” are sufficient. \n- I want to help where I can. In case something is unclear, feel free to ask follow-up questions. \n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n- The paper is well-written and clear\n- The method clearly and strongly outperforms its comparisons on all tested benchmarks\n- The method is applicable to a large class of problems\n\n*Weaknesses:* (see questions for details)\n- The experiments seem to be run on low-dimensional problems only (correct me if I’m wrong)\n- I’m not sure how large the class of problems the method could be applied to is exactly and how easily it is applicable to new problems.\n\n*Typos:*\n- 138: fails to\n- 143: cite\n- 226: and -> an\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UtLE0huSXEk", "reviewer": "Reviewer_RpwA", "summary": "This paper proposes a new MCMC algorithm to simulate from a posterior distribution in settings where calculating the likelihood function is computationally expensive. The authors propose a pseudo-marginal based MCMC algorithm which reduces the computational cost of calculating the expensive likelihood by using lower fidelity approximations. The proposed algorithm has the advantage that, via the pseudo-marginal structure, is asymptotically exact in the sense that samples generated from the algorithm will be from the \"perfect-fidelity\" limiting distribution.\n\nThe authors confirm that value of the proposed algorithm through five varied examples and compare their multi-fidelity approach against low and high fidelity alternatives. ", "questions": "- In the paper the authors state, \"*The full multi-fidelity MCMC algorithm with sign correction summarized in Appendix A. We note that while the Markov chain no longer converges to the target, $\\pi$  but instead an absolute value target density, the final estimate after sign-correction is unbiased, which is ultimately the downstream goal of interest.*\" Can the authors prove this statement?\n\n- In Section 4 the authors state, \"*Next, introduce a proposal distribution $\\mu$ on the positive integers. This proposal distribution should be chosen to balance between expected cost and variance of the resulting estimator; our overall goal is to mostly use cheap low-fidelity densities, but high variance estimators will presumably damage the mixing time and/or the asymptotic variance.*\" It wasn't clear to me how a user should choose this distribution. Could some guidance be given?", "limitations": "The authors address some of the limitations of their approach in the Discussion and Future Work section. \n\nThe authors only discuss MCMC-type approaches as alternatives to their methodology. I'm not very familiar with the multi-fidelity literature, however, from this paper it appears that a limited range of alternative approaches has been considered. For example, the authors do not discuss Gaussian process-based approaches, such as GP emulation or Bayesian optimisation. Therefore, I think it would be helpful if the authors were able to consider their work in the broader context of this field of research. There's also a related literature on multi-level Monte Carlo which seems to be missing.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality - The proposed methodology extends on the more traditional delayed-acceptance type approach to the expensive likelihood problem. The authors utilise a pseudo-marginal scheme which is commonly applied in the literature when dealing with intractable likelihood problems. \nQuality - The paper is of a good quality and provides a useful, and theoretically justifiable, solution to the problem of estimating parameters with expensive likelihoods. \nClarity - The paper is very clearly written and the supplementary material provides some additional details which would be helpful to users wishing to use this algorithm. A small area of improvement that the authors could consider would be to include an algorithm box in the main paper to make it a little easier for the reader to understand the algorithm.\nSignificance - The paper addresses an important problem in the literature, where evaluating expensive likelihood functions for increasingly complex models is a growing issue. However, the experimental section doesn't completely push the boundary on the class of expensive models. The examples used in the paper are nice in the sense that they are simple enough for the reader to understand, but are perhaps not sufficiently complex that a multi-fidelity pseudo-marginal MCMC approach would be essential for inference. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6ApBn89smJP", "reviewer": "Reviewer_G3Z4", "summary": "This paper introduces a muti-fidelity MCMC algorithm for the setting where a sequence of likelihoods with increasing fidelity are available. The authors use pseudo-marginal MCMC and construct an unbiased estimation for high-fidelity likelihood by randomized truncation of a telescoping series. In theory, the proposed method can converge to the target distribution asymptotically. In practice, several tasks including log-Gaussian Cox process, Bayesian ODE system identification, PDE-constrained optimization, and Gaussian process regression, are conducted to demonstrate the effectiveness of the proposed method.", "questions": "In the experiments, the fidelity k was set to be 10 (which is very low) and 1000 (which is very high). I wonder what if we use a proper k, e.g. we can treat k as a hyperparameter and tune it. How is the performance of such single fidelity compared to multi fidelity? My guess is that this single fidelity can also balance the trade-off between bias and variance. How is K in the two-stage methods chosen? I wonder if two-stage methods can perform as well as the proposed multi-fidelity method by tuning hyperparameters. \n\nIt might be better to add a comparison in terms of running time for all tasks. The number of likelihood evaluations may not be a proxy for cost since the cost of evaluating the likelihood in different methods is quite different. \n\nBy looking at the empirical results, the proposed method does not seem to improve the results significantly. Specifically, in Sections 5.1, 5.2, 5.3, and 5.5, the proposed method all performs similarly to previous methods. Only in Figure 5 PDE-constrained optimization, the improvement over baselines seems significant, though it is not clear to which baseline “Delta x” refers to.\n", "limitations": "The authors have discussion limitations in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\n- The problem setting is reasonable, that is, assuming a sequence of likelihoods with increasing fidelity are available.\n\n- As far as I understand, the proposed method is technically sound. One nice property of the method is that it is asymptotically correct whereas previous multi-fidelity methods are not in the setting of an infinite number of increasing likelihoods.\n\n- Five different experiments are conducted to demonstrate the proposed method. \n\nCons:\n- The empirical improvement is incremental.\n\n- The setup of baseline methods is unclear in the experiments. \n\nIn summary, I think the main weakness of this paper is the weak empirical performance of the proposed method. If the authors can demonstrate its strong empirical performance over previous methods, I will consider improving the score.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept