Research map / Probabilistic and scientific modeling / Variational and generative sampling
Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
Bryan D He, Christopher M De Sa, Ioannis Mitliagkas, Christopher Ré
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the good systematic order x_1,...,x_n instead of random scan | Sequence of Dependencies · Sequence of Dependencies | mixing time: n^2 -> n | Improved |
| Use the reverse systematic order instead of the good order | Sequence of Dependencies · Sequence of Dependencies | mixing time: n -> n^2 | Hurt |
| Alternate sampling between the x and y variable blocks | Two Islands · Two Islands | mixing time: n2^n -> 2^n | Improved |
| Group all x variables before all y variables | Two Islands · Two Islands | mixing time: 2^n -> n2^n | Hurt |
| Use random scan instead of systematic scan | Discrete Pyramid · Discrete Pyramid | mixing time: n^3 -> n | Improved |
| Use systematic scan instead of random scan | Memorize and Repeat · Memorize and Repeat | mixing time: n^3 -> n^2 | Improved |
| Choose the good systematic order x_1,...,x_n instead of random scan | Soft Dependencies · Soft Dependencies | mixing time: n^{3/2} -> n | Improved |
| Choose the reverse systematic order instead of random scan | Soft Dependencies · Soft Dependencies | mixing time: n^{3/2} -> n^2 | Hurt |
Closest papers by meaning
- Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling (ICML 2016 · similarity 0.90)
- Minibatch Gibbs Sampling on Large Graphical Models (ICML 2018 · similarity 0.89)
- Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees (NeurIPS 2019 · similarity 0.89)
- Diffusive Gibbs Sampling (ICML 2024 · similarity 0.88)
- Split Gibbs Discrete Diffusion Posterior Sampling (NeurIPS 2025 · similarity 0.85)
- Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
