Georgia Institute of Technology College of Sciences

MCMC and variational inference are two competing paradigms for the problem of sampling from a given probability distribution. In this talk, I'll show how they can work together to give the first polynomial-time sampling algorithm for approximately low-rank Ising models. Sampling was previously known when all eigenvalues of the interaction matrix fit in an interval of length 1; however, a single outlier can cause Glauber dynamics to mix torpidly. Our result covers the case when all but O(1) eigenvalues lie in an interval of length 1. To deal with positive eigenvalues, we use a temperature-based heuristic for MCMC called simulated tempering, while to deal with negative eigenvalues, we define a nonconvex variational problem over Ising models, solved using SGD. Our result has applications to sampling Hopfield networks with a fixed number of patterns, Bayesian clustering models with low-dimensional contexts, and antiferromagnetic/ferromagnetic Ising model on expander graphs.