A law of robustness for two-layer neural networks with arbitrary weights

Bubeck, Li and Nagaraj conjectured that, for generic data, any two-layer neural network with m neurons that fits n noisy labels must have Lipschitz constant at least of order \sqrt{n/m}, with no restriction on the size of the weights. Bubeck and Sellke proved a universal version of this law for Lipschitz-parameterized classes, but under a polynomial bound on the parameters; at depth three that boundedness hypothesis is genuinely necessary. The two-layer unbounded-weight case requires a different argument. We prove the conjectured law, up to one logarithmic factor, for every continuous piecewise-linear activation, in particular for ReLU networks. For data drawn uniformly from \mathbb{S}^{d-1}, d\ge3, or from N(0,I_d/d), labels in [-1,1] with noise level σ^2>0, and any width-m two-layer network with arbitrary real weights, biases and affine skip connection, fitting the data \varepsilon below the noise floor forces Lip(f)\ge c,\varepsilon\sqrt{n/(\bar m\log(C\bar m nd/\varepsilon))}, \bar m=(K-1)m+1, with high probability. A realized-kink-count version holds on the same event: every realized two-layer piecewise-linear function with k(f)\le n distinct kink hyperplanes obeys the bound with \bar m replaced by k(f)+1, irrespective of how many redundant hidden units parameterize it. The proof replaces parameter-space covering, impossible for unbounded weights, by a function-space covering. The central deterministic ingredient is a rigidity lemma: on B_2, and on \mathbb{S}^{d-1} for d\ge3, the coefficient of each canonical kink is controlled by the Lipschitz constant of the realized function, because kinks on distinct hyperplanes cannot cancel at generic points. Rigidity genuinely fails at d=2, and an explicit two-layer ReLU interpolant with O(1) Lipschitz constant at width 2n matches the law at the overparameterized endpoint.