Feedforward networks and single-hidden-layer universality

Fix $k\ge 1$ and linear forms ${\mathrm{\ell }}_j(x)=v_j\cdot x$ for $1\le j\le k$. Expanding the powers and summing signs gives the polarization identity ${\prod }_{j=1}^k{\mathrm{\ell }}_j(x)=\frac{1}{2^{k}k!}{\sum }_{ϵ\in \{-1,1{\}}^k}({\prod }_{j=1}^k{ϵ}_j)({\sum }_{j=1}^k{ϵ}_j{\mathrm{\ell }}_j(x){)}^k$. Indeed, in the multinomial expansion, a monomial ${\prod }_j{\mathrm{\ell }}_j^{r_j}$ has sign sum ${\prod }_j{\sum }_{{ϵ}_j=\pm 1}{ϵ}_j^{r_j+1}$, which is zero unless every $r_j$ is odd. Since ${\sum }_j{r}_j=k$, the only surviving tuple is $r_1=\cdots =r_k=1$, with coefficient $2^{k}k!$. Thus every product of $k$ linear forms lies in ${\mathcal{R}}_d$.

Every coordinate monomial $x_1^{{\alpha }_1}\cdots x_d^{{\alpha }_d}$ of positive total degree $k$ is a product of $k$ coordinate linear forms, with $x_i$ repeated ${\alpha }_i$ times. Step 1.1 puts it in ${\mathcal{R}}_d$. Constants lie in ${\mathcal{R}}_d$ by $k=0$, so every real polynomial restricts to an element of ${\mathcal{R}}_d{\mathrm{\mid }}_K$.

The restrictions to $K$ of real polynomials form a unital real function algebra: sums, scalar multiples, and products are polynomials, and the constant-one polynomial is a unit. If $x,y\in K$ are distinct, some coordinate differs, so the corresponding coordinate polynomial separates them. By [F1] these polynomial restrictions are uniformly dense in $C(K,\mathbb{R})$. Since step 2.1 places them inside ${\mathcal{R}}_d{\mathrm{\mid }}_K$, the latter is dense as well.

Put $u=w\mathrm{/}\parallel w{\parallel }_2$. For $d\ge 2$, start with $u$ and inspect the standard basis vectors in their finite order; for each $e_i$, subtract its orthogonal projection onto the span of the vectors already retained, and append and normalize the residual exactly when it is nonzero. Since the standard basis spans ${\mathbb{R}}^d$, this finite Gram–Schmidt procedure produces an orthonormal basis whose first vector is $u$. Let $Q$ be the associated orthogonal coordinate map. If $d=1$, take $Qx=ux$. In either case the first coordinate of $Qx$ is $u\cdot x$, and [F4] says $Q$ preserves Lebesgue measure.

Fix an integer $R\ge 1$. Since $Q$ is a finite matrix, choose $C_R<\mathrm{\infty }$ greater than $R$ times the largest sum of absolute entries in any row; then $Q([-R,R{]}^d)\subseteq [-C_R,C_R{]}^d$. Since $E$ has outer measure zero, [F1] makes it Lebesgue measurable and null. Thus $E_R=((E-b)\mathrm{/}\parallel w{\parallel }_2)\cap [-C_R,C_R]$ is a one-dimensional measurable null set by [F5]. By [F1], choose a Borel null set $B_R\supseteq E_R$. If $d=1$, the image under $Q$ of the set in the Statement intersected with $[-R,R]$ is contained in $B_R$. If $d\ge 2$, that image is contained in $B_R\times [-C_R,C_R{]}^{d-1}$.

If $d=1$, the bounded pullback image is contained in the Borel null set $B_R$, and the inverse orthogonal map preserves nullity by [F4]. If $d\ge 2$, the Borel set $B_R\times [-C_R,C_R{]}^{d-1}$ is Lebesgue measurable by [F7]; both Lebesgue factors are $\sigma$-finite by [F8], so Tonelli [F2] gives it product measure zero because its one-dimensional section factor $B_R$ has measure zero, and [F3] identifies that product measure with ${\lambda }_d$. Applying the inverse orthogonal map preserves nullity by [F4]. In either case the ridge pullback inside $[-R,R{]}^d$ is contained in a Borel null set.

