[论文] Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron co...

论文概要

研究领域: ML 作者: Mihailo Stojnic 发布时间: 2026-04-21 arXiv: 2604.19712

中文摘要

在 [97,99,100] 中，fl-RDT 框架被引入以刻画统计计算鸿沟（SCGs）。研究对称二元感知器（SBPs），[100] 在第 7 层提升水平获得算法阈值估计（对于间隔）， closely approaching 局部熵（LE）预测 [18]。本文进一步将参数 RDT 与重叠间隙性质（OGPs）——解空间的另一关键几何特征——联系起来。具体地，对任意正整数，我们考虑多级超度量 OGPs 并严格约束相关密度。为此，我们开发了一个分析性联合定界程序，包含组合与概率组件。通过将组合部分建模为凸问题、概率部分建模为嵌套积分，我们进行数值评估并获得前两级最紧界， closely approaching 第 3 与第 4 层提升水平参数 RDT 估计。我们在其他关键参数（包括重叠值与超度量簇相对大小）上也观察到 excellent agreement。基于这些观察，我们提出若干连接 OGP 与参数 RDT 的猜想。具体地，我们猜想算法阈值（对某些（甚至全部）可能取等）。最后，我们讨论连接 OGP 与参数 RDT 所有关键参数的完全同构的潜在存在性。

原文摘要

In [97,99,100], an fl-RDT framework is introduced to characterize \emph{statistical computational gaps} (SCGs). Studying \emph{symmetric binary perceptrons} (SBPs), [100] obtained an \emph{algorithmic} threshold estimate \(α_a\approx α_c^{(7)}\approx 1.6093\) at the 7th lifting level (for \(κ=1\) margin), closely approaching \(1.58\) local entropy (LE) prediction [18]. In this paper, we further connect parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer \(s\), we consider \(s\)-level ultrametric OGPs (\(ult_s\)-OGPs) and rigorously upper-bound the associated constraint densities \(α_{ult_s}\). To achieve this, we develop an analytical union-bounding program consisting of combinatorial and probabilistic components. B...

自动采集于 2026-04-23

#论文 #arXiv #ML #小凯