Barron space

In functional analysis, the Barron space is a function space. It is a Banach space. It originated from the study of universal approximation properties of two-layer neural networks. It has applications in approximation theory and statistical learning theory.

It is named after Andrew R. Barron, who did work on the functional analysis of two-layer neural networks, though he did not define Barron space in his works.¹

We quote the following universal approximation theorem:

In words, given a subset ${\displaystyle X\subset \mathbb {R} ^{n}}$, and a fixed activation function ${\displaystyle \sigma }$ that is not a polynomial function, then any continuous function of type ${\displaystyle X\to \mathbb {R} ^{m}}$ can be approximated as a 2-layered neural network with a linear layer ${\displaystyle (A,b)}$, followed by the nonlinear activation ${\displaystyle \sigma }$, followed by another linear layer ${\displaystyle C}$. Furthermore, given any compact subset ${\displaystyle K\subset X}$, the approximation can be arbitrarily good in the uniform norm.

Usually we only consider the case where the neural network has a single output, that is, the case where ${\displaystyle m=1}$, since for multiple outputs, the outputs can be separately approximated. We assume that ${\displaystyle m=1}$ for the rest of the article.

In the statement of the theorem, the middle layer is the hidden layer. The number ${\displaystyle k}$ is the number of neurons in the hidden layer. These neurons are called hidden neurons.

Given a compact set ${\displaystyle X\subset \mathbb {R} ^{n}}$, to approximate a generic continuous function to an accuracy of ${\displaystyle \epsilon }$ in the uniform norm over ${\displaystyle X}$, ${\displaystyle O(\epsilon ^{-d})}$ hidden neurons are needed. This is a manifestation of the curse of dimensionality.

In a 1993 paper, Barron showed that a large class of continuous functions are much more approximable than a generic continuous function. Specifically, he showed that there is a set of continuous functions such that, given any Borel probability measure ${\displaystyle \mu }$, only ${\displaystyle O(\epsilon ^{-2})}$ hidden neurons are needed to approximate ${\displaystyle f}$ to an accuracy of ${\displaystyle \epsilon }$ in the ${\displaystyle L^{2}(\mu )}$ norm. In this sense, these functions are nice, in that they can be efficiently approximated by a neural network without hitting the curse of dimensionality.²³

It is natural to consider the infinite width limit, where the summation turns into an integral:$${\displaystyle f(x):=\int c\,\sigma (a^{T}x+b)\;\rho (da,db,dc)}$$where ${\displaystyle a,b,c}$ takes values in ${\displaystyle \mathbb {R} ^{n},\mathbb {R} ,\mathbb {R} }$, and ${\displaystyle \rho }$ is a probability distribution over ${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} \times \mathbb {R} }$.

Different ${\displaystyle \rho }$ may lead to the same ${\displaystyle f}$. That is, the representation of a function as an infinite-width neural network is not unique. However, among these, one may be selected as having lowest regularization loss, as usual in statistical learning theory.

If ${\displaystyle \sigma }$ is the ReLU function, define as follows.

For any ${\displaystyle p\in [1,\infty ]}$, define the regularization loss of representation ${\displaystyle \rho }$ as$${\displaystyle \|\rho \|_{p}:=\mathbb {E} _{(a,b,c)\sim \rho }{\Big [}|c(\|a\|_{1}+|b|)|^{p}{\Big ]}^{1/p}}$$if ${\displaystyle p\in [1,\infty )}$, and$${\displaystyle \|\rho \|_{p}:=\sup _{(a,b,c)\in \operatorname {supp} \rho }|c(\|a\|_{1}+|b|)|}$$if ${\displaystyle p=\infty }$. This is defined in analogy to Lp spaces, and is motivated by the previous result on the number of hidden neurons.

The special case of ${\displaystyle p=1}$ is also called the path norm, since it is interpreted as the path weight ${\displaystyle c(\|a\|_{1}+|b|)}$, averaged across all paths from the inputs to the output of the neural network.

The p-Barron norm of ${\displaystyle f}$ is defined as$${\displaystyle \|f\|_{B_{p}}:=\inf _{\rho {\text{ represents }}f}\|\rho \|_{p}}$$The p-Barron space over ${\displaystyle X\subset \mathbb {R} ^{n}}$ is the set of continuous functions of type ${\displaystyle X\to \mathbb {R} }$ of finite p-Barron norm.

It can be proven that if ${\displaystyle \|f\|_{B_{p}}<\infty }$ for some ${\displaystyle p\in [1,\infty ]}$, then ${\displaystyle \|f\|_{B_{p}}}$ is the same for all ${\displaystyle p\in [1,\infty ]}$. Therefore, all these are the same, and we drop the p and call all of ${\displaystyle \|\cdot \|_{B_{p}}}$ the same Barron norm, and the space of them the Barron space. It is written as ${\displaystyle {\mathcal {B}}}$¹