The full pullback is the countable union of its intersections with $[-R,R{]}^d$, $R\ge 1$. Each intersection is a subset of the Borel null set from step 3.1, hence is measurable and null by [F6]. The full pullback is measurable by [F6] and null by countable subadditivity [F9]. If two functions differ only on $E$, their compositions differ only on this pullback, proving the consequence.

For each integer $n>2\mathrm{/}(b-a)$ define ${\chi }_n(x)=\theta (n(x-a))\theta (n(b-x))$; such integers exist by [F6], and can tend to infinity by [F8]. By [F2], ${\chi }_n$ is smooth, vanishes off $I$, and equals one on $[a+1\mathrm{/}n,b-1\mathrm{/}n]$. Every derivative of $\theta$ is continuous and vanishes outside $[0,1]$ in positive order, so [F7] bounds it on $[0,1]$; repeated chain and product rules [F7] bound ${\chi }_n^{(j)}$ by a constant times $n^j$. For every $\phi \in D_I$, all derivatives of its zero extension vanish at $a$ and $b$. Fix $M$. Taylor's formula [F4] gives, for every $N\ge 1$ and each $0\le r\le M$, bounds $\mathrm{\mid }{\phi }^{(r)}(x)\mathrm{\mid }\le C_{r,N}\mathrm{\mid }x-a{\mathrm{\mid }}^N$ near $a$ and $\mathrm{\mid }{\phi }^{(r)}(x)\mathrm{\mid }\le C_{r,N}^{\mathrm{\prime }}\mathrm{\mid }b-x{\mathrm{\mid }}^N$ near $b$. Applying the product rule on the two boundary strips, and taking $N>M$, shows $p_M(\phi -{\chi }_n\phi )\to 0$.

Fix $n$ and $M$. By [F3], choose a real polynomial $p$ uniformly approximating ${\phi }^{(M)}$ on $I$, and integrate it $M$ times while matching the values ${\phi }^{(j)}(a)$ for $0\le j<M$ to obtain a polynomial $q_0$. Put $e=\phi -q_0$. Then $e^{(M)}={\phi }^{(M)}-p$ and $e^{(j)}(a)=0$ for $j<M$. Repeated application of [F5], inducting downward from $j=M-1$, gives ${\sup }_I\mathrm{\mid }{e}^{(j)}\mathrm{\mid }\le (b-a{)}^{M-j}{\sup }_I\mathrm{\mid }{e}^{(M)}\mathrm{\mid }(0\le j<M);$ for $j=M$ the error is just ${\sup }_I\mathrm{\mid }{e}^{(M)}\mathrm{\mid }$. Thus sufficiently accurate approximation at order $M$ makes every derivative through order $M$ uniformly close. Approximating the finitely many coefficients of $q_0$ by rational numbers gives $q\in \mathbb{Q}[x]$ with the same approximation to any prescribed tolerance. Since the finitely many derivatives of ${\chi }_n$ are bounded on $I$, the product rule makes $p_M({\chi }_n(q-\phi ))$ arbitrarily small. Thus ${\chi }_{n}q\in D_I$ approximates ${\chi }_n\phi$ in $p_M$.

The set $\{{\chi }_{n}q:n\in \mathbb{N},n>2\mathrm{/}(b-a),q\in \mathbb{Q}[x]\}$ is countable. Given a metric neighborhood of $\phi \in D_I$, the summable metric weights reduce it to finitely many seminorms, bounded by $p_M$ for the largest index. Choose $n$ in step 1.1 so that $p_M(\phi -{\chi }_n\phi )$ is less than half the target tolerance, then choose $q$ in step 1.2 so that $p_M({\chi }_n\phi -{\chi }_{n}q)$ is less than the other half. The triangle inequality places ${\chi }_{n}q$ in the neighborhood. Hence this countable set is dense.

Base case $n=0$: the hypothesis is $DT=0$, so [F1] gives a constant regular distribution with some value $c\in \mathbb{C}$. Choose a real test function $\eta$ with integral one by [F5]. Since $c=⟨T,\eta ⟩$ and $T$ is real, $c\in \mathbb{R}$. Thus $T$ is represented by a real polynomial of degree at most zero.

Inductive step: let $n\ge 1$ and assume the result for $n-1$. The distribution $S=D^{n}T$ satisfies $DS=D^{n+1}T=0$ and is real by [F2]. By [F1], $S$ is the constant distribution with some value $c\in \mathbb{C}$. Choose a real test function $\eta$ with integral one by [F5]. Since $c=⟨S,\eta ⟩$ and $S$ is real, $c\in \mathbb{R}$.

