Neural Networks Learning and Memorization with (almost) no Over-Parameterization

Abstract

Many results in recent years established polynomial time learnability of various models via neural networks algorithms. However, unless the model is linear separable, or the activation is a polynomial, these results require very large networks -- much more than what is needed for the mere existence of a good predictor. In this paper we prove that SGD on depth two neural networks can memorize samples, learn polynomials with bounded weights, and learn certain kernel spaces, with near optimal network size, sample complexity, and runtime. In particular, we show that SGD on depth two network with $\tilde{O}\left(\frac{m}{d}\right)$ hidden neurons (and hence $\tilde{O}(m)$ parameters) can memorize $m$ random labeled points in ${\mathbb{S}}^{d-1}$.

References in corpus (10)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• An Improved Analysis of Training Over-parameterized Deep Neural Networks
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Decoupling Gating from Linearity

Cited by in corpus (11)

• Network size and weights size for memorization with two-layers neural networks
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• Learning Parities with Neural Networks
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Hardness of Learning Neural Networks with Natural Weights
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology
• On the Optimal Memorization Power of ReLU Neural Networks
• Subquadratic Overparameterization for Shallow Neural Networks
• Beyond Lazy Training for Over-parameterized Tensor Decomposition