论文标题
对大约低级的ISING模型进行采样：MCMC满足变异方法
Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods
论文作者
论文摘要
我们考虑使用一般交互矩阵$ j $上的超立方体上的模型，当除$ o（1）$ o（1）$ j $的其他所有算法时，都会以一定的间隔为$ j $ eigenvalues，并提供多项式的时间抽样算法。当 * All * eigenValues拟合长度为1时，以前以Glauber动力学而闻名。但是，单个离群值可以迫使Glauber动力学混合。 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.它还基于各种方法和统计物理学中的幼稚平均场近似值来改善先前的近似算法结果。 我们的方法基于MCMC和变异推理世界的新思想的新融合。作为我们算法的一部分，我们定义了一个新的非凸变性问题，该问题使我们能够通过负面的二次形式从指数重新加权，并展示如何使用随机梯度下降来证明该过程有效地使该过程有效。最重要的是，我们构建了一个新的模拟回火链（在Hubbard-Stratonovich变换引起的扩展状态空间上），该链克服了大型正征值带来的障碍，并将其与基于SGD的采样器结合起来，以解决完整问题。
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.
