Bubeck–Li–Nagaraj robustness law for arbitrary-weight two-layer networks

Let $\psi$ be any Lipschitz activation. For $x_1,\dots,x_n$ independent uniform on $\mathbb{S}^{d-1}$ (or distributed as $N(0,I_d/d)$) and $y_1,\dots,y_n$ independent uniform on $\{-1,+1\}$, let $\mathcal{N}_m$ denote the class of width-$m$ two-layer networks with arbitrary real weights, biases, and affine skip connection. With high probability, any $f\in\mathcal{N}_m$ fitting the data satisfies

$$\operatorname{Lip}_{\mathbb{S}^{d-1}}(f)\ge c\sqrt{n/m}.$$

Bubeck–Li–Nagaraj conjecture. The stated lower bound should hold for every Lipschitz activation and arbitrary weights, with no restriction on their magnitudes. The conjecture quantifies the robustness cost of fitting random noisy labels with a finite-width two-layer network. The paper proves the conjectured law up to one logarithmic factor for continuous piecewise-linear activations, including ReLU, while the general-activation case remains open in several width and dimension regimes.