Lifted RDT based capacity analysis of the 1-hidden layer treelike sign perceptrons neural networks
Not on the map. Why?
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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 20 of its 53 references that are in the map. First posted on arXiv 13 Dec 2023.
Builds on
20 of 53 references.
References · 20
- 2016Understanding deep learning requires rethinking generalizationcited by 1,657
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
- 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
- 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
- 2016Identity Matters in Deep Learningcited by 107
- 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
- 2019Optimization for deep learning: theory and algorithmscited by 70
- 2013Regularly random dualitycited by 23
- 2013Another look at the Gardner problemcited by 23
8 more
- 2019Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activationscited by 22
- 2023Fully lifted random duality theorycited by 17
- 2013Lifting ℓ1-optimization strong and sectional thresholdscited by 13
- 2013Lifting/lowering Hopfield models ground state energiescited by 13
- 2020Memory capacity of neural networks with threshold and ReLU activationscited by 13
- 2013Spherical perceptron as a storage memory with limited errorscited by 11
- 2020Activation function dependence of the storage capacity of treelike neural networkscited by 10
- 2019Mildly Overparametrized Neural Nets can Memorize Training Data Efficientlycited by 7
Built on by
Citing papers per year: 2024: 2; 2025: 1.
3 papers.