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 (5)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• 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 (5)

• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• On the Optimal Memorization Power of ReLU Neural Networks
• Subquadratic Overparameterization for Shallow Neural Networks
• Beyond Lazy Training for Over-parameterized Tensor Decomposition