mlsanityData to 14 Oct 2026

Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networks

arXiv 2410.06717 ↗First posted 9 Oct 2024cond-mat.dis-nn cs.LG math.PRcited by 6

Not on the map. Why?

Abstract (arXiv)

We analyze the problem of storing random pattern-label associations using two classes of continuous non-convex weights models, namely the perceptron with negative margin and an infinite-width two-layer neural network with non-overlapping receptive fields and generic activation function. Using a full-RSB ansatz we compute the exact value of the SAT/UNSAT transition. Furthermore, in the case of the negative perceptron we show that the overlap distribution of typical states displays an overlap gap (a disconnected support) in certain regions of the phase diagram defined by the value of the margin and the density of patterns to be stored. This implies that some recent theorems that ensure convergence of Approximate Message Passing (AMP) based algorithms to capacity are not applicable. Finally, we show that Gradient Descent is not able to reach the maximal capacity, irrespectively of the presence of an overlap gap for typical states. This finding, similarly to what occurs in binary weight models, suggests that gradient-based algorithms are biased towards highly atypical states, whose inaccessibility determines the algorithmic threshold.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 22 of its 60 references that are in the map. First posted on arXiv 9 Oct 2024.

Builds on

22 of 60 references.

References · 22

  1. 2020Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalizationcited by 71
  2. 2019Shaping the learning landscape in neural networks around wide flat minimacited by 47
  3. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  4. 2015Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapsescited by 39
  5. 2021Unveiling the structure of wide flat minima in neural networkscited by 28
  6. 2022Gaussian Universality of Perceptrons with Random Labelscited by 26
  7. 2019Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activationscited by 22
  8. 2021Learning through atypical "phase transitions" in overparameterized neural networkscited by 21
  9. 2015Local entropy as a measure for sampling solutions in Constraint Satisfaction Problemscited by 20
  10. 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
  11. 2021Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptroncited by 18
  12. 2014Origin of the computational hardness for learning with binary synapsescited by 16
10 more
  1. 2020Algorithmic pure states for the negative spherical perceptroncited by 13
  2. 2023Typical and atypical solutions in non-convex neural networks with discrete and continuous weightscited by 13
  3. 2021Tractability from overparametrization: The example of the negative perceptroncited by 12
  4. 2020Activation function dependence of the storage capacity of treelike neural networkscited by 10
  5. 2023The star-shaped space of solutions of the spherical negative perceptroncited by 8
  6. 2024Exact capacity of the wide hidden layer treelike neural networks with generic activationscited by 6
  7. 2023High-dimensional manifold of solutions in neural networks: insights from statistical physicscited by 4
  8. 2024Fixed width treelike neural networks capacity analysis -- generic activationscited by 4
  9. 2024Solution space and storage capacity of fully connected two-layer neural networks with generic activation functionscited by 3
  10. 2022On neural network kernels and the storage capacity problemcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 2.

6 papers.

  1. 2024Injectivity capacity of ReLU gatescited by 4
  2. 2024Deep ReLU networks -- injectivity capacity upper boundscited by 3
  3. 2025Binary perceptron computational gap -- a parametric fl RDT viewcited by 3
  4. 2025Generalization performance of narrow one-hidden layer networks in the teacher-student settingcited by 2
  5. 2026Parametric RDT approach to computational gap of symmetric binary perceptroncited by 1
  6. 2026Ultrametric OGP - parametric RDT symmetric binary perceptron connectioncited by 0