PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal scalings for local Metropolis--Hastings chains on nonproduct targets in high dimensions

Alexandros Beskos, Gareth Roberts, Andrew Stuart

arXiv:0908.0865v1math.PR

TL;DR

The paper asks how local Metropolis–Hastings step sizes should scale with dimension for nonproduct targets. It analyzes targets formed by changing a product reference law and establishes asymptotic results under general conditions. Its conclusions extend scaling analysis to structured nonproduct distributions, with diffusion limits for that setting left for future work.

  • Problem

    The paper investigates whether, and at what rate, local RWM and Langevin step sizes should diminish as the state-space dimension grows.

    Source: §1 · p. 1

  • Method

    It analyzes local MCMC for targets formed by changing a product reference law, deriving asymptotic acceptance and squared-jump-distance behavior under general conditions.

    Source: §1 · p. 3, §2.2 · p. 6

  • Results

    The analysis establishes asymptotic results for a family of structured nonproduct distributions arising in high-dimensional applications.

    Source: §7 · p. 21

  • Takeaways & Limitations

    The results contribute to understanding the computational complexity of Metropolis–Hastings methods for complex, structured high-dimensional targets.

    Source: §7 · p. 21

    A diffusion limit for optimally scaled MCMC in the nonproduct setting is anticipated to be a reversible stochastic PDE, but proving it remains future work.

    Source: §7 · p. 23

Abstract

from arXiv · show

We investigate local MCMC algorithms, namely the random-walk Metropolis and the Langevin algorithms, and identify the optimal choice of the local step-size as a function of the dimension $n$ of the state space, asymptotically as $n\to\infty$. We consider target distributions defined as a change of measure from a product law. Such structures arise, for instance, in inverse problems or Bayesian contexts when a product prior is combined with the likelihood. We state analytical results on the asymptotic behavior of the algorithms under general conditions on the change of measure. Our theory is motivated by applications on conditioned diffusion processes and inverse problems related to the 2D Navier--Stokes equation.

1. Introduction.

The paper studies how the step size for local Metropolis–Hastings algorithms should vary with dimension for targets that are changes of measure from product laws. It develops asymptotic scaling results under general conditions and motivates them with conditioned diffusions and inverse problems for the 2D Navier–Stokes equation.

1. Introduction.

  • The central question is whether RWM and Langevin step sizes should shrink with dimension, and at what rate, since extreme step sizes can harm acceptance and mixing.Source: §1 · pp. 1, 3
  • The framework extends product-target results to nonproduct laws and is motivated by conditioned diffusions and Navier–Stokes inverse problems.The paper relates similar asymptotic behavior across product and nonproduct cases to absolute continuity in the limit.Source: §1 · pp. 1, 3
  • For nonproduct targets, the paper identifies σ_n^2 = O(n^(-2κ-1/3)) as the appropriate scaling for SLA.Source: §1 · p. 3
  • The analysis uses average squared-jump distance to assess efficiency and derives results under general conditions on the change of measure from a product reference law.The authors describe this approach as simpler than preceding analyses.Source: §1 · pp. 2–3

2. The main results.

The section derives step-size scaling results for RWM and SLA on product and nonproduct targets, using acceptance probabilities and squared-jump-distance to assess efficiency. Under stated conditions, the nonproduct results preserve the product-case scaling, and the optimality analysis gives characteristic acceptance probabilities for tuning the step size.

2. The main results.

  • The analysis tracks the limiting acceptance exponent and average acceptance probability, then uses squared-jump-distance to assess efficiency under general conditions on the change of measure.The results are stated for equilibrium behavior; the authors note that transient-regime properties could differ.Source: §2 · p. 4

2.1. The product case.

  • At the critical scaling ρ = 2κ + I, average acceptance converges to a(l); above it acceptance tends to 1, while below it n^p times acceptance tends to 0 for every p ≥ 0.Here I is the algorithm-specific index, and the product-case results hold for RWM and SLA.Source: §2.1 · p. 5

2.2. The general case.

  • For nonproduct targets satisfying Conditions 3 and 5, the product-case acceptance limits hold; under the weaker Condition 2, acceptance stays bounded away from zero at or above the critical scaling.Condition 2 also yields vanishing n^p-scaled acceptance below the critical scaling for every p ≥ 0.Source: §2.2 · pp. 6–7

