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

arXiv: https://arxiv.org/abs/2607.07778 · HTML: https://mlsanity.com/paper/2607.07778/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 13 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 4 of 4)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)

## Abstract (arXiv)

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 √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 mathbbSd-1, d≥3, or from N(0,Id/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)≥ c,varepsilon√n/(bar mlog(Cbar 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)≤ 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 B2, and on mathbbSd-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.