Statistical Learning Theory 9 Nonuniform Learning 11 Optimization

Chapter 10 Universal Approximation

In our motivation of SRM in chapter 9, we talked about wanting to use an $\mathcal{H}$ so big that the approximation error $\inf_{h\in\mathcal{H}}L_{\mathcal{D}}(h)-L_{\text{bayes}}$ is zero. What kinds of $\mathcal{H}$ satisfy that?

To keep things simple, we’ll think about $\mathcal{Y}\subseteq\mathbb{R}$ for this chapter. We’re also going to assume for simplicity that $\mathcal{X}$ is compact. For intuition, sets like $\{x\in\mathbb{R}^{d}:\lVert x\rVert\leq R\}$ are compact; $\mathbb{R}^{d}$ isn’t, and neither is $\{x\in\mathbb{R}^{d}:\lVert x\rVert<R\}$ .

Definition 10.1.

¹¹1There are many definitions of compactness which are equivalent for metric spaces (but not necessarily more general topological spaces).

A metric space

\mathcal{X}

is totally bounded if for every

\eta>0

, its covering number

N_{\eta}^{\mathrm{cov}}(\mathcal{X})

(definition 4.8) is finite. A metric space which is totally bounded and complete (definition B.9) is called compact.

\mathcal{X}

is a subset of

\mathbb{R}^{d}

and we’re using the Euclidean metric, being complete is the same thing as being a closed set, and being totally bounded is the same as being bounded. That result is known as the Heine-Borel theorem.

One example would be the set of all functions $\mathcal{X}\to\mathcal{Y}$ . This way leads to a million mathematical counterexamples of being able to do even super basic things like computing expectations, let alone being able to learn.

A milder set to target is the set of all continuous functions. If there’s a continuous function achieving the Bayes error, then this immediately guarantees that the approximation error would be zero.

Definition 10.2.

For a compact metric space

\mathcal{X}

C(\mathcal{X})

denotes the Banach space of continuous functions

\mathcal{X}\to\mathbb{R}

, with norm given by

\lVert f\rVert_{\infty}=\sup_{x\in\mathcal{X}}\lvert f(x)\rvert

Recall that if

f

and

g

are elements of a function space and

a\in\mathbb{R}

, we have that

af+g

is the function mapping

x

af(x)+g(x)

. So,

\lVert f-g\rVert_{\infty}=\sup_{x\in\mathcal{X}}\lvert f(x)-g(x)\rvert

is one possible distance metric on functions.

The following result suggests that this is a reasonable (if strict) way to calculate distances between functions.

Proposition 10.3.

Suppose that

\ell(h,(x,y))=l_{y}(h(x))

for

l_{y}:\mathbb{R}\to\mathbb{R}

. Then

L_{\mathcal{D}}

\left(\operatorname*{\mathbb{E}}_{y\sim\mathcal{D}_{y}}\lVert l_{y}\rVert_{% \mathrm{Lip}}\right)

-Lipschitz with respect to

\lVert h-g\rVert_{\infty}

Proof.

We have that

\lvert L_{\mathcal{D}}(h)-L_{\mathcal{D}}(g)\rvert=\left\lvert\operatorname*{% \mathbb{E}}_{(x,y)\sim{\mathcal{D}}}l_{y}(h(x))-\operatorname*{\mathbb{E}}_{(x% ,y)\sim{\mathcal{D}}}l_{y}(g(x))\right\rvert\leq\operatorname*{\mathbb{E}}_{(x% ,y)\sim{\mathcal{D}}}\left\lvert l_{y}(h(x))-l_{y}(g(x))\right\rvert\\ \leq\operatorname*{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}\lVert l_{y}\rVert_{% \mathrm{Lip}}\lvert h(x)-g(x)\rvert\leq\left(\operatorname*{\mathbb{E}}_{(x,y)% \sim{\mathcal{D}}}\lVert l_{y}\rVert_{\mathrm{Lip}}\right)\lVert h-g\rVert_{% \infty}.\qed

