Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection
2026-04-21 • Machine Learning
Machine LearningInformation Theory
AI summaryⓘ
The authors study a complex math problem related to how solutions for a certain type of neural network (symmetric binary perceptrons) are structured. They connect two ideas: parametric replica symmetry breaking (RDT) and overlap gap properties (OGPs), both describing the solution space's shape. By analyzing these connections, they find close matches between their numerical bounds and previous estimates for where algorithms can find these solutions. They propose that these findings may be deeply linked and suggest conjectures about how these different mathematical tools describe the problem similarly. Their work helps better understand where algorithms might struggle or succeed in finding solutions.
symmetric binary perceptronstatistical computational gapsparametric replica symmetry breakingoverlap gap propertyultrametricityalgorithmic thresholdlocal entropyconvex optimizationnested integrationsolution space geometry
Authors
Mihailo Stojnic
Abstract
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.