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

Yitzchak Shmalo

cs.LGJul 8, 2026

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

Authors: Yitzchak Shmalo

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>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 $\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.

Explore similar work

Aug 24, 2026cs.LG

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU NetworksEvery Layer Counts: An Exponential L_2 Depth Hierarchy for ReLU Networks

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all

k\geq2

, we construct a globally

[0,1]

-valued,

1

-Lipschitz function realized by a depth-

(k+1)

network of width

\mathcal{O}(d^4)

, whereas any depth-

k

network with unrestricted weights and width at most

\frac{2^d}{2d(k-1)}

has squared

L_2

error at least

1/24

under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least

3

. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case

k=2

gives a compactly supported separation between depths

3

and

2

with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally

[0,1]

-valued and

\mathcal{O}(\sqrt d)

-Lipschitz and maps the unit hypercube onto

[0,1]

. It is computed by a polynomial-width depth-

4

network, whereas any depth-

3

network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.

Itay Safran

Rectified Linear Unit Networks Rectified Linear Unit Search Depth Tight Bounds Lipschitz Constant L2

Ask PDF

Jun 24, 2025stat.ML

Near-optimal estimates for the $\ell^p$ -Lipschitz constants of deep random ReLU neural networksNear-optimal estimates for the \ell^p-Lipschitz constants of deep random ReLU neural networks

This paper studies the

\ell^p

-Lipschitz constants of ReLU neural networks

Φ: \mathbb{R}^d \to \mathbb{R}

with random parameters for

p \in [1,\infty]

. The distribution of the weights follows a variant of the He initialization. In the case of zero-bias networks, we derive high probability upper and lower bounds for wide networks that differ at most by a factor that is logarithmic in the network's depth. Remarkably, the behavior of the

\ell^p

-Lipschitz constant varies significantly between the regimes

p \in [1,2)

and

p \in [2,\infty]

. For

p \in [2,\infty]

, the

\ell^p

-Lipschitz constant behaves similarly to

\Vert g\Vert_{p'}

, where

g \in \mathbb{R}^d

is a

d

-dimensional standard Gaussian vector and

1/p + 1/p' = 1

. In contrast, for

p \in [1,2)

, the

\ell^p

-Lipschitz constant aligns more closely to

\Vert g \Vert_{2}

. We extend our analysis to networks with possibly non-zero biases drawn from arbitrary symmetric distributions. In this case, we obtain high probability upper and lower bounds that differ at most by a factor that is logarithmic in the network's width and linear in its depth.

Sjoerd Dirksen, Patrick Finke, Paul Geuchen +2

Rectified Linear Unit Networks Lipschitz Constant Rectified Linear Unit Probability Optimal 3D Gaussian Splatting

Ask PDF

Apr 25, 2026stat.ML

Explicit integral representations and quantitative bounds for two-layer ReLU networks

An approach to construct explicit integral representations for two-layer ReLU networks is presented, which provides relatively simple representations for any multivariate polynomial. Quantitative bounds are provided for a particular, sharpened ReLU integral representation, which involves a harmonic extension and a projection. The bounds demonstrate that functions can be approximated with

L^{2}(\mathcal{D})

errors that do not depend explicitly on dimension or degree, but rather the coefficients of their monomial expansions and the distribution

\mathcal{D}

. We also present a connection to the RKHS of the exponential kernel

K(x,y)=\exp\left(\left\langle x,y\right\rangle \right)

, and a very simple integral representation involving additionally multiplication via a fixed function which has better quantitative bounds.

Anthony Lee

Rectified Linear Unit Networks Rectified Linear Unit Reproducing Kernel Hilbert Spaces Tight Bounds Polynomials Numerical Dispersion

Ask PDF

Abstract

Explore similar work

Every Layer Counts: An Exponential L2L_2L2​ Depth Hierarchy for ReLU NetworksEvery Layer Counts: An Exponential L_2 Depth Hierarchy for ReLU Networks

Near-optimal estimates for the ℓp\ell^pℓp-Lipschitz constants of deep random ReLU neural networksNear-optimal estimates for the \ell^p-Lipschitz constants of deep random ReLU neural networks

Explicit integral representations and quantitative bounds for two-layer ReLU networks

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU NetworksEvery Layer Counts: An Exponential L_2 Depth Hierarchy for ReLU Networks

Near-optimal estimates for the $\ell^p$ -Lipschitz constants of deep random ReLU neural networksNear-optimal estimates for the \ell^p-Lipschitz constants of deep random ReLU neural networks