10.1 Denseness

Even if the “target function” isn’t continuous, the approximation error could still be zero.

Example 10.4.

Consider

\mathcal{X}=[-1,1]

\mathcal{D}_{x}

being arbitrary on

\mathcal{X}

, and the true labels being determined by the discontinuous function

y=\operatorname{\mathds{1}}(x>0)

. Although this function isn’t in

C(\mathcal{X})

, you can get arbitrarily close to it, e.g. by taking the continuous functions

f_{\sigma}(x)=\begin{cases}0&\text{if }x\leq 0\\ x/\sigma&\text{if }0\leq x\leq\sigma\\ 1&\text{if }x\geq\sigma.\end{cases}

The absolute loss

l_{y}(\hat{y})=\lvert y-\hat{y}\rvert

L_{\mathcal{D}}(f_{\sigma})=\operatorname*{\mathbb{E}}\left[\left(1-\frac{x}{% \sigma}\right)\operatorname{\mathds{1}}\bigl{(}x\in(0,\sigma)\bigr{)}\right]% \leq\Pr\bigl{(}x\in(0,\sigma)\bigr{)}.

\sigma\to 0

, for every

{\mathcal{D}}

we necessarily have

\Pr(x\in(0,\sigma))\to 0

, and thus

L_{\mathcal{D}}(f_{\sigma})\to 0

. As such

\inf_{h\in C(\mathcal{X})}L_{\mathcal{D}}(h)=0

– even though if

\mathcal{D}_{x}

is continuous with positive density on

[0,\varepsilon]

, there is no

h\in C(\mathcal{X})

with

L_{\mathcal{D}}(h)=0

. The approximation error is still zero regardless.

C(\mathcal{X})

can approximate many interesting function classes. We can frame this with the following definition from metric topology:

Definition 10.5.

Let

\mathcal{G}\subseteq\mathcal{F}

for some metric space

\mathcal{F}

. We say that $\mathcal{G}$ is dense in $\mathcal{F}$ with respect to the metric

\rho

if, for every

f\in\mathcal{F}

\inf_{g\in\mathcal{G}}\rho(g,f)=0

That is, for every

f\in\mathcal{F}

that isn’t in

\mathcal{G}

, you need to be able to get arbitrarily close to

f

with points in

\mathcal{G}

. A canonical example is that the set of rational numbers is dense in the set of real numbers.

Proposition 10.6.

Suppose that $\mathcal{H}$ is dense in $\mathcal{F}$ with respect to $\lVert\cdot\rVert_{\infty}$ , and use loss $\ell(h,(x,y))=l_{y}(h(x))$ with finite $\operatorname*{\mathbb{E}}_{y\sim\mathcal{D}_{y}}\lVert l_{y}\rVert_{\mathrm{% Lip}}$ . Then $\inf_{h\in\mathcal{H}}L_{\mathcal{D}}(h)=\inf_{f\in\mathcal{F}}L_{\mathcal{D}}% (f)$ .

Proof.

Let

M=\operatorname*{\mathbb{E}}_{y\sim\mathcal{D}_{y}}\lVert l_{y}\rVert_{\mathrm% {Lip}}<\infty

. Choose

(f_{1},f_{2},\dots)

to be a sequence in

\mathcal{F}

such that

L_{\mathcal{D}}(f_{i})\to\inf_{f\in\mathcal{F}}L_{\mathcal{D}}(f)

. For each

f_{i}

, choose

h_{i}\in\mathcal{H}

such that

\lVert f_{i}-h_{i}\rVert_{\infty}\leq{1}/{i}

, which is possible because

\mathcal{H}

is dense in

\mathcal{F}

. Then, by proposition 10.3,

\lvert L_{\mathcal{D}}(h_{i})-L_{\mathcal{D}}(f_{i})\rvert\leq M\lVert h_{i}-f% _{i}\rVert_{\infty}\leq\frac{M}{i}\to 0

, and thus

