mlsanityData to 7 Oct 2026

Fixed width treelike neural networks capacity analysis -- generic activations

arXiv 2402.05696 ↗First posted 8 Feb 2024stat.ML cond-mat.dis-nn cs.ITcited by 4

Not on the map. Why?

Abstract (arXiv)

We consider the capacity of treelike committee machines (TCM) neural networks. Relying on Random Duality Theory (RDT), citeStojnictcmspnncaprdt23 recently introduced a generic framework for their capacity analysis. An upgrade based on the so-called partially lifted RDT (pl RDT) was then presented in citeStojnictcmspnncapliftedrdt23. Both lines of work focused on the networks with the most typical, sign, activations. Here, on the other hand, we focus on networks with other, more general, types of activations and show that the frameworks of citeStojnictcmspnncaprdt23,Stojnictcmspnncapliftedrdt23 are sufficiently powerful to enable handling of such scenarios as well. In addition to the standard linear activations, we uncover that particularly convenient results can be obtained for two very commonly used activations, namely, the quadratic and rectified linear unit (ReLU) ones. In more concrete terms, for each of these activations, we obtain both the RDT and pl RDT based memory capacities upper bound characterization for any given (even) number of the hidden layer neurons, d. In the process, we also uncover the following two, rather remarkable, facts: 1) contrary to the common wisdom, both sets of results show that the bounding capacity decreases for large d (the width of the hidden layer) while converging to a constant value; and 2) the maximum bounding capacity is achieved for the networks with precisely textbftwo hidden layer neurons! Moreover, the large d converging values are observed to be in excellent agrement with the statistical physics replica theory based predictions.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 23 of its 57 references that are in the map. First posted on arXiv 8 Feb 2024.

Builds on

23 of 57 references.

References · 23

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  3. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  4. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  5. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  6. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  7. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  8. 2016Identity Matters in Deep Learningcited by 107
  9. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  10. 2019Optimization for deep learning: theory and algorithmscited by 70
  11. 2013Regularly random dualitycited by 23
  12. 2013Another look at the Gardner problemcited by 23
11 more
  1. 2019Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activationscited by 22
  2. 2023Fully lifted random duality theorycited by 17
  3. 2013Upper-bounding ℓ1-optimization weak thresholdscited by 13
  4. 2013Lifting ℓ1-optimization strong and sectional thresholdscited by 13
  5. 2013Lifting/lowering Hopfield models ground state energiescited by 13
  6. 2020Memory capacity of neural networks with threshold and ReLU activationscited by 13
  7. 2013Spherical perceptron as a storage memory with limited errorscited by 11
  8. 2020Activation function dependence of the storage capacity of treelike neural networkscited by 10
  9. 2013Meshes that trap random subspacescited by 8
  10. 2019Mildly Overparametrized Neural Nets can Memorize Training Data Efficientlycited by 7
  11. 2023Capacity of the treelike sign perceptrons neural networks with one hidden layer -- RDT based upper boundscited by 3

Built on by

Cited by year

Citing papers per year: 2024: 4.

4 papers.

  1. 2024Exact full-RSB SAT/UNSAT transition in infinitely wide two-layer neural networkscited by 6
  2. 2024Injectivity capacity of ReLU gatescited by 4
  3. 2024Solution space and storage capacity of fully connected two-layer neural networks with generic activation functionscited by 3
  4. 2024Deep ReLU networks -- injectivity capacity upper boundscited by 3