The smooth polynomial $q(x)=c{x}^n\mathrm{/}n!$ has $D^{n}q=c$ as a regular distribution by [F3] and [F4]. Thus $U=T-q$ satisfies $D^{n}U=0$. The induction hypothesis applied with index $n-1$ gives a polynomial $r$ of degree at most $n-1$ whose regular distribution is $U$.

The polynomial $p=q+r$ has degree at most $n$ and its regular distribution is $T$, since regular distributions and distributional derivatives are linear. This completes the induction.

Choose a measurable representative $f$ of $[f]$. Truncate it to $f_M=\max (-M,\min (f,M))$. Since $\mathrm{\mid }f-f_M{\mathrm{\mid }}^p\le \mathrm{\mid }f{\mathrm{\mid }}^p$ and $f_M\to f$ pointwise wherever $f$ is finite, [F4] makes $\mathrm{\parallel }f-f_M{\mathrm{\parallel }}_{L^p(\mu )}<\epsilon \mathrm{/}2$ for some large $M$. Partition $[-M,M]$ into finitely many intervals of length at most $\delta$ and replace each value of $f_M$ by a fixed endpoint of its interval. If $\mu (K)>0$, choose $\delta$ with $\delta \mu (K{)}^{1\mathrm{/}p}<\epsilon \mathrm{/}2$; if $\mu (K)=0$, any $\delta >0$ suffices. The resulting finite-valued Borel simple function $s$ satisfies $\mathrm{\mid }s-f_M\mathrm{\mid }\le \delta$ pointwise, so $\mathrm{\parallel }s-f_M{\mathrm{\parallel }}_{L^p(\mu )}\le \delta \mu (K{)}^{1\mathrm{/}p}$. By [F5] and the triangle inequality, $\mathrm{\parallel }s-f{\mathrm{\parallel }}_{L^p(\mu )}<\epsilon$. Since $\mu$ is concentrated on $K$, replace $s$ by ${\mathbf{1}}_{K}s$: this finite Borel simple function represents the same class and admits a representation with every set $E_j\subseteq K$. Thus such supported simple functions are dense in $L^p(\mu )$.

Write such a simple function as $s={\sum }_{j=1}^N{c}_j{\mathbf{1}}_{E_j}$ with Borel $E_j\subseteq K$. For any $\eta >0$, regularity [F2] gives compact $F_j\subseteq E_j$ and open $O_j\supseteq E_j$ with $\mu (O_j\setminus F_j)<\eta$. By [F3] choose ${\psi }_j\in C_c^{\mathrm{\infty }}(O_j)$ with $0\le {\psi }_j\le 1$ and ${\psi }_j=1$ on $F_j$. Outside $O_j\setminus F_j$ the functions ${\psi }_j$ and ${\mathbf{1}}_{E_j}$ agree; everywhere their difference has magnitude at most one. Therefore $\mathrm{\parallel }{\psi }_j-{\mathbf{1}}_{E_j}{\mathrm{\parallel }}_{L^p(\mu )}^p\le \mu (O_j\setminus F_j)<\eta$.

The triangle inequality [F5] gives ${\parallel {\sum }_{j=1}^N{c}_j{\psi }_j-s\parallel }_{L^p(\mu )}\le {\sum }_{j=1}^N\mathrm{\mid }{c}_j\mathrm{\mid }{\eta }^{1\mathrm{/}p}$. Choose $\eta$ small enough that this is below $\epsilon \mathrm{/}2$, and choose $s$ from step 1.1 within $\epsilon \mathrm{/}2$ of $f$. Then the compactly supported continuous function ${\sum }_j{c}_j{\psi }_j$ is within $\epsilon$ of $f$ in $L^p(\mu )$.

Base case $d=1$: [F1] makes the zero set finite, hence countable and null by [F4].

