Proof of the UAT, by Weierstrass Theory

Weierstrass Theorem

Intuitive Explanation

Suppose

f\in C([0,1])

i.e., $f$ is continuous on $[0,1]$ .

Then for any

\varepsilon>0

there exists a polynomial $P(x)$ such that

|f(x)-P(x)|<\varepsilon, \qquad \forall x\in [0,1].

Next, let's try to prove this theorem.

Step 1: Construct the Bernstein polynomial

Define

B_n(f)(x) = \sum_{k=0}^{n} f\!\left(\frac{k}{n}\right) \binom{n}{k} x^k(1-x)^{n-k}.

This is the Bernstein polynomial.

Note that

\binom{n}{k} x^k(1-x)^{n-k}

is itself a polynomial in $x$ .

Therefore

B_n(f)(x)

is also a polynomial.

Step 2: Understand what it does. This polynomial is a bit abstract, but we can interpret it in another way.

First note the identity

\sum_{k=0}^{n} \binom{n}{k} x^k(1-x)^{n-k} =(x+(1-x))^n =1

Thus

B_n(f)(x)

is actually a weighted average of the sequence

f(0), f\left(\frac1n\right), \dots, f(1)

where the weights are

p_{n,k}(x) = \binom{n}{k} x^k(1-x)^{n-k}.

And the sum of these weights is 1.

But we can also interpret it from a probabilistic perspective.

Let the random variable

X_n\sim \mathrm{Binomial}(n,x).

That is,

P(X_n=k) = \binom{n}{k} x^k(1-x)^{n-k}.

Then

B_n(f)(x) = E\!\left[ f\!\left(\frac{X_n}{n}\right) \right].

This step is very elegant. The Bernstein polynomial is actually the expectation of

f\left(\frac{X_n}{n}\right).

Now let's analyze why it approximates $f(x)$ .

For the binomial distribution we have

E\!\left(\frac{X_n}{n}\right) = x,

\mathrm{Var} \!\left( \frac{X_n}{n} \right) = \frac{x(1-x)}{n}.

Therefore

\frac{X_n}{n}

becomes more and more concentrated around $x$ .

As $n\to\infty$ ,

\frac{X_n}{n} \to x.

Hence

f\!\left(\frac{X_n}{n}\right) \approx f(x).

Thus

B_n(f)(x) = E\!\left[ f\!\left(\frac{X_n}{n}\right) \right] \approx f(x).

Intuitively, this holds.

Rigorous Proof

Since $f$ is continuous on a closed interval, by properties of continuous functions on closed intervals: $f$ must be uniformly continuous. Therefore, for any $\varepsilon>0$ there exists $\delta>0$ such that whenever

|u-v|<\delta

we have

|f(u)-f(v)|<\frac{\varepsilon}{2}.

Decompose the error:

|B_n(f)(x)-f(x)| = \left| E\Big( f(X_n/n)-f(x) \Big) \right|.

By the expectation inequality for absolute values:

\le E\Big[ |f(X_n/n)-f(x)| \Big].

Split into two parts:

A= {|X_n/n-x|<\delta}

and

A^c= {|X_n/n-x|\ge \delta}.

First part: When $|X_n/n-x|<\delta$ ,

|f(X_n/n)-f(x)| < \frac{\varepsilon}{2}.

The contribution does not exceed $\frac{\varepsilon}{2}$ .

Second part: Let $M=\max_{[0,1]}|f|$ . Then

|f(X_n/n)-f(x)| \le 2M.

Thus the contribution does not exceed $2M·P(|X_n/n-x|\ge\delta)$ .

Using Chebyshev's inequality:

P(|X_n/n-x|\ge\delta) \le \frac{x(1-x)} {n\delta^2} \le \frac1{4n\delta^2}.

Therefore

2M· P(|X_n/n-x|\ge\delta) \le \frac{M}{2n\delta^2}.

When $n$ is sufficiently large,

\frac{M}{2n\delta^2} < \frac{\varepsilon}{2}.

Thus

|B_n(f)(x)-f(x)| < \varepsilon.

Moreover, this estimate is independent of $x$ .

Consequently,

\sup_{x\in[0,1]} |B_n(f)(x)-f(x)| \to 0.

That is,