2.3. Optimality.

  • The critical step-size scaling maximizes mean squared-jump-distance, with optimal acceptance probabilities 0.234 for RWM and 0.574 for SLA.These values hold for any reference density and any change of measure satisfying Conditions 3 and 5; the authors report that SLA's coefficient is larger because its proposal uses target information.Source: §2.3 · pp. 7–8

2.4. A generalization.

  • When the target parameters λ_i depend on n under the stated bounds, Theorems 1–4 still apply, with adjusted τ_RWM and τ_SLA in the limiting acceptance probabilities.The adjusted values require the specified limits to exist.Source: §2.4 · p. 8

3. Applications in infinite dimensions.

The section frames function-space applications as targets with density relative to a Gaussian reference measure. The Karhunen–Loève expansion represents that Gaussian law through independent scalar coordinates, connecting these applications to the paper’s product-law framework.

Applications in infinite dimensions.

  • Conditioned SDEs and differential-equation inverse problems both yield targets with density relative to a Gaussian reference measure.For conditioned SDEs, the reference is typically a conditioned Gaussian diffusion and the posterior follows through Girsanov; inverse problems combine a Gaussian prior with observations via Bayes’ formula.Source: §3 · p. 9
  • A Gaussian law is well defined exactly when its covariance operator is positive, self-adjoint, and trace-class, meaning its eigenvalues are summable.An orthonormal basis of eigenfunctions then provides coordinates for the expansion.Source: §3 · p. 9
  • The Karhunen–Loève expansion identifies a Gaussian measure on a Hilbert space with a product measure on square-summable scalar coordinates.The coordinates are independent, with variances determined by the covariance operator’s eigenvalues.Source: §3 · p. 9
  • The norm indexed by s measures function regularity through the decay rate of the scalar coefficients.The largest s for which the norm is finite measures regularity; in one dimension, a particular sine basis gives Sobolev spaces.Source: §3 · pp. 9–10
  • Finite-dimensional densities can be constructed by spectral, finite-difference, or other approximations, then analyzed through the paper’s conditions on the discretized functional.This connects the infinite-dimensional applications to the scaling results developed earlier.Source: §3 · p. 10

4. Diffusion bridges.

Diffusion bridges provide an application in which a Brownian bridge Gaussian law serves as reference for a diffusion conditioned on endpoints. Spectral truncation and finite differences produce finite-dimensional targets, and the stated conditions permit the paper’s limiting scaling results to apply.

4. Diffusion bridges.

  • Conditioning an SDE to connect two space-time points defines a diffusion bridge, a setting motivated by applications including rare vacancy motion in a crystal lattice.For the lattice example, a vacancy moves when a neighboring atom enters it, and the model is conditioned on that rare event.Source: §4 · pp. 10–11
  • For the diffusion bridge, the Brownian bridge Gaussian measure is the reference, and Girsanov’s theorem gives the change of measure under mild conditions on the drift.When Γ^-1h is a gradient, the stochastic-integral expression can be replaced by a Riemann integral.Source: §4 · pp. 10–11

4.1. The Fourier expansion.

  • Spectral truncation gives a finite-dimensional approximation of the bridge target using n = d × N coordinates from the Brownian-bridge Karhunen–Loève expansion.The scalar covariance eigenfunctions use Dirichlet boundary conditions; the reference coordinates are then represented through the expansion.Source: §4.1 · pp. 11–12

4.2. The results.

  • Under Condition 6, Proposition 1 establishes that the limiting results of Theorems 3 and 4 apply to the spectrally truncated bridge target.The condition requires G to be bounded below and to satisfy a polynomial-growth bound on its increments; a polynomial-growth assumption on its gradient implies that bound.Source: §4.2 · p. 13

4.3. Finite differences.

  • The same limiting results apply to the finite-difference bridge target when Condition 6 holds.The finite-difference setup assumes paths are approximately constant on intervals of length Δt = T/n and uses finite-dimensional distributions of independent Brownian bridges as reference.Source: §4.3 · pp. 13–14

5. Data assimilation.

The data-assimilation application formulates Eulerian velocity observations and Lagrangian tracer trajectories as inverse problems for the initial condition of a two-dimensional incompressible Navier–Stokes model. A Gaussian prior and Fourier truncation yield finite-dimensional targets, for which the paper’s limiting scaling results apply under stated conditions.

