PaperlayerView exact revision on arXiv

Source-linked AI summary

Informed proposals for local MCMC in discrete spaces

Giacomo Zanella

arXiv:1711.07424v1stat.COmath.PR

TL;DR

Designing informed Metropolis-Hastings proposals for high-dimensional discrete spaces remains unclear. This paper develops locally-balanced proposals, proves their high-dimensional Peskun-optimality, and reports orders-of-magnitude efficiency improvements over alternative schemes.

  • Problem

    How to appropriately extend informed MCMC proposals to discrete spaces remains unclear, despite proposal choice strongly affecting sampling efficiency.

  • Method

    The paper formulates pointwise informed proposals, characterizes locally-balanced proposals, and analyzes their optimality under regularity assumptions.

  • Results

    Locally-balanced proposals are asymptotically Peskun-optimal and deliver orders-of-magnitude efficiency improvements over alternative schemes in simulated and real-data experiments.

  • Takeaways & Limitations

    The framework provides practical, easy-to-implement methodological guidance for designing informed MCMC proposals in high-dimensional discrete problems.

  • Takeaways & Limitations

    The theoretical analysis assumes a symmetric base kernel, leaving extensions to general base kernels for future work.

Abstract

from arXiv · show

There is a lack of methodological results to design efficient Markov chain Monte Carlo (MCMC) algorithms for statistical models with discrete-valued high-dimensional parameters. Motivated by this consideration, we propose a simple framework for the design of informed MCMC proposals (i.e. Metropolis-Hastings proposal distributions that appropriately incorporate local information about the target) which is naturally applicable to both discrete and continuous spaces. We explicitly characterize the class of optimal proposal distributions under this framework, which we refer to as locally-balanced proposals, and prove their Peskun-optimality in high-dimensional regimes. The resulting algorithms are straightforward to implement in discrete spaces and provide orders of magnitude improvements in efficiency compared to alternative MCMC schemes, including discrete versions of Hamiltonian Monte Carlo. Simulations are performed with both simulated and real datasets, including a detailed application to Bayesian record linkage. A direct connection with gradient-based MCMC suggests that locally-balanced proposals may be seen as a natural way to extend the latter to discrete spaces.

1 Introduction

MCMC efficiency depends strongly on proposal design: uninformed random-walk schemes can mix poorly, while existing informed methods are mainly tailored to continuous spaces. This work develops locally-balanced proposals as a unified, theoretically motivated approach for high-dimensional discrete and continuous problems, with substantial empirical efficiency gains.

  • Metropolis-Hastings efficiency depends drastically on the proposal distribution and its interaction with the target, affecting convergence speed.
  • Random-walk proposals are easy to implement but propose blindly without target information, potentially causing poor mixing and slow convergence.
  • Continuous-space informed methods, including gradient-based proposals and HMC, improve MCMC performance, but discrete spaces often lack feasible embeddings preserving their natural topology [Neal, 2011, Girolami and Calderhead, 2011].
  • The paper formulates informed proposals through a simple framework unifying continuous and discrete settings and introduces locally-balanced proposals for high-dimensional discrete problems.
  • The paper characterizes locally balanced proposals through local-limit exactness, establishes their high-dimensional Peskun optimality, relates them to Barker’s algorithm, and evaluates them empirically.

2 Locally-balanced proposals

This section develops pointwise informed proposals that reweight local symmetric kernels using a function of target density, and defines locally balanced kernels through small-scale convergence of their reversible measures to the target. The framework explains why square-root reweighting corrects the local bias and motivates balancing functions as a route to more efficient Metropolis-Hastings algorithms.

  • Motivation: Naively weighting proposals by π(y) is unsuitable for small σ because the reversible measure converges to π(x)^2dx rather than the target π(x)dx.For large σ, the same proposal is approximately target-reversible, motivating the distinction between globally balanced and locally balanced proposals.
  • Motivation: Square-root weighting, g(t)=√t, yields a proposal whose reversible measure converges to π(x)dx as σ↓0 and therefore provides an example of a locally balanced proposal.This construction corrects the local-limit distortion produced by direct density weighting.
  • Pointwise informed proposals: Pointwise informed proposals reweight the symmetric kernel Kσ(x,dy) by g(π(y)) and normalize, while retaining the kernel’s topological structure.The class includes uninformed proposals when g(t)=1 and naively informed proposals proportional to Kσ(x,y)π(y) when g(t)=t; g is assumed continuous and bounded by a linear function.
  • Locally-balanced kernels: Locally balanced kernels are reversible with respect to distributions that converge weakly to the target as σ↓0, reducing the Metropolis-Hastings correction needed for local moves.The resulting expectation is higher acceptance and longer moves, improving efficiency when local-move regimes arise in high dimensions.
  • Balancing functions: Theorem 1 characterizes exactly which functions g make pointwise informed proposals locally balanced, and subsequent results compare their asymptotic efficiency with other pointwise informed proposals.These functions are termed balancing functions.

