on two-layer ReLU networks

Overview

This note records the spectral reason two-layer ReLU networks behave like low-pass filters. The key point in Zhang, Zhao, Zhong, and Zhou is that the useful basis functions are not merely expressive; their Gram matrix is severely ill-conditioned, so finite precision and gradient flow both privilege low generalized Fourier modes (Zhang et al., 2023).

🏷️ Setup

The ReLU activation is

$$\sigma (x)=\mathrm{ReLU}(x)=\max (x,0).$$

Two elementary identities drive most of the analysis:

$$\sigma (cx)=c\sigma (x),c>0,$$

and, in the distributional sense,

$${\sigma }^{\prime \prime }={\delta }_0.$$

A two-layer ReLU network on a bounded domain $D\subset {\mathbb{R}}^d$ has the form

$$h(x)=c+\sum _{i=1}^n{a}_i\sigma (w_i\cdot x-b_i),w_i\in {\mathbb{S}}^{d-1}.$$

The homogeneity lets one normalize the direction $w_i$ and treat $b_i$ as the location of the kink hyperplane. Thus the approximation problem is not only about the span of ridge functions; it is also about the numerical conditioning of that nonlocal basis.

Continuous feature operator

For an infinite-width model, write $V={\mathbb{S}}^{d-1}\times [-1,1]$ and

$$f(x)={\int }_{V}h(w,b)\sigma (w\cdot x-b)dwdb.$$

The adjoint feature map sends a parameter density $h$ to a function on $D$. Its Gram operator is the integral operator on parameter space with kernel

$$G(w,b,w^{\prime },b^{\prime })={\int }_D\sigma (w\cdot x-b)\sigma (w^{\prime }\cdot x-b^{\prime })dx.$$

☘️ One-Dimensional Gram Spectrum

In one dimension, take $D=[-1,1]$. After absorbing the affine part, a fixed-bias network is

$$h(x)=c+\sum _{i=1}^n{a}_i\sigma (x-b_i),b_i\in [-1,1].$$

As an approximation space, this is the same continuous piecewise-linear space generated by linear finite elements on the nodes $b_i$. The important difference is the coordinate system. Hat functions are local and give a sparse, well-conditioned mass matrix. ReLU functions are nonlocal and highly correlated, so their Gram matrix is dense and badly conditioned.

The continuous Gram kernel is

$$G(x,y)={\int }_{-1}^1\sigma (z-x)\sigma (z-y)dz.$$

For $x,y\in [-1,1]$ this can be written as

$$G(x,y)=\frac{1}{12}|x-y{|}^3+\frac{1}{12}(2-x-y)\left(2(1-x)(1-y)-(x-y{)}^2\right).$$

Let $K$ be the integral operator

$$K\varphi (x)={\int }_{-1}^{1}G(x,y)\varphi (y)dy.$$

Since ${\partial }_x^{4}G(x,y)=\delta (x-y)$, an eigenpair $K{\varphi }_k={\mu }_k{\varphi }_k$ satisfies

$${\varphi }_k^{(4)}=\frac{1}{{\mu }_k}{\varphi }_k$$

with boundary conditions

$${\varphi }_k(1)={\varphi }_k^{\prime }(1)={\varphi }_k^{\prime \prime }(-1)={\varphi }_k^{\prime \prime \prime }(-1)=0.$$

Thus the ReLU Gram eigenfunctions are generalized Fourier modes: alternating cosine-like and sine-like oscillations at high index. Their eigenvalues obey

$${\mu }_k=\Theta (k^{-4}).$$

Same space, different numerics

The ReLU basis and the finite-element hat basis can span the same piecewise-linear space in one dimension, but solving for the coefficients is not numerically equivalent. The finite-element basis is local; the ReLU basis encodes the same function through cumulative, highly correlated ramps.

For quasi-evenly spaced biases, the discrete Gram matrix

$$G_{ij}=G(b_i,b_j)$$

has eigenvalues comparable to the rescaled continuous spectrum:

