Parametric RDT approach to computational gap of symmetric binary perceptron
Not on the map. Why?
Abstract (arXiv)
We study potential presence of statistical-computational gaps (SCG) in symmetric binary perceptrons (SBP) via a parametric utilization of 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 satisfiability (αc) -- algorithmic (αa) constraints density threshold change thereby suggesting a potential existence of a nonzero computational gap SCG=αc-αa. The second level estimate is shown to match the theoretical αc whereas the rrightarrow ∞ level one is proposed to correspond to αa. For example, for the canonical SBP (kappa=1 margin) we obtain αc≈ 1.8159 on the second and αa≈ 1.6021 (with converging tendency towards ~ 1.59 range) on the seventh level. Our propositions remarkably well concur with recent literature: (i) in [20] local entropy replica approach predicts αLE≈ 1.58 as the onset of clustering defragmentation (presumed driving force behind locally improving algorithms failures); (ii) in αrightarrow 0 regime we obtain on the third lifting level kappa≈ 1.2385√fracαa-logleft ( α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.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 41 of its 112 references that are in the map. First posted on arXiv 15 Jan 2026.
Builds on
41 of 112 references.
References · 41
- 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
- 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
- 2015Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapsescited by 39
- 2021Unveiling the structure of wide flat minima in neural networkscited by 28
- 2013Regularly random dualitycited by 24
- 2013Another look at the Gardner problemcited by 24
- 2013Limits of local algorithms over sparse random graphscited by 23
- 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
- 2015Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscited by 20
- 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
- 2021Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptroncited by 18
- 2023Fully lifted random duality theorycited by 18
29 more
- 2014Origin of the computational hardness for learning with binary synapsescited by 16
- 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
- 2013Discrete perceptronscited by 14
- 2013Lifting ℓ1-optimization strong and sectional thresholdscited by 13
- 2013Lifting/lowering Hopfield models ground state energiescited by 13
- 2020Algorithmic pure states for the negative spherical perceptroncited by 13
- 2021Binary perceptron: efficient algorithms can find solutions in a rare well-connected clustercited by 13
- 2023Typical and atypical solutions in non-convex neural networks with discrete and continuous weightscited by 13
- 2023Binary perceptrons capacity via fully lifted random duality theorycited by 13
- 2019Clustering of solutions in the symmetric binary perceptroncited by 12
- 2022Algorithms and Barriers in the Symmetric Binary Perceptron Modelcited by 12
- 2013Spherical perceptron as a storage memory with limited errorscited by 11
- 2023Fl RDT based ultimate lowering of the negative spherical perceptron capacitycited by 11
- 2013Entropy landscape of solutions in the binary perceptron problemcited by 10
- 2014Local algorithms for independent sets are half-optimalcited by 9
- 2019On-Line Balancing of Random Inputscited by 9
- 2021Tight Lipschitz Hardness for Optimizing Mean Field Spin Glassescited by 9
- 2024Hardness of sampling solutions from the Symmetric Binary Perceptroncited by 8
- 2020Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamicscited by 7
- 2014Constructive discrepancy minimization for convex setscited by 6
- 2024Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networkscited by 6
- 2020Algorithmic Thresholds in Mean Field Spin Glassescited by 5
- 2023Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimizationcited by 5
- 2024Discrepancy Algorithms for the Binary Perceptroncited by 5
- 2024Some easy optimization problems have the overlap-gap propertycited by 5
- 2025Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDTcited by 5
- 2025A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energycited by 5
- 2025CLuP practically achieves ~ 1.77 positive and ~ 0.33 negative Hopfield model ground state free energycited by 3
- 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.