Fourier Derivation Of Barron Approximation Bounds

From Fourier Representation to a Shallow Network

A Fourier representation writes a function as a weighted average of oscillatory features. The key approximation idea is to sample a finite number of those features and average them. The resulting finite sum is a shallow network with cosine activation. Its approximation error can be controlled by the total first moment of the frequency weights, rather than by counting a separate approximation cost for every frequency.

We will derive both an integrated mean-square bound and a uniform bound. They have different strengths: the integrated bound is dimension-independent, while the uniform bound also depends on how many points are needed to cover the domain. The construction here uses cosine ridge units; a Fourier argument for these units does not, by itself, prove the same result for a different activation.

Definition: Suppose a real-valued function $f:\mathbb{R}^d\to\mathbb{R}$ has the Fourier representation $$ f(x)=\int_{\mathbb{R}^d} e^{i\omega\cdot x}\,\nu(d\omega), $$ where $\nu$ is a finite complex measure and the integral is real for every $x$. Write $|\nu|$ for its total-variation measure. Its Fourier first moment is $$ B=\int_{\mathbb{R}^d}\|\omega\|\,|\nu|(d\omega). $$ We assume $B<\infty$. For an integrable Fourier transform, the convention is $\nu(d\omega)=\widehat f(\omega)\,d\omega$, with $\widehat f(\omega)=(2\pi)^{-d}\int f(x)e^{-i\omega\cdot x}\,dx$ whenever this inversion formula applies.

The first moment $B$ is the relevant size measure because changing $x$ by a small amount changes a frequency-$\omega$ feature by an amount proportional to $\|\omega\|$. Frequencies near zero contribute to the constant level of the function but contribute little to its variation across the domain. We therefore approximate $f(x)-f(0)$, leaving $f(0)$ as an exact output bias.

The Sampling Construction

Assume first that $B>0$. By the polar decomposition of a complex measure, there is a measurable function $q$ with $|q(\omega)|=1$ for $|\nu|$-almost every $\omega$, such that $\nu(d\omega)=q(\omega)|\nu|(d\omega)$. Draw a frequency $\Omega$ from the probability measure $$ P(\Omega\in d\omega)=\frac{\|\omega\|}{B}|\nu|(d\omega). $$ This is a probability measure because its total mass is $B/B=1$. It places no mass at $\omega=0$.

For a sampled frequency, define the real-valued feature $$ H_\Omega(x)=B\,\operatorname{Re}\left[q(\Omega)\frac{e^{i\Omega\cdot x}-1}{\|\Omega\|}\right]. $$ Equivalently, if $q(\Omega)=e^{i\phi}$, this is $B\{\cos(\Omega\cdot x+\phi)-\cos(\phi)\}/\|\Omega\|$. Each feature is a cosine ridge unit together with a constant adjustment. Given independent draws $\Omega_1,\ldots,\Omega_m$, set $$ f_m(x)=f(0)+\frac{1}{m}\sum_{j=1}^m H_{\Omega_j}(x). $$ Thus $f_m$ has one output bias and $m$ sampled cosine units.

Theorem: For every $x$, $E[H_\Omega(x)]=f(x)-f(0)$. If $K$ is any measurable subset of the ball $\{x:\|x\|\le R\}$, and $P_X$ is any probability distribution supported on $K$, then $$ E\left[\int_K |f_m(x)-f(x)|^2\,P_X(dx)\right]\le \frac{B^2R^2}{m}. $$ If $B=0$, $f$ is constant and the same construction is unnecessary: $f_m=f$ exactly.

To prove unbiasedness, integrate with respect to the sampling distribution. Since $\nu=q|\nu|$, and the real part of the Fourier representation of $f(x)-f(0)$ equals that real-valued difference, $$ E[H_\Omega(x)] =\int \operatorname{Re}\{q(\omega)(e^{i\omega\cdot x}-1)\}\,|\nu|(d\omega) =f(x)-f(0). $$ The integrand is zero at $\omega=0$, so omitting that frequency causes no change.

For the error bound, use $|e^{it}-1|\le |t|$ and $|\omega\cdot x|\le\|\omega\|\|x\|$. For $x\in K$, $$ |H_\Omega(x)|\le B\|x\|\le BR. $$ The $m$ sampled features are independent and have mean $f(x)-f(0)$. Therefore the variance of their average is $1/m$ times the variance of one feature, which is no greater than its second moment. Consequently, $$ E[|f_m(x)-f(x)|^2]\le \frac{E[|H_\Omega(x)|^2]}{m}\le\frac{B^2R^2}{m}. $$ Integrating this nonnegative inequality with respect to $P_X$, and interchanging expectation and integration by Tonelli’s theorem, gives the stated result. $\square$

