{"ID":6267707,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-11T17:31:52.507564388Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07778","arxiv_id":"2607.07778","title":"A law of robustness for two-layer neural networks with arbitrary weights","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 $σ^2\u003e0$, 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.","short_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-paramete...","url_abs":"https://arxiv.org/abs/2607.07778","url_pdf":"https://arxiv.org/pdf/2607.07778v1","authors":"[\"Yitzchak Shmalo\"]","published":"2026-07-08T17:44:15Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"math.PR\",\"stat.ML\"]","methods":"[]","has_code":false}