Overview
Field: Machine Learning Author: Mihailo Stojnic arXiv: 2604.19712
Abstract
In [97,99,100], an fl-RDT framework is introduced to characterize *statistical computational gaps* (SCGs). Studying *symmetric binary perceptrons* (SBPs), [100] obtained an *algorithmic* threshold estimate \(\alpha_a \approx \alpha_c^{(7)} \approx 1.6093\) at the 7th lifting level (for \(\kappa=1\) margin), closely approaching the $1.58$ local entropy (LE) prediction [18]. In this paper, the author further connects parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer \(s\), \(s\)-level ultrametric OGPs (\(ult_s\)-OGPs) are considered and the associated constraint densities \(\alpha_{ult_s}\) are rigorously upper-bounded.
To achieve this, an analytical union-bounding program is developed, consisting of combinatorial and probabilistic components. The combinatorial part is modeled as a convex problem, while the probabilistic part is formulated as nested integrals, enabling numerical evaluation. The resulting bounds for the first two levels are the tightest known, closely approaching the level-3 and level-4 lifted parametric RDT estimates. Excellent agreement is also observed for other key parameters, including overlap values and relative sizes of ultrametric clusters.
Based on these observations, the author proposes several conjectures linking OGP and parametric RDT, including that algorithmic thresholds coincide (in some, or even all, cases with equality). Finally, the potential existence of a complete isomorphism connecting all key parameters of OGP and parametric RDT is discussed.