The Barron space is a Banach space.^{3: Thm. 2.3}

If ${\displaystyle \sigma }$ is not the ReLU function, then define the p-extended Barron norm:$${\displaystyle \|\rho \|_{p}:=\mathbb {E} _{(a,b,c)\sim \rho }{\Big [}|c(\|a\|_{1}+|b|\color {red}{+1}\color {black})|^{p}{\Big ]}^{1/p}}$$$${\displaystyle \|f\|_{{\tilde {B}}_{p}}:=\inf _{\rho {\text{ represents }}f}\|\rho \|_{p}}$$Similarly, define the p-extended Barron spaces.

In general, they are not the same for different values of p.

There is a generalization for multilayer neural networks with ReLU activations.⁴

Theorem.^{1: Thm. 1} Given ${\displaystyle f\in {\mathcal {B}}}$, then for any positive integer ${\displaystyle k}$, there exists a two-layer ReLU network with ${\displaystyle M}$ hidden neurons$${\displaystyle f_{M}(x)={\frac {1}{M}}\sum _{i=1}^{M}c_{i}\;\operatorname {ReLU} (a_{i}\cdot x+b_{i})}$$such that ${\displaystyle \left\|f_{M}-f\right\|_{L^{2}(\Omega )}^{2}\leq {\frac {3\|f\|_{B}^{2}}{M}}}$, and ${\displaystyle {\frac {1}{M}}\sum _{i=1}^{M}|c_{i}|(\|a_{i}\|_{1}+|b_{i}|)\leq 2\|f\|_{B}}$.

Theorem.^{1: Thm. 2} (converse to the previous theorem) For any ${\displaystyle f}$ continuous on ${\displaystyle X\subset \mathbb {R} ^{n}}$, if there exists a sequence of two-layer ReLU networks ${\displaystyle f_{M}}$ with ${\displaystyle M=1,2,\dots }$ hidden neurons, converging ${\displaystyle f_{M}\to f}$ pointwise, and the Barron norms of these ${\displaystyle f_{M}}$ are uniformly bounded by a single ${\displaystyle C}$:$${\displaystyle {\frac {1}{M}}\sum _{i=1}^{M}|c_{i}|(\|a_{i}\|_{1}+|b_{i}|)\leq C,\quad \forall M=1,2,3,\dots }$$then ${\displaystyle f\in {\mathcal {B}}}$ and ${\displaystyle \|f\|_{B}\leq C}$.

Theorem. For any ${\displaystyle f}$ continuous on ${\displaystyle X\subset \mathbb {R} ^{n}}$, define$${\displaystyle \gamma (f):=\inf _{\hat {f}}\int _{\mathbb {R} ^{n}}\|\omega \|_{1}^{2}|{\hat {f}}(\omega )|d\omega }$$where ${\displaystyle {\hat {f}}}$ ranges over Fourier transformations of all possible extensions of ${\displaystyle f}$ to all of ${\displaystyle \mathbb {R} ^{n}}$, then, if ${\displaystyle \gamma (f)<\infty }$, then ${\displaystyle f\in {\mathcal {B}}}$.

Furthermore, we have the explicit upper bound:^{1: Prop. 2}$${\displaystyle \|f\|_{\mathcal {B}}\leq 2\gamma (f)+2\|\nabla f(0)\|_{1}+2|f(0)|}$$

Let ${\displaystyle S=\{z_{1},z_{2},\dots ,z_{m}\}\subseteq Z}$ be a sample of points and consider a function class ${\displaystyle {\mathcal {F}}}$ of real-valued functions over ${\displaystyle Z}$. Then, the empirical Rademacher complexity of ${\displaystyle {\mathcal {F}}}$ given ${\displaystyle S}$ is defined as:

${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}})={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{f\in {\mathcal {F}}}\left|\sum _{i=1}^{m}\sigma _{i}f(z_{i})\right|\right]}$

Theorem.^{1: Thm. 3} For any ${\displaystyle C>0}$, let ${\displaystyle {\mathcal {F}}_{C}:=\{f\in {\mathcal {B}}:\|f\|_{B}\leq C\}}$, then ${\displaystyle \operatorname {Rad} _{S}({\mathcal {F}}_{C})\leq 2C{\sqrt {\frac {2\ln(2n)}{|S|}}}}$, where as a reminder ${\displaystyle n}$ is the number of dimensions of the domain of ${\displaystyle f}$.

This result shows that the space of functions bounded in Barron norm has low Rademacher complexity, which according to statistical learning theory, means they are highly learnable. This rhymes with the fact that they are well approximable by a network with few hidden neurons.