(L_{\mathcal{D}}(h_{i}))

converges to the same point as

(L_{\mathcal{D}}(f_{i}))

. ∎

10.2 Universal Approximators

Definition 10.7.

We call a hypothesis class

\mathcal{H}

²²2There are many variants of universality (see e.g. [SFL11]); this is a reasonable baseline that’s essentially what they call

c

-universal. of functions

\mathcal{X}\to\mathbb{R}

universal if

\mathcal{H}\cap C(\mathcal{X})

is dense in

C(\mathcal{X})

with respect to

\lVert\cdot\rVert_{\infty}

The following property is known as separating compact sets. It establishes that thresholding functions in a universal hypothesis class can shatter any set, so that

\operatorname{VCdim}(\operatorname{sgn}\circ\mathcal{H})=\infty

. It also implies that the Rademacher complexity is infinite.

Proposition 10.8.

Let

V,W\subset\mathcal{X}

be disjoint compact sets,³³3Finite sets are compact. and let

\mathcal{H}

be universal. Choose any

a>0

. Then there exists an

h\in\mathcal{H}

such that

h(x)>a

for all

x\in V

, and

h(x)<-a

for all

x\in W

Proof.

If either set is empty, the result is trivial. Otherwise, define $\operatorname{\rho}_{V}(x)=\min_{v\in V}\operatorname{\rho}(x,v)$ , and likewise $\operatorname{\rho}_{W}$ . Since the sets are compact, we can use just $\min$ instead of $\inf$ , and they’ll still be well-defined continuous functions in $C(\mathcal{X})$ . Since the sets are compact and disjoint, if $\operatorname{\rho}_{V}(x)=0$ then $\operatorname{\rho}_{W}(x)>0$ , and vice versa. Thus the following $g$ is well-defined and continuous:

g(x)=2a\,\frac{\operatorname{\rho}_{W}(x)-\operatorname{\rho}_{V}(x)}{% \operatorname{\rho}_{W}(x)+\operatorname{\rho}_{V}(x)}.

x\in V

, then

\operatorname{\rho}_{V}(x)=0

, and so

g(x)=2a

for

x\in V

. Likewise,

g(x)=-2a

for

x\in W

. Thus, any

h\in\mathcal{H}

with

\lVert h-g\rVert_{\infty}<a

will satisfy the property we want. Since

g

is continuous and

\mathcal{H}

is dense in

C(\mathcal{X})

, such an

h

must exist. ∎

This result implies that, at least for binary classifiers, it’s impossible to PAC-learn a universal $\mathcal{H}$ . Depending on the $\mathcal{H}$ , though, we may be able to nonuniformly learn it with SRM or similar algorithms. If we use a decomposition $\mathcal{H}=\mathcal{H}_{1}\cup\mathcal{H}_{2}\cup\cdots$ for $\mathcal{H}_{1}\subset\mathcal{H}_{2}\subset\cdots$ , then even if the approximation error in all of $\mathcal{H}$ is zero, the approximation error in $\mathcal{H}_{k}$ might not be. As we consider $\mathcal{H}_{k}$ for increasing $k$ , we trade off higher estimation error for lower approximation error.

There might be some particular $\mathcal{H}_{k}$ where we can achieve zero approximation error (if there’s some $h\in\mathcal{H}$ achieving the minimal loss, ⁴⁴4Well-specified doesn’t imply realizable; you might have $\inf_{h\in\mathcal{H}}L_{\mathcal{D}}(h)>0$ . also called the well-specified setting).

Even when the approximation error of

\mathcal{H}

is zero, though, we may only have the approximation error of

\mathcal{H}_{k}

going to zero as

k

increases, without ever reaching it for any

k

. (This is called a misspecified setting.) This would be true e.g. in example 10.4 with

\mathcal{H}_{k}=\{f:\lVert f\rVert_{\mathrm{Lip}}\leq k\}

and an

\mathcal{D}_{x}

with positive density on

[0,\varepsilon]