5. Data assimilation.

  • The application estimates the initial condition of two-dimensional incompressible Navier–Stokes flow from observations, using either velocity-field measurements or Lagrangian tracer trajectories.The model is chosen to unify the two data types, although compressible flow models would be more appropriate for weather forecasting.Source: §5 · pp. 14–16

5.1. The Fourier expansion.

  • A mean-zero Gaussian prior with precision operator L = −A^α is conditioned on observations, and Fourier truncation yields a finite-dimensional approximation of the posterior target.The prior is well defined when α > 1; the two observation operators correspond to the Eulerian and Lagrangian cases.Source: §5.1 · pp. 17–18

5.2. The results.

  • For α > 1, Proposition 3 establishes that the limiting results of Theorems 3 and 4 apply to both Eulerian and Lagrangian targets under the stated specifications.The analysis relies on regularity bounds for the observation maps and spectral truncation to obtain a sampling problem in R^n.Source: §5.2 · p. 19

6. Further directions.

The paper considers preconditioning and an implicit Langevin scheme as ways to address limitations of shared-step local proposals. Coordinate-specific scales define the preconditioned methods, while the implicit scheme preserves Gaussian targets at θ = 1/2 and can yield O(1) squared-jump-distance in the Gaussian case.

6. Further directions.

  • Shared-step proposals adapt to the smallest coordinate scale, while preconditioning adjusts step sizes to individual coordinate scales.The paper states that its analytical conditions also cover these modified algorithms.Source: §6.1 · p. 20

6.1. Preconditioning.

  • Preconditioned RWM and SLA use proposal steps σ_nλ_i,n in coordinate i, and Corollary 2 gives their asymptotic results under Conditions 3 and 5.The scalings λ_i,n are assumed bounded above and below by constants times i^-κ.Source: §6.1 · pp. 20–21

6.2. Implicit scheme and Gaussian law.

  • At θ = 1/2 with φ_n ≡ 0, the implicit scheme leaves Gaussian targets invariant for any step size, giving O(1) squared-jump-distance.The paper also reports that implicit proposals can give O(1) squared-jump-distance for discretized non-Gaussian targets with density relative to a Gaussian measure and.Source: §6.2 · p. 21, §6.1 · p. 21

7. Conclusions.

The paper analyzes local MCMC on structured nonproduct targets and relates algorithmic efficiency to both jump distance and proposal cost. Its scaling analysis depends on tail conditions, while diffusion limits for the nonproduct setting remain a direction for future work.

7. Conclusions.

  • The paper establishes analytical results for local MCMC on nonproduct distributions arising in high-dimensional applications.The conclusions frame this as a contribution toward understanding Metropolis–Hastings computational complexity for structured targets.Source: §7 · p. 21
  • The inverse squared-jump-distance indicates the number of steps needed to cover the invariant measure as a function of dimension.Overall comparisons must also account for the cost of each proposed step.Source: §7 · p. 21
  • Relative efficiency depends on implementation costs and the structure of the Gaussian reference measure, including whether its precision operator is banded.The methods require evaluating φn(x) and Lnx; different proposals have additional sampling or inversion costs.Source: §7 · p. 22
  • Optimal scaling is governed by the interplay between reference-measure tails and how the change of measure behaves in the tails.The paper states that the norm exponents and their bounds matter near the infinite-dimensional limit, and that its conditions hold for the applications considered.Source: §7 · p. 22
  • The setting also encompasses Bayesian models with independent-component priors when the likelihood defines the change of measure.The lower bound on φn in Condition 3, corresponding to an upper bound on the likelihood, is typically satisfied in this context.Source: §7 · pp. 22–23
  • Diffusion limits under optimal proposal scaling remain a proposed direction for further study in the nonproduct setting.The anticipated limit is a stochastic PDE reversible with respect to the target measure; proving it could provide further insight into MCMC optimality.Source: §7 · p. 23

APPENDIX A: TAYLOR EXPANSIONS FOR MCMC

The appendix introduces a Taylor expansion of Rn for use in the proofs, with the target taken to be the reference product law.

