PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit error bounds for Markov chain Monte Carlo

Daniel Rudolf

arXiv:1108.3201v2math.PRcs.NAmath.NA

TL;DR

The paper addresses how to bound the error when estimating expectations by Markov chain Monte Carlo. It proves explicit bounds under different convergence assumptions and gives a burn-in recipe; applications to log-concave densities and convex bodies are shown to be polynomially tractable.

  • Problem

    The paper asks how the error of numerical integration based on Markov chains behaves when the target expectation must be approximated.

    Source: §1 · p. 5

  • Method

    It derives explicit error bounds under different Markov-chain convergence assumptions and gives a theoretically justified burn-in choice.

    Source: §1 · pp. 7, 9, §2 · p. 57

  • Results

    An L2-spectral gap gives an upper error bound for finite Lp integrands with p > 2, and the studied log-concave-density and convex-body integration problems are polynomially tractable.

    Source: §1 · pp. 10–11

  • Takeaways & Limitations

    The bounds support polynomially tractable integration for log-concave densities using a ball walk and for convex bodies using hit-and-run.

    Source: §1 · p. 11

    For finite-state bounds, dependence on the initial distribution includes a factor the authors describe as unsatisfactory for extension to general state spaces.

    Source: §2.2 · p. 24

Abstract

from arXiv · show

We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure {\pi}. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to the L2 -norm of f . If there exists an L2 -spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to the Lp -norm of f for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of the integration with respect to a possibly unnormalized density. More precise, we consider the integration with respect to log-concave densities and the integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.

1. Introduction and results

The paper develops explicit error bounds for estimating expectations with Markov chain Monte Carlo, under several convergence assumptions. It also gives a burn-in choice and applies the bounds to integration with log-concave densities and over convex bodies.

1. Introduction and results

  • The underlying problem is to estimate the expectation of a function when direct sampling from the target distribution may not be reasonably available.The paper studies the mean square error of the Markov-chain estimator.Source: §1 · pp. 5–6
  • For finite reversible chains, the paper provides an explicit L2 error bound and a lower bound, and presents a burn-in choice that is optimal under stated conditions.For sufficiently large N and the stated additional condition, nopt lies between n0 and (1 + η)n0.Source: §1 · p. 8
  • With the number of steps fixed, the recommended burn-in minimizes the upper error bound and is within a factor of 1 + η of n0 under the stated conditions.Numerical experiments are reported to confirm the theoretical burn-in choice.Source: §1 · pp. 8–9
  • For reversible Markov chains with L1-exponential convergence, the paper gives explicit error estimates and extends them to general state spaces.The general-state-space bound assumes a bounded density for the initial distribution with respect to π.Source: §1 · p. 9
  • An L2-spectral gap yields an upper error bound for integrands with finite Lp norm when p > 2, under a weaker convergence condition than L1-exponential convergence.The burn-in choice for this bound is justified by numerical experiments.Source: §1 · p. 10
  • For log-concave densities on a Euclidean ball, the Metropolis algorithm based on a ball walk yields polynomially tractable integration in dimension d and Lipschitz constant L.The unit-ball geometry is essential to the cited L2-spectral-gap estimate; the ball walk may get stuck on domains with corners.Source: §1 · pp. 10–11
  • For integration over convex bodies, hit-and-run yields polynomially tractable computation in dimension d and radius r.The general error result applies to integrands with finite Lp norm for p > 2.Source: §1 · p. 11

2. Finite state spaces

This section develops explicit error bounds for finite reversible Markov chains, covering stationary and nonstationary starts and burn-in choices. Examples and remarks illustrate the bounds’ tightness, use of eigenvalue information, and limitations.

2.1. Markov chains.

  • The analysis assumes finite-state chains are irreducible, aperiodic, and reversible with respect to π; periodic chains can be made aperiodic using a lazy transition matrix.The lazy version retains π as a stationary distribution.Source: §2.1 · pp. 14–15
  • For reversible transition matrices with β < 1, the distribution νP^k converges to π exponentially fast as k increases.Here β is the second-largest absolute eigenvalue of P, as introduced in the preceding discussion.Source: §2.1 · pp. 16–17

2.2. Error bounds.

  • With a stationary initial distribution, no burn-in is needed, and the stationary-start error representation is compared with the case of a nonstationary initial distribution.The paper denotes the stationary-start estimator by Sn, with burn-in n0 = 0.Source: §2.2 · p. 18
  • For a reversible chain started from its stationary distribution, the error bounds include an equality that determines the integration error exactly and explicit L2 bounds.The results concern the estimator with initial distribution π; the exact-error claim is stated for this stationary-start case.Source: §2.2 · pp. 18–19
  • For reversible chains with β < 1, the section gives an explicit upper error bound for a nonstationary start, with its excess over the stationary-start error controlled independently of n and n0.The section also derives a lower error bound and provides an explicit constant for the upper estimate.Source: §2.2 · pp. 22, 24, 25
  • The burn-in n0 limits the influence of the initial distribution, while n must be large to reduce stationary-start error; the estimate depends on the trade-off between them.The paper notes that the bound’s dependence on the initial distribution includes a factor q∞, which complicates extension to general state spaces.Source: §2.2 · p. 24

