Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T20:02:49.103Z Has data issue: false hasContentIssue false
  • English
  • Français

Error Bounds and Normalising Constants for Sequential Monte Carlo Samplers in High Dimensions

Part of: Probabilistic methods, simulation and stochastic differential equations Parametric inference

Published online by Cambridge University Press:  22 February 2016

Alexandros Beskos ,
Dan O. Crisan ,
Ajay Jasra  and
Nick Whiteley
Alexandros Beskos*
Affiliation:
National University of Singapore
Dan O. Crisan*
Affiliation:
Imperial College London
Ajay Jasra*
Affiliation:
National University of Singapore
Nick Whiteley*
Affiliation:
University of Bristol
*
∗ Postal address: Department of Statistics and Applied Probability, National University of Singapore, 6 Science Drive 2, 117546, Singapore.
∗∗ Postal address: Department of Mathematics, Imperial College London, 180 Queens Gate, London SW7 2AZ, UK.
∗ Postal address: Department of Statistics and Applied Probability, National University of Singapore, 6 Science Drive 2, 117546, Singapore.
∗∗∗∗ Postal address: Department of Mathematics, University of Bristol, University Walk, Bristol BS8 1TW, UK.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we develop a collection of results associated to the analysis of the sequential Monte Carlo (SMC) samplers algorithm, in the context of high-dimensional independent and identically distributed target probabilities. The SMC samplers algorithm can be designed to sample from a single probability distribution, using Monte Carlo to approximate expectations with respect to this law. Given a target density in d dimensions our results are concerned with d → ∞, while the number of Monte Carlo samples, N, remains fixed. We deduce an explicit bound on the Monte-Carlo error for estimates derived using the SMC sampler and the exact asymptotic relative -error of the estimate of the normalising constant associated to the target. We also establish marginal propagation of chaos properties of the algorithm. These results are deduced when the cost of the algorithm is O(Nd2).

Keywords

Sequential Monte Carlohigh dimensionspropagation of chaosnormalising constant

MSC classification

Primary: 65C05: Monte Carlo methods
Secondary: 62F15: Bayesian inference
Type
Research Article
Information
Advances in Applied Probability , Volume 46 , Issue 1 , March 2014 , pp. 279 - 306
Copyright
© Applied Probability Trust 

References

Bédard, M. (2007). Weak convergence of Metropolis algorithms for non-i.i.d. target distributions. Ann. Appl. Prob. 17, 1222–1244.CrossRefGoogle Scholar
Bengtsson, T., Bickel, P. and Li, B. (2008). Curse-of-dimensionality revisited: collapse of the particle filter in very large scale systems. In Probability and Statistics: Essays in Honor of David A. Freeman, Institute of Mathematical Statistics, Beachwood, OH, pp. 316–334.Google Scholar
Beskos, A., Crisan, D. and Jasra, A. (2014). On the stability of sequential Monte Carlo methods in high dimensions. To appear in Ann. Appl. Prob. CrossRefGoogle Scholar
Bickel, P., Li, B. and Bengtsson, T. (2008). Sharp failure rates for the bootstrap particle filter in high dimensions. In Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh, Institute of Mathematical Statistics, Beachwood, OH, pp. 318–329.Google Scholar
Breyer, L. A., Piccioni, M. and Scarlatti, S. (2004). Optimal scaling of MaLa for nonlinear regression. Ann. Appl. Prob. 14, 1479–1505.Google Scholar
Campillo, F., Cérou, F., Le Gland, F. and Rakotozafy, R. (1995). Particle and cell approximations for nonlinear filtering. Res. Rep. (2567), INRIA.Google Scholar
Cérou, F., Del Moral, P. and Guyader, A. (2011). A nonasymptotic theorem for unnormalized Feynman–Kac particle models. Ann. Inst. H. Poincaré Prob. Statist. 47, 629–649.Google Scholar
Chopin, N. (2002). A sequential particle filter for static models. Biometrika 89, 539–551.Google Scholar
Del Moral, P. (2004). Feynman–Kac Formulae: Genealogical and Interacting Particle Systems with Applications. Springer, New York.Google Scholar
Del Moral, P., Doucet, A. and Jasra, A. (2006). Sequential Monte Carlo samplers. J. R. Statist. Soc. B 68, 411–436.CrossRefGoogle Scholar
Del Moral, P., Doucet, A. and Jasra, A. (2012). An adaptive sequential Monte Carlo method for approximate Bayesian computation. Statist. Comput. 22, 1009–1020.Google Scholar
Del Moral, P., Doucet, A. and Jasra, A. (2012). On adaptive resampling strategies for sequential Monte Carlo methods. Bernoulli 18, 252–278.Google Scholar
Denison, D. G. T., Holmes, C. C., Mallick, B. K. and Smith, A. F. M. (2002). Bayesian Methods for Nonlinear Classification and Regression. John Wiley, Chichester.Google Scholar
Doucet, A., Godsill, S. and Andrieu, C. (2000). On sequential Monte Carlo sampling methods for Bayesian filtering. Statist. Comput. 3, 197–208.Google Scholar
Eberle, A., and Marinelli, C. (2013). Quantitative approximations of evolving probability measures and sequential Markov chain Monte Carlo methods. Prob. Theory Relat. Fields 155, 665–701.Google Scholar
Kantas, N., Beskos, A. and Jasra, A. (2014). Sequential Monte Carlo methods for high dimensional inverse problems: a case study for the Navier–Stokes equations. Preprint. Available at: http://arxiv.org/abs/1307.6127[stat.Co].Google Scholar
Kontoyiannis, I. and Meyn, S. P. (2005). Large deviations asymptotics and the spectral theory of multiplicatively regular Markov processes. Electron. J. Prob. 10, 61–123.CrossRefGoogle Scholar
Neal, R. M. (2001). Annealed importance sampling. Statist. Comput. 11, 125–139.Google Scholar
Rebeschini, P. and Van Handel, R. (2013). Can local particle filters beat the curse of dimensionality? Preprint. Available at: http://arxiv.org/abs/1301.6585.Google Scholar
Roberts, G. O. and Rosenthal, J. S. (1998). Optimal scaling of discrete approximations to Langevin diffusions. J. R. Statist. Soc. B 60, 255–268.Google Scholar
Roberts, G. O. and Rosenthal, J. S. (2001). Optimal scaling for various Metropolis–Hastings algorithms. Statist. Sci. 16, 321–390.Google Scholar
Roberts, G. O., Gelman, A. and Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. Ann. Appl. Prob. 7, 110–120.Google Scholar
Schweizer, N. (2012). Non-asymptotic error bounds for sequential MCMC and stability of Feynman–Kac propagators. Preprint. Available at: http://arxiv.org/abs/1204.2382.Google Scholar
Snyder, C., Bengtsson, T., Bickel, P. and Anderson, J. (2008). Obstacles to high-dimensional particle filtering. Monthly Weather Rev. 136, 4629–4640.CrossRefGoogle Scholar
Whiteley, N. (2012). Sequential Monte Carlo samplers: error bounds and insensitivity to initial conditions. Stoch. Anal. Appl. 5, 774–798.CrossRefGoogle Scholar
Whiteley, N., Kantas, N. and Jasra, A. (2012). Linear variance bounds for particle approximations of time-homogeneous Feynman–Kac formulae. Stoch. Process. Appl. 122, 1840–1865.Google Scholar