$${\lambda }_k(G)=\frac{n}{2}{\mu }_k+O(1).$$

Consequently, the condition number grows at least polynomially:

$$\kappa (G)=\frac{{\lambda }_1(G)}{{\lambda }_n(G)}=\Omega (n^3),$$

and for exactly evenly spaced biases the sharper behavior is $\Omega (n^4)$. For random biases sampled from a density bounded above and below, the same $k^{-4}$ spectral scale persists with high probability, up to logarithmic factors in the condition-number bound.

🔭 Radon Transform Viewpoint

The distributional identity ${\sigma }^{\prime \prime }={\delta }_0$ explains why the higher-dimensional spectrum is tied to the Laplacian. For a single ridge function,

$${\Delta }_x\sigma (w\cdot x-b)=\delta (w\cdot x-b),|w|=1.$$

Therefore, for

$$f(x)={\int }_{V}h(w,b)\sigma (w\cdot x-b)dwdb,$$

we have formally

$$\Delta f(x)={\int }_{{\mathbb{S}}^{d-1}}h(w,w\cdot x)dw={\mathcal{R}}^{\ast }h(x),$$

where ${\mathcal{R}}^{\ast }$ is the adjoint Radon transform.

Radon identities

For suitable functions, the Radon transform satisfies

$$\mathcal{R}\Delta f={\partial }_b^2\mathcal{R}f,{\mathcal{R}}^{\ast }{\partial }_b^{2}g=\Delta {\mathcal{R}}^{\ast }g,$$

and Helgason’s inversion formula gives

$$c_{d}f=(-\Delta {)}^{(d-1)/2}{\mathcal{R}}^{\ast }\mathcal{R}f.$$

Let ${\varphi }_k(w,b)$ be a parameter-space eigenfunction of the Gram operator with eigenvalue ${\lambda }_k$, and define its realized function

$$u_k(x)={\int }_V\sigma (w\cdot x-b){\varphi }_k(w,b)dwdb.$$

For odd $d$, the paper derives

$$c_d{u}_k={\lambda }_k(-\Delta {)}^{(d+3)/2}{u}_{k}x\in D,$$

with an analogous formula involving $(-\Delta {)}^{-1/2}{\chi }_D{u}_k$ for even $d$. Weyl’s law then yields the asymptotic Gram spectrum

$${\lambda }_k=\Theta \left(k^{-(d+3)/d}\right).$$

This is the precise version of the low-pass heuristic: high-index Gram eigenmodes correspond asymptotically to high-frequency Laplace modes, and their singular values are small.

💻 Finite Precision Cutoff

The universal approximation theorem is an exact-real-arithmetic statement. Numerically, the least-square solution uses a pseudoinverse or regularized solve, so Gram eigenvalues below the roundoff or data-noise scale are discarded.

If $\epsilon$ denotes machine precision or noise level, the paper’s estimate implies that a two-layer ReLU network can stably recover only about

$$O\left({\epsilon }^{-d/(2d+3)}\right)$$

leading modes, no matter how wide the network becomes after the width passes the resolution threshold. Equivalently, the largest stable frequency in each coordinate direction is only about

$$O\left({\epsilon }^{-1/(2d+3)}\right).$$

Consequence for double precision

With double precision, the paper estimates the resolvable frequency per direction as roughly $1351$ in dimension $1$, $172$ in dimension $2$, $55$ in dimension $3$, and $5$ in dimension $10$. The width can remove discretization error before this cutoff, but it cannot remove the finite-precision spectral cutoff.

This also clarifies a positive feature. The same low-pass behavior that suppresses oscillatory target components also suppresses high-frequency noise and reduces some overfitting sensitivity.

💡 Training Dynamics

The same ill-conditioning appears in gradient flow. In one dimension, write

$$h(x,t)=\sum _{i=1}^n{a}_i(t)\sigma (x-b_i(t))$$

and train against $f$ by the population square loss on $D=[-1,1]$. The gradient flow is

