Robustness Law for Two-Layer Neural Networks: Proof of the Bubeck Conjecture

Mathematicians have proved a long-standing conjecture by Sébastien Bubeck, Yuanzhi Li and Dheeraj Nagaraj: two-layer neural networks with arbitrary weights, fitted to noisy data, must have a high Lipschitz constant. The result was published on arXiv in July 2026 and overcomes earlier restrictions on parameter size that were thought to be necessary for the proof.

History of the conjecture

A few years ago, Bubeck, Li and Nagaraj conjectured that for typical data, any two-layer neural network with m neurons that fits n noisy labels exactly must have a Lipschitz constant of at least √(n/m), regardless of constraints on the weights. Bubeck and Selke later proved a weaker version of this law, but only for bounded parameters. That did not match practice: neural network weights can often be arbitrary and very large.

What was proved

In the new paper, the authors overcome this limitation and prove the conjecture in full, for two-layer networks with unbounded weights. The result holds for all continuous piecewise-linear activation functions, including the popular ReLU.

• Proved for data uniformly distributed on the sphere S^(d-1) (d ≥ 3) or drawn from the Gaussian distribution N(0, I_d/d)
• Holds for any weights, biases and skip connections between layers
• The result is tight up to a logarithmic factor
• The theorem links the Lipschitz constant to the error level below the noise (ε), the network size and the data dimension

How the earlier limits were overcome

Previous proofs used the parameter-space covering method: they split the set of all possible weights into finite regions and analyzed each one. This worked under polynomial bounds on the weights, but became impossible for unbounded weights, since there are infinitely many such regions.

The authors changed strategy. Instead of covering the parameter space, they cover the function space, analyzing the realized function itself and its geometric properties. The central tool of the proof is the kink rigidity lemma: in high dimensions, every coefficient of every linear piece of a piecewise-linear function is controlled by its Lipschitz constant, because kinks (break points) on different hyperplanes cannot cancel each other out at typical data points.

What this means

The robustness law exposes a fundamental trade-off in machine learning: if a neural network is to learn noisy data with high accuracy, it has to remain highly sensitive to small input perturbations. This is an unavoidable mathematical law, not merely a quirk of existing algorithms. The result explains why regularization and noise injection help neural networks generalize better: they explicitly slow the network's adaptation to noise, balancing accuracy against stability.