用提升的随机对偶理论分析二值感知机的计算间隙，发现关键阈值随参数层级变化。
Binary perceptron computational gap -- a parametric fl RDT view
- 采用参数化提升随机对偶理论研究二值感知机的算法可行性。
- 在第五层得到约束密度约0.7764，逼近集群解分裂区间(0.77,0.78)。
- 揭示了参数序列演化与高效算法存在的潜在关联，适合研究计算复杂性者阅读。
近期研究表明，非对称二值感知机（ABP）可能表现出统计-计算间隙，其特征为两个相变约束密度阈值： extbf{ extit{(i)}} 可满足阈值 $α_c$，低于/高于时ABP能否作为存储记忆成功/失败； extbf{ extit{(ii)}} 算法阈值 $α_a$，低于/高于时能否高效确定权重使系统作为存储记忆运行。本文研究一种特定参数化的全提升随机对偶理论（fl RDT）在该问题上的应用。随着fl RDT提升层级推进，关键参数序列 $oldsymbol{c}$ 的结构发生显著变化。前两级中$oldsymbol{c}$呈自然递减型；更高层级中其行为转变与 $α_c$-$α_a$ 阈值变化相关。第二级数值给出 $α=α_c≈0.8331$，随层级上升估计值下降，第五级已实现良好收敛，得 $α≈0.7764$。该结果与文献[17,88]所提集群解分裂区间(0.77,0.78)高度一致，该区间被认为导致局部优化算法失效；同时，$oldsymbol{c}$序列的行为转变也与负霍普菲尔德模型近年证实存在高效接近同类阈值算法的现象极为相似。
原文摘要 · Abstract (English)
Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: \textbf{\emph{(i)}} the \emph{satisfiability threshold} $α_c$, below/above which ABP succeeds/fails to operate as a storage memory; and \textbf{\emph{(ii)}} \emph{algorithmic threshold} $α_a$, below/above which one can/cannot efficiently determine ABP's weight so that it operates as a storage memory. We consider a particular parametric utilization of \emph{fully lifted random duality theory} (fl RDT) [85] and study its potential ABP's algorithmic implications. A remarkable structural parametric change is uncovered as one progresses through fl RDT lifting levels. On the first two levels, the so-called $\c$ sequence -- a key parametric fl RDT component -- is of the (natural) decreasing type. A change of such phenomenology on higher levels is then connected to the $α_c$ -- $α_a$ threshold change. Namely, on the second level concrete numerical values give for the critical constraint density $α=α_c\approx 0.8331$. While progressing through higher levels decreases this estimate, already on the fifth level we observe a satisfactory level of convergence and obtain $α\approx 0.7764$. This allows to draw two striking parallels: \textbf{\emph{(i)}} the obtained constraint density estimate is in a remarkable agrement with range $α\in (0.77,0.78)$ of clustering defragmentation (believed to be responsible for failure of locally improving algorithms) [17,88]; and \textbf{\emph{(ii)}} the observed change of $\c$ sequence phenomenology closely matches the one of the negative Hopfield model for which the existence of efficient algorithms that closely approach similar type of threshold has been demonstrated recently [87].
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。