Barron Spaces And Dimension-Independent Approximation

Why a Fourier Norm Can Control Network Approximation

A function can vary across many input coordinates yet still have a compact representation as an average of one-dimensional ridge functions. A useful way to quantify this structure is to measure the size of its Fourier representation, weighting higher frequencies more heavily. This produces a function-class norm that directly controls the size of a finite shallow network approximating the function.

The bounds below concern shallow networks with the cosine activation. They make two different approximation claims. In integrated squared error, the rate depends on network width but has no explicit dimension factor. For uniform error on a cube, a finite grid argument gives a transparent bound involving the dimension. These are approximation statements: they do not by themselves assert that a particular training algorithm finds the approximating network.

Fourier Representations and the Barron-Type Norm

Let $\mu$ be a finite complex Borel measure on $\mathbb{R}^d$. Its Fourier representation, using the convention adopted here, is $f(x)=\int_{\mathbb{R}^d} e^{i\omega\cdot x}\,d\mu(\omega)$. For a real-valued function, we require the conjugate-symmetry condition $\mu(-A)=\overline{\mu(A)}$ for every Borel set $A$. This ensures that the integral is real for every $x$. Write $|\mu|$ for the total variation measure of $\mu$.

Definition: A real-valued function $f$ on $\mathbb{R}^d$ is in the Fourier Barron class considered here if it has a representation $$ f(x)=\int_{\mathbb{R}^d}e^{i\omega\cdot x}\,d\mu(\omega) $$ by a finite conjugate-symmetric complex Borel measure $\mu$ satisfying $$ \int_{\mathbb{R}^d}(1+\|\omega\|_2)\,d|\mu|(\omega)<\infty. $$ Its weighted Fourier norm is $$ \|f\|_{\mathcal B}=\int_{\mathbb{R}^d}(1+\|\omega\|_2)\,d|\mu|(\omega). $$

The Fourier transform uniquely determines a finite measure on $\mathbb{R}^d$. Thus, for representations that agree with $f$ on all of $\mathbb{R}^d$, this definition does not take an infimum over alternative measures: the representing measure, and hence the displayed norm, is unique. When the approximation domain is only a subset of $\mathbb{R}^d$, different measures can agree there; that is a distinct restricted-domain convention and is not needed for the bounds proved here.

The factor $1+\|\omega\|_2$ controls both the total mass and the first frequency moment. In particular, $f$ is bounded by the total variation mass and is Lipschitz with constant at most the first frequency moment. The second fact follows from $|e^{iu}-e^{iv}|\leq |u-v|$ and $|\omega\cdot(x-y)|\leq\|\omega\|_2\|x-y\|_2$.

Worked Example: A Single Nonzero-Frequency Cosine

Let $a,\phi\in\mathbb{R}$, let $\omega_0\in\mathbb{R}^d$ be nonzero, and set $f(x)=a\cos(\omega_0\cdot x+\phi)$. Using $\cos u=(e^{iu}+e^{-iu})/2$, its measure has atoms $\mu(\{\omega_0\})=ae^{i\phi}/2$ and $\mu(\{-\omega_0\})=ae^{-i\phi}/2$.

Because $\omega_0\ne 0$, these are distinct locations. Each atom has total variation $|a|/2$, so the total variation is $|a|$. Both locations have Euclidean norm $\|\omega_0\|_2$. Therefore $\|f\|_{\mathcal B}=|a|(1+\|\omega_0\|_2)$.

The nonzero-frequency condition matters. If instead $\omega_0=0$, the function is the constant $a\cos\phi$. The two nominal atoms now coincide and their masses combine to $a\cos\phi$, giving norm $|a\cos\phi|$, not necessarily $|a|$.

Worked Example: Adding Two Frequencies

For $x=(x_1,x_2)\in\mathbb{R}^2$, consider $f(x)=2\cos(x_1)+\cos(2x_2+\pi/3)$. The first cosine has atoms at $e_1$ and $-e_1$, each of mass magnitude $1$. Their contribution to the weighted norm is $2(1+\|e_1\|_2)=2(2)=4$.

The second cosine has atoms at $2e_2$ and $-2e_2$, each of mass magnitude $1/2$. Their contribution is $2(1/2)(1+\|2e_2\|_2)=1(3)=3$. The four locations are distinct, so their total variation contributions add. Hence $\|f\|_{\mathcal B}=4+3=7$.

