A Corrective View of Neural Networks: Representation, Memorization and Learning

Abstract

We develop a corrective mechanism for neural network approximation: the total available non-linear units are divided into multiple groups and the first group approximates the function under consideration, the second group approximates the error in approximation produced by the first group and corrects it, the third group approximates the error produced by the first and second groups together and so on. This technique yields several new representation and learning results for neural networks. First, we show that two-layer neural networks in the random features regime (RF) can memorize arbitrary labels for arbitrary points under under Euclidean distance separation condition using $\tilde{O}(n)$ ReLUs which is optimal in $n$ up to logarithmic factors. Next, we give a powerful representation result for two-layer neural networks with ReLUs and smoothed ReLUs which can achieve a squared error of at most $\epsilon$ with $O(C(a,d){\epsilon }^{-1/(a+1)})$ for $a\in \mathbb{N}\cup \{0\}$ when the function is smooth enough (roughly when it has $\Theta (ad)$ bounded derivatives). In certain cases $d$ can be replaced with effective dimension $q\ll d$. Previous results of this type implement Taylor series approximation using deep architectures. We also consider three-layer neural networks and show that the corrective mechanism yields faster representation rates for smooth radial functions. Lastly, we obtain the first $O(\mathrm{subpoly}(1/\epsilon ))$ upper bound on the number of neurons required for a two layer network to learn low degree polynomials up to squared error $\epsilon$ via gradient descent. Even though deep networks can express these polynomials with $O(\mathrm{polylog}(1/\epsilon ))$ neurons, the best learning bounds on this problem require $\mathrm{poly}(1/\epsilon )$ neurons.

arXiv commentContains 2 figures (you heard that right!), V2 removes dimension dependence in memorization bounds

References in corpus (19)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Understanding deep learning requires rethinking generalization
• A Convergence Theory for Deep Learning via Over-Parameterization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Approximating Continuous Functions by ReLU Nets of Minimal Width
• To understand deep learning we need to understand kernel learning
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• SGD Learns the Conjugate Kernel Class of the Network
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?
• Network size and weights size for memorization with two-layers neural networks
• Neural Networks Learning and Memorization with (almost) no Over-Parameterization
• On the Approximation Properties of Random ReLU Features
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Neural tangent kernels, transportation mappings, and universal approximation
• Approximation power of random neural networks
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth

Cited by in corpus (9)

• Network size and weights size for memorization with two-layers neural networks
• Computational Separation Between Convolutional and Fully-Connected Networks
• A law of robustness for two-layers neural networks
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth
• When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?
• When does gradient descent with logistic loss find interpolating two-layer networks?
• A Recipe for Global Convergence Guarantee in Deep Neural Networks
• The staircase property: How hierarchical structure can guide deep learning
• The Separation Capacity of Random Neural Networks