Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909695213568000 |
|---|---|
| author | Gaitonde, Jason Mossel, Elchanan |
| author_facet | Gaitonde, Jason Mossel, Elchanan |
| contents | A popular method for sampling from high-dimensional distributions is the \emph{Gibbs sampler}, which iteratively resamples sites from the conditional distribution of the desired measure given the values of the other coordinates. It is natural to ask to what extent does the order of site updates matter in the mixing time? Two natural choices are (i) standard, or \emph{random scan}, Glauber dynamics where the updated variable is chosen uniformly at random, and (ii) the \emph{systematic scan} dynamics where variables are updated in a fixed, cyclic order. We first show that for systems of dimension $n$, one round of the systematic scan dynamics has spectral gap at most a factor of order $n$ worse than the corresponding spectral gap of a single step of Glauber dynamics, tightening existing bounds in the literature by He, et al. [NeurIPS '16] and Chlebicka, Łatuszyński, and Miasodejow [Ann. Appl. Probab. '25]. The corresponding bound on mixing times is sharp even for simple spin systems by an explicit example of Roberts and Rosenthal [Int. J. Statist. Prob. '15]. We complement this with a converse statement: if all, or even just one scan order rapidly mixes, the Glauber dynamics has a polynomially related mixing time, resolving a question of Chlebicka, Łatuszyński, and Miasodejow. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11136 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics Gaitonde, Jason Mossel, Elchanan Probability Data Structures and Algorithms Computation A popular method for sampling from high-dimensional distributions is the \emph{Gibbs sampler}, which iteratively resamples sites from the conditional distribution of the desired measure given the values of the other coordinates. It is natural to ask to what extent does the order of site updates matter in the mixing time? Two natural choices are (i) standard, or \emph{random scan}, Glauber dynamics where the updated variable is chosen uniformly at random, and (ii) the \emph{systematic scan} dynamics where variables are updated in a fixed, cyclic order. We first show that for systems of dimension $n$, one round of the systematic scan dynamics has spectral gap at most a factor of order $n$ worse than the corresponding spectral gap of a single step of Glauber dynamics, tightening existing bounds in the literature by He, et al. [NeurIPS '16] and Chlebicka, Łatuszyński, and Miasodejow [Ann. Appl. Probab. '25]. The corresponding bound on mixing times is sharp even for simple spin systems by an explicit example of Roberts and Rosenthal [Int. J. Statist. Prob. '15]. We complement this with a converse statement: if all, or even just one scan order rapidly mixes, the Glauber dynamics has a polynomially related mixing time, resolving a question of Chlebicka, Łatuszyński, and Miasodejow. |
| title | Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics |
| topic | Probability Data Structures and Algorithms Computation |
| url | https://arxiv.org/abs/2410.11136 |