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

Researchers prove a law of robustness for two-layer neural networks with arbitrary weights, showing that fitting noisy data forces the Lipschitz constant to be at least of order √(n/m). The result holds for ReLU networks and other piecewise-linear activations, with high probability for data drawn uniformly from a sphere or Gaussian distribution.

arXiv:2607.07778v1 Announce Type: new Abstract: 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 $\sigma^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 $\mathrm{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.