Improved mixing time bounds for sampling spin models on graphs

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β\leq \frac{1}{2}+\varepsilon$

Data Structures and Algorithms

Summary

Sampling complex systems made of many interacting parts is challenging and important for physics and computer science. The authors developed a new mathematical technique that improves how quickly a well-known sampling process, Glauber dynamics, can reliably generate typical configurations of the Sherrington-Kirkpatrick spin model. Their method involves a subtle adjustment called a rank-1 perturbation, allowing them to prove faster convergence up to a certain temperature threshold. This ensures that, for moderate interaction strengths, sampling can be done efficiently using this approach.

What this means in practice

  • For statistical physics simulators: Improve algorithms generating typical states of spin glass models at moderate temperatures by guaranteeing faster convergence.
  • For probabilistic modelers: Use new spectral gap bounds to design more efficient Markov chain methods for sampling complex systems with many interacting components.

A theory result. No direct application yet.

Authors

Mathews Boban, Anqi Li, Shayan Oveis Gharan

Abstract

We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this technique instead of upper-bounding the influence matrix of a link of co-dimension 2 by $λI$ (where $λ$ is the second eigenvalue of the link), we upper-bound the influence matrix after a carefully chosen rank-1 shift. The rank-1 shift allows for a significantly smaller upper-bound but it comes at the cost of bounding the average loss due to rank-1 perturbations. As an application we use this method to show that the natural Glauber dynamics mixes in polynomial time to generate samples from the Sherrington-Kirkpatrick model for $β\leq \tfrac{1}{2}+\varepsilon$, for an absolute constant $\varepsilon>0$. At the heart of the proof we manage to bound the loss due to rank-1 perturbations by averaging over all links of co-dimension 2.
View PDFOpen arXiv