skip to content

What does the universal approximation theorem guarantee about a one-hidden-layer network?

level: middleimportance: must knowfreq 62%

answer

  1. existence, not a recipe
  2. approximate within epsilon, not exact
  3. domain closed and bounded, fixed first
  4. target must be continuous
  5. activation must not be a polynomial

basics

~20 s

It is an existence result: for any continuous target on a closed bounded region and any error tolerance, some one-hidden-layer network with a non-polynomial activation stays inside that tolerance. The width needed is unbounded and unspecified.

solid answer

~40 s

The theorem says the functions computable by a single hidden layer are dense in the continuous functions on a compact domain. Concretely: fix a closed bounded region `K`, a continuous target `f`, and a tolerance `eps > 0`; if the activation is continuous and not a polynomial, then there exist a finite width `N` and weights such that `max over x in K of |g(x) - f(x)| < eps`. Four things are load-bearing. The domain is compact and fixed before the weights are chosen. The target is continuous. The activation must not be a polynomial. And `N` is whatever it takes: the theorem bounds nothing. It is approximation, not exact representation, and it is pure approximation theory: no training procedure, no data, no sample size appears anywhere in the statement.

code

python · 23 lines
python
import math

def sigmoid(z):
    if z < -30: return 0.0
    if z > 30: return 1.0
    return 1.0 / (1.0 + math.exp(-z))

def bumps(n, lo=0.0, hi=2 * math.pi):
    e = [lo + (hi - lo) * i / n for i in range(n + 1)]
    return [(e[i], e[i + 1], math.sin((e[i] + e[i + 1]) / 2)) for i in range(n)]

def net(x, units, steep=2000.0):
    return sum(h * (sigmoid(steep * (x - a)) - sigmoid(steep * (x - b)))
               for a, b, h in units)

grid = [2 * math.pi * i / 500 for i in range(501)]
for n in (8, 64, 256):
    units = bumps(n)
    err = max(abs(net(x, units) - math.sin(x)) for x in grid)
    print(2 * n, "hidden units -> max error", round(err, 4))
# 16 hidden units -> max error 0.3701
# 128 hidden units -> max error 0.0455
# 512 hidden units -> max error 0.0098

go deeper

for a junior

Be ready to state it in one sentence: one hidden layer can get arbitrarily close to a continuous function on a bounded region, given enough units. Say approximate, not represent exactly.

for a middle

An interviewer expects the conditions and the mechanism: compact domain, continuous target, non-polynomial activation, unbounded width, plus the bump picture of how steep units tile an interval.

for a senior

Volunteer the caveats before you are asked. Say plainly that the theorem is silent on optimization, on data, and on how wide the layer has to be, so it never justifies an architecture choice on its own.

for a principal

Own the framing: an existence-and-density result constrains almost nothing about engineering. Be able to explain to a team why density is a weak property and what evidence would actually settle a modelling decision.

