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 S d-1, d 3, or from N(0,I d/d), labels in [-1,1] with noise level sigma 2>0, and any width- m two-layer network with arbitrary real weights, biases and affine skip connection, fitting the data epsilon below the noise floor forces Lip(f) c, epsilon sqrt n/(m (C m nd/epsilon)), 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) n distinct kink hyperplanes obeys the bound with 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 S d-1 for d 3, 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.