Complexity results for MCMC derived from quantitative bounds
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Complexity results for MCMC derived from quantitative bounds. / Yang, Jun; Rosenthal, Jeffrey S.
I: Annals of Applied Probability, Bind 33, Nr. 2, 01.04.2023, s. 1459-1500.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Complexity results for MCMC derived from quantitative bounds
AU - Yang, Jun
AU - Rosenthal, Jeffrey S.
PY - 2023/4/1
Y1 - 2023/4/1
N2 - This paper considers how to obtain MCMC quantitative convergence bounds which can be translated into tight complexity bounds in high-dimensional settings. We propose a modified drift-and-minorization approach, which establishes generalized drift conditions defined in subsets of the state space. The subsets are called the “large sets”, and are chosen to rule out some “bad” states which have poor drift property when the dimension of the state space gets large. Using the “large sets” together with a “fitted family of drift functions”, a quantitative bound can be obtained which can be translated into a tight complexity bound. As a demonstration, we analyze several Gibbs samplers and obtain complexity upper bounds for the mixing time. In particular, for one example of Gibbs sampler which is related to the James–Stein estimator, we show that the number of iterations required for the Gibbs sampler to converge is constant under certain conditions on the observed data and the initial state. It is our hope that this modified drift-and-minorization approach can be employed in many other specific examples to obtain complexity bounds for high-dimensional Markov chains.
AB - This paper considers how to obtain MCMC quantitative convergence bounds which can be translated into tight complexity bounds in high-dimensional settings. We propose a modified drift-and-minorization approach, which establishes generalized drift conditions defined in subsets of the state space. The subsets are called the “large sets”, and are chosen to rule out some “bad” states which have poor drift property when the dimension of the state space gets large. Using the “large sets” together with a “fitted family of drift functions”, a quantitative bound can be obtained which can be translated into a tight complexity bound. As a demonstration, we analyze several Gibbs samplers and obtain complexity upper bounds for the mixing time. In particular, for one example of Gibbs sampler which is related to the James–Stein estimator, we show that the number of iterations required for the Gibbs sampler to converge is constant under certain conditions on the observed data and the initial state. It is our hope that this modified drift-and-minorization approach can be employed in many other specific examples to obtain complexity bounds for high-dimensional Markov chains.
UR - http://dx.doi.org/10.1214/22-aap1846
U2 - 10.1214/22-aap1846
DO - 10.1214/22-aap1846
M3 - Journal article
VL - 33
SP - 1459
EP - 1500
JO - Annals of Applied Probability
JF - Annals of Applied Probability
SN - 1050-5164
IS - 2
ER -
ID: 361385361