## The statement, precisely Let `K` be a compact (closed and bounded) subset of d-dimensional real space, say the cube `[0, 1]^d`, and let `f: K -> R` be continuous. Fix a tolerance `eps > 0`. If the activation `sigma` is continuous and is **not** a polynomial, then there exist a finite width `N`, input weight vectors `w_1..w_N`, biases `b_1..b_N` and output weights `a_1..a_N` such that ``` g(x) = sum_{i=1..N} a_i * sigma(w_i . x + b_i) max over x in K of |g(x) - f(x)| < eps ``` Equivalently: the set of one-hidden-layer networks is **dense** in the continuous functions on `K` under the sup norm. The classical version (Cybenko, Hornik, late 1980s) assumed a sigmoidal activation — non-constant, bounded, monotone; the later refinement (Leshno, Lin, Pinkus and Schocken) showed the real condition is simply that the activation is not a polynomial, which is why ReLU qualifies. ## Four conditions worth naming out loud 1. **Compact domain, chosen first.** The quantifiers run: for every `K`, every `f`, every `eps`, there exist weights. `K` is fixed before the weights exist. Nothing is claimed off `K`. 2. **Continuous target.** A finite network with a continuous activation is a continuous function, so it cannot match a hard jump uniformly: near a step of height `h`, the sup-norm error is stuck at about `h/2` no matter the width. Discontinuous targets need a weaker, averaged notion of closeness. 3. **Non-polynomial activation.** If `sigma` were a polynomial of degree `k`, every `sigma(w . x + b)` is a polynomial of degree at most `k` in `x`, so the whole sum lives in a fixed finite-dimensional space of low-degree polynomials — far too small to be dense. 4. **Unbounded width.** `N` depends on `f`, on `eps` and on the dimension, and the theorem supplies no bound on it. 'One hidden layer suffices' and 'one small hidden layer suffices' are different claims. ## The bump reading The easiest constructive intuition: with a steep sigmoid, `sigma(s * (x - a))` approaches a step that switches on at `a`. Subtract two shifted steps and you get a **bump** supported on `[a, b]` — two hidden units per bump. Chop a bounded interval into `n` cells, put one bump on each, and scale each bump by the target's value at that cell's midpoint. The result is a staircase that tracks the target. Take `f(x) = sin(x)` on `[0, 2*pi]`. A staircase with `n` cells is off by roughly how far `sin` can move across one cell, about `(2*pi/n) * max|f'| / 2 = pi/n`. To push that under `0.01` you need a few hundred cells — and each cell costs two hidden units, so several hundred units for a one-dimensional sine wave. That is a construction, not a lower bound; smarter constructions do much better. But it makes the width point concrete, and it shows why the theorem is an existence statement rather than an engineering recommendation. The same construction in `d` inputs needs bumps that are products across dimensions, so tiling the cube costs on the order of `n^d` cells — the curse of dimensionality shows up immediately in the naive construction. ## What the theorem does not say - **Nothing about optimization.** It asserts weights exist. It names no learning procedure, so it cannot promise that any procedure finds them. - **Nothing about data.** The weights are chosen with knowledge of `f` on all of `K`. Recovering them from a finite sample is a separate statistical question the theorem never touches. - **Nothing off the domain.** Outside `K` the network is unconstrained. - **Nothing about width being reasonable.** - **Nothing about exactness.** `eps` is strictly positive; equality is not claimed. ## Why interviewers ask it It is a clean test of whether a candidate can separate three things that beginners collapse together: what a hypothesis class *can* represent, what an algorithm *will* find, and what data *can* pin down. A strong answer states the theorem in one sentence, names the compactness and continuity conditions, and volunteers the width and optimization caveats before being asked.

  • Why must the activation be non-polynomial?
    If the activation is a polynomial of degree `k`, then `sigma(w . x + b)` is itself a polynomial of degree at most `k` in the inputs, and any finite sum of such terms is too. The hidden layer can then only produce functions from one fixed, finite-dimensional space of low-degree polynomials, which is nowhere near dense in the continuous functions. Widening the layer adds units but never escapes that space.
  • Does the theorem cover a discontinuous target, such as a hard indicator function?
    Not under the uniform statement. A finite network with a continuous activation is continuous, and a continuous function cannot stay within a small `eps` of a jump on both sides of it — the sup-norm error is pinned near half the jump height. You can still get close in an averaged sense, with the error squeezed into a shrinking neighbourhood of the discontinuity, but that is a weaker claim than the theorem's.
  • Does the theorem tell you how many training examples you need?
    No. Data never appears in it. The weights are constructed knowing the target everywhere on the domain, so the theorem is about what the hypothesis class contains, not about what a finite sample can identify. How many examples pin down a good member of that class is a separate statistical question with its own machinery.

It is like being told a bounded room can be tiled to any precision with small enough tiles. True, and it tells you nothing about how many tiles, how to cut them, or what lies outside the room.

saying these in an interview costs you the question

  • Says a network can represent any function exactly
  • Drops the closed and bounded domain condition
  • Claims the theorem guarantees training finds the weights
  • Assumes a modest hidden layer always suffices
  • Thinks it holds for any activation, including linear

context

resolving links…