# Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 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 ℓ1-optimization strong and sectional thresholds](https://mlsanity.com/paper/1306.3770/) (2013)
- [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)
- [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)

- [A CLuP algorithm to practically achieve ~ 0.76 SK--model ground state free energy](https://mlsanity.com/paper/2507.09247/) (2025)
- [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 consider the memorization capabilities of multilayered sign perceptrons neural networks (SPNNs). A recent rigorous upper-bounding capacity characterization, obtained in citeStojnictcmspnncaprdt23 utilizing the Random Duality Theory (RDT), demonstrated that adding neurons in a network configuration may indeed be very beneficial. Moreover, for particular treelike committee machines (TCM) architectures with d≤ 5 neurons in the hidden layer, citeStojnictcmspnncaprdt23 made a very first mathematically rigorous progress in over 30 years by lowering the previously best known capacity bounds of citeMitchDurb89. Here, we first establish that the RDT bounds from citeStojnictcmspnncaprdt23 scale as ~ √d and can not on their own universally (over the entire range of d) beat the best known ~ log(d) scaling of the bounds from citeMitchDurb89. After recognizing that the progress from citeStojnictcmspnncaprdt23 is therefore promising, but yet without a complete concretization, we then proceed by considering the recently developed fully lifted RDT (fl RDT) as an alternative. While the fl RDT is indeed a powerful juggernaut, it typically relies on heavy numerical evaluations. To avoid such heavy numerics, we here focus on a simplified, partially lifted, variant and show that it allows for very neat, closed form, analytical capacity characterizations. Moreover, we obtain the concrete capacity bounds that universally improve for any d over the best known ones of citeMitchDurb89.