Capacity lower bound for the Ising perceptron
Capacity lower bound for the Ising perceptron
复制标题
伊辛感知器的容量下限
DOI：
10.1145/3313276.3316383
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Nike Sun
中科院分区：
文献类型：
--
作者：
Jian Ding;Nike Sun
我们考虑具有高斯无序的伊辛感知器，它相当于由 M 个随机半空间相交的离散立方体 {−1,+1}N。感知器的容量是交集非空的最大整数 MN 。 Krauth 和 Mézard (1989) 推测（随机）比率 MN/N 在概率上收敛于显式常数 α⋆≐ 0.83。 Kim 和 Roche (1998) 以高概率证明了正常数 γ 的存在，使得 γ ≤ MN/N ≤ 1−γ ；另见 Talagrand (1999)。在本文中，我们证明了在显式单变量函数 S(λ) 在 λ=0 处最大化的条件下，Krauth-Mézard 猜想 α⋆ 是具有正概率的下界。我们的证明是将二阶矩方法应用于感知器配置的某个切片，由所谓的 TAP（Thouless、Anderson 和 Palmer，1977）或 AMP（近似消息传递）迭代选择，其缩放限制已由 Bayati 和 Montanari（2011）和 Bolthausen（2012）表征。为了验证 S(λ) 的条件，我们概述了一种方法，该方法在当前版本中使用（非严格的）数值积分包实现。在本文的未来版本中，我们打算通过实施严格的数值方法来完成验证。
We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube {−1,+1}N intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured by Krauth and Mézard (1989) that the (random) ratio MN/N converges in probability to an explicit constant α⋆≐ 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ≤ MN/N ≤ 1−γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mézard conjecture α⋆ is a lower bound with positive probability, under the condition that an explicit univariate function S(λ) is maximized at λ=0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on S(λ) we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method.