3 Peskun optimality of locally-balanced proposals

This section uses Peskun ordering to compare pointwise-informed Metropolis–Hastings schemes on discrete spaces. It shows that balancing the proposal function yields efficiency gains and becomes asymptotically optimal under a local high-dimensional condition.

  • Peskun ordering: Peskun ordering links off-diagonal kernel dominance to improved MCMC efficiency through spectral gaps and asymptotic variances [Peskun, 1973, Tierney, 1998].If P1(x, y) ≥ cP2(x, y) for x ≠ y, then Gap(P1) ≥ cGap(P2), with corresponding asymptotic-variance improvement.
  • Optimal balancing: For any positive proposal function g, the balancing transform ˜g(t) = min{g(t), t g(1/t)} produces a more efficient MH algorithm up to factor 1/c_gc_˜g.The transform satisfies ˜g(t) = t˜g(1/t), and the efficiency factor converges to one in many increasing-dimensional models.
  • High-dimensional optimality: When condition (A) holds for well-behaved g, the comparison factor converges to one, making locally-balanced proposals asymptotically Peskun-optimal.A sufficient setting is a bounded-degree conditional-independence graph with a base kernel updating a fixed number of variables.
  • Discrete examples: The framework covers discrete models with local moves, including independent binary components, weighted permutations with transpositions, and Ising models with single-bit flips.The first is analyzed explicitly, while the permutation and Ising targets provide non-trivial applied examples for later illustrations.
  • Sufficient conditions: For these three examples, boundedness conditions on probabilities, permutation weights, or Ising biases are sufficient for condition (A) for every locally bounded g.Specifically, binary probabilities stay uniformly inside (0,1), permutation weights are bounded above and below, and Ising biases are uniformly bounded.

4 Optimal choice of balancing function

This section identifies the Barker balancing function, g(t) = t/(1 + t), as optimal among locally-balanced proposals for independent binary components. The result follows by analyzing a time-rescaled limiting process whose bits flip independently and optimizing their rates.

  • Connection with acceptance probabilities: Balancing functions correspond to Metropolis-Hastings acceptance probabilities when g(t) is bounded by 1, but the broader balancing-function class also includes valid unbounded choices such as g(t) = t.The acceptance-probability condition is g(t) = t g(1/t), while balancing functions need not themselves be probabilities.
  • Independent binary components: For independent binary components, the Barker balancing function g(t) = t/(1 + t) yields the smallest mixing time among locally-balanced proposals.The comparison uses a two-step asymptotic analysis: convergence to a limiting continuous-time process, followed by optimization of its mixing behavior.
  • Limiting process: After time rescaling, any fixed number of components converges weakly to a continuous-time Markov chain in which each bit flips independently.The theorem assumes the chain starts at stationarity and states convergence for every positive integer number of tracked components.
  • Optimization argument: Optimizing the limiting flip rates first gives c_i = 1/2 for every component, exactly matching the balancing condition g(t) = t g(1/t).This agrees with the earlier conclusion that locally-balanced proposals are asymptotically optimal in high dimensions.
  • Optimal balancing function: The optimal balancing function is g_opt(t) = t/(1 + t), equivalently producing proposal weights proportional to π^(n)(y)/(π^(n)(x) + π^(n)(y)) over neighboring states.This is the Barker choice previously considered for acceptance probabilities.

5 Connection to MALA and gradient-based MCMC

In continuous spaces, locally-balanced proposals replace intractable pointwise target evaluations with local approximations. A first-order Taylor approximation recovers MALA as a specific locally-balanced proposal and suggests flexible gradient-based extensions.

  • Continuous-space motivation: Pointwise informed proposals are typically infeasible for efficient sampling in continuous spaces, motivating local approximations of the target around the current state.The intractable target term π(y) is replaced by a local approximation around x.
  • First-order proposals: A first-order Taylor expansion of log π(y) yields a family of first-order informed proposals using the local gradient ∇log π(x).The approximation is elog π(y) ≈ elog π(x)+∇log π(x)·(y−x).
  • Connection to MALA: MALA is a specific locally-balanced proposal obtained with g(t)=t and a Gaussian kernel K_σ(x,·)=N(x,σ^2).This construction uses the first-order Taylor approximation and symmetric K_σ satisfying (4).
  • Extensions: The framework suggests extensions through alternative balancing functions, kernels, or approximations for π(y), highlighting its flexibility for gradient-based schemes.These modifications are presented as possible ways to extend classical gradient-based methods.

