Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?

Matti Vihola (University of Jyväskylä)


The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix, at step $n+1$, $S_n=\mathrm{Cov}(X_1,\ldots,X_n)+\varepsilon I$, that is, the sample covariance matrix of the history of the chain plus a (small) constant $\varepsilon>0$ multiple of the identity matrix $I$ . The lower bound on the eigenvalues of $S_n$ induced by the factor $\varepsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\varepsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away from zero. The behaviour of $S_n$ is studied in detail, indicating that the eigenvalues of $S_n$ do not tend to collapse to zero in general. In dimension one, it is shown that $S_n$ is bounded away from zero if the logarithmic target density is uniformly continuous. For a modification of the AM algorithm including an additional fixed component in the proposal distribution, the eigenvalues of $S_n$ are shown to stay away from zero with a practically non-restrictive condition. This result implies a strong law of large numbers for super-exponentially decaying target distributions with regular contours.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 45-75

Publication Date: January 2, 2011

DOI: 10.1214/EJP.v16-840


  1. Andrieu, Christophe; Moulines, Éric. On the ergodicity properties of some adaptive MCMC algorithms. Ann. Appl. Probab. 16 (2006), no. 3, 1462--1505. MR2260070 (2008f:65005)
  2. Andrieu, Christophe; Robert, Christian. Controlled MCMC for optimal sampling. Technical Report Ceremade 0125, Universite Paris Dauphine (2001).
  3. Andrieu, Christophe; Thoms, Johannes. A tutorial on adaptive MCMC. Stat. Comput. 18 (2008), no. 4, 343--373. MR2461882
  4. Atchadé, Yves; Fort, Gersende. Limit theorems for some adaptive MCMC algorithms with subgeometric kernels. Bernoulli 16 (2010), no. 1, 116--154. MR2648752 (Review)
  5. Atchadé, Yves; Rosenthal, Jeffrey. On adaptive Markov chain Monte Carlo algorithms. Bernoulli 11 (2005), no. 5, 815-828. MR2172842 (2006h:62077)
  6. Athreya, K. B.; Ney, P. A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245 (1978), 493--501. MR0511425 (80i:60092)
  7. Bai, Yan; Roberts, Gareth; Rosenthal, Jeffrey. On the containment condition for adaptive Markov chain Monte Carlo algorithms. Preprint (2008). Available at this URL.
  8. Esseen, Carl-Gustav. On the Kolmogorov-Rogozin inequality for the concentration function. Z. Wahrscheinlichkeitstheorie verw. Gebiete 5 (1966), no. 3, 210-216.
  9. Haario, Heikki; Saksman, Eero; Tamminen Johanna. An adaptive Metropolis algorithm. Bernoulli 7 (2001), no. 2, 223-242. MR1828504 (2002c:65008)
  10. Hall, P.; Heyde, C. C. Martingale limit theory and its application. Probability and Mathematical Statistics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. xii+308 pp. ISBN: 0-12-319350-8 MR0624435 (83a:60001)
  11. Jarner, Søren Fiig; Hansen, Ernst. Geometric ergodicity of Metropolis algorithms. Stochastic Process. Appl. 85 (2000), no. 2, 341--361. MR1731030 (2001c:60108)
  12. Nummelin, Esa. A splitting technique for Harris recurrent Markov chains. Z. Wahrscheinlichkeitstheorie verw. Gebiete 43 (1978), no. 3, 309-318.
  13. Roberts, Gareth O.; Rosenthal, Jeffrey S. General state space Markov chains and MCMC algorithms. Probab. Surv. 1 (2004), 20--71 (electronic). MR2095565 (2005i:60135)
  14. Roberts, Gareth O.; Rosenthal, Jeffrey S. Coupling and ergodicity of adaptive Markov chain Monte Carlo algorithms. J. Appl. Probab., 44 (2007), no. 2, 458-475. MR2340211 (2008g:60221)
  15. Roberts, Gareth O.; Rosenthal, Jeffrey S. Examples of adaptive MCMC. J. Comput. Graph. Statist. 18 (2009), no. 2, 349-367.
  16. Rogozin, B. A. An estimate for concentration functions. Theory Probab. Appl. 6 (1961), no. 1, 94-97.
  17. Saksman, Eero; Vihola, Matti. On the ergodicity of the adaptive Metropolis algorithm on unbounded domains. Ann. Appl. Probab. 20 (2010), no. 6, 2178-2203.
  18. Vihola, Matti. On the stability and ergodicity of an adaptive scaling Metropolis algorithm. Preprint (2009), arXiv:0903.4061v2

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.