dorsal/arxiv
View SchemaParametric RDT approach to computational gap of symmetric binary perceptron
| Authors | Mihailo Stojnic |
|---|---|
| Categories | |
| ArXiv ID | 2601.10628vv1 |
| URL | https://arxiv.org/abs/2601.10628 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of \emph{fully lifted random duality theory} (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered $c$-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with \emph{satisfiability} ($\alpha_c$) -- \emph{algorithmic} ($\alpha_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=\alpha_c-\alpha_a$. The second level estimate is shown to match the theoretical $\alpha_c$ whereas the $r\rightarrow \infty$ level one is proposed to correspond to $\alpha_a$. For example, for the canonical SBP ($\kappa=1$ margin) we obtain $\alpha_c\approx 1.8159$ on the second and $\alpha_a\approx 1.6021$ (with converging tendency towards $\sim 1.59$ range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts $\alpha_{LE}\approx 1.58$ as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in $\alpha\rightarrow 0$ regime we obtain on the third lifting level $\kappa\approx 1.2385\sqrt{\frac{\alpha_a}{-\log\left ( \alpha_a \right ) }}$ which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) $c$-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.
{
"annotation_id": "e93b7c45-ae1f-4ff7-927e-db55f40b1ee3",
"date_created": "2026-02-17T05:53:26.454000Z",
"date_modified": "2026-02-17T05:53:26.454000Z",
"file_hash": "30eee686e7a0b35e988e58abc8b493e7d7032c1bb927b82de8df4b1370dac67a",
"private": false,
"record": {
"abstract": "We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of \\emph{fully lifted random duality theory} (fl-RDT) [96]. A structural change from decreasingly to arbitrarily ordered $c$-sequence (a key fl-RDT parametric component) is observed on the second lifting level and associated with \\emph{satisfiability} ($\\alpha_c$) -- \\emph{algorithmic} ($\\alpha_a$) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap $SCG=\\alpha_c-\\alpha_a$. The second level estimate is shown to match the theoretical $\\alpha_c$ whereas the $r\\rightarrow \\infty$ level one is proposed to correspond to $\\alpha_a$. For example, for the canonical SBP ($\\kappa=1$ margin) we obtain $\\alpha_c\\approx 1.8159$ on the second and $\\alpha_a\\approx 1.6021$ (with converging tendency towards $\\sim 1.59$ range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts $\\alpha_{LE}\\approx 1.58$ as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in $\\alpha\\rightarrow 0$ regime we obtain on the third lifting level $\\kappa\\approx 1.2385\\sqrt{\\frac{\\alpha_a}{-\\log\\left ( \\alpha_a \\right ) }}$ which qualitatively matches overlap gap property (OGP) based predictions of [43] and identically matches local entropy based predictions of [24]; (iii) $c$-sequence ordering change phenomenology mirrors the one observed in asymmetric binary perceptron (ABP) in [98] and the negative Hopfield model in [100]; and (iv) as in [98,100], we here design a CLuP based algorithm whose practical performance closely matches proposed theoretical predictions.",
"arxiv_id": "2601.10628",
"authors": [
"Mihailo Stojnic"
],
"categories": [
"stat.ML",
"cond-mat.dis-nn",
"cs.IT",
"cs.LG",
"math.IT",
"math.PR"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Parametric RDT approach to computational gap of symmetric binary perceptron",
"url": "https://arxiv.org/abs/2601.10628",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a6806df5-be40-4e04-a36f-771895033854",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}