2026, June, 06

Proof of the UAT, by Weierstrass Theory

The core purpose of UAT (Universal Approximation Theorem) is that neural networks can approximate any continuous function, and continuous functions can be approximated by polynomials (Weierstrass theorem).

Suppose

f∈C([0,1])f\in C([0,1])

i.e., ff is continuous on [0,1][0,1].

Then for any

ε>0\varepsilon>0

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

∣f(x)−P(x)∣<ε,∀x∈[0,1].|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

Bn(f)(x)=∑k=0nf ⁣(kn)(nk)xk(1−x)n−k.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

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

is itself a polynomial in xx.

Therefore

Bn(f)(x)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

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

Thus

Bn(f)(x)B_n(f)(x)

is actually a weighted average of the sequence

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

where the weights are

pn,k(x)=(nk)xk(1−x)n−k.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

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

That is,

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

Then

Bn(f)(x)=E ⁣[f ⁣(Xnn)].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(Xnn).f\left(\frac{X_n}{n}\right).

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

For the binomial distribution we have

E ⁣(Xnn)=x,E\!\left(\frac{X_n}{n}\right) = x,Var ⁣(Xnn)=x(1−x)n.\mathrm{Var} \!\left( \frac{X_n}{n} \right) = \frac{x(1-x)}{n}.

Therefore

Xnn\frac{X_n}{n}

becomes more and more concentrated around xx.

As n→∞n\to\infty,

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

Hence

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

Thus

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

Intuitively, this holds.

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

∣u−v∣<δ|u-v|<\delta

we have

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

Decompose the error:

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

By the expectation inequality for absolute values:

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

Split into two parts:

A=∣Xn/n−x∣<δA= {|X_n/n-x|<\delta}

and

Ac=∣Xn/n−x∣≥δ.A^c= {|X_n/n-x|\ge \delta}.

First part: When ∣Xn/n−x∣<δ|X_n/n-x|<\delta,

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

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

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

∣f(Xn/n)−f(x)∣≤2M.|f(X_n/n)-f(x)| \le 2M.

Thus the contribution does not exceed 2M⋅P(∣Xn/n−x∣≥δ)2M·P(|X_n/n-x|\ge\delta).

Using Chebyshev's inequality:

P(∣Xn/n−x∣≥δ)≤x(1−x)nδ2≤14nδ2.P(|X_n/n-x|\ge\delta) \le \frac{x(1-x)} {n\delta^2} \le \frac1{4n\delta^2}.

Therefore

2M⋅P(∣Xn/n−x∣≥δ)≤M2nδ2.2M· P(|X_n/n-x|\ge\delta) \le \frac{M}{2n\delta^2}.

When nn is sufficiently large,

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

Thus

∣Bn(f)(x)−f(x)∣<ε.|B_n(f)(x)-f(x)| < \varepsilon.

Moreover, this estimate is independent of xx.

Consequently,

sup⁡x∈[0,1]∣Bn(f)(x)−f(x)∣→0.\sup_{x\in[0,1]} |B_n(f)(x)-f(x)| \to 0.

That is,

Bn(f)→fB_n(f) \to f

uniformly.

Weierstrass theorem is proved.

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]→Rf:[a,b]\to \mathbb{R} and any ϵ>0\epsilon>0, there exists a single-hidden-layer neural network

N(x)=∑i=1nαiσ(βix+γi)N(x) = \sum_{i=1}^{n} \alpha_i \sigma(\beta_i x + \gamma_i)

such that

∣N(x)−f(x)∣<ϵ,∀x∈[a,b]|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)P(x). That is,

∀ϵ>0,∃P(x) s.t. ∣f(x)−P(x)∣<ϵ/2\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 a0+a1x+⋯+amxma_0 + a_1 x + \dots + a_m x^m.

Step 2: Approximate monomials xkx^k using an activation function

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

The single-hidden-layer network has the form:

N(x)=∑i=1nαiσ(βix+γi) N(x) = \sum_{i=1}^{n} \alpha_i \sigma(\beta_i x + \gamma_i)

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

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

Its Taylor expansion is non-zero locally:

σ(x)=12+14x−148x3+… \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 αi,βi,γi\alpha_i, \beta_i, \gamma_i, the linear combination

∑iαiσ(βix+γi) \sum_i \alpha_i \sigma(\beta_i x + \gamma_i)

can approximate xkx^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)=∑k=0makxkP(x) = \sum_{k=0}^m a_k x^k, for each xkx^k find the corresponding neuron combination Nk(x)N_k(x) that approximates it:

∣Nk(x)−xk∣<ϵ2(m+1) |N_k(x) - x^k| < \frac{\epsilon}{2 (m+1)}

Then combine:

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

Error bound:

∣N(x)−P(x)∣≤∑k=0m∣ak∣∣Nk(x)−xk∣<∑k=0m∣ak∣ϵ2(m+1)<ϵ/2 |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:

1. ∣f(x)−P(x)∣<ϵ/2|f(x) - P(x)| < \epsilon/2 (Weierstrass theorem)
2. ∣P(x)−N(x)∣<ϵ/2|P(x) - N(x)| < \epsilon/2 (neuron approximation of polynomials)

By the triangle inequality:

∣f(x)−N(x)∣≤∣f(x)−P(x)∣+∣P(x)−N(x)∣<ϵ/2+ϵ/2=ϵ |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)≈∑kf ⁣(kn)⋅(nk)xk(1−x)n−k⏟base functionf(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)≈∑iai⋅σ(wix+bi)f(x) \approx \sum_i a_i·\sigma(w_i x+b_i)

The difference is only:

• Weierstrass uses polynomial bases xk(1−x)n−kx^k(1-x)^{n-k}
• Neural networks use activation function bases σ(wx+b)\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".