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

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 ${\mathbb{R}}^d$ using only $┌n/d┐$ 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 $\epsilon$, the neural tangent kernel can also memorize with only $O\left(\frac{n}{d}\cdot \log (1/\epsilon )\right)$ 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\left(\frac{n}{d}\cdot \frac{\log (1/\epsilon )}{\epsilon }\right)$ neurons, as well as nearly-optimal size of the weights.

arXiv comment27 pages

References in corpus (12)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• On Lazy Training in Differentiable Programming
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Norm-Based Capacity Control in Neural Networks
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks

Cited by in corpus (10)

• A Corrective View of Neural Networks: Representation, Memorization and Learning
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
• Large-time asymptotics in deep learning
• A law of robustness for two-layers neural networks
• On Sparsity in Overparametrised Shallow ReLU Networks
• Knowledge Infused Policy Gradients for Adaptive Pandemic Control
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• On the Optimal Memorization Power of ReLU Neural Networks
• Neural Networks with Complex-Valued Weights Have No Spurious Local Minima
• When Are Solutions Connected in Deep Networks?