Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
This work addresses a theoretical bottleneck in statistical physics and machine learning for models like anti-ferromagnetic Ising systems, providing improved analysis where prior approaches break down.
The paper tackles the problem of analyzing mixing times for Glauber dynamics in Ising models with a negative spectral outlier, where existing methods fail, and develops a new Gaussian approximation method to achieve near-optimal mixing time bounds in these regimes.
We study the mixing time of Glauber dynamics for Ising models in which the interaction matrix contains a single negative spectral outlier. This class includes the anti-ferromagnetic Curie-Weiss model, the anti-ferromagnetic Ising model on expander graphs, and the Sherrington-Kirkpatrick model with disorder of negative mean. Existing approaches to rapid mixing rely crucially on log-concavity or spectral width bounds and therefore can break down in the presence of a negative outlier. To address this difficulty, we develop a new covariance approximation method based on Gaussian approximation. This method is implemented via an iterative application of Stein's method to quadratic tilts of sums of bounded random variables, which may be of independent interest. The resulting analysis provides an operator-norm control of the full correlation structure under arbitrary external fields. Combined with the localization schemes of Eldan and Chen, these estimates lead to a modified logarithmic Sobolev inequality and near-optimal mixing time bounds in regimes where spectral width bounds fail. We complement these results by proving exponential lower bounds on the mixing time for low temperature anti-ferromagnetic Ising models on sparse random regular graphs and Erdös-Rényi graphs, based on the existence of gapped states as in the recent work of Sellke.