# Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper bounds

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 54 references that are in the map.
- First posted on arXiv 13 Dec 2023.

## Builds on (most cited first, 20 of 20)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity](https://mlsanity.com/paper/1810.07770/) (2018)
- [Optimization for deep learning: theory and algorithms](https://mlsanity.com/paper/1912.08957/) (2019)
- [Regularly random duality](https://mlsanity.com/paper/1303.7295/) (2013)
- [Another look at the Gardner problem](https://mlsanity.com/paper/1306.3979/) (2013)
- [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)
- [Fully lifted random duality theory](https://mlsanity.com/paper/2312.00070/) (2023)
- [Lifting/lowering Hopfield models ground state energies](https://mlsanity.com/paper/1306.3975/) (2013)
- [Memory capacity of neural networks with threshold and ReLU activations](https://mlsanity.com/paper/2001.06938/) (2020)
- [Binary perceptrons capacity via fully lifted random duality theory](https://mlsanity.com/paper/2312.00073/) (2023)
- [Spherical perceptron as a storage memory with limited errors](https://mlsanity.com/paper/1306.3809/) (2013)
- [Activation function dependence of the storage capacity of treelike neural networks](https://mlsanity.com/paper/2007.11136/) (2020)
- [Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently](https://mlsanity.com/paper/1909.11837/) (2019)

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

- [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)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)

## Abstract (arXiv)

We study the capacity of sign perceptrons neural networks (SPNN) and particularly focus on 1-hidden layer treelike committee machine (TCM) architectures. Similarly to what happens in the case of a single perceptron neuron, it turns out that, in a statistical sense, the capacity of a corresponding multilayered network architecture consisting of multiple sign perceptrons also undergoes the so-called phase transition (PT) phenomenon. This means: (i) for certain range of system parameters (size of data, number of neurons), the network can be properly trained to accurately memorize all elements of the input dataset; and (ii) outside the region such a training does not exist. Clearly, determining the corresponding phase transition curve that separates these regions is an extraordinary task and among the most fundamental questions related to the performance of any network. Utilizing powerful mathematical engine called Random Duality Theory (RDT), we establish a generic framework for determining the upper bounds on the 1-hidden layer TCM SPNN capacity. Moreover, we do so for any given (odd) number of neurons. We further show that the obtained results exactly match the replica symmetry predictions of citeEKTVZ92,BHS92, thereby proving that the statistical physics based results are not only nice estimates but also mathematically rigorous bounds as well. Moreover, for d≤ 5, we obtain the capacity values that improve on the best known rigorous ones of citeMitchDurb89, thereby establishing a first, mathematically rigorous, progress in well over 30 years.