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

Abstract

We consider the memorization capabilities of multilayered sign perceptrons neural networks (SPNNs). A recent rigorous upper-bounding capacity characterization, obtained in Stojnictcmspnncaprdt23 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, Stojnictcmspnncaprdt23 made a very first mathematically rigorous progress in over 30 years by lowering the previously best known capacity bounds of MitchDurb89. Here, we first establish that the RDT bounds from Stojnictcmspnncaprdt23 scale as d and can not on their own universally (over the entire range of d) beat the best known (d) scaling of the bounds from MitchDurb89. After recognizing that the progress from Stojnictcmspnncaprdt23 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 MitchDurb89.

Tasks

Reproductions