10.3 Universal approximation of neural networks

As you may have heard before (probably invoked in somewhat mystical ways), classes of neural networks are universal.

A feedforward neural network (or multilayer perceptron, MLP) is a function defined hierarchically as

f(x)=f^{(D)}(x)\qquad f^{(k)}(x)=\sigma_{k}(W_{k}f^{(k-1)}(x)+b_{k})\qquad f^{% (0)}(x)=x,

where

W_{k}\in\mathbb{R}^{d_{k}^{\prime}\times d_{k-1}}

b_{k}\in\mathbb{R}^{d_{k}^{\prime}}

, and

\sigma_{k}:\mathbb{R}^{d_{k}^{\prime}}\to\mathbb{R}^{d_{k}}

; usually,

d_{k}=d_{k}^{\prime}

. Typically

\sigma_{D}(z)=z

, while intermediate hidden layers use nonlinear activations. Many common choices are componentwise, such as

\operatorname{ReLU}(z)=\max\{z,0\}

\tanh

, or

\operatorname{sigmoid}(z)=\frac{1}{1+\exp(-z)}

. Other choices include

\operatorname{softmax}(z)=(\exp(z_{j}))_{j}/\sum_{j}\exp(z_{j})

, max pooling, attention operators, and so on.

On A3, you bounded the Rademacher complexity for some such networks, with some assumptions on

\sigma_{k}

{\mathcal{D}}

, bounds on

W_{k}

, and that

b_{k}=0

. (There are [slightly] better bounds than this one; we’ll talk about this a bit soon.) Your bound didn’t explicitly depend on the number of parameters, just on their norms.

It’s worth noting now that neural networks are usually trained via stochastic gradient descent, but this non-convex optimization can be difficult: in general, it’s NP-hard, even to optimize a single ReLU unit with square loss ([GKM+21]). We’ll talk more about optimization soon.

10.3.1 Constructive proofs

The following result is easy to understand, and extremely simple, but is indicative of universal approximation results in general.

Theorem 10.9.

Let $g:[0,1]\to\mathbb{R}$ be $M$ -Lipschitz. For any $\varepsilon>0$ , there exists a network $f$ such that $\lVert f-g\rVert_{\infty}\leq\varepsilon$ , where the network has one hidden layer with ReLU activations of width $N=\lceil M/\varepsilon\rceil$ , and one linear output unit.

Proof.

First off, if

M=0

, then we can indeed do it with a hidden layer of width zero: the linear output unit just outputs the constant

g(0)

. Otherwise, we know

M>0

We’re going to construct a piecewise-linear approximation $f$ to the function $g$ . To do this, it’ll be simplest if we extend $g$ slightly past its domain $[0,1]$ : let $g^{\prime}:[0,\infty)\to\mathbb{R}$ be $g^{\prime}(t)=\begin{cases}g(t)&\text{if }t\in[0,1]\\ g(1)&\text{if }t\geq 1\end{cases}$ . We have $\lVert g^{\prime}\rVert_{\mathrm{Lip}}=\lVert g\rVert_{\mathrm{Lip}}$ .

We’ll make

f(b_{i})=g^{\prime}(b_{i})

for each

b_{i}=\frac{i\varepsilon}{M}

, where

i\in\{0,\dots,N\}

: ⁵⁵5

b_{0}=0,\qquad b_{1}=\frac{\varepsilon}{M},\quad\cdots,\quad b_{N-1}=\left(% \left\lceil\frac{M}{\varepsilon}\right\rceil-1\right)\frac{\varepsilon}{M}<1,% \qquad b_{N}=\left\lceil\frac{M}{\varepsilon}\right\rceil\frac{\varepsilon}{M}% \geq 1.

We can make our piecewise-linear approximation if we start the function at

f(0)=g^{\prime}(0)

and then have a slope on each

[b_{i},b_{i+1})