B_n(f) \to f

uniformly.

Weierstrass theorem is proved.

Proof of the UAT

Next, we will go through the process of proving the Universal Approximation Theorem (UAT) using polynomial approximation, step by step, in language understandable with basic calculus. We take the univariate continuous function as an example for clarity; the vector case can be generalized similarly.

Goal: Given a continuous function $f:[a,b]\to \mathbb{R}$ and any $\epsilon>0$ , there exists a single-hidden-layer neural network

N(x) = \sum_{i=1}^{n} \alpha_i \sigma(\beta_i x + \gamma_i)

such that

|N(x) - f(x)| < \epsilon, \quad \forall x\in [a,b]

where $\sigma$ is a "non-polynomial, continuous" activation function (e.g., sigmoid).

Step 1: Use the Weierstrass Theorem

We have already proved this theorem earlier: any continuous function can be approximated by a polynomial $P(x)$ . That is,

\forall \epsilon>0, \exists P(x) \text{ s.t. } |f(x)-P(x)|<\epsilon/2

Here we do not consider neural networks yet; we transform the problem into "approximating a polynomial". As we know, a polynomial can be written as $a_0 + a_1 x + \dots + a_m x^m$ .

Step 2: Approximate monomials $x^k$ using an activation function

If we can approximate $x^k$ by a linear combination of neurons in one hidden layer, then we can approximate the polynomial $P(x)$ .

The single-hidden-layer network has the form:

N(x) = \sum_{i=1}^{n} \alpha_i \sigma(\beta_i x + \gamma_i)

Choose a suitable $\sigma(x)$ , such as the sigmoid:

\sigma(x) = \frac{1}{1+e^{-x}}

Its Taylor expansion is non-zero locally:

\sigma(x) = \frac12 + \frac14 x - \frac1{48} x^3 + \dots

One can generate arbitrary polynomial terms using linear combinations of its shifted versions.

By adjusting $\alpha_i, \beta_i, \gamma_i$ , the linear combination

\sum_i \alpha_i \sigma(\beta_i x + \gamma_i)

can approximate $x^k$ to arbitrary precision (similar to Taylor polynomial approximation in calculus).

Important intuition here: Each neuron is a "nonlinear function block", and summing many such blocks can combine into a polynomial form.

Step 3: Combine to approximate the polynomial

For a polynomial $P(x) = \sum_{k=0}^m a_k x^k$ , for each $x^k$ find the corresponding neuron combination $N_k(x)$ that approximates it:

|N_k(x) - x^k| < \frac{\epsilon}{2 (m+1)}

Then combine:

N(x) = \sum_{k=0}^m a_k N_k(x)

Error bound:

|N(x) - P(x)| \le \sum_{k=0}^m |a_k||N_k(x)-x^k| < \sum_{k=0}^m |a_k| \frac{\epsilon}{2(m+1)} < \epsilon/2

Step 4: Triangle inequality completes the approximation

We have two sources of error:

$|f(x) - P(x)| < \epsilon/2$ (Weierstrass theorem)
$|P(x) - N(x)| < \epsilon/2$ (neuron approximation of polynomials)

By the triangle inequality:

|f(x) - N(x)| \le |f(x)-P(x)| + |P(x)-N(x)| < \epsilon/2 + \epsilon/2 = \epsilon

QED.

In other words: the nonlinear units of a neural network act as an "adjustable polynomial basis", and a single layer can combine them into any polynomial, thereby approximating any continuous function.

UAT and the Machine Learning Perspective

This proof is actually quite interesting:

The Bernstein polynomial essentially expresses

f(x) \approx \sum_k f\!\left(\frac{k}{n}\right) \cdot \underbrace{ \binom{n}{k} x^k(1-x)^{n-k} }_{\text{base function}}

This closely resembles a neural network

f(x) \approx \sum_i a_i·\sigma(w_i x+b_i)

The difference is only:

Weierstrass uses polynomial bases $x^k(1-x)^{n-k}$
Neural networks use activation function bases $\sigma(wx+b)$

Thus from a modern perspective, the UAT theorem can be understood as a generalization of the Weierstrass theorem to "neural network basis functions". Weierstrass says "the polynomial basis is dense", while UAT says "the neuron basis is also dense".