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 $ Δ_\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 $ λ_{\min}(H) = Ω( Δ_\pm/\sqrt{\log n} ) $. Conversely, we construct worst-case families satisfying the matching upper bound $ λ_{\min}(H) = O( Δ_\pm/\sqrt{\log n} ) $, showing that this rate is tight up to universal constants.