揭示对称二元感知机中几何结构与算法阈值的深层联系
Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection
- 引入超度量重叠间隙特性，构建参数化RDT与OGP的关联框架
- 计算出前两级超度量OGP上界：1.6578和1.6219，逼近对应RDT估计值
- 提出关键猜想：两者极限阈值相等，可能存在完全同构关系
在[97,99,100]中，引入fl-RDT框架以刻画统计-计算鸿沟（SCGs）。研究对称二元感知机（SBPs）时，[100]在第7次提升层级（κ=1）得到算法阈值估计α_a≈α_c^{(7)}≈1.6093，接近1.58的局部熵预测[18]。本文进一步将参数化RDT与重叠间隙性质（OGPs）关联，针对任意正整数s，定义s级超度量OGPs（ult_s-OGPs），并严格上界约束密度α_{ult_s}。通过构建包含组合与概率部分的解析联合界程序，将组合部分转为凸问题，概率部分化为嵌套积分，数值求解得首两级上界：¯α_{ult_1}≈1.6578、¯α_{ult_2}≈1.6219，分别紧邻第3、4次提升层级的RDT估计值α_c^{(3)}≈1.6576、α_c^{(4)}≈1.6218。同时观察到重叠值与超度量簇相对大小高度一致。据此提出多个猜想：算法阈值α_a=lim_{s→∞}α_{ult_s}=lim_{s→∞}¯α_{ult_s}=lim_{r→∞}α_c^{(r)}，且α_{ult_s}≤α_c^{(s+2)}（某些甚至全部可能取等）。最后讨论ult-OGP与参数化RDT所有关键参数间可能存在全同构关系。
原文摘要 · Abstract (English)
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. By casting the combinatorial part as a convex problem and the probabilistic part as a nested integration, we conduct numerical evaluations and obtain that the tightest bounds at the first two levels, $\barα_{ult_1} \approx 1.6578$ and $\barα_{ult_2} \approx 1.6219$, closely approach the 3rd and 4th lifting level parametric RDT estimates, $α_c^{(3)} \approx 1.6576$ and $α_c^{(4)} \approx 1.6218$. We also observe excellent agreement across other key parameters, including overlap values and the relative sizes of ultrametric clusters. Based on these observations, we propose several conjectures linking $ult$-OGP and parametric RDT. Specifically, we conjecture that algorithmic threshold $α_a=\lim_{s\rightarrow\infty} α_{ult_s} = \lim_{s\rightarrow\infty} \barα{ult_s} = \lim_{r\rightarrow\infty} α_{c}^{(r)}$, and $α_{ult_s} \leq α_{c}^{(s+2)}$ (with possible equality for some (maybe even all) $s$). Finally, we discuss the potential existence of a full isomorphism connecting all key parameters of $ult$-OGP and parametric RDT.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。