6 Simulation studies

Simulation studies compare informed and random-walk MCMC schemes across permutation and Ising targets, showing that locally balanced proposals can deliver substantial efficiency gains, especially for highly non-uniform distributions. The experiments also examine acceptance rates, computational cost, target concentration, initialization, and the scope of single-site updates.

  • Simulation design and scope: The simulations compare six schemes using a common base kernel, while chain behavior can depend on initialization and specialized global-update algorithms are outside the comparison.Chains initialized far from the target may become stuck and reject nearly all moves; global methods can perform better for multimodal Ising targets but are complementary to the single-site schemes studied.
  • Permutation targets: For permutation targets, LB1 and LB2 have acceptance rates approaching 1 as dimensionality increases, while efficiency comparisons account for their higher per-iteration computational cost.The number of successful flips per unit computation time provides the study’s main cost-adjusted diagnostic.
  • Permutation targets: In structured permutation targets with weights decreasing away from the diagonal, results resemble the i.i.d. case, with HB substantially less efficient than LB1 and LB2.The structured-weight experiment reports an even more prominent efficiency gap between HB and the locally balanced schemes.
  • Ising model: Locally balanced schemes LB1 and LB2 are orders of magnitude more efficient than alternative schemes for highly non-uniform Ising targets.This advantage is measured by effective sample sizes per unit time and is especially pronounced as target concentration increases.

7 Application to Bayesian record linkage

The application uses locally-balanced proposals to update high-dimensional discrete matchings in bipartite record-linkage problems. On Italian survey data, LB substantially improves sampling efficiency and scales to nearly one billion posterior pairwise matching probabilities.

  • Model and sampler: Locally-balanced proposals address the challenge of efficiently updating the high-dimensional discrete matching object M in bipartite record linkage.The task merges two databases with duplicates across, but not within, databases; this is the commonly studied bipartite case (Sadinle [2017]).
  • Regional record linkage: The study applies four MCMC schemes—RW, GB, LB, and HB—to 20 Italian regional linkage tasks averaging roughly 1,300 individuals each.The data come from the 2008 and 2010 Italian Survey on Household and Wealth, containing 11 variables per individual.
  • Regional record linkage: LB improves relative efficiency by roughly two orders of magnitude over RW and GB and one order over HB across 20 regional linkage tasks.Efficiency is measured as effective sample size per computation time, averaged over five Hamming-distance statistics and reported relative to RW.
  • Regional record linkage: LB provides more reliable posterior probabilities for which record pairs are matched than HB.The regional experiments ran LB for 35,000 iterations per region, requiring about 120 seconds per region on average.
  • Full-dataset linkage: Applied to the full Italy dataset without regional blocking, LB estimates nearly one billion posterior pairwise matching probabilities in less than 40 minutes.The full-data implementation uses the block-wise method from Section 6.4 and avoids excluding possible cross-region matches.

8 Discussion and future work · A Additional calculations and proofs

The paper presents locally-balanced proposals as an easy-to-implement framework with high-dimensional optimality guarantees, then identifies extensions involving gradient-based methods, multiple-try Metropolis, implementation, and theory.

  • 8 Discussion and future work: The framework addresses informed Metropolis-Hastings proposal design in discrete spaces through pointwise informed proposals and locally-balanced criteria, proving high-dimensional optimality under regularity assumptions.The authors characterize the framework as simple, original, and useful for implementation.
  • 8 Discussion and future work: The connection to MALA could improve gradient-based MCMC robustness and reduce the burden of tuning gradient-based schemes.
  • 8 Discussion and future work: Extending the analysis to Multiple-Try Metropolis is suggested because its selection weights resemble multiplicative biasing terms in pointwise informed proposals.The authors expect the results to translate naturally to that context.
  • 8 Discussion and future work: Future implementation work should study the tradeoff between per-iteration computational cost and statistical efficiency, including block-wise implementations and cheaper approximations to the informed term.The exact target would still be used in the Metropolis-Hastings accept/reject step when approximating the informed term.
  • 8 Discussion and future work: Sampling locally-balanced proposals is trivially parallelizable, so GPUs could reduce the computational overhead of informed proposals [Lee et al., 2010].
  • 8 Discussion and future work: Theoretical extensions include interpolating between locally and globally balanced proposals, adaptively learning the needed interpolation level, and generalizing the sufficient optimality condition.These directions target regimes intermediate between local and global behavior and broader theoretical settings.

