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

arXiv: https://arxiv.org/abs/2012.11654 · HTML: https://mlsanity.com/paper/2012.11654/

## Key facts

- Cited by 87 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2020.

## Built on by (most cited first, 30 of 87)

- [Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models](https://mlsanity.com/paper/2208.06677/) (2022)
- [Scaling Laws for Precision](https://mlsanity.com/paper/2411.04330/) (2024)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [On the Optimization and Generalization of Multi-head Attention](https://mlsanity.com/paper/2310.12680/) (2023)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domains](https://mlsanity.com/paper/2305.02657/) (2023)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Characterizing the Spectrum of the NTK via a Power Series Expansion](https://mlsanity.com/paper/2211.07844/) (2022)
- [Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks](https://mlsanity.com/paper/2109.09304/) (2021)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [Reparameterization invariance in approximate Bayesian inference](https://mlsanity.com/paper/2406.03334/) (2024)
- [Sample Complexity Bounds for Score-Matching: Causal Discovery and Generative Modeling](https://mlsanity.com/paper/2310.18123/) (2023)
- [On the Expected Complexity of Maxout Networks](https://mlsanity.com/paper/2107.00379/) (2021)
- [Convergence of Deep ReLU Networks](https://mlsanity.com/paper/2107.12530/) (2021)
- [Generalization Properties of NAS under Activation and Skip Connection Search](https://mlsanity.com/paper/2209.07238/) (2022)
- [Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels](https://mlsanity.com/paper/2302.01629/) (2023)
- [On the Convergence of Encoder-only Shallow Transformers](https://mlsanity.com/paper/2311.01575/) (2023)
- [The Positivity of the Neural Tangent Kernel](https://mlsanity.com/paper/2404.12928/) (2024)
- [Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension](https://mlsanity.com/paper/2405.14630/) (2024)
- [Phenomenology of Double Descent in Finite-Width Neural Networks](https://mlsanity.com/paper/2203.07337/) (2022)
- [How Spurious Features Are Memorized: Precise Analysis for Random and NTK Features](https://mlsanity.com/paper/2305.12100/) (2023)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks](https://mlsanity.com/paper/2310.20579/) (2023)
- [On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks](https://mlsanity.com/paper/2203.14328/) (2022)
- [Lower and Upper Bounds for Numbers of Linear Regions of Graph Convolutional Networks](https://mlsanity.com/paper/2206.00228/) (2022)
- [Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum](https://mlsanity.com/paper/2307.14531/) (2023)
- [Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach](https://mlsanity.com/paper/2310.06112/) (2023)
- [Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization](https://mlsanity.com/paper/2502.01347/) (2025)

## Abstract (arXiv)

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.