$$\frac{d{a}_i}{dt}=-{\int }_D(h(x,t)-f(x))\sigma (x-b_i)dx,$$ $$\frac{d{b}_i}{dt}=a_i{\int }_D(h(x,t)-f(x)){\sigma }^{\prime }(x-b_i)dx.$$

Following the paper, introduce an auxiliary function $w(b,t)$ by

$${\partial }_b^{2}w(b,t)=h(b,t)-f(b),w(1,t)={\partial }_{b}w(1,t)=0.$$

Let ${\theta }_m$ be the $m$-th generalized Fourier eigenfunction of the one-dimensional Gram kernel and write

$$\hat{w}(m,t)={\int }_{D}w(b,t){\theta }_m(b)db.$$

The relation ${\partial }_b^{2}w=h-f$ means that $\hat{w}(m,t)$ measures the error in mode $m$, with two derivatives of smoothing. The paper proves lower bounds on how fast this coefficient can be reduced. Under bounded coefficients and equispaced initial biases, halving mode $m$ requires at least

$$O\left(\frac{m^3|\hat{w}(m,0)|}{n}\right)$$

time. Since a discrete method that tracks the gradient flow needs time step $O(n^{-1})$, this already implies at least $O(m)$ numerical steps when the initial error in mode $m$ is nonzero. Under an additional bounded-variation assumption on $a_i(t{)}^2$ and a scaling regime $n\ge m^4$, the lower bound improves to

$$O\left(m^4|\hat{w}(m,0)|\right)$$

time, or at least $O(m^2)$ numerical steps.

Adaptivity is slow in the hard modes

Moving the biases is supposed to make the representation adaptive. The gradient-flow bounds say that the high-frequency modes needed for this adaptivity are precisely the modes that move slowly. Fixed-width training can therefore inherit the low-pass bias even outside the strict NTK picture.

🧩 Rashomon Set Perspective

The paper also gives a probability-side explanation. Define the Rashomon set as the subset of network parameters whose $L^2$ error is below a chosen tolerance. For oscillatory targets, this set has small normalized measure. In one of the paper’s estimates, Hoeffding’s inequality gives an exponential upper bound of the form

$$\mathbb{P}(R_{\epsilon })\le \exp \left(-\frac{n(1-\epsilon {)}^2\Vert f{\Vert }_{L^2(D)}^4}{2A^2{\kappa }^2}\right),$$

where $A$ bounds the output weights and $\kappa$ is a hyperplane-transform bound for the Poisson solution $g$ with $\Delta g=f$. For high-frequency $f$, this bound expresses the same practical message: randomly landing near a good shallow representation is unlikely, and training must search through a small target region.

📝 Notes

• The Laplacian/Radon calculation is the right continuum picture, but the paper’s main numerical lesson is about the Gram matrix. Expressivity alone does not decide what finite precision can recover.
• In one dimension, ReLU and linear finite elements can represent the same piecewise-linear functions. The finite-element basis is a good coordinate system; the ReLU ramp basis is not.
• Smoother activations can make the Gram spectrum decay even faster. ReLU is already biased against high frequencies, but analytic activations such as sigmoid or tanh can be more strongly biased in this least-square spectral sense.

🔗 See Also

• on eigenvalue estimate of kernel --- The ReLU Gram spectrum gives a concrete kernel with polynomial eigenvalue decay, feeding directly into finite-sample condition-number estimates.
• on improved Nyström bounds --- Random-feature and NTK Gram matrices are natural places to compare full kernels with low-rank sampled approximations.
• on subspace spanned by trajectory --- The training-dynamics discussion here is another instance where optimization is constrained by the spectral subspace reached along the trajectory.
• on “sum of squares” --- Ill-conditioned normal equations and pseudoinverse truncation are recurring numerical themes behind least-square representations.

📚 References

🐻  Zhang, S., Zhao, H., Zhong, Y. & Zhou, H. 2023. Why Shallow Networks Struggle to Approximate and Learn High Frequencies.