PaperlayerView exact revision on arXiv

Source-linked AI summary

FLARE MCMC: Fidelity-based Layer-Adaptive REcursive proposals for MCMC

Harini Venkatesan, Christian Shelton, Ming-Feng Ho, Simeon Bird, Mengxuan Wu

arXiv:2608.13774v1cs.AI

TL;DR

MCMC can mix slowly and become computationally burdensome when likelihood evaluations are expensive. FLARE MCMC uses recursively layered lower-fidelity models to guide target-model sampling, producing more efficient samples across scientific domains under the same computational budget.

  • Problem

    Metropolis-Hastings MCMC can mix slowly, requiring more dependent samples and costly likelihood evaluations to approximate posterior distributions effectively.

  • Method

    FLARE MCMC recursively uses cheaper lower-fidelity posterior approximations as proposals for higher-fidelity MCMC, with adaptive layer tuning.

  • Results

    Across three scientific domains, FLARE MCMC produces more efficient samples than existing adaptive multilevel MCMC methods under the same computational budget.

  • Takeaways & Limitations

    FLARE MCMC offers a simple multi-fidelity approach for improving sampling efficiency in simulation-based scientific and engineering inference.

  • Takeaways & Limitations

    In the cosmology experiment, computational expense prevented collecting enough samples for reliable effective sample size estimates.

Abstract

from arXiv · show

Markov chain Monte Carlo (MCMC) requires only the ability to evaluate the likelihood, making it a common technique for inference in complex models. However, it can have a slow mixing rate, requiring the generation of many samples to obtain good estimates and an overall high computational cost. FLARE MCMC is a multi-fidelity layered MCMC method that exploits lower-fidelity approximations of the true likelihood calculation to improve mixing and leads to overall faster performance. Such lower-fidelity likelihoods are commonly available in scientific and engineering applications where the model involves a simulation whose resolution or accuracy can be tuned. Our technique uses recursive, layered chains with simple layer tuning; it does not require the likelihood to take any form or have any particular internal mathematical structure. We demonstrate experimentally that FLARE MCMC achieves larger effective sample sizes for the same computational time across different scientific domains including hydrology and cosmology.

1. Introduction.

MH-MCMC is broadly applicable because it requires only likelihood evaluations, but its lack of problem-specific guidance can cause slow mixing and high computational cost. FLARE MCMC addresses this limitation by recursively using cheaper lower-fidelity models to guide higher-fidelity chains, improving effective sampling per unit time without requiring gradients.

  • Motivation: MH-MCMC samples from almost any distribution using only likelihood evaluations, but its lack of problem-specific guidance can produce slow mixing and computational burden.Its mixing time is the speed of generating effectively new samples.
  • Motivation: Gradient-based methods can accelerate mixing, but gradients may be unavailable when likelihoods require lengthy, complex, or non-differentiable simulations.The cosmological simulation in the experiments cannot produce gradients, so automatic differentiation and analytic gradients are unavailable.
  • FLARE MCMC: FLARE MCMC exploits cheaper lower-fidelity approximations of the same posterior, such as models obtained by coarsening spatial or temporal grids.The approach targets computational models that can be run at multiple fidelities and may involve PDEs, ODEs, or integrals.
  • FLARE MCMC: Recursive MCMC chains use coarser models to guide higher-resolution chains, yielding faster convergence and more effective samples per computation time despite lower-fidelity overhead.The claimed improvement applies to the target model while accounting for the additional cost of lower-fidelity computations.
  • Background: MCMC constructs an easy-to-simulate Markov chain whose stationary distribution is the target distribution, commonly a posterior conditioned on observations.The parameters are represented as θ ∈ Θ ⊂ R^R, with prior distribution p(θ) and observations D.

2. Background.

MCMC can sample distributions using likelihood evaluations, but slow mixing and expensive simulations increase the number and cost of required samples. FLARE MCMC addresses this setting with recursive, fidelity-ordered chains while retaining sampling from the true model and simplifying differences between approximations.

  • Metropolis-Hastings: Metropolis-Hastings generates a candidate from q(θ̃_i|θ_i) and accepts or rejects it to form the next chain state.The proposal distribution can be chosen broadly, subject to mild conditions such as positivity everywhere.
  • MCMC challenges: Slow mixing makes consecutive samples highly dependent, so more samples are needed for a representative approximation; expensive likelihood evaluations further increase computational cost.In many scientific applications, evaluating the likelihood requires a lengthy simulation.
  • Related methods: Prior acceleration strategies include coupled or tempering chains, multilevel estimators, and cheap models used to construct MCMC proposals.These approaches target mixing, estimator variance, or proposal-generation cost through different uses of multiple fidelities and chains.
  • FLARE MCMC: FLARE MCMC resembles MLDA through recursive layers but uses a simpler discrepancy-mitigation construction that needs no internal distribution variables.The passage also states that FLARE MCMC generates more effective samples in a shorter amount of time than MLDA.
  • Fidelity hierarchy: FLARE MCMC orders models by fidelity, samples from the highest-fidelity true model, and uses nested chains with coarser fidelities.Fidelity can be adjusted through simulation resolution, such as the spatial or temporal grid used for a differential-equation model.