m_{i}=\frac{g^{\prime}(b_{i+1})-g^{\prime}(b_{i})}{b_{i+1}-b_{i}}=\frac{M}{% \varepsilon}\bigl{(}g^{\prime}(b_{i+1})-g^{\prime}(b_{i})\bigr{)}.

We can get that with the desired architecture by letting

m_{-1}=0

and using simply

f(x)=g(0)+\sum_{i=0}^{N-1}\left(m_{i}-m_{i-1}\right)\operatorname{ReLU}\left(x% -b_{i}\right),

i.e. the hidden layer has each neuron with weight

1

and bias

-b_{i}

, and the weights to the single output neuron are

m_{i}-m_{i-1}

with bias

g(0)

How good of an approximation is this $f$ ? Well, $g^{\prime}$ is $M$ -Lipschitz, and since $f$ is piecewise-linear its Lipschitz constant is the max of the slope of any of its pieces:

\lVert f\rVert_{\mathrm{Lip}}=\max_{i}\frac{\lvert g^{\prime}(b_{i+1})-g^{% \prime}(b_{i})\rvert}{b_{i+1}-b_{i}}\leq M.

Thus

\lVert f-g^{\prime}\rVert_{\mathrm{Lip}}\leq 2M

. We also know that

f-g^{\prime}

equals

0

on each

b_{i}

, and any input in

[0,1]

will have a

b_{i}

no more than

\frac{\varepsilon}{2M}

away. Thus, as in chapter 4,

\lVert f-g\rVert_{\infty}=\sup_{x\in[0,1]}\big{\lvert}(f-g)(x)\big{\rvert}\leq 2% M\cdot\frac{\varepsilon}{2M}=\varepsilon.\qed

Here’s a similar result in

\mathbb{R}^{d}

Theorem 10.10.

Let $g:[0,1]^{d}\to\mathbb{R}$ be continuous. For any $\varepsilon>0$ , ⁶⁶6 $\delta$ exists for any $\varepsilon$ , since continuous functions on compact domains are uniformly continuous, and $\lVert\cdot\rVert_{2}$ and $\lVert\cdot\rVert_{\infty}$ are equivalent. choose $\delta>0$ such that $\lVert x-x^{\prime}\rVert_{\infty}\leq\delta$ implies $\lvert g(x)-g(x^{\prime})\rvert\leq\varepsilon$ . Then there is a three-layer ReLU network $f$ with $\operatorname{\mathcal{O}}\left(\frac{1}{\delta^{d}}\right)$ ReLU nodes satisfying $\int_{[0,1]^{d}}\lvert f(x)-g(x)\rvert\,\mathrm{d}x\leq 2\varepsilon$ .

Proof (sketch).

Approximate the continuous

g

by a piecewise-constant

h

, with pieces given by hyper-rectangles. Construct a two-layer ReLU net to (approximately) check whether the input

x

is in each hyper-rectangle. Put those networks side-by-side as the first two layers of

f

, so that the second hidden layer is (approximately) an indicator vector of which hyper-rectangle

x

is in. Use a linear readout layer to set any value on those pieces. For details, see Theorem 2.1 of [TEL21]. ∎

Notice the curse of dimensionality: the size of the network depends exponentially on the dimension, which for deep learning is typically at least hundreds, perhaps millions or more. This isn’t just a proof artifact; it’s necessary to approximate arbitrary continuous functions. The construction also needs really large weights, and has a really bad Lipschitz constant; it also only gives an $L_{1}$ approximation bound, not sup-norm like before.

10.3.2 Non-constructive bound via Stone-Weierstrass

We can actually get a sup-norm bound with only one hidden layer a different way, using the celebrated Stone-Weierstrass approximation theorem from analysis.

Theorem 10.11 (Stone-Weierstrass, special case).

Let $\mathcal{X}$ be a compact metric ⁷⁷7More generally, $\mathcal{X}$ can be compact Hausdorff. space. Suppose $\mathcal{F}$ is a set of functions from $\mathcal{X}\to\mathbb{R}$ such that:

•

