{
  "id": "1103.3965",
  "version": "v2",
  "published": "2011-03-21T10:41:30.000Z",
  "updated": "2012-04-18T09:25:17.000Z",
  "title": "On the Stability of Sequential Monte Carlo Methods in High Dimensions",
  "authors": [
    "Alexandros Beskos",
    "Dan Crisan",
    "Ajay Jasra"
  ],
  "categories": [
    "stat.CO"
  ],
  "abstract": "We investigate the stability of a Sequential Monte Carlo (SMC) method applied to the problem of sampling from a target distribution on $\\mathbb{R}^d$ for large $d$. It is well known that using a single importance sampling step one produces an approximation for the target that deteriorates as the dimension $d$ increases, unless the number of Monte Carlo samples $N$ increases at an exponential rate in $d$. We show that this degeneracy can be avoided by introducing a sequence of artificial targets, starting from a `simple' density and moving to the one of interest, using an SMC method to sample from the sequence. Using this class of SMC methods with a fixed number of samples, one can produce an approximation for which the effective sample size (ESS) converges to a random variable $\\varepsilon_N$ as $d\\rightarrow\\infty$ with $1<\\varepsilon_{N}<N$. The convergence is achieved with a computational cost proportional to $Nd^2$. If $\\varepsilon_N\\ll N$, we can raise its value by introducing a number of resampling steps, say $m$ (where $m$ is independent of $d$). In this case, ESS converges to a random variable $\\varepsilon_{N,m}$ as $d\\rightarrow\\infty$ and $\\lim_{m\\to\\infty}\\varepsilon_{N,m}=N$. Also, we show that the Monte Carlo error for estimating a fixed dimensional marginal expectation is of order $\\frac{1}{\\sqrt{N}}$ uniformly in $d$. The results imply that, in high dimensions, SMC algorithms can efficiently control the variability of the importance sampling weights and estimate fixed dimensional marginals at a cost which is less than exponential in $d$ and indicate that, in high dimensions, resampling leads to a reduction in the Monte Carlo error and increase in the ESS.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-04-18T09:25:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sequential monte carlo methods",
      "high dimensions",
      "monte carlo error",
      "fixed dimensional marginal",
      "smc method"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1103.3965B"
    }
  }
}