{
  "id": "1205.4181",
  "version": "v3",
  "published": "2012-05-18T15:25:55.000Z",
  "updated": "2015-01-30T09:28:17.000Z",
  "title": "On the stability of some controlled Markov chains and its applications to stochastic approximation with Markovian dynamic",
  "authors": [
    "Christophe Andrieu",
    "Vladislav B. Tadić",
    "Matti Vihola"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/13-AAP953 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2015, Vol. 25, No. 1, 1-45",
  "doi": "10.1214/13-AAP953",
  "categories": [
    "math.ST",
    "stat.ME",
    "stat.TH"
  ],
  "abstract": "We develop a practical approach to establish the stability, that is, the recurrence in a given set, of a large class of controlled Markov chains. These processes arise in various areas of applied science and encompass important numerical methods. We show in particular how individual Lyapunov functions and associated drift conditions for the parametrized family of Markov transition probabilities and the parameter update can be combined to form Lyapunov functions for the joint process, leading to the proof of the desired stability property. Of particular interest is the fact that the approach applies even in situations where the two components of the process present a time-scale separation, which is a crucial feature of practical situations. We then move on to show how such a recurrence property can be used in the context of stochastic approximation in order to prove the convergence of the parameter sequence, including in the situation where the so-called stepsize is adaptively tuned. We finally show that the results apply to various algorithms of interest in computational statistics and cognate areas.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-11-01T14:13:11.000Z",
      "abstract": "We develop a practical approach to establish the stability, that is the recurrence in a given set, of a large class of controlled Markov chains. These processes arise in various areas of applied science and encompass important numerical methods. We show in particular how individual Lyapunov functions and associated drift conditions for the parametrised family of Markov transition probabilities and the parameter update can be combined to form Lyapunov functions for the joint process, leading to the proof of the desired stability property. Of particular interest is the fact that the approach applies even in situations where the two components of the process present a time-scale separation, which is a crucial feature of practical situations. We then move on to show how such a recurrence property can be used in the context of stochastic approximation in order to prove the convergence of the parameter sequence, including in the situation where the so-called stepsize is adaptively tuned. We finally show that the results apply to various algorithms of interest in computational statistics and cognate areas.",
      "comment": "31 pages, accepted for publication in the Annals of Applied Probability",
      "journal": null,
      "doi": null,
      "authors": [
        "Christophe Andrieu",
        "Vladislav B. Tadic",
        "Matti Vihola"
      ]
    },
    {
      "version": "v3",
      "updated": "2015-01-30T09:28:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65C05",
      "65C05",
      "60J05"
    ],
    "keywords": [
      "controlled markov chains",
      "stochastic approximation",
      "markovian dynamic",
      "applications",
      "encompass important numerical methods"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 31,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1205.4181A"
    }
  }
}