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

Abstract

For $n$ unit vectors $x_1,\dots ,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\ne j}\min \{\Vert x_i-x_j{\Vert }_2,\Vert x_i+x_j{\Vert }_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.