3. FLARE MCMC: Fidelity-based Layer-Adaptive REcursive proposals for MCMC.

FLARE MCMC uses recursively nested, lower-fidelity chains to propose samples for finer layers, reducing expensive likelihood evaluations while improving computational efficiency. Its analysis establishes convergence and ergodicity conditions, including adaptive layer tuning, and derives a cost-aware benchmark for selecting inner-chain lengths.

  • Computational efficiency: The layered proposals avoid many expensive fine-fidelity likelihood evaluations and are more likely to be accepted, yielding overall running-time savings when coarse evaluations are much faster.The method evaluates performance through sample quality per computational time, despite the computational cost of the coarser chains.
  • Recursive layered proposals: FLARE MCMC recursively uses an M-step chain targeting the coarser posterior as the proposal for each finer layer, initialized at the current sample.At the coarsest layer, the proposal is a standard simple distribution; the framework is illustrated with J = 2 inner layers and M = 2 steps.
  • Acceptance construction: Each layer uses a Metropolis-Hastings acceptance probability; for non-coarsest layers, its proposal ratio does not depend on M and previously computed coarse likelihood values require no additional time.The coarsest-layer acceptance rule reduces to the standard Metropolis-Hastings form because its proposal is standard.
  • Convergence analysis: Under minorization, FLARE MCMC is uniformly ergodic; convergence depends on nested support coverage, coupling across layers, and similarity of adjacent approximations.Preserving target-distribution modes across coarsening is expected to increase coupling terms and accelerate outer-chain mixing.
  • Layer tuning: Theoretical optimization derives inner-step counts balancing likelihood cost and mixing, but unknown coupling constants and integer constraints make empirical M values necessary in practice.The lemma remains a theoretical benchmark for the optimal computational trade-off across layers.
  • Adaptive tuning: FLARE MCMC with adaptive layer-tuning parameters is ergodic under diminishing adaptation and simultaneous uniform ergodicity.This result extends the convergence analysis to adaptive proposal tuning at each layer.

4. Experiments.

Experiments across pendulum, hydrology, and cosmology problems evaluate FLARE MCMC against standard and multi-fidelity MCMC methods using layered fidelity constructions. FLARE MCMC consistently improves sampling efficiency, while cosmology results are assessed through literature comparisons because reliable ESS estimates were unavailable.

  • Experimental design: Three posterior-sampling problems span a simple pendulum, a hydrology benchmark, and a computationally demanding cosmology simulation.The experiments adjust relevant simulation parameters to construct three fidelities and target sampling at the highest fidelity.
  • Layering: Two higher-fidelity layers significantly improve over standard MCMC and other multilevel methods when layer costs differ by roughly orders of magnitude.Although FLARE MCMC can use more than J = 2 layers, two layers are the practical limit in these examples.
  • Parameter tuning: M = 5 offers the best trade-off between computation time and sampling efficiency, while larger M decreases overall sampling efficiency.This conclusion comes from evaluating ESS across different M values under a fixed total computation time.
  • Comparative results: FLARE MCMC consistently and significantly outperforms competing multilevel methods in ESS/s for both bulk and tail distributions.The comparison includes standard Metropolis-Hastings, MLDA, MLDA with AEM, MLMCMC, and MFMC.
  • Cosmology: In cosmology, FLARE MCMC converges toward literature mean values using fewer samples and less time, but reliable ESS estimates could not be collected.The cosmology simulation was too computationally expensive for a sufficient sample size, and the As parameter showed slightly unusual behavior.

5. Summary. · Appendix A. Convergence Rate Proofs.

The appendix proves convergence-rate results for FLARE MCMC by recursively transferring a minorized lower bound from coarse chains to finer layers. The proof proceeds by induction and uses coupling probabilities to establish the bound after M steps.

  • Appendix A. Convergence Rate Proofs.: The convergence-rate appendix begins by applying Lemma A.1 to obtain a minorized lower bound after M steps of a coarse chain.This bound is then used recursively in the finer layer.
  • Appendix A. Convergence Rate Proofs.: Lemma A.1 specifies transition distributions p_j and invariant target distributions π_j for each chain level.Its conclusion depends on the existence of a positive ξ_j satisfying the lemma’s stated condition.
  • Appendix A. Convergence Rate Proofs.: The proof of Lemma A.1 uses induction, verifying the base case at k = 1 before assuming the result for the preceding induction step.The base case follows from the assumption made in the lemma.
  • Appendix A. Convergence Rate Proofs.: The induction step rewrites the next-step transition bound using the assumed bound for the previous step.The construction introduces ϕ_k, the probability that the chain couples to the stationary distribution in k steps.
  • Appendix A. Convergence Rate Proofs.: The induction concludes by establishing the transition bound after M steps.This is the result used to obtain the recursively applicable coarse-chain minorization.
  • Appendix A. Convergence Rate Proofs.: The proof of Lemma 3.3 defines a transition kernel for which the level-j proposal uses the Mth sample from the level-(j +1) chain.The proposed state is therefore identified with θ_M from the finer chain before invoking Lemma A.1.