From the Fourier Integral to a Finite Shallow Network

Write $\nu=|\mu|$, and let $q=d\mu/d\nu$ be the Radon–Nikodym derivative. Then $|q|=1$ $\nu$-almost everywhere. Set $B=\|f\|_{\mathcal B}$. If $B>0$, define a probability measure $p$ on frequencies by $dp(\omega)=(1+\|\omega\|_2)d\nu(\omega)/B$. Since $\mu$ is conjugate-symmetric, the Fourier integral is real and can be written as $\int \operatorname{Re}(q(\omega)e^{i\omega\cdot x})\,d\nu(\omega)$. For each sampled frequency, this real part is a cosine ridge function with a phase. Reweighting by $p$ gives the identity

f(x)=E_p\left[\frac{B}{1+\|\omega\|_2} \operatorname{Re}\!\left(q(\omega)e^{i\omega\cdot x}\right)\right].

Thus $f$ is an expectation of shallow cosine units. Replacing that expectation by an average of $m$ sampled units yields a width-$m$ network. Crucially, each sampled summand has absolute value at most $B$, regardless of the input dimension.

Theorem: Let $f$ have the Fourier representation and finite norm $B$ defined above, and let $\rho$ be any probability measure on a measurable input domain. For each integer $m\geq1$, there is a width-$m$ cosine network $$ g_m(x)=\frac{1}{m}\sum_{j=1}^m \frac{B}{1+\|\omega_j\|_2} \operatorname{Re}\!\left(q(\omega_j)e^{i\omega_j\cdot x}\right) $$ such that $$ E\!\left[\|g_m-f\|_{L^2(\rho)}^2\right]\leq\frac{B^2}{m}, \qquad E\!\left[\|g_m-f\|_{L^2(\rho)}\right]\leq\frac{B}{\sqrt m}. $$ Here the $\omega_j$ are independent draws from $p$, and the outer expectation is over the sampled network. If $B=0$, then $f=0$, and the zero network gives zero error.

Proof. For $B>0$, let $Y_j(x)=B(1+\|\omega_j\|_2)^{-1}\operatorname{Re}(q(\omega_j)e^{i\omega_j\cdot x})$. The representation identity gives $E[Y_j(x)]=f(x)$, and $|Y_j(x)|\leq B$. Independence therefore gives, pointwise in $x$,

E\!\left[(g_m(x)-f(x))^2\right] =\frac{\operatorname{Var}(Y_1(x))}{m} \leq\frac{E[Y_1(x)^2]}{m} \leq\frac{B^2}{m}.

Integrating this nonnegative quantity with respect to $\rho$ and interchanging expectation and integration by Tonelli’s theorem yields the first inequality. Jensen’s inequality applied to the square root gives $E[\|g_m-f\|_{L^2(\rho)}]\leq \sqrt{E[\|g_m-f\|_{L^2(\rho)}^2]}\leq B/\sqrt m$. In particular, some realization has integrated squared error at most $B^2/m$: otherwise the expectation would exceed that value. $\square$

This bound has no explicit factor of $d$. It is an integrated-error result for any chosen probability distribution $\rho$, not a uniform guarantee at every input. Dimension can still affect the problem through the function itself, its norm $B$, the domain, or the measure $\rho$.

Worked Example: An Integrated Error Guarantee

Suppose a function has weighted Fourier norm $B=7$, as in the two-frequency example, and we want an integrated squared error guarantee of at most $0.49$. The theorem gives $B^2/m=49/m$, so we need $49/m\leq0.49$, or $m\geq100$.

With $m=100$, the expected squared $L^2(\rho)$ error of the randomly sampled network is at most $49/100=0.49$, and its expected $L^2(\rho)$ error is at most $7/10=0.7$. These are different statements: the latter is a bound on the expected norm, not on the square root of the expected squared norm in the reverse direction.

A Uniform Bound on a Bounded Cube

A uniform guarantee requires controlling all inputs, rather than averaging over $\rho$. On a bounded cube, the norm also supplies the regularity needed to pass from a finite grid to the whole domain. The resulting bound displays a dimension factor through the number of grid points.