APPENDIX A: TAYLOR EXPANSIONS FOR MCMC

  • A Taylor expansion of Rn from equation (2.1) is introduced for use throughout the proofs.The expansion is considered as a function of the proposal scale σn around zero.Source: Appendix A · p. 23
  • For this setup, x is distributed according to the reference product law ˜πn.The passage specifies the target as ˜πn.Source: Appendix A · p. 23
  • The expansion concerns the term Rn in equation (2.1), which the appendix uses in its proofs.The passage identifies Rn as the object being expanded.Source: Appendix A · p. 23

A.1. The RWM algorithm.

The RWM appendix analyzes Taylor expansions of Rn under several scaling regimes, using coefficient bounds and limit results to characterize its behavior.

A.1. The RWM algorithm.

  • The expansion uses coefficient sequences that are i.i.d. across i, with polynomial bounds whose relevant expectations do not depend on i.The passage uses Conditions 1(i) and 1(ii) to bound these terms.Source: §A.1 · p. 23
  • When ε = 0, A1,n converges in law to a zero-mean Gaussian with variance l^2E[C1,·^2]/(1 + 2κ), and A2,n converges in L2 to l^2E[C2,·]/(1 + 2κ).The passage notes that the A2,n limit can also be expressed in terms of K.Source: §A.1 · p. 24
  • For the stated regime with ε ≥ 0, E[Rn] tends to −∞ at rate n^ε, while centered moments of order 2q are O(n^(ε·q)).In this result, the residual term converges to zero in L1(˜πn).Source: §A.1 · p. 24
  • The analytical expression for C2,i yields an integral involving {g′(u)}^2 exp{−g(u)} that is negative.The supplied passage states the integral is less than zero.Source: §A.1 · p. 25

A.2. The SLA algorithm.

The SLA appendix uses a sixth-order Taylor expansion and reports coefficient-level limits and asymptotic behavior of Rn under the stated scaling regimes.

A.2. The SLA algorithm.

  • The expansion coefficients satisfy C1,· = C2,· = 0 and E[C3,·] = E[C4,·] = E[C5,·] = 0, while E[C6,·] < 0.The appendix also states an analytical calculation for E[C3,·].Source: §A.2 · p. 25
  • For ε > 0, Aj,n converges to zero in L2(˜πn) for every j from 3 through 6.The passage places these limits within the sixth-order expansion.Source: §A.2 · pp. 25–26
  • For the scaling regime in which the appendix uses the preceding results, limits of A3,n and A6,n can be expressed using the same constant K.The passage attributes this relation to calculations demonstrated in.Source: §A.2 · p. 26
  • The residual converges to zero in L1(˜πn), while E[Rn] tends to −∞ as fast as n3ε, and for every positive integer q, E[(Rn − E[Rn])2q] is O(n3ε·q).Source: §A.2 · p. 26

APPENDIX B: PROOFS

Appendix B proves the asymptotic results by controlling acceptance-related terms and transferring product-target expansions to changed-measure targets. It also derives scaling constants for the RWM and SLA in the applications considered.

APPENDIX B: PROOFS

  • n = l^2 n^(-2κ-1)n^(-ε), ε > 0: R_n → 0 in L^1 under the product reference law, yielding the stated result by continuity of x ↦ 1 ∧ e^x.The proof transfers this convergence to π_n using Condition 3.Source: Appendix B · pp. 30, 32
  • n = l^2 n^(-2κ-1)n^ε, ε ∈ (0,1): E[R_n] tends to −∞ at rate n^ε, and the expected acceptance tends to zero faster than any polynomial order.The proof also bounds centered moments of R_n and applies Lemma B.1(ii).Source: Appendix B · p. 30
  • For Theorem 2, when ρ ≥ 2κ + I, the proof establishes a lower bound on E_πn[a_n(x,y)]; the range 2κ < ρ < 2κ + I follows from Theorem 1(iii).Source: Appendix B · p. 30
  • For ρ > 2κ, Conditions 3 and 5 imply φ_n(y) − φ_n(x) → 0 in L^q(π_n) for every q > 0, for both RWM and SLA.Source: Appendix B · p. 30
  • Comparing with the product case, R_n has the same limiting behavior under π_n and ˜π_n, implying the same a(l) as when the target law is ˜π_n.The Martingale CLT is applied under π_n.Source: Appendix B · p. 32
  • The application proofs calculate the stated τ_RWM and τ_SLA scaling constants, including for the discrete-time path setting.Source: Appendix B · pp. 35–36
Loading 0908.0865v1…