Margin, Not Dimension, Governs the Complexity of Training a ReLU

Training a single rectified linear unit on $n$ labeled points is $\mathsf{NP}$-hard and $\mathsf{W}[1]$-hard in the input dimension $d$. Under the Exponential Time Hypothesis (ETH), no algorithm runs in time $\phi (d)n^{o(d)}$ for any computable $\phi$. We study the geometric activation margin $\gamma$ of an optimal neuron. If some optimum separates the sample with margin at least $\gamma$, squared-loss training on rational data has a global minimizer computable in time $n^{O(1/{\gamma }^2)}\mathrm{poly}(L)$, where $L$ is the input bit length. The bound extends to convex coercive losses with polynomial-time exact solvers for fixed activation patterns. Its exponent is independent of $d$ and optimal up to a constant factor: margin-promised training is $\mathsf{W}[1]$-hard in $1/{\gamma }^2$ and, under ETH, admits no $\phi (1/\gamma )n^{o(1/{\gamma }^2)}$ algorithm. For squared loss, no computable margin rate asymptotically above $1/\sqrt{d}$ holds uniformly across a family witnessing dimension hardness. Conversely, a computable uniform rate above $1/\sqrt{d}$ gives a $\phi (d)n^{o(d)}\mathrm{poly}(L)$ algorithm.