Each $f\in\mathcal{F}$ is continuous: $\mathcal{F}\subseteq C(\mathcal{X})$ .
•
For each $x\in\mathcal{X}$ , there is at least one $f\in\mathcal{F}$ with $f(x)\neq 0$ .
•
For all $f,g\in\mathcal{F}$ and $\alpha\in\mathbb{R}$ , $\alpha f+g\in\mathcal{F}$ and $fg=(x\mapsto f(x)g(x))\in\mathcal{F}$ . ⁸⁸8 $\mathcal{F}$ is an algebra.
•

For each $x\neq x^{\prime}\in\mathcal{X}$ , there is at least one $f\in\mathcal{F}$ with $f(x)\neq f(x^{\prime})$ . ⁹⁹9 $\mathcal{F}$ separates points.

Then $\mathcal{F}$ is dense in $C(\mathcal{X})$ with respect to $\lVert\cdot\rVert_{\infty}$ .

You may have heard of the Weierstrass theorem, which shows that polynomial functions are dense in

C([a,b])

; this is a generalization. The rough idea of the proof is to first show that the closure of

\mathcal{F}

is also closed under maxima and minima, use point separation to interpolate a target function at each two points, then use maxima and minima to build those local interpolants into a global approximation.

Proposition 10.12.

$\mathcal{F}_{\exp}$ is dense in $C(\mathcal{X})$ , where $\mathcal{X}\subset\mathbb{R}^{d}$ is compact and

\mathcal{F}_{\exp}=\left\{x\mapsto\sum_{i=1}^{m}a_{i}\exp(\langle w_{i},x% \rangle):m\geq 1;w_{1},\dots,w_{m}\in\mathbb{R}^{d};a_{1},\dots,a_{m}\in% \mathbb{R}\right\}.

Notice that

\mathcal{F}_{\exp}

is a set of one-hidden-layer neural networks with exponential hidden activations and unbounded width.

Proof.

We just need to show it satisfies the conditions of Stone-Weierstrass. The first two are clear. For $f(x)=\sum_{i=1}^{m}a_{i}\exp(\langle w_{i},x\rangle)$ and $g(x)=\sum_{i=1}^{m^{\prime}}a_{i}^{\prime}\exp(\langle w_{i}^{\prime},x\rangle)$ , we have

	$\displaystyle\alpha f+g=\left(x\mapsto\sum_{i=1}^{m}(\alpha a_{i})\exp(\langle w% _{i},x\rangle)+\sum_{i=1}^{m^{\prime}}a_{i}^{\prime}\exp(\langle w_{i}^{\prime% },x\rangle)\right)\in\mathcal{F}_{\exp}$
	$\displaystyle fg=\left(x\mapsto\sum_{i=1}^{m}\sum_{j=1}^{m^{\prime}}a_{i}a_{j}% ^{\prime}\exp(\langle w_{i}+w^{\prime}_{j},x\rangle)\right)\in\mathcal{F}_{% \exp}.$

To show

\mathcal{F}_{\exp}

separates

x_{1}

and

x_{2}

, consider

f(x)=\exp(\langle x_{1}-x_{2},x\rangle)

, so that

\displaystyle\frac{f(x_{1})}{f(x_{2})}=\frac{\exp\bigl{(}\lVert x_{1}\rVert^{2% }-\langle x_{2},x_{1}\rangle\bigr{)}}{\exp\bigl{(}\langle x_{1},x_{2}\rangle-% \lVert x_{2}\rVert^{2}\bigr{)}}=\exp\left(\lVert x_{1}\rVert^{2}-2\langle x_{1% },x_{2}\rangle+\lVert x_{2}\rVert^{2}\right)=\exp\left(\lVert x_{1}-x_{2}% \rVert^{2}\right),

which is one iff

x_{1}=x_{2}

; thus if

x_{1}\neq x_{2}

f(x_{1})\neq f(x_{2})

. ∎

Proposition 10.13 (([HSW89])).

Let