2.3. Burn-in.

  • For a fixed total budget N, the suggested burn-in minimizes the upper error estimate and is independent of the desired precision ε.The setup fixes N = n + n0 and balances the choices of burn-in and sampling steps.Source: §2.3 · pp. 25, 27, 28

2.4. Examples.

  • For the circle walk with T = 999, the lower error bound is nontrivial only for N ≥ 3,014,610, after the prescribed burn-in n0 = 1,396,699.The passage reports the exact error and upper and lower bounds in Figure 1.Source: Random walk on a circle · p. 29, Figure 1 · p. 30
  • For the hypercube walk at d = 50, the exact error and upper and lower bounds are close after burn-in, and the bounds are polynomial in d, the magnitude of log(|D|).These curves are shown in Figure 2.Source: Random walk on the hypercube · p. 31, Figure 2 · p. 31
  • As n0 grows, u1 maximizes the error over integrands with ∥f∥2 ≤ 1; Theorem 2.25 is tight when β1 = β, while Theorem 2.20 gives the right asymptotic coefficient when β1 and β are known.When β1 and β|D|−1 are available, the error can be approximated by the lower and upper bounds.Source: Random walk on the star · pp. 33–34

2.5. Notes and remarks.

  • Doeblin-based bounds cover periodic, non-reversible chains, but their constants can be exponentially poor and they neither attain the optimal leading coefficient nor support burn-in tuning.For the i.i.d. uniform example on {0, 1}^d, the estimate is exponentially bad in d, whereas Theorem 2.20 is independent of d.Source: §2.5 · p. 34
  • Applying Markov’s inequality with the Theorem 2.25 burn-in gives a confidence estimate whose burn-in is independent of the confidence parameter α.The passage also notes that Chernoff bounds provide better results than this Markov-inequality approach.Source: §2.5 · pp. 35–36
  • The paper identifies the burn-in justification and Theorem 2.25’s lower bound as new contributions, while noting that related finite-state error estimates already exist.The authors say some assumptions in related estimates, such as aperiodicity or reversibility, are weakened; they then extend results to general state spaces.Source: §2.5 · p. 36

3. General state spaces

This section develops tools for Markov chains on general state spaces, relating convergence and spectral-gap properties to mean-square error bounds for reversible chains.

3.1. Markov chains.

  • For p ∈ [1, ∞], the Markov operator satisfies ∥Pf∥p ≤ ∥f∥p and has operator norm ∥P∥Lp→Lp = 1.Source: §3.1 · p. 41
  • Reversibility with respect to π is equivalent to the Markov operator P being self-adjoint on L2.Source: §3.1 · p. 43
  • An L2-spectral gap implies L2-geometric ergodicity; for reversible kernels, the two properties are equivalent.The convergence analysis targets the speed at which νP^m approaches π.Source: §3.1 · pp. 43–44
  • An L2-spectral gap implies Lp-exponential convergence for every p ∈(1, ∞); for normal P, it is equivalent to L2-exponential convergence.Source: §3.1 · p. 46
  • For normal P, L1- or L∞-exponential convergence implies an L2-spectral gap.Source: §3.1 · p. 47
  • For reversible kernels, L1- and L∞-exponential convergence with (α, 2M) are equivalent to each other and to π-a.e. uniform ergodicity with (α, M); each implies an L2-spectral gap.Source: §3.1 · p. 49

3.2. Error bounds.

  • Proposition 3.26 gives mean-square error bounds for f ∈L2 when the chain starts in stationarity and is reversible, using the spectral measure of P.Source: §3.2 · pp. 50–51

2. The error obeys

The section develops and illustrates explicit Markov-chain error bounds under different convergence assumptions, including reversible chains with L1-exponential convergence and chains with an L2-spectral gap. It examines how burn-in relates to the initial distribution and offers burn-in guidance alongside examples and an introduction to the Metropolis–Hastings algorithm.