Inductive step: let $d\ge 2$ and assume the claim in dimension $d-1$. Write $P(x^{\mathrm{\prime }},t)={\sum }_{j=0}^m{Q}_j(x^{\mathrm{\prime }})t^j$, where $x^{\mathrm{\prime }}\in {\mathbb{R}}^{d-1}$ and the highest coefficient $Q_m$ is a nonzero polynomial. By the induction hypothesis, $Z=\{x^{\mathrm{\prime }}:Q_m(x^{\mathrm{\prime }})=0\}$ is null. For every $x^{\mathrm{\prime }}\mathrm{\notin }Z$, the section $t\mapsto P(x^{\mathrm{\prime }},t)$ is a nonzero univariate polynomial, so its zero set is finite by [F1] and null by [F4].

Fix $R\ge 1$. The set $\{(x^{\mathrm{\prime }},t)\in [-R,R{]}^d:P(x^{\mathrm{\prime }},t)=0\}$ is Borel because $P$ is continuous. Its section has measure at most $2R$ when $x^{\mathrm{\prime }}\in Z$ and measure zero otherwise. Both Lebesgue factors are $\sigma$-finite by [F6], so Tonelli [F2] shows that its product measure is zero, since $Z$ is null; [F3] identifies this with its Euclidean Lebesgue measure.

The full zero set is the countable union of these Borel null intersections over integers $R\ge 1$. Countable subadditivity [F4] makes it measurable and null. The base case and induction step prove the assertion for every $d\ge 1$.

Let $X=D_{[-1,1]}$ with its fixed-support Fréchet topology. For each $n\in {\mathbb{N}}_0$, set $E_n=\{\phi \in X:g_{\phi }^{(n+1)}(x)=0\text{ for every }x\in \mathbb{R}\}$. Linearity of convolution makes $E_n$ a linear subspace. For fixed $x$, its defining functional is continuous: on the compact interval $x-[-1,1]$, local essential boundedness of $\sigma$ gives a finite bound $M_x$, and $\mathrm{\mid }{g}_{\phi }^{(n+1)}(x)-g_{\psi }^{(n+1)}(x)\mathrm{\mid }\le 2M_x{p}_{n+1}(\phi -\psi )$. Thus $E_n$, an intersection of kernels of continuous functionals, is closed.

If a smooth function $g$ has $(n+1)$st derivative zero, [F6] first makes $g^{(n)}$ constant; subtracting its corresponding multiple of $x^n\mathrm{/}n!$ leaves an $n$th derivative equal to zero. Repeating this argument down to order zero shows $g$ is a polynomial of degree at most $n$. Conversely every such polynomial has $(n+1)$st derivative zero. Thus the hypothesis gives $X={\bigcup }_{n=0}^{\mathrm{\infty }}{E}_n$.

By [F2]–[F4], the Baire theorem applies to $X$. Therefore some closed subspace $E_N$ has nonempty interior; otherwise the closed sets $E_n$ would all be nowhere dense and their countable union could not equal $X$. A linear subspace with nonempty interior contains a neighborhood of zero, and scaling any vector into that neighborhood shows it is the whole space. Hence $E_N=X$.

Membership $E_N=X$ says $g_{\phi }^{(N+1)}=0$ for every test function supported in $[-1,1]$. Repeated application of [F6] then makes every $g_{\phi }$ a polynomial of degree at most $N$, as claimed.

Restrict each unit of $N$ to $t{e}_1$. If its first weight coordinate is zero, that unit is constant in $t$. If that coordinate is nonzero, [F2] says the set of $t$ for which its preactivation lies in $E$ is null. There are finitely many units, so their union is null by [F4] and cannot contain a nondegenerate interval by [F3]. Every nonempty relatively open subset of $[0,1]$ contains a nondegenerate interval, so the complement is dense in $[0,1]$. On this dense complement every nonconstant unit equals $p(w_{j1}t+b_j)$. Thus $N(t{e}_1)$ agrees there with a polynomial $P_N(t)$ of degree at most $q$; the constant units are absorbed into its constant term.

Suppose ${\sup }_{0\le t\le 1}\mathrm{\mid }N(t{e}_1)-t^{q+1}\mathrm{\mid }<{\epsilon }_q$. On the dense subset from step 1.1, $\mathrm{\mid }{P}_N(t)-t^{q+1}\mathrm{\mid }<{\epsilon }_q$; continuity of both polynomials extends the weak bound $\le {\epsilon }_q$ to all of $[0,1]$.

