Low-Temperature Sampling via Equilibrium Disagreements
summary
The gist
The framework develops a new method for sampling at low temperatures using Glauber dynamics, addressing bottlenecks caused by phase coexistence in this regime…
In short
The framework uses Glauber dynamics to sample at low temperatures, overcoming slow mixing caused by phase coexistence. The core innovation links convergence within a single phase to the geometry of disagreements between two independent configurations from that phase. This geometric understanding leads to fast convergence guarantees for three canonical models on random regular graphs.
Key concepts
- Glauber Dynamics
- This is a method used to simulate physical systems, like spin models, by making local changes randomly. In this paper, it's used to sample configurations from the target phase of a model at low temperatures. The goal is to ensure the simulation reaches the correct equilibrium state quickly.
- Phase Coexistence
- This occurs when a system can exist in multiple stable states simultaneously, which often leads to very slow mixing times in simulations. The paper addresses this bottleneck by relating convergence to how two independent samples from the same phase disagree geometrically.
- Weak Poincaré Inequality
- This is a mathematical tool used to prove fast convergence rates for Markov chains like Glauber dynamics. The authors derive a simple version based on the geometry of disagreements between two independent configurations, which allows them to bound the variance and guarantee rapid mixing.
Terminology used across episodes
This episode discusses
- Low-Temperature Sampling via Equilibrium Disagreements · Paper Radio
- Rapid mixing of Potts Glauber dynamics throughout uniqueness · Paper Radio
- Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs · Paper Radio
- Rapid Mixing on Random Regular Graphs beyond Uniqueness
- Characterizing the limiting critical Potts measures on locally regular-tree-like expander graphs
- Planting and MCMC Sampling from the Potts model
- Rapid phase ordering for Ising and Potts dynamics on random regular graphs
- Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs · Paper Radio
- Improved rapid phase ordering for Ising dynamics on random regular graphs · Paper Radio
- The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
- On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
The paper
Low-Temperature Sampling via Equilibrium Disagreements · Read on arXiv
Department of Computer Science, University of Oxford · Department of Computer Science, University of Rochester
We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: --- For the hard-core model on random bipartite d-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in n 3/2+o(1) steps throughout the non-uniqueness regime λ>λ c(d). --- For the random-cluster model on random d-regular graphs, for every real q>2, Glauber dynamics initialised from the all-in edge set mixes within the ordered phase in n 3/2+o(1) steps for all β at least β c. Similarly, Glauber dynamics initialised from the all-out edge set mixes within the disordered phase in n 3/2+o(1) steps for β at most β c. --- For the ferromagnetic Ising model on random d-regular graphs, Glauber dynamics initialised from all-plus or all-minus mixes within the corresponding phase in n 3/2+o(1) steps throughout the low-temperature regime β>β c(d). We also give an n 2+o(1) -time algorithm that combines phase samples into samples from the full distribution, avoiding in particular time-costly approximations of the corresponding partition functions to the target sampling accuracy.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Low-Temperature Sampling via Equilibrium Disagreements".
Jane: Here's the gist of the paper. The framework develops a new method for sampling at low temperatures using Glauber dynamics, addressing bottlenecks caused by phase coexistence in this regime, which can otherwise lead to exponentially slow mixing times.
Tom: The core innovation is relating convergence within a single phase to the geometry of disagreements between two independent configurations drawn from that phase.
Jane: The approach is applied to three canonical models on random regular graphs: 1.
Tom: Hard-core model on random bipartite d-regular graphs: Glauber dynamics initialized from either one-sided independent set mixes within the corresponding phase in n 3/2+o(1) steps throughout the non-uniqueness regime lambda > lambda c(d).
Paper summary: Tom: So to recap, the paper "Low-Temperature Sampling via Equilibrium Disagreements" introduces a new framework for sampling at low temperatures using Glauber dynamics that overcomes bottlenecks caused by phase coexistence, which usually leads to exponentially slow mixing times.
Jane: The main thesis is relating convergence within a single phase to the geometry of disagreements between two independent configurations drawn from that same phase, which provides a path toward fast convergence from natural initializations.
Lu: They apply this idea to three canonical models on random regular graphs: the hard-core model on random bipartite d-regular graphs, the random-cluster model on random d-regular graphs, and the ferromagnetic Ising model >
Meng: For these models, they establish fast convergence times for Glauber dynamics starting from natural initializations within each phase, specifically showing mixing within n to the power of three over one plus o one steps under certain conditions on parameters like lambda or beta >
Lalam: They also contribute an algorithm that combines these phase samples into an epsilon sample from the full distribution, which avoids time-costly approximations of the partition functions and this is especially important for models like the hard-core and ferromagnetic Ising model >
Tom: Essentially, they've moved from a problem where we had to wait for potentially exponential times to a situation where we have concrete time bounds based on geometric properties of the configurations >
Jane: It matters because these results apply across different types of phase transitions; for example, the hard-core phases merge at the uniqueness threshold, while the random-cluster phases remain distinct and stable even at beta sub c of d >
Conclusion: Tom: So looking at the whole paper "Low-Temperature Sampling via Equilibrium Disagreements" and its authors, they've provided concrete runtime bounds for sampling in regimes where standard methods would struggle due to phase coexistence.
Jane: The big takeaway is that by focusing on the geometry of disagreement between two samples from the same phase, they’ve created a new way to guarantee fast convergence for Glauber dynamics using natural starting points >
Lu: This framework connects equilibrium configuration geometry directly to Glauber dynamics convergence, leading to bounds like n to the power of three steps for several key models >
Meng: For someone who has to deploy this at scale, the practical implication is that we can expect much faster sampling times than what's currently guaranteed by standard theoretical approaches when dealing with these multi-modal distributions >
Lalam: The authors also developed a fast algorithm to get an epsilon sample from the full distribution in time proportional to n squared, which is significant because it avoids those slow approximation techniques for partition functions >
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game