2. The error obeys

  • Under the reversible-chain assumptions, the section also establishes lower and upper error bounds and an asymptotic error result for L2-bounded integrands.The asymptotic result is presented under the same assumptions as the explicit bound in Theorem 3.34.Source: §2 · pp. 52, 57
  • The bounds relate nonstationary-start error to stationary-start error; increasing burn-in removes the initial-distribution influence, while matching initial and stationary distributions eliminates that bias.For L2-spectral-gap bounds, the integrand norm is Lp for p > 2; the initial-part influence vanishes when the distributions match.Source: §2 · pp. 53, 56, 61
  • For reversible, L1-exponentially convergent chains, the section gives explicit L2 error bounds for nonstationary starts, with constants independent of sample size and burn-in.The theorem assumes the initial distribution has a bounded density relative to the stationary distribution.Source: §2 · pp. 54–56
  • An L2-spectral gap yields error bounds for integrands in Lp, p > 2, without requiring reversibility; for reversible chains, the bound also has an asymptotic form.As p approaches 2, the bound grows without limit; for p > 2 it is explicit.Source: §2 · pp. 60–61

3.3. Burn-in.

  • With a fixed budget of N = n + n0 chain steps, the burn-in subsection states explicit burn-in choices for reversible chains and chains with an L2-spectral gap.It frames the choice as a trade-off between burn-in n0 and sample size n to make the error bound as small as possible.Source: §3.3 · pp. 61–62
  • Theorem 3.45’s suggested burn-in is close to the numerically computed minimizer, but with N = 10^5 and β = 0.999 the available resources cannot yield an error below 1.For sufficiently large resources, the computed burn-ins for p ∈ {2} ∪ [4, ∞) are of the same magnitude.Source: §3.3 · p. 63
  • When β, C, and p are known, choose the suggested burn-in; underestimating log(C)/log(β^-1) can strongly affect error, while overestimating it has less impact.If β or C is unknown, choosing n = n0 = N/2 achieves the same convergence rate at an asymptotic factor-of-2 error cost.Source: §3.3 · pp. 63–64

3.4. Examples.

  • In Example 1, the reversible chain is uniformly ergodic with parameters (1/24, 1/2) and has an L2-spectral gap with β ≤ 1/24.It is also L1-exponentially convergent with parameters (1/24, 1).Source: Example 1 · p. 67
  • In Example 2, the lazy chain is L1-exponentially convergent with parameters (1/2, 3), and the convergence rate α = 1/2 is optimal because β = 1/2.For δ = 10^-3, the lower error bound becomes non-trivial at N ≥ n0 + 6 = 19, while the upper-bound curve is shifted down from the exact error.Source: Example 2 · pp. 68–69
  • Metropolis–Hastings constructs a transition kernel reversible with respect to its target density, including when that density is unnormalized.For an independent proposal, the passage states that a condition involving γ > 0 yields uniform ergodicity.Source: Metropolis-Hastings algorithm · pp. 71–72
  • For this reversible Metropolis–Hastings kernel, L1-exponential convergence with (1 − ξ⁻¹, 1) implies an L2-spectral gap for its Markov operator, with 1 − β ≥ ξ⁻¹.Source: Metropolis-Hastings algorithm · p. 72

3.5. Notes and remarks.

  • The paper presents an explicit error bound for S_n,n0 when integrands belong to L_V; for reversible chains, V-uniform ergodicity is equivalent to an L2-spectral gap.When V ∈ Lp for some p > 2, L_V is contained in Lp, so Theorem 3.41 can also be applied.Source: §3.5 · p. 77
  • With reversibility and L1-exponential convergence, the paper gives an L2-norm error bound; with only an L2-spectral gap, it gives uniform upper bounds in Lp for p > 2 without requiring reversibility.The latter setting requires that the stationary distribution be hat π; the suggested burn-in choice is also described as new.Source: §3.5 · p. 78

4. Applications

This section applies MCMC error bounds to integration with possibly unnormalized log-concave densities and over convex bodies, framing the problems in an oracle-complexity setting. It establishes polynomial tractability under stated conditions, including for convex-body integration using lazy hit-and-run when p > 2 is fixed.

4. Applications.

  • For general density classes, the integration complexity can grow linearly with C, motivating MCMC methods for tractability with respect to C on certain classes.The section notes that C can be very large and presents MCMC as a way to achieve this tractability goal for suitable inputs.Source: §4 · pp. 80–81

4.1. Integration with respect to log-concave densities.

  • For a ball domain rBd, the ball walk has local conductance at least 0.3 when its step radius δ is at most r/(d + 1).This lower bound supports the spectral-gap analysis of the lazy Metropolis chain used for integration.Source: §4.1 · pp. 82, 84
  • The log-concave-density algorithm uses a lazy Metropolis chain based on a ball-walk proposal, initialized uniformly on rBd, with an error bound requiring p > 2.The section gives a choice of step size and burn-in for this approximation; p > 2 is required to apply the cited error bound.Source: §4.1 · pp. 83–85
  • For fixed p > 2, integration over rBd with log-concave densities is polynomially tractable, with complexity polynomial in L, ε^-1, d, and r.The result also gives tractability with respect to C = e^(2rL); for p in [4, ∞], the complexity bound can be independent of p.Source: §4.1 · p. 85

