Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Pros
- The problem setting is reasonable, that is, assuming a sequence of likelihoods with increasing fidelity are available.

- 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.

- Five different experiments are conducted to demonstrate the proposed method. 

Cons:
- The empirical improvement is incremental.

- The setup of baseline methods is unclear in the experiments. 

In 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.

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. 

It 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. 

By 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.

limitations: The authors have discussion limitations in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
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.

(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. 


questions: 1: Under what conditions does the proposed approach give rise to estimators of finite variance and with finite expected cost?

As 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

\mu(k) * |\pi_k(\theta) - \pi_{k-1}(\theta)| / \mu_k

whose 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.

2: 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?

2: 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 

3: 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.

Typos etc.:
l99: "that may not even inference problems, such as quantum simulations and PDE-constrained optimization problems." is missing a verb: "be" I think.
l180: "I(N=n)" should this read "I(K=k)"?

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.

Some 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

The authors confirm that value of the proposed algorithm through five varied examples and compare their multi-fidelity approach against low and high fidelity alternatives. 
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. 
Quality - The paper is of a good quality and provides a useful, and theoretically justifiable, solution to the problem of estimating parameters with expensive likelihoods. 
Clarity - 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.
Significance - 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. 
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?

- 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. 

The 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

The 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. 

*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.

strengths_and_weaknesses: *Strengths:*
- The paper is well-written and clear
- The method clearly and strongly outperforms its comparisons on all tested benchmarks
- The method is applicable to a large class of problems

*Weaknesses:* (see questions for details)
- The experiments seem to be run on low-dimensional problems only (correct me if I’m wrong)
- 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.

*Typos:*
- 138: fails to
- 143: cite
- 226: and -> an

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. 
- 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. 
- 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. 
- 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. 

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.

I will use the rest of the section to make some high-level remarks. 
- I would increase my score if the reviewers provide good answers to the questions detailed above. More concretely this means:
- 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. 
- 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.
- 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. 
- I want to help where I can. In case something is unclear, feel free to ask follow-up questions.
review_title: null

Meta-review: metareview: In "multi-fidelity" Monte Carlo, a sequence of estimators of increasing cost and quality (in the sense of approximating some, typically intractable, limiting model) are available. The authors define a target distribution on an extended space including both fidelity and model parameters. Then, a Markov chain which targets a distribution over this extended space can recover the marginal of interest.

All reviewers were positive about the work and there seems to be a consensus that the paper is well-written and clear, the method is applicable in a broad setting and demonstrates an advantage in tested benchmarks (albeit perhaps low dimensional),
Reviewer ga3Z raised a valid concern about the mixing time considering the nature of the unbiased estimation methods based on couplings described in section 3. These methods achieve unbiased estimates at the expense of estimation variance and expected running time (time to coupling). The reviewer mentions that this algorithm can still suffer from the same problems that annealing based methods can suffer in terms of mixing. Such limitations should be made explicit in the paper. 

After the rebuttal, I feel that most concerns have been addressed and the paper can be a valuable contribution to Neurips, hence I suggest acceptance.

confidence: Certain
Decision: Accept