Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks

Abstract

A recent line of work has analyzed the theoretical properties of deep neural networks via the Neural Tangent Kernel (NTK). In particular, the smallest eigenvalue of the NTK has been related to the memorization capacity, the global convergence of gradient descent algorithms and the generalization of deep nets. However, existing results either provide bounds in the two-layer setting or assume that the spectrum of the NTK matrices is bounded away from 0 for multi-layer networks. In this paper, we provide tight bounds on the smallest eigenvalue of NTK matrices for deep ReLU nets, both in the limiting case of infinite widths and for finite widths. In the finite-width setting, the network architectures we consider are fairly general: we require the existence of a wide layer with roughly order of $N$ neurons, $N$ being the number of data samples; and the scaling of the remaining layer widths is arbitrary (up to logarithmic factors). To obtain our results, we analyze various quantities of independent interest: we give lower bounds on the smallest singular value of hidden feature matrices, and upper bounds on the Lipschitz constant of input-output feature maps.

arXiv commentappeared at ICML 2021, this version corrects a mistake in Lemma 5.4 which also affects Lemma 5.5. These two Lemmas have been edited and the corresponding proofs corrected. All the other results remain untouched

References in corpus (16)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• On the Number of Linear Regions of Deep Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• The loss surface of deep and wide neural networks
• Deep ReLU Networks Have Surprisingly Few Activation Patterns
• The Emergence of Spectral Universality in Deep Networks
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• Products of Many Large Random Matrices and Gradients in Deep Neural Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• A Random Matrix Perspective on Mixtures of Nonlinearities for Deep Learning
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Geometrical and analytical characteristic properties of piecewise affine mappings