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

arXiv: https://arxiv.org/abs/2410.06717 · HTML: https://mlsanity.com/paper/2410.06717/

## 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 (most cited first, 22 of 22)

- [Statistical Mechanics of Deep Linear Neural Networks: The Back-Propagating Kernel Renormalization](https://mlsanity.com/paper/2012.04030/) (2020)
- [Shaping the learning landscape in neural networks around wide flat minima](https://mlsanity.com/paper/1905.07833/) (2019)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses](https://mlsanity.com/paper/1509.05753/) (2015)
- [Unveiling the structure of wide flat minima in neural networks](https://mlsanity.com/paper/2107.01163/) (2021)
- [Gaussian Universality of Perceptrons with Random Labels](https://mlsanity.com/paper/2205.13303/) (2022)
- [Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations](https://mlsanity.com/paper/1907.07578/) (2019)
- [Learning through atypical "phase transitions" in overparameterized neural networks](https://mlsanity.com/paper/2110.00683/) (2021)
- [Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems](https://mlsanity.com/paper/1511.05634/) (2015)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron](https://mlsanity.com/paper/2102.13069/) (2021)
- [Origin of the computational hardness for learning with binary synapses](https://mlsanity.com/paper/1408.1784/) (2014)
- [Algorithmic pure states for the negative spherical perceptron](https://mlsanity.com/paper/2010.15811/) (2020)
- [Typical and atypical solutions in non-convex neural networks with discrete and continuous weights](https://mlsanity.com/paper/2304.13871/) (2023)
- [Tractability from overparametrization: The example of the negative perceptron](https://mlsanity.com/paper/2110.15824/) (2021)
- [Activation function dependence of the storage capacity of treelike neural networks](https://mlsanity.com/paper/2007.11136/) (2020)
- [The star-shaped space of solutions of the spherical negative perceptron](https://mlsanity.com/paper/2305.10623/) (2023)
- [Exact capacity of the wide hidden layer treelike neural networks with generic activations](https://mlsanity.com/paper/2402.05719/) (2024)
- [High-dimensional manifold of solutions in neural networks: insights from statistical physics](https://mlsanity.com/paper/2309.09240/) (2023)
- [Fixed width treelike neural networks capacity analysis -- generic activations](https://mlsanity.com/paper/2402.05696/) (2024)
- [Solution space and storage capacity of fully connected two-layer neural networks with generic activation functions](https://mlsanity.com/paper/2404.13404/) (2024)
- [On neural network kernels and the storage capacity problem](https://mlsanity.com/paper/2201.04669/) (2022)

## Built on by (most cited first, 6 of 6)

- [Injectivity capacity of ReLU gates](https://mlsanity.com/paper/2410.20646/) (2024)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)
- [Binary perceptron computational gap -- a parametric fl RDT view](https://mlsanity.com/paper/2511.01037/) (2025)
- [Generalization performance of narrow one-hidden layer networks in the teacher-student setting](https://mlsanity.com/paper/2507.00629/) (2025)
- [Parametric RDT approach to computational gap of symmetric binary perceptron](https://mlsanity.com/paper/2601.10628/) (2026)
- [Ultrametric OGP - parametric RDT symmetric binary perceptron connection](https://mlsanity.com/paper/2604.19712/) (2026)

## 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.