Put $h=1\mathrm{/}(q+1)$ and evaluate the $(q+1)$st forward difference at $t=0$. Its nodes are $jh$ for $0\le j\le q+1$, all in $[0,1]$. The forward-difference operation $Q(t)\mapsto Q(t+h)-Q(t)$ lowers the degree of every nonconstant polynomial by one and multiplies its leading coefficient by its degree times $h$. Iterating it $q+1$ times therefore annihilates $P_N$ and gives $(q+1)!h^{q+1}$ on $t^{q+1}$. The approximation bound [step 2.1] makes the absolute value of the resulting error sum at most $2^{q+1}{\epsilon }_q$, since the binomial coefficients sum to $2^{q+1}$. But this is half of $(q+1)!h^{q+1}$ by the definition of ${\epsilon }_q$, a contradiction.

Hence no network attains the stated error on this target, so the family is not uniformly dense on $K$. The argument includes $q=0$, where it says constants cannot approximate $t$ to arbitrary accuracy.

Fix $k\ge 1$ and $w\in {\mathbb{R}}^d$. If a smooth function has $g^{(k)}\equiv 0$, induction on $k$ shows it is a polynomial of degree at most $k-1$: for $k=1$, [F4] makes it constant; for $k\ge 2$, [F4] makes $g^{(k-1)}$ constant $c$, and subtracting $c{x}^{k-1}\mathrm{/}(k-1)!$ reduces to the induction hypothesis. Since $g$ is not a polynomial, choose $b_k$ with $g^{(k)}(b_k)\mathrm{\ne }0$. For $\delta \mathrm{\ne }0$, repeated application of [F4] gives the finite-difference identity ${\mathrm{\Delta }}_{\delta }^{k}g(y)={\delta }^k{g}^{(k)}(\xi )$ for some $\xi$ between $y$ and $y+k\delta$, where ${\mathrm{\Delta }}_{\delta }g(y)=g(y+\delta )-g(y)$. Indeed, the case $k=1$ is [F4]; for the induction step apply [F4] to $x\mapsto {\mathrm{\Delta }}_{\delta }^{k-1}g(x)$ between $y$ and $y+\delta$, then apply the induction hypothesis to $g^{\mathrm{\prime }}$ at the resulting point. The binomial expansion of ${\mathrm{\Delta }}_{\delta }^{k}g(y)$ is ${\sum }_{j=0}^k(-1{)}^{k-j}\left(\genfrac{}{}{0px}{}{k}{j}\right)g(y+j\delta )$. For $h>0$, define $R_{k,h}(x)=\frac{1}{g^{(k)}(b_k)h^k}{\sum }_{j=0}^k(-1{)}^{k-j}\left(\genfrac{}{}{0px}{}{k}{j}\right)g(b_k+jhw\cdot x),$ a finite linear combination of units from [F1]. If $w\cdot x=0$ then $R_{k,h}(x)=0=(w\cdot x{)}^k$. Otherwise the identity with $\delta =h(w\cdot x)$ gives $R_{k,h}(x)=\frac{(w\cdot x{)}^k}{g^{(k)}(b_k)}{g}^{(k)}({\xi }_{x,h}),\mathrm{\mid }{\xi }_{x,h}-b_k\mathrm{\mid }\le kh\mathrm{\mid }w\cdot x\mathrm{\mid }\mathrm{.}$ By [F3], choose $M<\mathrm{\infty }$ with $\mathrm{\mid }w\cdot x\mathrm{\mid }\le M$ on $K$. Continuity of $g^{(k)}$ at $b_k$ makes $g^{(k)}({\xi }_{x,h})\to g^{(k)}(b_k)$ uniformly over $x\in K$ as $h\downarrow 0$, since $\mathrm{\mid }{\xi }_{x,h}-b_k\mathrm{\mid }\le khM$. Therefore $R_{k,h}\to (w\cdot x{)}^k$ uniformly on $K$.

Constants belong to the network family through its output bias. Step 1.1 puts every positive-degree polynomial ridge function in the uniform closure of the family; finite sums of such approximants are still finite networks. By [F2], that closure contains a dense subspace of $C(K,\mathbb{R})$.

Given $\epsilon >0$, first choose a polynomial ridge combination within $\epsilon \mathrm{/}2$ of $f$ by [F2], then approximate its finitely many ridge terms closely enough using step 1.1 that their total error is below $\epsilon \mathrm{/}2$. The resulting one-hidden-layer network is within $\epsilon$ of $f$.