  We consider Ising models on the hypercube with a general interaction matrix
$J$, and give a polynomial time sampling algorithm when all but $O(1)$
eigenvalues of $J$ lie in an interval of length one, a situation which occurs
in many models of interest. This was previously known for the Glauber dynamics
when *all* eigenvalues fit in an interval of length one; however, a single
outlier can force the Glauber dynamics to mix torpidly. Our general result
implies the first polynomial time sampling algorithms for low-rank Ising models
such as Hopfield networks with a fixed number of patterns and Bayesian
clustering models with low-dimensional contexts, and greatly improves the
polynomial time sampling regime for the antiferromagnetic/ferromagnetic Ising
model with inconsistent field on expander graphs. It also improves on previous
approximation algorithm results based on the naive mean-field approximation in
variational methods and statistical physics.
  Our approach is based on a new fusion of ideas from the MCMC and variational
inference worlds. As part of our algorithm, we define a new nonconvex
variational problem which allows us to sample from an exponential reweighting
of a distribution by a negative definite quadratic form, and show how to make
this procedure provably efficient using stochastic gradient descent. On top of
this, we construct a new simulated tempering chain (on an extended state space
arising from the Hubbard-Stratonovich transform) which overcomes the obstacle
posed by large positive eigenvalues, and combine it with the SGD-based sampler
to solve the full problem.
