Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
复制标题
DOI：
10.1088/1742-5468/ac3657
复制
发表时间：
2021-11-01
影响因子：
2.4
通讯作者：
de Feo, Simone
中科院分区：
文献类型：
--
作者：
Angelini, Maria Chiara;Fachin, Paolo;de Feo, Simone
过度参数化是推理和机器学习领域最近发展的一个关键因素。然而，解释这一成功的好理论仍然缺乏。在本文中，我们研究了一个非常简单的情况下，不匹配的过参数化算法应用于一个最研究的推理问题：种植集团问题。我们分析了与著名的Jerrum算法同类的蒙特卡罗（MC）算法。我们展示了如何MC算法是在一般次优的种植集团的恢复。然而，我们展示了如何通过添加一个（不匹配的）参数来提高其性能：温度;我们在数值上发现，这种过参数化的算法版本可以达到种植集团问题的假设算法阈值。
Over-parametrization was a crucial ingredient for recent developments in inference and machine-learning fields. However a good theory explaining this success is still lacking. In this paper we study a very simple case of mismatched over-parametrized algorithm applied to one of the most studied inference problem: the planted clique problem. We analyze a Monte Carlo (MC) algorithm in the same class of the famous Jerrum algorithm. We show how this MC algorithm is in general suboptimal for the recovery of the planted clique. We show however how to enhance its performances by adding a (mismatched) parameter: the temperature; we numerically find that this over-parametrized version of the algorithm can reach the supposed algorithmic threshold for the planted clique problem.