Appendix B. Optimal M proof.

The proof derives the optimal M by simplifying the objective, differentiating it, and transforming the resulting condition into a Lambert W expression.

  • Objective simplification: The objective is simplified because the ratio min is constant with respect to M_j.The proof then maximizes the resulting objective under the stated parameter constraints.
  • Optimization condition: Differentiation yields the condition used to identify the objective function’s maximizer.The derivation introduces Υ := −log c > 0 and μ := β + 1, then rewrites c^M_j as e^(−ΥM_j).
  • Lambert W transformation: The substitution y = Υμ + ΥM_j converts the maximization condition into a form solvable with the Lambert W function.Using 1 + Υ(β + M_j) = Υμ + ΥM_j, the proof obtains ΥM_j = y − Υμ.
  • Optimal M: The resulting maximizer is expressed using the −1 branch of the Lambert W function.The proof specifically identifies W−1 as the relevant branch.

Appendix C. Layer Tuning Ergodicity Proof.

Appendix C proves layer-tuning ergodicity by induction across layers and shows that diminishing-step-size gradient descent yields diminishing adaptation. A pendulum-chain example illustrates the evolution of the tuning parameter across nested fidelity layers.

  • Ergodicity proof: Ergodicity is established by applying Theorem 3.4 at layer J −1 and extending the result by induction with base case at layer J.The proof explicitly begins with layer J −1 and then invokes induction from layer J.
  • Ergodicity proof: n ≥ ln τ ln(1 −ξj) is required to ensure that, for every τ > 0, a finite n = n(τ) exists.This bound appears in the proof’s convergence argument.
  • Diminishing adaptation: Diminishing adaptation follows because gradient descent updates ωj+1 to minimize the Kullback-Leibler divergence between layers ψj and ψj+1.At each step, the update changes ωj+1 according to the gradient of Hj+1.
  • Diminishing adaptation: If the stepsize ηt asymptotes to 0, adaptation decreases to 0 as t →∞.This is the stated condition ensuring convergence of the tuning updates.
  • Pendulum example: Figure 9 tracks ωj over collected samples for a doubly nested pendulum chain, where each j = 1 sample starts an inner j = 2 chain of length M = 5.The inner layer uses the small angle approximation as fidelity and starts with a relatively high ω because it poorly approximates the posterior.

Appendix D. Uniform Smoothing Parameter.

Appendix D examines the evolution of the uniform smoothing parameter ω_j for doubly nested layers, with experiments run on a 48-core machine where memory was not restrictive.

  • Uniform smoothing parameter: Figure 9 shows the evolution of ω_j for doubly nested layers j = 1 and j = 2.The figure tracks the smoothing parameter across both layers.
  • Experimental setup: Experiments used 4 Intel® Xeon® Silver 4214 CPUs at 2.20GHz, totaling 48 cores, with 250GB of memory that was never restrictive.The reported hardware configuration supported the experiments without memory limitations.

Appendix E. Computational Infrastructure.

The appendix describes parallel execution and core-hour accounting across the experiments. It also reports that FLARE MCMC produces more compact, comparatively converged cosmology samples than standard MCMC within the same time period.

  • Execution and evaluation: Each chain runs in parallel on a different core, while time is reported for one chain and effective sample size is calculated across 10 chains.All methods use multiprocessing; the listed runtime covers a single-chain run.
  • Execution and evaluation: Cosmology likelihood calculations use 20 cores in parallel, so one day saved corresponds to 20 days of saved core-hours.Pendulum and hydrology likelihoods use a single core.
  • Cosmology sampling: In the cosmology pairwise plot, MCMC generates more samples in the same time, but they remain scattered before convergence, unlike the relatively compact FLARE MCMC samples.The comparison covers all four cosmology parameters.

Appendix F. Pairwise Plot for Cosmology Model.

Figure 10 presents pairwise plots for all four cosmology-model parameters, comparing samples from a 48-hour MCMC run with samples from FLARE MCMC.

  • Pairwise plots: Figure 10 compares pairwise plots for all four cosmology-model parameters using random samples from MCMC and FLARE MCMC.The MCMC samples were collected over 48 hours; MCMC is shown in black and FLARE MCMC in green.
Loading 2608.13774v1…