Algorithms and Barriers in the Symmetric Binary Perceptron Model
Algorithms and Barriers in the Symmetric Binary Perceptron Model
复制标题
DOI：
10.1109/focs54457.2022.00061
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
D. Gamarnik;Eren C. Kizildag;Will Perkins;Chang-Qing Xu
中科院分区：
文献类型：
--
作者：
D. Gamarnik;Eren C. Kizildag;Will Perkins;Chang-Qing Xu
二元(或Ising)感知器是单层神经网络的玩具模型，可以被视为具有高度连通性的随机约束满足问题。该模型及其对称变种对称二进制感知器(SBP)在统计物理、数学和机器学习中得到了广泛的研究。SBP表现出显著的统计与计算差距：已知的高效算法找到解的密度远远低于解的存在阈值。此外，SBP还表现出一个显著的结构性质：在所有正的约束密度下，几乎所有的解都是被大海明距离隔开的‘完全冻结’的单态[1]，[2]。这表明，找到SBP的解决方案可能在计算上是困难的。然而，与此同时，SBP确实允许在足够低的密度下使用多项式时间搜索算法。文献[3]对这一难题提出了一种猜想的解释：有效的算法在冰冻的情况下成功地找到了大尺寸的指数级稀有星团。然而，最近发现，这种罕见的大型星系团在所有亚临界密度下都存在，甚至在那些远远高于已知有效算法极限的密度下也是如此[4]。因此，这个模型表现出的统计到计算差距的驱动因素仍然是一个谜。在这篇文章中，我们进行了一个不同的景观分析来解释这个问题所表现出的统计到计算的差距。我们证明了在足够高的密度下，SBP表现出多重叠间隙性质(m-OGP)，这是一种复杂的几何性质，被认为是大类算法的严格障碍。我们的分析表明，m-OGP门限(A)远低于可满足性门限；以及(B)匹配最著名的算法门限，直到对数因子$m\right tarrow\inty$。然后，我们证明了m-OGP排除了SBP超过这个阈值的稳定算法类。我们猜想m-OGP门限的$m\right tarrow\inty$是问题的算法门限。此外，我们还研究了已知的感知器模型高效算法的稳定性，并证明了为非对称二元感知器设计的Kim-Roche算法在我们所考虑的意义上是稳定的。
The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be viewed as a random constraint satisfaction problem with a high degree of connectivity. The model and its symmetric variant, the symmetric binary perceptron (SBP), have been studied widely in statistical physics, mathematics, and machine learning.The SBP exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore, the SBP exhibits a striking structural property: at all positive constraint densities almost all of its solutions are ‘totally frozen’ singletons separated by large Hamming distance [1], [2]. This suggests that finding a solution to the SBP may be computationally intractable. At the same time, however, the SBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in [3]: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms [4]. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the statistical-to-computational gap exhibited by this problem. We show that at high enough densities the SBP exhibits the multi Overlap Gap Property (m-OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the m-OGP threshold (a) is well below the satisfiability threshold; and (b) matches the best known algorithmic threshold up to logarithmic factors as $m\rightarrow\infty$. We then prove that the m-OGP rules out the class of stable algorithms for the SBP above this threshold. We conjecture that the $m\rightarrow\infty$ limit of the m-OGP threshold marks the algorithmic threshold for the problem. Furthermore, we investigate the stability of known efficient algorithms for perceptron models and show that the Kim-Roche algorithm [5], devised for the asymmetric binary perceptron, is stable in the sense we consider.