Robustness Law of Two-Layer Neural Networks: Proof of Bubeck's Conjecture

Mathematicians proved a long-standing conjecture by Sanjiv Bubeck, Yu Li, and Hariharan Nagarajan that two-layer neural networks with arbitrary weights, fitted to noisy data, necessarily have a high Lipschitz constant. The result was published on arXiv in July 2026 and overcomes previous limitations on parameter size that were considered necessary for the proof.

History of the Hypothesis

Several years ago, Sanjiv Bubeck, Yu Li, and Hariharan Nagarajan posed a hypothesis: for typical data, any two-layer neural network with m neurons that exactly fits n noisy labels must have a Lipschitz constant of at least √(n/m) — regardless of weight constraints. Bubeck and Selke later proved a weaker version of this law, but only for bounded parameters. In practice this did not match reality: neural network weights can often be arbitrary and very large.

What Was Proven

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

• Proven for data uniformly distributed on the sphere S^(d-1) (d ≥ 3) or from a Gaussian distribution N(0, I_d/d)
• Valid for any weights, biases, and skip connections between layers
• The result is sufficiently precise: the error is only a logarithmic factor
• The theorem relates the Lipschitz constant to the size of error below the noise level (ε), network size, and data dimensionality

How Previous Limitations Were Overcome

Previous proofs used a parameter space covering method — they partitioned the set of all possible weights into finite regions and analyzed each. This worked with polynomial weight bounds, but became impossible for unbounded weights, since there would be infinitely many such regions.

The authors changed strategy: instead of covering parameter space, they use covering of functional space — analyzing the realized function itself and its geometric properties. The central tool of the proof is the kink rigidity lemma: in high dimension, each coefficient of each linear part of a piecewise-linear function is controlled by its Lipschitz constant, because kinks (break points) on different hyperplanes cannot mutually compensate in typical data points.

What This Means

The robustness law reveals a fundamental trade-off in machine learning: if a neural network wants to learn noisy data with high accuracy, it must maintain high sensitivity to small input perturbations — this is an inevitable mathematical law, not just 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 and robustness.