\mathcal{X}\subset\mathbb{R}^{d}

be compact, and

\sigma:\mathbb{R}\to\mathbb{R}

be continuous with

\lim_{z\to-\infty}\sigma(z)=0

\lim_{z\to\infty}\sigma(z)=1

. Then

\mathcal{F}_{\sigma}

is dense in

C(\mathcal{X})

, where

\mathcal{F}_{\sigma}

is defined as

\mathcal{F}_{\sigma}=\left\{x\mapsto\sum_{i=1}^{m}a_{i}\sigma(\langle w_{i},x% \rangle+b_{i}):m\geq 1;w_{i}\in\mathbb{R}^{d};a_{i},b_{i}\in\mathbb{R}\right\}.

Proof (sketch).

For any continuous target

g

, first find an

f_{0}\in\mathcal{F}_{\exp}

such that

\lVert f_{0}-g\rVert_{\infty}\leq\varepsilon/2

, possible by proposition 10.12. Now, find some coefficients such that

\exp(z)\approx\sum_{j}c_{j}\sigma(t_{j}z+b_{j})

is sufficiently accurate so that replacing each

\exp(\langle w_{i},x\rangle)

f_{0}

\sum_{j}c_{j}\sigma(t_{j}\langle w_{i},x\rangle+b_{j})

, we find an

f\in\mathcal{F}_{\sigma}

such that

\lVert f-f_{0}\rVert_{\infty}\leq\varepsilon/2

. ∎

More generally, this general approach works if

\sigma

is anything (locally bounded and piecewise continuous) that’s not (almost everywhere) a polynomial ([LLP+93]). (A shallow network with fixed-degree polynomial activations is itself a polynomial of fixed degree.) These are for shallow, wide networks, but if you use a deep, narrow network you can get away even with (non-affine) polynomial activations ([KL20]).

There are also a variety of other results. Maybe most important is an infinite-width construction of [BAR93]; also see Section 3 of [TEL21] or Section 9.3 of [BAC25].

10.4 Circuit complexity

We won’t go into depth on this perspective, but it’s definitely worth knowing it exists. [SB14], Chapter 20 overview the general basic results, but the standard classic text is [PAR94]. The short version:

•

Two-layer networks with threshold activations can represent all functions from $\{\pm 1\}^{d}\to\{\pm 1\}$ . Since computers always represent things as binary strings, that’s pretty powerful.
•
But, it takes exponential width to do that.
•
But, for any Boolean function that can be computed with maximal runtime $T$ , there exists a network of size $\operatorname{\mathcal{O}}(T^{2})$ that implements that function.

There’s also recent work on relating circuit complexity to ResNets, Transformers, and chain of thought ([MS23, CHI25, SHT24, AHR+25, JAC26]).

10.5 Interpretation

“Neural networks can do anything!!”

(You don’t hear “decision trees can do anything!!” as often, but it’s just as true….)

These results mean that, for any (continuous) function (on a compact domain) that we’d like to approximate, there is some neural net that can closely approximate that behaviour. Continuous functions also aren’t a huge limit, as in example 10.4. So, there is some neural network that can approximate “what’s the next bit in the response of a very smart human to a Unicode string of length at most 128,000 bytes.” But we can only guarantee that there’s such a network that’s very large (in parameter count and also weight norm). There’s also a really really big decision tree that can do that.

So, does ERM in a large enough hypothesis class, or SRM, or whatever other learning algorithm, necessarily generalize? Maybe not.

Also, for neural networks ERM is NP-hard; does gradient descent approximate it well? Maybe not.

But, are these constructions with enormous norms indicative of the actual norm required for functions we care about? Maybe not.

One way to help answer these questions is to characterize what kinds of functions have large norms. This is mostly beyond the scope of this course, but the typical traditional scheme is based on functions in Sobolev classes; [BAC25] has a bunch of material on this. There’s also recent work on, say, constructing Transformers to do some particular task, as an existence proof of approximation for that task (rather than universally).