Theorem: Suppose $B=\|f\|_{\mathcal B}>0$, and let $C=[-R,R]^d$, where $R>0$. Construct $g_m$ by the independent sampling scheme above. Fix a grid spacing parameter $\delta>0$ and $0<\alpha<1$. Put $$ K=\left(\left\lceil\frac{2R}{\delta}\right\rceil+1\right)^d. $$ Then, with probability at least $1-\alpha$, $$ \sup_{x\in C}|g_m(x)-f(x)| \leq B\sqrt{\frac{2\log(2K/\alpha)}{m}} +2B\sqrt d\,\delta. $$

Proof. Each summand $Y_j(x)$ has mean $f(x)$ and lies in $[-B,B]$. Hoeffding’s inequality for independent bounded random variables gives, at any fixed $x$, $P(|g_m(x)-f(x)|>t)\leq2\exp(-mt^2/(2B^2))$. Partition each coordinate interval $[-R,R]$ into $\lceil2R/\delta\rceil$ equal subintervals, and take the Cartesian product of their endpoints. This grid has at most $K$ points, and every point in $C$ is within Euclidean distance $\sqrt d\,\delta$ of a grid point.

Apply the union bound to the grid. With $t=B\sqrt{2\log(2K/\alpha)/m}$, the probability that any grid-point error exceeds $t$ is at most $2K\exp(-mt^2/(2B^2))=\alpha$.

It remains to extend the grid guarantee. For any $x,y$, the Fourier representation and $|e^{iu}-e^{iv}|\leq|u-v|$ give $|f(x)-f(y)|\leq B\|x-y\|_2$. Each sampled summand has Lipschitz constant at most $B\|\omega_j\|_2/(1+\|\omega_j\|_2)\leq B$; averaging preserves this bound, so $g_m$ is also $B$-Lipschitz. Consequently $g_m-f$ is $2B$-Lipschitz. Moving from an arbitrary point to its nearest grid point increases the error by at most $2B\sqrt d\,\delta$. Adding this to the grid bound proves the result. $\square$

Worked Example: Reading the Uniform Bound

Take $d=2$, $R=1$, $m=1000$, $\alpha=0.05$, and $\delta=0.1$. Then $K=(\lceil2/0.1\rceil+1)^2=21^2=441$. The grid term, divided by $B$, is $\sqrt{2\log(2(441)/0.05)/1000} =\sqrt{2\log(17640)/1000}$, which is approximately $0.140$.

The between-grid term, divided by $B$, is $2\sqrt2(0.1)$, approximately $0.283$. Thus with probability at least $0.95$, $\sup_{x\in[-1,1]^2}|g_m(x)-f(x)|\leq0.423B$, up to rounding. The grid contribution grows with $d$, since $K$ grows exponentially in $d$; this bound is not a dimension-free uniform approximation claim.

What the Bounds Do—and Do Not—Say

The norm provides an approximation budget: a smaller $B$ gives tighter bounds at fixed width. The integrated result is especially notable because its $B/\sqrt m$ rate has no explicit dimension dependence. The uniform result is more demanding and, for the simple grid argument used here, pays for the size of a grid covering the input cube. Neither result says that every function in the class is easy to learn from finite data; approximation error is only one component of a statistical learning problem.

A common mistake is to take “dimension-independent” to mean “uniformly accurate on a high-dimensional cube at the same width.” The integrated theorem does not imply that. It bounds average squared error under a specified probability measure. A uniform bound must also control variation between inputs, and the explicit grid proof does so at a cost depending on $d$. Another important check is the zero-frequency case: when a cosine’s frequency is zero, its two Fourier atoms coincide, so their masses must be combined before computing total variation.

Key takeaway: A finite weighted Fourier norm turns a function into an expectation of bounded cosine ridge units. Sampling $m$ units gives expected integrated error at most $B/\sqrt m$; on a bounded cube, a grid argument gives a uniform bound with explicit dependence on dimension, width, and confidence.

Check Your Understanding

Use the definitions and bounds above to check your understanding.

Why is the weighted Fourier norm defined here not an infimum over full-space representations?
For $a\cos(\omega\cdot x+\phi)$ with $\omega\ne0$, what are the two atom masses, and why do their total variation contributions add?
State the integrated squared-error bound for a width-$m$ sampled network when $\|f\|_{\mathcal B}=B$.
Which part of the uniform approximation bound introduces an explicit dependence on $d$, and why?
If $\omega=0$, what function does $a\cos(\omega\cdot x+\phi)$ represent, and what is its weighted Fourier norm?