揭示对称二元感知机中计算与统计极限的潜在差距
Parametric RDT approach to computational gap of symmetric binary perceptron
- 用参数化随机对偶理论分析感知机模型的解空间结构变化
- 推算出可满足性阈值约1.8159，算法可达阈值约1.6021，存在非零间隙
- 结果与已有理论预测高度一致，适合研究计算复杂性者参考
本文通过参数化使用全提升随机对偶理论（fl-RDT），研究对称二元感知机（SBP）中统计-计算间隙（SCG）的潜在存在。在第二层提升时观察到关键参数序列 $c$ 的有序性从递减变为任意，该变化与可满足性（$α_c$）和算法性（$α_a$）约束密度阈值转变相关，暗示存在非零计算间隙 $SCG = α_c - α_a$。第二层估计与理论 $α_c$ 一致，而 $r\rightarrow \infty$ 层次的估计被认为对应 $α_a$。以典型 SBP（$κ=1$ 边界）为例，得 $α_c \approx 1.8159$（第二层），$α_a \approx 1.6021$（第七层，趋于 ∼1.59）。结果与近期文献高度吻合：(i) [20] 局部熵重现实例预测 $α_{LE} \approx 1.58$ 为团簇解分裂起点；(ii) 在 $α\rightarrow 0$ 极限下，第三层得 $κ \approx 1.2385\sqrt{\frac{α_a}{-\log(α_a)}}$，定性匹配 OGP 预测 [43] 及局部熵预测 [24]；(iii) $c$-序列序变现象与不对称感知机 [98] 和负霍普菲尔德模型 [100] 一致；(iv) 借鉴 CLuP 算法设计，其实际性能与理论预测接近。
原文摘要 · Abstract (English)
We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of \emph{fully lifted random duality theory} (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered $c$-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with \emph{satisfiability} ($α_c$) -- \emph{algorithmic} ($α_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=α_c-α_a$. The second level estimate is shown to match the theoretical $α_c$ whereas the $r\rightarrow \infty$ level one is proposed to correspond to $α_a$. For example, for the canonical SBP ($κ=1$ margin) we obtain $α_c\approx 1.8159$ on the second and $α_a\approx 1.6021$ (with converging tendency towards $\sim 1.59$ range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts $α_{LE}\approx 1.58$ as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in $α\rightarrow 0$ regime we obtain on the third lifting level $κ\approx 1.2385\sqrt{\frac{α_a}{-\log\left ( α_a \right ) }}$ which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) $c$-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。