4.2. Integration over a convex body.

  • For convex-body integration, the target is the expectation of f under the uniform distribution on an input convex set A, and the oracle can return a uniform point on A intersected with any queried line.The setup does not assume that uniform samples from A can be generated directly.Source: §4.2 · pp. 85–86
  • Hit-and-run chooses a uniformly random direction and samples uniformly along the resulting chord; its transition kernel is reversible, and its lazy version has an L2-spectral-gap lower bound for r ≥ 1.The lower-bound proposition applies to A ∈ Sd(r).Source: §4.2 · pp. 86–88
  • Theorem 4.12 considers approximating S(f, A) with a Markov chain having transition kernel eH and initial distribution uniform ν on Bd; p > 2 is necessary to apply Theorem 3.45(ii).Source: §4.2 · pp. 89–90
  • For fixed p > 2, convex-body integration is polynomially tractable in ε, d, and r; for p ∈ [4, ∞], complexity is bounded independently of p.The theorem concerns integration over Fp(r, d).Source: §4.2 · p. 90

4.3. Notes and remarks.

  • Theorem 4.8 extends an earlier result to integrands in Lp for p > 2 on rBd, retaining the same magnitude of constants and dependence on d, L, and ε, and establishing tractability.Source: §4.3 · p. 90
  • The notes state that ball-walk uniform-ergodicity constants are exponentially bad in d, preventing that bound from establishing polynomial tractability; hit-and-run had not yet been applied to integration of the form (4.6).A hit-and-run generalization for log-concave-density sampling is cited as a possible route to further error bounds [LV06].Source: §4.3 · p. 91

A. Appendix

The appendix introduces functional-analysis tools used to understand MCMC error: the Spectral Theorem, the Riesz–Thorin Interpolation Theorem, and conductance with the Cheeger inequality.

A. Appendix

  • The appendix presents the Spectral Theorem for linear, bounded, self-adjoint operators.It is identified as fundamental to understanding MCMC error.Source: A. Appendix · p. 91
  • The Riesz–Thorin Interpolation Theorem is introduced for operators acting on Lp spaces.Source: A. Appendix · p. 91
  • Conductance and the Cheeger inequality are introduced as further functional-analysis tools.Source: A. Appendix · p. 91

A.1. Spectral Theorem.

This subsection states a spectral theorem for bounded self-adjoint operators, describing a spectral measure and its relation to the operator's spectrum and continuous functions of the operator.

A.1. Spectral Theorem.

  • The associated signed measure is non-negative when its two arguments are equal.Source: §A.1 · p. 92
  • The spectrum of P is closed, lies in [λ, Λ], and includes both λ and Λ.Source: §A.1 · p. 92
  • A self-adjoint bounded operator P has a uniquely determined spectral measure E with compact support in spec(P|H).The passage defines a spectral measure through projection-valued properties, including orthogonal projections and countable additivity.Source: §A.1 · pp. 91–92
  • For continuous F on [λ, Λ], functional calculus defines a self-adjoint operator F(P).Its operator norm equals the maximum of |F(α)| over α in spec(P|H).Source: §A.1 · p. 92

A.2. Interpolation Theorem.

This subsection presents the Riesz–Thorin interpolation theorem for operators bounded on two Lq spaces and notes extensions to sequence spaces and complex-valued functions.

A.2. Interpolation Theorem.

  • The interpolation result assumes bounds for a linear operator on Lq1 and Lq2 spaces, with an interpolation parameter θ.The spaces are defined using a probability measure π.Source: §A.2 · pp. 92–93
  • The theorem remains valid when the function spaces are replaced by the corresponding sequence spaces ℓp.Source: §A.2 · p. 93
  • The stated result also holds for complex-valued functions, without the additional factor of two.Source: §A.2 · p. 93

A.3. Conductance and the Cheeger inequality.

This section defines conductance through the probability of leaving a set under the Markov chain and relates it to the Markov operator and Cheeger inequality.

A.3. Conductance and the Cheeger inequality.

  • Conductance is the infimum, over sets A with 0 < π(A) ≤ 1/2, of the conditional probability that X2 lies outside A given X1 lies in A.The numerator of the defining ratio is the probability of X1 ∈ A and X2 ∈ Ac.Source: §A.3 · p. 93
  • The Markov operator P is self-adjoint on L2(D, π).Source: §A.3 · p. 93
  • The Cheeger inequality relates Λ to the conductance ϕ(K, π).Source: §A.3 · p. 93
  • For general state spaces, the Cheeger inequality is proved by Lawler and Sokal [LS88] and by Lovász and Simonovits [LS93].A finite-state-space proof is referenced to [Beh00].Source: §A.3 · p. 93
Loading 1108.3201v2…