A.1 Proof of Theorem 1

The proof establishes Theorem 1 by controlling the normalization integrals under a linear growth condition on g, then proving sufficiency through kernel concentration and Scheffé’s theorem. Necessity follows from a two-state counterexample whenever condition (4) fails.

  • A.1 Proof of Theorem 1: A linear bound g(t) ≤ a + bt, together with bounded π and concentrating symmetric kernels, controls Zg,σ and the associated integrals as σ ↓ 0.Lemma 1 uses pointwise convergence, Fatou’s lemma, bounded convergence, and kernel reversibility to establish the required integral bounds.
  • A.1 Proof of Theorem 1: Under condition (4), the normalized proposal density converges pointwise to π, and Scheffé’s theorem completes the sufficiency proof that the proposals are locally balanced.Kernel concentration gives the needed limit for the g-dependent term, while Lemma 1 supplies normalization control.
  • A.1 Proof of Theorem 1: If condition (4) fails at some t0 > 0, a two-state target with probabilities proportional to (1, t0) provides a counterexample to local balance for general bounded continuous densities.The construction uses counting measure on X = {0, 1} and examines the limiting proposal behavior as Kσ concentrates at the identity.

A.2 Proof of Theorem 2 · A.3 Proof of Theorem 3 · A.4 Proof of Proposition 1

These appendices prove variance and spectral-gap comparisons for lazy reversible kernels, establish general upper and lower bounds for symmetrized informed proposals, and verify proposal-ratio control in permutation examples.

  • A.2 Proof of Theorem 2: A.2 proves that lazifying a reversible kernel by factor c yields varπ(h, P̃) = c^-1 varπ(h, P) + (1−c)c^-1 varπ(h).The proof uses shared eigenfunctions and transformed eigenvalues λ̃_i = cλ_i + (1−c).
  • A.2 Proof of Theorem 2: A.2 combines the lazification identity with Peskun ordering [1973, Thm.2.1.1] to prove Theorem 2’s variance comparison in both c > 1 and c ≤ 1 cases.The corresponding spectral-gap statement follows directly from the definition of Gap(P).
  • A.3 Proof of Theorem 3: A.3 extends Theorem 3 through Theorem 5 to continuous spaces, using a bounded target density, a symmetric Markov kernel, and Radon–Nikodym proposal ratios.The result provides both upper and lower bounds for the associated Metropolis–Hastings kernels.
  • A.3 Proof of Theorem 3: A.3 replaces g with g̃(t) = min{g(t), t g(1/t)} to enforce a more balanced proposal while comparing Pg and Pg̃.The proof derives the bounds from proposal Radon–Nikodym derivatives, normalization inequalities, and the definition of the imbalance constant bg.
  • A.3 Proof of Theorem 3: A.3 bounds the symmetrized proposal contribution using min{g̃(txy), txy g̃(tyx)}, then obtains the upper and lower bounds in (28).The displayed intermediate relations (31)–(34) support the final comparison.
  • A.4 Proof of Proposition 1: A.4 proves Proposition 1 for permutation transpositions by comparing gρ with the infimum and supremum of g over a compact interval I.Local boundedness of g and 1/g ensures these extrema are finite and positive.
  • A.4 Proof of Proposition 1: A.4 observes that unchanged permutation coordinates preserve the corresponding proposal ratios, and states that the proofs for Examples 1 and 3 are analogous.The argument fixes ρ′ = ρ ◦ (i0, j0) with i0 < j0 and compares only the transposed coordinates.

A.5 Proof of Theorem 4 · A.5.1 Some references for mixing time of product chains · B Supplement for the simulation studies

