How Much Can You Project? A Neural Tangent Kernel Theory of Intrinsic Dimension

Neural networks with millions of parameters are routinely trained within a surprisingly small effective parameter space, a phenomenon formalized by Li et al. as "intrinsic dimension", which has remained without theoretical explanation since its discovery. We provide the first such explanation for asymptotically wide networks, showing that intrinsic dimension emerges from the interplay of the Neural Tangent Kernel (NTK) and the Johnson–Lindenstrauss lemma. Specifically, we ask whether the NTK regime survives when training is restricted to a randomly chosen low-dimensional subspace of the full parameter space. We prove that it does when the subspace dimension $d$ exceeds a threshold of order ${\epsilon }^{-2}\log N$: a block-structured random Gaussian projection preserves the NTK entry-wise throughout training with high probability as network width grows. Crucially, this threshold is independent of the ambient parameter dimension $D$, which can be arbitrarily large. We complement this result with matching lower bounds: the ${\epsilon }^{-2}$ dependence is unavoidable for random Gaussian projections, while no linear map can beat the ${\epsilon }^{-2}\log N$ threshold for the hardest gradient configurations. Thus, we identify a critical dimension $d^{\ast }$ above which random subspace training preserves the NTK regime and below which the same mechanism fails. We also identify a distinct threshold at $d=N$: below it, the projected kernel is rank-deficient and a component of the training error is permanently frozen, with the effect determined by its alignment with the surviving eigenspace. Experiments on standard benchmarks support our theoretical predictions.