PRX 速递：模拟退火算法在解决稀疏硬推理问题中的局限性

关键词：模拟退火法算法，图着色问题，玻璃相变，非平衡统计物理，复杂系统

论文题目：Limits and Performances of Algorithms Based on Simulated Annealing in Solving Sparse Hard Inference Problems

论文来源：Physical Review X

论文链接：https://journals.aps.org/prx/abstract/10.1103/PhysRevX.13.021011

种植着色问题（the planted-coloring problem，图着色算法的一种）是一个典型的推理问题，对此，贝叶斯最优算法的阈值，如置信度传播（belief propagation, BP）可以解析计算。模拟退火法（simulated annealing，SA）是一种基于蒙特卡罗的算法，比置信度传播更加通用和稳健，因此具有更广泛的适用性。

这篇 Physical Review X 文章分析了模拟退火法的局限性和性能。作者表明，模拟退火在恢复种植解方面是次优的，因为它被玻璃态所吸引，而玻璃态并不影响置信度传播算法。与以前的猜想不同，该研究通过比较顺磁相的拐点和动态临界温度，提出了对模拟退火法算法阈值的解析估计。这是热力学相变和 Glauber 动力学的失衡行为之间的一个基本联系。

作者还研究了模拟退火法的改进版本，称为副本模拟退火法（replicated SA, RSA），其中几个弱耦合的副本被一起冷却。副本模拟退火法的算法阈值与贝叶斯最优阈值相吻合。最后，该研究发展了一个近似解析理论，解释了副本模拟退火法的最佳性能，并预测了在非常多副本的极限下，向种植解转变的位置。对副本模拟退火法的研究结果支持这样的观点，即先验参数与生成模型的参数不匹配可能会产生一种最佳的、非常稳健的算法。