Neural Tangent Kernel at Initialization: Linear Width Suffices

Arindam Banerjee, Pedro Cisneros-Velarde, Libin Zhu, Misha BelkinUAI 2023 · OpenReview

Abstract

In this paper we study the problem of lower bounding the minimum eigenvalue of the neural tangent kernel (NTK) at initialization, an important quantity for the theoretical analysis of training in neural networks. We consider feedforward neural networks with smooth activation functions. Without any distributional assumptions on the input, we present a novel result: we show that for suitable initialization variance, $\widetilde{\Omega}(n)$ width, where $n$ is the number of training samples, suffices to ensure that the NTK at initialization is positive definite, improving prior results for smooth activations under our setting. Prior to our work, the sufficiency of linear width has only been shown either for networks with ReLU activation functions, and sublinear width has been shown for smooth networks but with additional conditions on the distribution of the data. The technical challenge in the analysis stems from the layerwise inhomogeneity of smooth activation functions and we handle the challenge using generalized Hermite series expansion of such activations.

Introduction

Understanding why deep neural networks converge to global minima despite their highly non-convex loss landscapes is a central challenge in machine learning theory. A powerful framework for this analysis is the Neural Tangent Kernel (NTK). If the minimum eigenvalue of the NTK at initialization is strictly positive, the network behaves approximately like a linear model in a local neighborhood, satisfying the Polyak-Łojasiewicz condition and ensuring rapid convergence of gradient descent.

Historically, a significant gap existed between theory and practice regarding the required network width $m$ relative to the number of samples $n$. While empirical evidence suggests linear over-parameterization is often sufficient, theoretical guarantees for smooth activation functions (like Sigmoid or Tanh) previously required massive widths—up to $m = \Omega(n^2)$—unless restrictive assumptions were made about the input data distribution. This paper bridges that gap, proving that linear width $m = \Omega(n \log n)$ is sufficient for smooth networks without distributional assumptions.

Methodology: Generalized Hermite Series

The primary technical hurdle in analyzing smooth activations is their "inhomogeneity." Unlike the ReLU function, which scales linearly ($\phi(cx) = c\phi(x)$), smooth functions warp the signal layer-by-layer.

To address this, the authors utilize a generalized Hermite series expansion. While standard Hermite polynomials are effective for ReLU networks, they are insufficient for tracking the signal transformation through multiple layers of smooth activations. The generalized expansion allows for a precise layerwise analysis, enabling the authors to:

  1. Track Signal Propagation: Ensure the "learning signal" (represented by the minimum eigenvalue) does not vanish as it passes through deep layers.
  2. Matrix Concentration: Prove that the NTK of a finite-width network remains close to its infinite-width limit using concentration bounds derived from these expansions.

Theoretical Results

The core contribution is Theorem 4.1, which establishes that for a fixed depth $L$, a width $m = \Omega(n \log n)$ ensures the NTK is positive definite at initialization with high probability. This result improves the state-of-the-art for smooth activations from quadratic to near-linear width.

A key insight from the analysis is the Initialization Variance Trade-off. While small initialization variance can help smooth the loss surface (controlling the Hessian), variance that is too small causes the NTK's minimum eigenvalue to decay exponentially. The paper identifies a "Goldilocks" zone for initialization that maintains trainability while ensuring stability.

Empirical Validation

To verify the theoretical findings, the authors conducted numerical experiments using 3-layer fully-connected networks with Sigmoid and Tanh activations. Input data points were drawn i.i.d. from a standard Gaussian distribution $\mathcal{N}(0, \mathbb{I}_{100})$.

Minimum eigenvalue of the NTK vs. network width for Sigmoid and Tanh activation functions.

The experiments tested widths $m$ ranging from 200 to 4,000, with the number of samples $n$ scaled linearly with $m$. As shown in Figure 1, the empirical minimum eigenvalue $\lambda_{\min}(K)$ remains strictly positive and stays above the theoretical prediction, confirming that linear width is indeed sufficient to prevent the kernel from becoming singular as the problem size scales.

Conclusion and Limitations

This work significantly tightens the over-parameterization requirements for smooth neural networks, bringing theoretical bounds in line with the linear scaling observed in ReLU networks.

However, some limitations remain for future exploration:

  • Depth Dependence: The constants in the width requirement still grow with depth $L$, a challenge shared with prior work.
  • Training Dynamics: The current analysis focuses on initialization. While a positive eigenvalue at the start is necessary for convergence, future work could extend these linear width guarantees to the entire training trajectory.
  • Activation Constraints: The proof assumes $\phi(0)=0$ for technical simplicity, though the authors anticipate this can be relaxed in future iterations.

Summary updated

Abstract

In this paper we study the problem of lower bounding the minimum eigenvalue of the neural tangent kernel (NTK) at initialization, an important quantity for the theoretical analysis of training in neural networks. We consider feedforward neural networks with smooth activation functions. Without any distributional assumptions on the input, we present a novel result: we show that for suitable initialization variance, $\widetilde{\Omega}(n)$ width, where $n$ is the number of training samples, suffices to ensure that the NTK at initialization is positive definite, improving prior results for smooth activations under our setting. Prior to our work, the sufficiency of linear width has only been shown either for networks with ReLU activation functions, and sublinear width has been shown for smooth networks but with additional conditions on the distribution of the data. The technical challenge in the analysis stems from the layerwise inhomogeneity of smooth activation functions and we handle the challenge using generalized Hermite series expansion of such activations.
BibTeX
@inproceedings{banerjee2023neural,
  author = {Arindam Banerjee and Pedro Cisneros-Velarde and Libin Zhu and Misha Belkin},
  title = {{Neural Tangent Kernel at Initialization: Linear Width Suffices}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=VJaoe7Rp9tZ},
}
Figure