Binary perceptron computational gap -- a parametric fl RDT view
Not on the map. Why?
Abstract (arXiv)
Recent studies suggest that asymmetric binary perceptron (ABP) likely exhibits the so-called statistical-computational gap characterized with the appearance of two phase transitioning constraint density thresholds: textbf(i) the satisfiability threshold αc, below/above which ABP succeeds/fails to operate as a storage memory; and textbf(ii) algorithmic threshold αa, below/above which one can/cannot efficiently determine ABP's weight so that it operates as a storage memory. We consider a particular parametric utilization of fully lifted random duality theory (fl RDT) [85] and study its potential ABP's algorithmic implications. A remarkable structural parametric change is uncovered as one progresses through fl RDT lifting levels. On the first two levels, the so-called c sequence -- a key parametric fl RDT component -- is of the (natural) decreasing type. A change of such phenomenology on higher levels is then connected to the αc -- αa threshold change. Namely, on the second level concrete numerical values give for the critical constraint density α=αc≈ 0.8331. While progressing through higher levels decreases this estimate, already on the fifth level we observe a satisfactory level of convergence and obtain α≈ 0.7764. This allows to draw two striking parallels: textbf(i) the obtained constraint density estimate is in a remarkable agrement with range α∈ (0.77,0.78) of clustering defragmentation (believed to be responsible for failure of locally improving algorithms) [17,88]; and textbf(ii) the observed change of c sequence phenomenology closely matches the one of the negative Hopfield model for which the existence of efficient algorithms that closely approach similar type of threshold has been demonstrated recently [87].
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 37 of its 98 references that are in the map. First posted on arXiv 2 Nov 2025.
Builds on
37 of 98 references.
References · 37
- 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 115
- 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 27
- 2013Limits of local algorithms over sparse random graphscited by 23
- 2013Another look at the Gardner problemcited 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 17
- 2014Origin of the computational hardness for learning with binary synapsescited by 16
25 more
- 2020Optimal Low-Degree Hardness of Maximum Independent Setcited by 16
- 2013Discrete perceptronscited by 14
- 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
- 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
- 2020Optimization of Mean-field Spin Glassescited 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
Built on by
Citing papers per year: 2026: 3.
3 papers.