Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently

Abstract

It has been observed \citep{zhang2016understanding} that deep neural networks can memorize: they achieve 100\% accuracy on training data. Recent theoretical results explained such behavior in highly overparametrized regimes, where the number of neurons in each layer is larger than the number of training samples. In this paper, we show that neural networks can be trained to memorize training data perfectly in a mildly overparametrized regime, where the number of parameters is just a constant factor more than the number of training samples, and the number of neurons is much smaller.

38 pages

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• When Are Nonconvex Problems Not Scary?
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Implicit Regularization in Deep Matrix Factorization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• An Improved Analysis of Training Over-parameterized Deep Neural Networks

Cited by in corpus (13)

• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• Memory capacity of neural networks with threshold and ReLU activations
• Learning Parities with Neural Networks
• Hardness of Learning Neural Networks with Natural Weights
• When Do Curricula Work?
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• Active Subspace of Neural Networks: Structural Analysis and Universal Attacks
• Training Two-Layer ReLU Networks with Gradient Descent is Inconsistent
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks
• When Are Solutions Connected in Deep Networks?
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron