揭示异步二元感知机中稀有密集解簇的局部熵特性，解释算法难题与可解区间的矛盾。
Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
- 用全提升随机对偶理论分析非典型解簇的局部熵行为
- 发现局部熵在 α ∈ (0.77,0.78) 区间崩溃，与最优求解器能力范围吻合
- 为感知机计算间隙提供关键机制解释，适合理解算法极限的研究者
我们研究经典异步二元感知机（ABP）及其关联的局部熵（LE），作为其算法难解性的潜在来源。尽管在可满足相中典型解孤立，暗示普遍难解性，但高效算法仍能在约束密度 α 接近容量但有限距离时运行（存在计算间隙）。近年来，稀有大密度解簇的存在及快速算法对其的寻获被视为解决此悖论的机制。这些非典型解簇的局部熵单调性或崩溃被认为导致其稀疏化甚至完全瓦解。全提升随机对偶理论（fl RDT）使典型结构研究成为可能；其大偏离升级版 sfl LD RDT 进而支持非典型特征分析。本文利用 [96,97] 的工具，建立通用框架研究 ABP 的非典型局部熵。二级提升即得结果与复制方法高度一致。对于经典零阈值 ABP，发现局部熵在 α ∈ (0.77,0.78) 区间崩溃，基本对应当前最优 ABP 求解器可处理的 α ∼ 0.75–0.77 范围，表明局部熵行为可能是计算间隙存在的关键反映。
原文摘要 · Abstract (English)
We study classical asymmetric binary perceptron (ABP) and associated \emph{local entropy} (LE) as potential source of its algorithmic hardness. Isolation of \emph{typical} ABP solutions in SAT phase seemingly suggests a universal algorithmic hardness. Paradoxically, efficient algorithms do exist even for constraint densities $α$ fairly close but at a finite distance (\emph{computational gap}) from the capacity. In recent years, existence of rare large dense clusters and magical ability of fast algorithms to find them have been posited as the conceptual resolution of this paradox. Monotonicity or breakdown of the LEs associated with such \emph{atypical} clusters are predicated to play a key role in their thinning-out or even complete defragmentation. Invention of fully lifted random duality theory (fl RDT) [90,93,94] allows studying random structures \emph{typical} features. A large deviation upgrade, sfl LD RDT [96,97], moves things further and enables \emph{atypical} features characterizations as well. Utilizing the machinery of [96,97] we here develop a generic framework to study LE as an ABP's atypical feature. Already on the second level of lifting we discover that the LE results are closely matching those obtained through replica methods. For classical zero threshold ABP, we obtain that LE breaks down for $α$ in $(0.77,0.78)$ interval which basically matches $α\sim 0.75-0.77$ range that currently best ABP solvers can handle and effectively indicates that LE's behavior might indeed be among key reflections of the ABP's computational gaps presumable existence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。