Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices

Abstract

For $n$ unit vectors $x_1,\ldots,x_n \in \mathbb{R}^d$, we study the continuous ReLU derivative Gram matrix $H$, whose entries are obtained by averaging pairwise gated inner products over a standard Gaussian direction. Writing $ \Delta_\pm := \min_{i \neq j} \min\{ \|x_i-x_j\|_2, \|x_i+x_j\|_2 \} $ for their projective separation, we prove the universal dimension-free lower bound $ \lambda_{\min}(H) = \Omega( \Delta_\pm/\sqrt{\log n} ) $. Conversely, we construct worst-case families satisfying the matching upper bound $ \lambda_{\min}(H) = O( \Delta_\pm/\sqrt{\log n} ) $, showing that this rate is tight up to universal constants.