The appendix proves Theorem 4 by showing convergence of finite-component dynamics to an independent-component continuous-time Markov chain, then relates its mixing time to worst-component flipping rates. It also notes that constant scaling choices optimize the relevant mixing-time quantity and supplies additional simulation diagnostics.

  • A.5 Proof of Theorem 4: Lemma 3 supplies the auxiliary bound needed in the proof of Theorem 4 for controlling the rate contributions from components beyond the first k.The proof further uses boundedness of the associated terms and a vanishing-probability argument.
  • A.5 Proof of Theorem 4: For each k, S1:k is a product chain with independent components, connecting Theorem 4 to established results on product-chain mixing and cutoff.The cited references include Diaconis and Saloff-Coste [1996, Thm.2.9] and Levin et al. [2009, Ch.20.4].
  • A.5.1 Some references for mixing time of product chains: The relevant mixing-time quantity is maximized, and mixing time therefore minimized, by choosing vi constant across components, vi = ¯v for all i.The quantity is ¯Z(v)^−1 lim inf_i→∞ vi under the stated assumptions on flipping rates.
  • B Supplement for the simulation studies: The supplementary simulation material provides additional traceplots, acceptance rates, and effective sample sizes for the study in Section 6.2.The supplied passage identifies these diagnostics but does not report their numerical values or comparisons.

B.1 Supplement to Section 6.2 … C.3 Metropolis-within-Gibbs sampler

The supplements show that locally balanced proposals outperform alternatives as discrete targets become rougher, while detailing the Ising benchmarks and the Bayesian record-linkage model, likelihood, and Metropolis-within-Gibbs sampler. The record-linkage sampler updates hyperparameters by Gibbs steps and the matching structure through competing Metropolis schemes built on local matching moves.

  • B.1 Supplement to Section 6.2: Figure 8 compares the five Section 6.2 MCMC methods using Hamming-distance traceplots and estimated autocorrelation functions at n = 500.
  • B.1 Supplement to Section 6.2: Locally balanced schemes strongly outperform competing samplers for rough targets, whereas uninformed random-walk proposals perform best for flatter targets.HB is slightly better for flatter targets but collapses as target difficulty increases.
  • B.2 Supplement to Section 6.3: The Section 6.3 benchmark uses Ising-model distributions for image analysis, with pixel variables representing object or background classifications and Potts models providing a multiple-object generalization.The Ising-type prior induces positive correlation among neighboring variables, yielding an Ising posterior with biasing terms.
  • B.2 Supplement to Section 6.3: The Ising experiments vary grid size from 20 to 1000 and target concentration through spatial correlation and increasingly informative external fields.Targets use μ = 0, 0.5, 1, 2, 3 and σ = 0, 1.5, 3, 3, 3; Target 0 is uniform, so all schemes share the same transition kernel.
  • C Supplement for the Record Linkage application: The record-linkage application models an unknown matching M between two data lists, following priors based mostly on Miller et al. [2015] and Zanella et al. [2016] and likelihood ideas from Copas and Hilton [1990] and Steorts et al. [2016].
  • C.1 Prior distribution on the matching structure: The matching prior is permutation-invariant, with the total number of entities determined through matched pairs and singletons; simulations use weakly informative independent priors on p_match and λ.The exchangeability assumption makes each matching with fixed counts equally likely, while the count components have independent Poisson distributions conditional on λ and p_match.
  • C.2 Likelihood distribution: The likelihood is a discrete spike-and-slab model in which singletons follow empirical field distributions, while matched records share latent field values with distortion probability β = 0.001.The field parameters θ_s are estimated empirically in real-data applications, following a standard empirical Bayes procedure such as Zanella et al. [2016].
  • C.3 Metropolis-within-Gibbs sampler: The Metropolis-within-Gibbs sampler alternates Gibbs updates for p_match and λ with Metropolis updates for M, using Beta and truncated-Gamma full conditionals and a common local-move kernel.The kernel proposes add, delete, single-switch, and double-switch moves after sampling an index pair uniformly; updating M is the challenging computational step compared across RW, GB, LB, and HB.

C.4 Blocking implementation

When full informed proposals become costly as n_x and n_y grow, the implementation applies MCMC updates to sub-blocks of indices while preserving invariance. In Section 7, blocks of size 300 alternate between uniform random selection and feature-based selection favoring likely matches.

  • C.4 Blocking implementation: Sub-block updates reduce the computational cost of sampling from GB, LB, and HB when n_x and n_y are large.The implementation applies informed schemes to selected index subsets I and J rather than the full state space.
  • C.4 Blocking implementation: The block-wise chain remains invariant with respect to Q when the MCMC kernel on I × J is invariant with respect to its corresponding restricted target.
  • C.4 Blocking implementation: In Section 7, both index subsets I and J were set to size 300.The procedure permits other random or deterministic subset-selection schemes.
  • C.4 Blocking implementation: The implementation alternated uniform random block selection with feature-based blocks that group indices agreeing on three randomly selected features.Oversized blocks were uniformly subsampled to 300, while uniform random selection ensured irreducibility and feature matching favored likely matches.
Loading 1711.07424v1…