Ultrametric OGP - parametric RDT symmetric binary perceptron connection
Mihailo Stojnic · 2026
Read Ultrametric OGP - parametric RDT symmetric binary perceptron connection by Mihailo Stojnic (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19712.txt.
Introduction
Stojnic links two views of hard search gaps in symmetric binary perceptrons, simple neural nets with binary weights. He proves upper bounds on constraint densities for multi-level ultrametric overlap gap properties. His proof joins a combinatorial part, cast as a convex problem, with a nested probabilistic part. The tightest first- and second-level bounds sit near past parametric estimates, backing conjectures that both views share one threshold in the limit.
Catalog record
| CREATOR | Mihailo Stojnic |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 148056 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19712
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ultrametric OGP - parametric RDT symmetric binary perceptron connection Mihailo Stojnic Abstract Abstract In [ 99 , 100 , 97 ] , a parametric fully lifted random duality theory (fl-RDT) framework is introduced as a viable analytical method for characterizing statistical computational gaps (SCGs). For example, a study of the symmetric binary perceptron (SBP) [ 100 ] obtained an algorithmic constraint density threshold estimate of \alpha_{a}\approx\alpha_{c}^{(7)}\approx 1.6093 at the 7th level of lifting (for the canonical margin/threshold \kappa=1 ). With a predicted convergence tendency toward the 1.59-1.60 range, these results closely approach the corresponding \alpha_{LE}\approx 1.58 replica method local entropy (LE) prediction from [ 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 \alpha_{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{\alpha}_{ult_{1}}\approx 1.6578 and \bar{\alpha}_{ult_{2}}\approx 1.6219 , closely approach the 3rd and 4th lifting level parametric RDT estimates, \alpha_{c}^{(3)}\approx 1.6576 and \alpha_{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 \alpha_{a}=\lim_{s\rightarrow\infty}\alpha_{ult_{s}}=\lim_{s\rightarrow\infty}\bar{\alpha}_{ult_{s}}=\lim_{r\rightarrow\infty}\alpha_{c}^{(r)} , and \alpha_{ult_{s}}\leq\alpha_{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. Index Terms: Symmetric binary perceptrons; ultrametric OGP; fl-RDT; statistical-computational gaps . 1 Introduction The significant progress in AI over the last two decades is largely driven by theoretical and algorithmic developments in machine learning and neural networks from previous decades. Classical perceptrons, both binary (BP) and spherical (SP), have been essential as both architectural components and prototype models for complex structures. Given their analytical tractability, ability to emulate artificial reasoning, and remarkable simplicity, they remain a primary focus of AI research. Among the various features of perceptrons, storage or classifying capacity is perhaps the most significant. This critical data density, \alpha_{c} , determines a perceptron’s success as a storing memory. The relevance of capacity and its analytical characterizations, recognized already in early pattern recognition studies [ 110 , 112 , 30 ] , continues to be vital today. Research into these concepts has historically interconnected fields such as cognitive science, logic, psychology, information theory, optimization, and statistical physics, providing the robust theoretical support necessary for modern AI. 1.1 Perceptrons key milestones A significant body of influential work [ 52 , 53 , 84 , 85 , 105 , 107 , 106 , 88 , 90 ] has built upon initial SP considerations [ 110 , 112 , 30 ] . As overall understanding has deepened, focus has shifted toward different architectures. For example, the positive spherical perceptrons (PSPs) are now very well understood; analytical studies [ 84 , 85 , 88 ] have utilized convexity/strong deterministic duality, provided a substantial upgrade on [ 110 , 112 , 30 ] , and rigorously proved statistical physics replica predictions [ 52 , 53 ] . In contrast, the negative spherical perceptrons (NSPs) lack these features, presenting an analytical challenge [ 90 , 37 , 35 , 36 , 38 , 39 , 8 , 17 ] . Simple shift to a negative threshold removes the convexity advantage, ultimately requiring more sophisticated approaches [ 91 , 94 , 95 , 93 ] . Similarly, convexity and strong deterministic duality are absent in BPs. Simple replica symmetric (RS) predictions [ 52 , 53 , 89 ] do not apply to asymmetric BPs (ABP), which instead require replica symmetry breaking (RSB) frameworks [ 69 , 33 , 77 , 25 , 56 , 92 ] . However, symmetric BPs (SBP) offer a unique case: while RS predictions still do not hold, favorable underlying combinatorics allow for elegant analytical characterizations [ 1 , 78 , 2 , 13 , 45 ] . 1.1.1 Satisfiability and algorithmic thresholds The capacity \alpha_{c} discussed in a majority of the above papers relates to achievability limits. It represents the satisfiability threshold for maximal data density given unlimited computational resources. On the other hand, the introduction of an alternative algorithmic threshold, \alpha_{a} , allows one to define the density achievable through computationally efficient methods. While \alpha_{a}\leq\alpha_{c} always holds, the existence of a (nonzero) statistical-computational gap (SCG), defined as SCG=\alpha_{c}-\alpha_{a} , measures the actual utilization of the perceptron’s predicted power. Determining the size of this gap remains a significant challenge. While worst-case complexity theory suggests that ABP and SBP are NP-complete [ 11 ] , such a complexity assessment may often fail to adequately reflect typical algorithmic solvability. For instance, in ABPs, while \alpha_{c}\approx 0.8331 , current algorithms suggest \alpha_{a}\approx 0.75-0.77 [ 14 , 15 , 17 ] (for existence of efficient algorithms in a wide range of \alpha<\alpha_{c} , see also [ 26 , 14 , 64 , 67 ] ). This indicates a gap that is notably more favorable than what NP theory might predict (for algorithmic implications of similar type in other problems (including planted ones) see, e.g., [ 74 , 49 , 50 , 51 , 4 , 3 , 48 , 23 , 70 ] ). Conversely, for SBPs in the \alpha\rightarrow 0 regime, the best known algorithms [ 20 ] are in \kappa\sim\sqrt{\alpha} range (where \kappa is the SBPs margin/threshold) and remain significantly below the corresponding \alpha_{c} scaling. 1.2 Relevant prior work Despite extensive studies across various scientific fields over the last several decades, computational gaps continue to be a mystery. While significant progress has been made on specific problems, a generic resolution remains elusive. In recent years, two concepts have emerged as key geometric properties of the solution space for hard optimization problems: the Overlap Gap Property (OGP) [ 40 , 49 , 50 , 51 , 3 , 31 , 74 ] and Local Entropy (LE) [ 15 , 16 , 18 , 22 , 98 ] . These properties are presumably correlated with the mismatch between satisfiability (information-theoretic) and algorithmic thresholds, as well as the existence of statistical computational gaps (SCG). While our primary interest is their relevance to developing efficient algorithms, we also emphasize that their focus on the clustering of typical and atypical solutions has yielded results of independent value. Below, we briefly review the aspects of these two concepts that have been of main interest over the last few years. 1.2.1 Overlap gap properties (OGPs) The OGP based approaches toward resolving SCG mysteries [ 40 , 49 , 50 , 51 , 3 , 31 , 74 ] propose connecting algorithmic efficiency to gaps in the spectrum of attainable near-solutions overlaps. They suggests that the absence of such gaps implies the existence of efficient algorithms, viewing \alpha_{a} as the maximal \alpha that ensures the absence of OGP. For instance, in the case of SBP (which is