Network size and weights size for memorization with two-layers neural networks

2020/06/04 by Sébastien Bubeck, Bubeck, Sébastien, Ronen Eldan +5
Computer Science · #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2006.02855

openalex publication_date 2020/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In 1988, Eric B. Baum showed that two-layers neural networks with threshold activation function can perfectly memorize the binary labels of n points in general position in ℝ^d using only \ulcorner n/d \urcorner neurons. We observe that with ReLU networks, using four times as many neurons one can fit arbitrary real labels. Moreover, for approximate memorization up to error ε, the neural tangent kernel can also memorize with only O((n)/(d) ⋅ log(1/ε) ) neurons (assuming that the data is well dispersed too). We show however that these constructions give rise to networks where the magnitude of the neurons' weights are far from optimal. In contrast we propose a new training procedure for ReLU networks, based on complex (as opposed to real) recombination of the neurons, for which we show approximate memorization with both O((n)/(d) ⋅ \fraclog(1/ε)ε) neurons, as well as nearly-optimal size of the weights.

Citations

• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
• A Corrective View of Neural Networks: Representation, Memorization and Learning

Related

• Memory capacity of neural networks with threshold and ReLU activations
• On the Optimal Memorization Power of ReLU Neural Networks
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity