Source-linked AI summary
Robust adaptive Metropolis algorithm with coerced acceptance rate
Matti Vihola
TL;DR
The paper addresses the instability of covariance-based adaptive Metropolis methods for heavy-tailed targets and the need to control acceptance rates while learning proposal shape. It introduces RAM, which uses a single computationally simple matrix update to adapt shape and acceptance simultaneously. RAM handles the Student target without finite second moments and appears competitive with AM plus scale adaptation for finite-variance targets, while remaining unsuitable for strongly multimodal targets.
Problem
Covariance-based AM and ASWAM can be unstable for targets without finite second moments, motivating an approach that learns shape while controlling acceptance rate.
Method
RAM replaces empirical-covariance adaptation with a single matrix update that estimates target shape and simultaneously targets a given mean acceptance probability.
Results
RAM keeps proposal adaptation bounded in the heavy-tailed Student example, whereas the AM covariance grows without an upper bound and ASWAM shows considerable variation.
Takeaways & Limitations
RAM can cope with arbitrarily heavy-tailed targets and appears competitive with AM and ASWAM for sufficiently regular light-tailed targets having second moments.
Takeaways & Limitations
RAM is not suitable for strongly multimodal targets, although this limitation also applies to random-walk approaches generally.
Abstract
from arXiv · showhide
The adaptive Metropolis (AM) algorithm of Haario, Saksman and Tamminen [Bernoulli 7 (2001) 223-242] uses the estimated covariance of the target distribution in the proposal distribution. This paper introduces a new robust adaptive Metropolis algorithm estimating the shape of the target distribution and simultaneously coercing the acceptance rate. The adaptation rule is computationally simple adding no extra cost compared with the AM algorithm. The adaptation strategy can be seen as a multidimensional extension of the previously proposed method adapting the scale of the proposal distribution in order to attain a given acceptance rate. The empirical results show promising behaviour of the new algorithm in an example with Student target distribution having no finite second moment, where the AM covariance estimate is unstable. In the examples with finite second moments, the performance of the new approach seems to be competitive with the AM algorithm combined with scale adaptation.
1. Introduction
MCMC uses ergodic averages to approximate integrals, but the proposal shape strongly affects convergence efficiency. The paper introduces RAM to learn target shape while coercing acceptance rates without relying on empirical covariance.
- MCMC motivation: MCMC approximates integrals through ergodic averages of an easily simulated Markov chain.The averages converge to the target integral as the number of samples increases.
- Random walk Metropolis: The RWM algorithm proposes moves using a symmetric density transformed by a nonsingular shape matrix S.Each proposal is accepted with the Metropolis probability or rejected, leaving the chain at its previous state.
- Motivation: The proposal shape crucially affects the speed of convergence even when the chain is asymptotically valid.This makes shape selection central to efficient MCMC.
- Related methods: AM estimates proposal shape from the empirical covariance, while earlier acceptance-rate methods adapt only a scalar proposal scale.AM commonly uses a user-selected scaling parameter, with 2.4/√d widely used under certain theoretical conditions.
- Related methods: ASWAM combines AM’s covariance-based shape adaptation with acceptance-probability optimization.It computes a scaling factor from observed acceptance probabilities while retaining the covariance Cholesky factor.
- Contribution: RAM seeks a matrix factor that captures target shape and attains a given mean acceptance rate through one computationally simple update.Unlike ASWAM, it avoids empirical covariance, which can be problematic for targets without finite second moments.
2. Algorithm
RAM iterates random-walk proposals, Metropolis acceptance decisions, and a rank-one matrix adaptation. The update expands or shrinks proposal contours in the current proposal direction according to the acceptance error.
- Setup: RAM starts from a lower-diagonal factor, a spherically symmetric proposal density, a step-size sequence, and a target acceptance probability.The step sizes lie in (0,1] and decay to zero.
- RAM iteration: Each iteration proposes Yn = Xn−1 + Sn−1Un and accepts it with probability min{1, π(Yn)/π(Xn−1)}.Rejected proposals leave Xn equal to Xn−1.
- RAM iteration: The adaptation step computes Sn as the Cholesky factor of a symmetric positive-definite rank-one update of the previous proposal matrix.This guarantees a unique valid factor at every update.
- Proposal geometry: Spherically symmetric base proposals become elliptically symmetric after transformation by Sn−1, with axes determined by Sn−1ST n−1.The resulting proposal geometry reflects the eigenstructure of the transformed matrix.
- Directional adaptation: If αn < α∗, RAM shrinks the proposal in the current proposal direction; if αn > α∗, it expands that direction.The update therefore adjusts directional scale according to whether observed acceptance is below or above target.
- Interpretation and cost: In one dimension, RAM behaves similarly to ASM and can be viewed as its multidimensional generalization.The paper also notes that rank-one Cholesky updates or downdates keep the adaptation computationally efficient.
- Step-size choice: Choosing ηn = n^-1 is not advisable because adaptation then becomes inefficient when the initial factor differs substantially from the target scale and shape.With this choice, the logarithm of Sn changes at approximately logarithmic speed, limiting growth or shrinkage.
3. Stable points
This section characterizes stable points of RAM, including affine invariance and uniqueness results for elliptically symmetric targets. It also notes broader existence and uniqueness limitations and identifies stable points proportional to the identity for i.i.d. product targets.
- Stable-point formulation: Stable points are matrices S∗ satisfying the mean-field equation hπ(S) = 0, toward which the adaptation process may converge.The RAM recursion is described as a Robbins–Monro stochastic approximation seeking a root of hπ.
- Affine invariance: RAM is invariant under affine transformations: transforming the target and initialization transforms the process through (AS_n)(AS_n)^T with identical distributions.This establishes affine invariance at the process level, not only for individual stable points.
- Affine invariance: The mean field transforms affinely, while orthogonal rotations leave it unchanged; consequently, unique lower-diagonal positive-diagonal solutions transform as ASQ.The orthogonal matrix Q accounts for the rotational non-uniqueness before selecting the lower-diagonal representative.
- Elliptical targets: For elliptically symmetric targets, stable points are proportional to the target’s shape matrix Σ^2, and the solution is unique when the radial function p is non-increasing.The uniqueness argument uses strict decrease of the scalar function g(θ) until it reaches zero.
- Product targets: For i.i.d. product targets, RAM has a stable point proportional to the identity matrix.The result follows from permutation symmetry and continuity of the coordinate-wise mean-field terms.
- Scope and stability: General existence and uniqueness are not established: the paper believes a solution generally exists, but fixed points may fail to be unique.The paper gives a one-dimensional ASM example with non-unique fixed points and reports empirical support for general stability.
4. Validity
Under stated proposal, target-density, step-size, and stability conditions, the RAM algorithm is valid in the sense that empirical averages converge to target integrals. The paper also establishes convergence of the adaptation for elliptically symmetric targets, while noting that stability is difficult to verify and may require enforcement.
- Validity conditions: The validity result targets convergence of empirical averages to the corresponding target integral under suitable conditions.The section defines validity through convergence of empirical averages and states sufficient conditions for this property.
- Validity conditions: The assumptions allow Gaussian or Student proposal densities and require the target to be either bounded with bounded support or positive, continuously differentiable, and suitably light-tailed.For the unbounded-support case, the tails must be super-exponentially decaying with regular contours.
- Validity conditions: The theorem establishes a strong law of large numbers for suitable functions when the adaptation step sizes and proposal-matrix eigenvalues satisfy the stated conditions.The result holds almost surely on the event that the stability bounds remain nondegenerate and finite.
- Adaptation convergence: For elliptically symmetric targets, the adaptation can also be shown to converge under the conditions associated with the paper’s convergence theorems.The paper states this as an additional convergence result beyond the general validity theorem.
- Stability caveat: Stability is natural but difficult to verify in practice; the paper does not provide a precise stability analysis and instead describes an enforcement modification.Bounding the eigenvalues of the updated proposal matrix preserves stability, but may change stable points and invalidate the elliptically symmetric-target conclusion.
5. Experiments
The experiments compare RAM with AM and ASWAM on heavy-tailed Student, Gaussian, and multimodal Gaussian targets. RAM is stable for the heavy-tailed target, competitive or more accurate in several finite-moment settings, but struggles with separated modes.
- Multivariate Student distribution: The bivariate Student target has no second moments, making the empirical covariance estimates used by AM and ASWAM unstable.This target therefore directly tests robustness beyond finite-covariance settings.
- Multivariate Student distribution: AM's covariance grows without bound, whereas RAM converges toward a limiting value; ASWAM remains bounded but exhibits considerable persistent variation.ASWAM offsets the growing Cholesky factor with a decaying scale factor to maintain the desired acceptance rate.
- Multivariate Student distribution: RAM estimates of the proportion outside the 90% HPD set are centered around the true value, while AM slightly overestimates and ASWAM tends to underestimate it.AM also shows more variation than ASWAM and RAM in this diagnostic.
- Gaussian distribution: In Gaussian targets, RAM is comparable to AM and ASWAM in dimension two and more accurate than AM and AMS as dimension increases.The comparison uses overall root mean square error of quantile estimates across randomly generated covariance matrices.
- Mixture of separate Gaussians: The mixture experiment shows RAM learns a local shape, which can be a weakness when modes are separated even though random-walk methods already find multimodality challenging.As component means separate further, RAM's stable point approaches the common within-component covariance.
6. Discussion
RAM attains a specified acceptance probability while estimating the target’s shape and can handle arbitrarily heavy-tailed targets. Its limitations include unsuitability for strongly multimodal targets and theoretical results restricted to elliptically symmetric and product-type targets.
- RAM attains a given acceptance probability while simultaneously estimating the shape of the target distribution.
- Unlike covariance-based AM and ASWAM, RAM can cope with targets having arbitrarily heavy tails.
- RAM is not suitable for strongly multimodal targets, as with random-walk-based approaches generally.
- For sufficiently regular light-tailed targets with second moments, experiments indicate that RAM is competitive with AM and ASWAM.
- The theoretical analysis covers only elliptically symmetric and product-type target densities, while stability without prior bounds remains an open question.
Appendix A. Regularity of directional mean acceptance probability
The appendix establishes regularity properties for the directional mean acceptance probability by using continuity, boundedness, approximation, and dominated convergence arguments. It first treats continuous target densities and then extends the reasoning to general densities through smooth approximation.
- For continuous target densities, pointwise convergence of the acceptance integrand follows from continuity of the density.
- Dominated convergence applies because the integrand is bounded by 1, establishing continuity of the directional mean acceptance function.
- As the scale parameter tends to 0, the integrand tends to 1; as it tends to infinity, the integrand tends to 0.
- For general target densities, the proof approximates the density by smooth non-negative functions and normalizes them into probability densities.
Appendix B. Proofs of convergence
The convergence proofs verify regularity and stability conditions for random-walk Metropolis kernels over bounded shape-matrix classes. Under the stated assumptions, the proposal matrices remain spectrally bounded with high probability, which supports a strong law of large numbers.
- The random-walk Metropolis kernel uses proposal density q_s(z) = det(s)^-1 q(s^-1z) for lower triangular shape matrices with positive diagonal.
- Kernel integration is denoted by ∫f(y)P_s(x,dy), and the convergence argument considers these kernels over admissible shape matrices.
- The assumptions require unique invariant distributions, simultaneous drift and minorisation, continuity, and a uniform bound on H(s,x,u).
- Irreducibility, aperiodicity, and reversibility establish uniqueness of the invariant distribution, while prior work supplies the drift, continuity, and Student-proposal conditions.
- With high probability, eigenvalues of S_nS_n^T remain within finite bounds, which is sufficient for the strong law of large numbers.