论文标题
景观修改符合旋转系统：从torpid到快速混合，隧道和退火
Landscape modification meets spin systems: from torpid to rapid mixing, tunneling and annealing in the low-temperature regime
论文作者
论文摘要
给定一个目标gibbs分布$π^0_β\ propto e^{ - β\ mathcal {h}} $从$σ_n上的低温状态中进行采样：= \ { - 1，+1，+1 \}^n $，在本文中，我们建议和分析替代分布的动力学， $π^{f} _ {α，c，1/β} \ propto e^{ - \ Mathcal {h}^{f} _ {α，c，1/β}} $，$ \ Mathcal {h}由参数$ f，α，c $和$β$修改和控制，并共享与$ \ MATHCAL {H} $相同的固定点。 With appropriate tuning of these parameters, the major advantage of the proposed Metropolis dynamics on the modified landscape is that it enjoys an $\mathcal{O}(1)$ critical height while its stationary distribution $π^{f}_{α,c,1/β}$ maintains close proximity with the original target $π^0_β$ in the low-temperature.我们证明了在修改的景观上的快速混合和隧道，对系统尺寸$ n $和反向温度$β$的多项式依赖性，而原始的大都市动力学则与对临界高度和$β$的指数依赖性混合在一起。在模拟退火的情况下，我们证明了其在幂律冷却计划下的长期收敛速度，该速度比经典设置中的典型对数冷却快。 我们在许多模型上说明了我们的结果，包括各种确定性和随机图的Ising模型以及德里达的随机能量模型。在这些应用中，原始动力学会混合在一起，而修改后的景观上的拟议动力学则与对$β$和$ n $的多项式依赖性迅速混合在一起，并在$ \ Mathcal {o}（O}（O}（n^4）$时间中发现近似地面状态。本文强调了景观的几何形状和结构在加速采样器或优化器的设计中的新颖使用。
Given a target Gibbs distribution $π^0_β \propto e^{-β\mathcal{H}}$ to sample from in the low-temperature regime on $Σ_N := \{-1,+1\}^N$, in this paper we propose and analyze Metropolis dynamics that instead target an alternative distribution $π^{f}_{α,c,1/β} \propto e^{-\mathcal{H}^{f}_{α,c,1/β}}$, where $\mathcal{H}^{f}_{α,c,1/β}$ is a transformed Hamiltonian whose landscape is suitably modified and controlled by the parameters $f,α,c$ and $β$ and shares the same set of stationary points as $\mathcal{H}$. With appropriate tuning of these parameters, the major advantage of the proposed Metropolis dynamics on the modified landscape is that it enjoys an $\mathcal{O}(1)$ critical height while its stationary distribution $π^{f}_{α,c,1/β}$ maintains close proximity with the original target $π^0_β$ in the low-temperature. We prove rapid mixing and tunneling on the modified landscape with polynomial dependence on the system size $N$ and the inverse temperature $β$, while the original Metropolis dynamics mixes torpidly with exponential dependence on the critical height and $β$. In the setting of simulated annealing, we prove its long-time convergence under a power-law cooling schedule that is faster than the typical logarithmic cooling in the classical setup. We illustrate our results on a host of models including the Ising model on various deterministic and random graphs as well as Derrida's Random Energy Model. In these applications, the original dynamics mixes torpidly while the proposed dynamics on the modified landscape mixes rapidly with polynomial dependence on both $β$ and $N$ and find the approximate ground state provably in $\mathcal{O}(N^4)$ time. This paper highlights a novel use of the geometry and structure of the landscape to the design of accelerated samplers or optimizers.