Worked Example: A Gaussian Target

Let $d=1$ and $f(x)=e^{-x^2/2}$. Its Fourier representation under the stated convention has density $\widehat f(\omega)=(2\pi)^{-1/2}e^{-\omega^2/2}$. This is the standard normal density, so $\nu$ is a probability measure and $q(\omega)=1$.

The first moment is $$ B=\int_{\mathbb{R}}|\omega|(2\pi)^{-1/2}e^{-\omega^2/2}\,d\omega =\frac{2}{\sqrt{2\pi}}\int_0^\infty \omega e^{-\omega^2/2}\,d\omega =\sqrt{\frac{2}{\pi}}. $$ The last integral equals $1$, by the substitution $u=\omega^2/2$. The sampled frequencies have density $|\omega|\widehat f(\omega)/B$, and the feature is $H_\Omega(x)=B\{\cos(\Omega x)-1\}/|\Omega|$. Its expectation is $e^{-x^2/2}-1$, as required.

On any domain inside $[-1,1]$, the integrated mean-square error is at most $2/(\pi m)$, since $R=1$ and $B^2=2/\pi$. For $m=100$, this bound is $2/(100\pi)$, approximately $0.00637$. It holds for any probability distribution supported on that domain.

A Uniform Approximation Bound

An integrated error bound averages over a specified distribution of inputs. To control the largest error anywhere in a domain, we also need a way to pass from finitely many points to the whole domain. The finite first moment supplies that control: every sampled feature, and the target itself, is Lipschitz.

Theorem: Suppose $K$ is a compact subset of $\{x:\|x\|\le R\}$, and let $x_1,\ldots,x_N$ be a finite $\delta$-net of $K$: every $x\in K$ is within distance $\delta$ of some $x_k$. For the sampled approximation above, $$ E\left[\sup_{x\in K}|f_m(x)-f(x)|\right] \le BR\sqrt{\frac{2\log(2N)}{m}}+2B\delta. $$ A $\delta$-net can be chosen with $N\le (1+2R\sqrt d/\delta)^d$.

For any $x,y$, the elementary inequality $|e^{is}-e^{it}|\le |s-t|$ gives $$ |H_\Omega(x)-H_\Omega(y)| \le B\frac{|\Omega\cdot(x-y)|}{\|\Omega\|} \le B\|x-y\|. $$ Averaging preserves this Lipschitz bound, so $f_m$ is $B$-Lipschitz. The same argument applied to the Fourier integral gives $|f(x)-f(y)|\le B\|x-y\|$. Thus $f_m-f$ is $2B$-Lipschitz.

At any fixed net point $x_k$, $f_m(x_k)-f(x_k)$ is an average of $m$ independent centered random variables, each taking values in $[-BR,BR]$. Hoeffding’s exponential bound implies that this average has moment-generating function bounded by $\exp(t^2B^2R^2/(2m))$ for every real $t$. Applying this bound to both signs at each of the $N$ points, and using the log-sum-exp inequality, yields $$ E\left[\max_{1\le k\le N}|f_m(x_k)-f(x_k)|\right] \le BR\sqrt{\frac{2\log(2N)}{m}}. $$ For every $x\in K$, choose a net point $x_k$ within distance $\delta$. The Lipschitz bound then gives $$ |f_m(x)-f(x)|\le |f_m(x_k)-f(x_k)|+2B\delta. $$ Taking the supremum and expectation proves the displayed uniform bound. To obtain the stated covering-number estimate, partition the containing cube $[-R,R]^d$ into cubes of side at most $\delta/\sqrt d$, and choose one point of $K$ from each cube that intersects $K$. The diameter of each cube is at most $\delta$, and the number of cubes is at most $(1+2R\sqrt d/\delta)^d$. $\square$

Worked Example: Turning a Finite Cover into a Uniform Bound

Continue with the Gaussian target on $K=[-1,1]$, so $R=1$ and $B=\sqrt{2/\pi}$. Take $m=100$ and $\delta=0.1$. A grid with spacing $0.1$, including both endpoints, has $N=21$ points and is a $0.1$-net.

