2023/12/13 by Mihailo Stojnic, Stojnic, Mihailo · 1 citation
Computer Science · Physics and Astronomy · #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical Physics (math-ph) #Neural Networks and Applications #Probability (math.PR) #Statistical Mechanics and Entropy #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2312.08257
openalex publication_date 2023/12/13 · openalex created_date 2023/12/15 · openalex updated_date 2026/07/28
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.