Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity

Abstract

We study finite sample expressivity, i.e., memorization power of ReLU networks. Recent results require $N$ hidden nodes to memorize/interpolate arbitrary $N$ data points. In contrast, by exploiting depth, we show that 3-layer ReLU networks with $\Omega (\sqrt{N})$ hidden nodes can perfectly memorize most datasets with $N$ points. We also prove that width $\Theta (\sqrt{N})$ is necessary and sufficient for memorizing $N$ data points, proving tight bounds on memorization capacity. The sufficiency result can be extended to deeper networks; we show that an $L$-layer network with $W$ parameters in the hidden layers can memorize $N$ data points if $W=\Omega (N)$. Combined with a recent upper bound $O(WL\log W)$ on VC dimension, our construction is nearly tight for any fixed $L$. Subsequently, we analyze memorization capacity of residual networks under a general position assumption; we prove results that substantially reduce the known requirement of $N$ hidden nodes. Finally, we study the dynamics of stochastic gradient descent (SGD), and show that when initialized near a memorizing global minimum of the empirical risk, SGD quickly finds a nearby point with much smaller empirical risk.

28 pages, 2 figures. NeurIPS 2019 Camera-ready version

Cited by in corpus (31)

• Are All Layers Created Equal?
• Layer-adaptive sparsity for the Magnitude-based Pruning
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Universal Approximation with Deep Narrow Networks
• Universal Approximation Power of Deep Residual Neural Networks via Nonlinear Control Theory
• Network size and weights size for memorization with two-layers neural networks
• WeMix: How to Better Utilize Data Augmentation
• Memory capacity of neural networks with threshold and ReLU activations
• Approximation in shift-invariant spaces with deep ReLU neural networks
• Equivariant Subgraph Aggregation Networks
• Minimum Width for Universal Approximation
• From Local Structures to Size Generalization in Graph Neural Networks
• An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
• Large-time asymptotics in deep learning
• Provable Memorization via Deep Neural Networks using Sub-linear Parameters
• NEU: A Meta-Algorithm for Universal UAP-Invariant Feature Representation
• A law of robustness for two-layers neural networks
• When Do Curricula Work?
• On the Optimal Memorization Power of ReLU Neural Networks
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Abstraction Mechanisms Predict Generalization in Deep Neural Networks
• NeuroDB: A Neural Network Framework for Answering Range Aggregate Queries and Beyond
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• A Law of Robustness for Weight-bounded Neural Networks
• CNN with large memory layers
• When Are Solutions Connected in Deep Networks?
• Why Does Multi-Epoch Training Help?
• The Separation Capacity of Random Neural Networks
• A Theoretical Analysis of Learning with Noisily Labeled Data