The uniform theorem gives $$ E\left[\sup_{x\in[-1,1]}|f_m(x)-f(x)|\right] \le \sqrt{\frac{2}{\pi}}\sqrt{\frac{2\log(42)}{100}} +2\sqrt{\frac{2}{\pi}}(0.1). $$ Since $\log(42)$ is approximately $3.738$, the first term is approximately $0.218$, and the second is approximately $0.160$. The resulting upper bound is approximately $0.378$. This is a valid bound, not a prediction that the actual error will be close to $0.378$; the covering and concentration steps can make it conservative.

What the Bounds Say—and What They Do Not

The integrated theorem has a particularly direct interpretation: with a fixed domain radius, the expected squared error decreases at rate $1/m$, so the root-mean-square error decreases at rate $1/\sqrt m$. Its constant is $B R$, and it has no explicit dimension factor. The uniform theorem also improves as $m$ grows, but it pays for a cover of the domain. The displayed covering-number bound makes the dimension dependence visible through the number of net points.

The sampling probabilities are important. Frequencies are drawn in proportion to $\|\omega\||\nu|(d\omega)$, not simply in proportion to $|\nu|(d\omega)$. This choice makes each normalized feature bounded on a radius-$R$ domain by $BR$. Without frequency normalization, the first moment would not give this uniform bound on the sampled features.

Worked Example: A Two-Frequency Target

Consider $f(x)=0.4\cos x+0.6\cos(3x)$. Its symmetric Fourier measure has masses $0.2$ at each of $1$ and $-1$, and masses $0.3$ at each of $3$ and $-3$. Hence $$ B=0.4(1)+0.6(3)=2.2. $$ After weighting the masses by frequency magnitude, the probability of sampling $|\Omega|=1$ is $0.4/2.2=2/11$, while the probability of $|\Omega|=3$ is $1.8/2.2=9/11$.

Here $q=1$, and the sampled feature is $H_\Omega(x)=2.2\{\cos(\Omega x)-1\}/|\Omega|$. Averaging its expectation over the two possible absolute frequencies gives $$ \frac{2}{11}\,2.2(\cos x-1) +\frac{9}{11}\,\frac{2.2}{3}(\cos(3x)-1) =0.4(\cos x-1)+0.6(\cos(3x)-1) =f(x)-f(0). $$ At $x=\pi/3$, the two possible feature values are $-1.1$ and $-22/15$, with probabilities $2/11$ and $9/11$. Their mean is $-1.4$, which equals $f(\pi/3)-f(0)=-0.4-1$. Their variance is $$ \frac{2}{11}(1.1)^2+\frac{9}{11}\left(\frac{22}{15}\right)^2-(-1.4)^2 =1.98-1.96=0.02. $$ Thus at this input the mean-square error of the $m$-feature average is $0.02/m$.

A common mistake is to take a pointwise Monte Carlo guarantee and declare it a uniform guarantee with the same rate and constant. Pointwise control applies at a fixed $x$; it does not directly control the supremum over an uncountable set. The correction is to use a finite net, bound the maximum error on that net, and control what happens between net points using Lipschitz continuity. The net size, and therefore the domain’s dimension and geometry, enters the resulting bound.

A second caution is about the activation. The derivation represents the target by sampled cosine ridge units. Although it is a shallow-network approximation result, it is not automatically a ReLU approximation result: changing the activation requires a separate representation argument and corresponding control of its coefficients. The Fourier first moment identifies the size needed for this cosine-feature construction; it does not erase the assumptions of a different network theorem.

Key takeaway: A finite Fourier first moment $B$ gives a sampled cosine network whose expected integrated squared error on a radius-$R$ domain is at most $B^2R^2/m$. A uniform guarantee follows by combining concentration on a finite net with the Lipschitz control supplied by the same frequency moment.

Check Your Understanding

Use the definitions and derivations above to answer the following.

Why is the sampling distribution weighted by $\|\omega\|$, and how does that choice lead to a bound on the size of each sampled feature?
For a target with $B=3$, approximated on a ball of radius $2$ with $m=36$ features, what integrated mean-square error bound follows for any input distribution supported on the ball?
Why does the uniform bound require a finite cover even though the pointwise estimator is unbiased?
Which part of the uniform-bound proof introduces dependence on the dimension?
Does the Fourier-feature derivation alone prove an identical approximation result for ReLU networks? Explain.

Fourier Derivation Of Barron Approximation Bounds

What You'll Learn