Deep Learning and Approximation theory 2023

Nadav Dym

September 21, 2023

2

Preface
These are lecture notes from the course ‘Deep Learning and Approximation Theory’ which I taught in the
Technion in the spring of 2023. The course is intended for graduate and advanced undergraduate students.
Its goal is to introduce students to modern research which focuses on understanding the approximation power
of neural networks. The course is divided into two main chapters: the first chapter deals with approximation
results pertaining to fully connected neural networks. The second chapter discusses approximation results
for neural network architectures which are invariant to permutations or other group actions.
I am making these notes public with the hope that they will be of interest to people outside the Technion.
However, note that wile I did some minimal proof reading of these notes, they have not undergone very serious
editing and will tend to contain more errors than, say, a textbook. Use at your own risk... Please do let me
know via email of any errors which you find.
Chapter 0

Some math preliminaries

Lesson 1
The first goal of this lesson is to show some fundamental facts about approximation: basically that poly-
nomials are dense in the space of continuous functions, while polynomials of finite degrees are not. The
secondary goal is to clarify some of the math background necessary for this course, and help close the gaps
to those who need to. For additional reading see [Simmons, 1963].

Definition 0.1. Let X be a vector space over R. A norm is a function ∥ · ∥ : X → R satisfying

1. Positivity: For every x ∈ X, ∥x∥ ≥ 0, with equality if and only if x = 0.

2. Triangle inequality: ∥x + y∥ ≤ ∥x∥ + ∥y∥ for every x, y ∈ X.

3. Homogeneity: ∥λx∥ = |λ|∥x∥ for all x ∈ X and λ ∈ R.

Example 0.2. In Rn , we have the norms

pPn
1. the standard 2 norm ∥x∥2 = 2
i=1 (xi ) .
Pn
2. the 1 norm ∥x∥1 = i=1 |xi |
Pn 1/p
3. In general, for p ≥ 1 we can define the norm ∥x∥p = ( i=1 |xi |p )

4. The ∞ norm ∥x∥∞ = max1≤i≤n |xi |.

We also say that (X, ∥ · ∥) is a normed space. Later today we will use the reverse triangle inequality:

|∥x∥ − ∥y∥| ≤ ∥x − y∥

which follows from the triangle inequality (check).

Definition 0.3. Let X be a non-empty set. A metric d is a function d : X × X → R which satisfies the
following conditions

1. Positivity: for every x, y ∈ X, d(x, y) ≥ 0 with equality if and only if x = y.

2. Symmetry: for every x, y ∈ X, d(x, y) = d(y, x).

3. Triangle inequality: for every x, y, z ∈ X

d(x, z) ≤ d(x, y) + d(y, z).

We also say that (X, d) is a metric space.

3
4 CHAPTER 0. SOME MATH PRELIMINARIES

Example 0.4. 1. For any non-empty set X, we can define the ‘discrete metric’ d(x, x) = 0 and d(x, y) = 1
if x ̸= y.

2. On X = R we have the metric d(x, y) = |x − y|.

pPn
3. On X = Rn we have the metric d2 (x, y) = ∥x − y∥2 = i=1 (xi − yi )2 , and more generally dp (x, y) =
∥x − y∥p

4. If (X, d) is a metric space, and Y ⊆ X, then (Y, d) is a metric space.

As examples 2-3 suggest, norms induce metrics:

Proposition 0.5. If (X, ∥ · ∥) is a normed space then d(x, y) = ∥x − y∥ is a metric on X.

Problem 0.6. The discrete metric on R is not induced from a norm. Explain why.

Definition 0.7 (Convergence). Let (X, d) be a metric space. We say that a sequence xn , n = 1, 2, . . . of
elements in X converges to x if
d(xn , x) → 0

Definition 0.8 (Cauchy sequences). Let (X, d) be a metric space. We say that a sequence xn , n = 1, 2, . . . of
elements in X is Cauchy if for every ϵ > 0 there exists N such that for all n, m ≥ N we have d(xn , xm ) < ϵ.

A converging sequence is always a Cauchy sequence: If xn → x then for all ϵ > 0 there exists N such
that for all n > N we have d(xn , x) < ϵ/2, and so for n, m > N we use the triangle inequality to obtain

d(xn , xm ) ≤ d(xn , x) + d(xm , x) < ϵ/2 + ϵ/2 = ϵ

A metric space is complete if ever Cauchy sequence has a limit. For example Rd and closed subsets of Rd
are complete, while [0, 1) or the rational numbers are not complete.

Definition 0.9. Let (X, d) be a metric space. For x0 ∈ X and r > 0, the open ball Br (x0 ) is the set

Br (x0 ) = {x ∈ X| d(x, x0 ) < r}

Definition 0.10 (Open sets). Let (X, d) be a metric space. We say that U ⊆ X is an open set if for all
x ∈ U there exists some r > 0 such that Br (x) ⊆ U .

Example 0.11. 1. An open ball is an open set.

2. In Rd , the hyper-cube (0, 1)d is an open set.

Definition 0.12 (Closed sets). Let (X, d) be a metric space. We say that a set C ⊆ X is closed if for every
sequence xn ∈ C which converges to a point x ∈ X, we have that x ∈ C.

Problem 0.13. Show that a set C ⊆ X is closed if and only if its complement is open.

Definition 0.14 (Compactness). Let (X, d) be a metric space. We say that a set K ⊆ X is compact if
every sequence xn ⊆ K has a subsequence which converges to a limit in K.

Example 0.15. The set (0, 1] is not a compact subset of R because the sequence 1/n, and all its subsequences,
converge to a point which is not in the set. The set [0, 1] is compact. In general in Rn any closed and bounded
set is compact.

Definition 0.16 (Continuity). Let (X, dX ) and (Y, dY ) be metric spaces. We say that a function f : X → Y
is continuous if for every sequence xn → x in X, we have that f (xn ) → f (x) in Y .

Proposition 0.17. Let (X, dX ) and (Y, dY ) be metric spaces. If f : X → Y is continuous and K ⊆ X is
compact, then f (K) is compact.
 5

Proof. We need to show that f (K) is compact. Let yn be a sequence in f (K). There exist xn ∈ K such that
f (xn ) = yn . By compactness of K, the sequence xn has a subsequence xnk which converges to some x ∈ K.
By continuity
ynk = f (xnk ) → f (x) ∈ f (K)
and so we showed that yn has a converging subsequence, and thus f (K) is compact.
Corollary 0.18. Let (X, d) be a metric space. K ⊆ X compact, and f : X → R a continuous function.
Then f obtains a maximum and minimum of K.
Proof. By the previous proposition f (K) is a compact subset of R and so it is bounded: there exists some
M > 0 such that |f (x)| < M . It follows that S = supx∈K f (x) is finite. There exists a sequence xn ⊆ K
such that f (xn ) → S. By compactness xn has a subsequence which converges to x ∈ K and by continuity
f (x) = S so x is a maximum. The same argument can be used to show the existence of a minimum.
Let V be a vector space over the reals and K ⊆ V be a subset. Denote

C(K) = {f : K → R| f is continuous}.

If we additionally assume that K is compact, we can define a norm on C(K) by

∥f ∥ = max |f (x)|
x∈K

by the previous corollary this is well defined. We can verify that this is indeed a norm. Positivity and
homogeneity are rather obvious. As for the triangle inequality: For f, g ∈ C(K) and for all x ∈ K

|f (x) + g(x)| ≤ |f (x)| + |g(x)| ≤ ∥f ∥ + ∥g∥

and since this inequality is true for all x it is also true for the x which maximize |f (x) + g(x)|.
Problem 0.19. Give an example of f, g for which (i) the inequality is strict and (ii) the inequality is not
strict.
The norm on C(K) induces the metric ∥f − g∥ = maxx∈K |f (x) − g(x)| on functions. This metric space
will be central in this course. We will consider questions such as: given a subset of function P ⊆ C(K), can
any function f ∈ C(K) be approximated by functions in P ? That is, can we, for every given ϵ > 0 find some
p ∈ P such that
∥f − p∥ = max |f (x) − p(x)| < ϵ
x∈K

or equivalently, can we find a sequence pn ⊆ P such that ∥pn − f ∥ → 0? When this happens we say that pn
uniformly converges to f , and we say that P is dense in C(K).
We state Weierstrass’s theorem
Theorem 0.20 (Weierstrass). Every continuous function f : [a, b] → R can be approximated uniformly by
polynomials.
we will later discuss this theorem’s generalization, the Stone-Weierstrass theorem. For now, we want to
show that we cannot approximate a continuous function by polynomials of degree ≤ D. Denote

RD [x] = { polynomials of degree ≤ D}

This is a vector space of dimension D + 1, with the norm ∥f ∥C[a,b]] = maxx∈[a,b] |f (x)|. We will show that
all finite dimensional normed spaces are ‘topologically equivalent’ and through this show that they cannot
approximate all functions. In contrast, note that the space of all polynomials R[x] is infinite dimensional.
Definition 0.21. Let (X, ∥ · ∥X ) and (Y, ∥ · ∥Y ) be normed spaces over R. We say that a map T : X → Y
is an isomorphism of normed spaces if T is linear, onto, and there exists 0 < m < M such that

m∥x∥X ≤ ∥T x∥Y ≤ M ∥x∥X

6 CHAPTER 0. SOME MATH PRELIMINARIES

Problem 0.22. Show that the identity map Ix = x is a isomorphism between (Rn , ∥ · ∥∞ ) and (Rn , ∥ · ∥1 ).
What are the constants? Can you do the same when ∞ is replaced with 2?
Solution. We have that
n
X
∥x∥1 = |xi | ≥ max |xi | = ∥x∥∞ ,
i
i=1
and on the other hand
n
X n
X
∥x∥1 = |xi | ≤ |x|∞ = n|x|∞ ,
i=1 i=1
and so we obtained
m∥x∥∞ ≤ ∥x∥1 ≤ M ∥x∥∞ .
with m = 1 and M = n. Note that these constants aren’t unique: we can make M larger of m smaller. They
are however the optimal constants one can choose, as can be seen by taking
x = [1, 0, 0, . . . , 0] and x = [1, 1, . . . , 1]

We say that (X, ∥ · ∥X ) and (Y, ∥ · ∥Y ) are isomorphic if there exists an isomorphism between them.
As it turns out, there is always an isomorphism between normed spaces of the same finite dimension.
Theorem 0.23. Let (V, ∥ · ∥) be a vector space over R of dimension n. Then there is a isomorphism between
V and (Rn , ∥ · ∥2 ).
Proof. Let v1 , . . . , vn be a basis for V , and e1 , . . . , en denote the standard basis for Rn . We define a linear
map T : Rn → V by
Xn
T (x) = x i vi .
i=1
The map T is linear and onto. It is also one-to-one, for T (x) = 0 implies that all xi are zero. It remains to
show that the norm ∥T x∥ can be bounded from above and below by ∥x∥ up to some constant. Define
v
u n
uX
M =t ∥vi ∥2
i=1

we have, using the properties of the norm and Cauchy-Schwarz, that

v v
n
X n
X n
X
u n u n
uX uX
∥T x∥ = ∥ x i vi ∥ ≤ ∥xi vi ∥ ≤ |xi |∥vi ∥ ≤ t 2
|xi | t ∥vi ∥2 = M ∥x∥2
i=1 i=1 i=1 i=1 i=1

this gives us the first inequality we need. We can also use it to get the other direction: the inequality we
just proved shows that the map
N : Rn → R, N (x) = ∥T x∥
is continuous. For if xn → x then, using the reverse triangle inequality:
|N (xn ) − N (x)| = |∥T xn ∥ − ∥T x∥| ≤ ∥T (xn − x)∥ ≤ M ∥xn − x∥2 → 0
The continuous function N obtains a minimum on the compact set S1 = {x ∈ Rn | ∥x∥2 = 1}. This minimum
is clearly non-negative. Moreover, we saw that N is injective and so doesn’t assume zero values on S1 , which
then implies that since ∥ · ∥ is a norm, N (x) = ∥T x∥ is never zero on S1 , and so there is a positive minimum
m > 0. It follows that for all x ∈ S1
∥T x∥ ≥ m = m∥x∥2
this inequality holds for all x. If x = 0 then both sides are zero. Otherwise we have
 
x
∥T x∥ = ∥x∥2 · ∥T ∥ ≥ ∥x∥2 · m
∥x∥2
 7

Corollary 0.24. Every real finite dimensional normed spaces is complete.

sketch of proof. Let (V, ·) be a real normed space of dimension n and let T : V → Rn be an isomorphism.
One can verify that vn ⊆ V converges to v ∈ V if and only if T vn converges to T v, and similarly vn is a
Cauchy sequence if and only if T vn is a Cauchy sequence. Since vn is Cauchy, so is T vn , and since Rn is
complete, T vn has a limit x, and so vn has a limit T −1 x.

Corollary 0.25. Let (V, ∥ · ∥) be a real normed vector space, and P ⊆ V is a finite dimensional subspace,
and assume that pn ⊆ P converges to some limit f ∈ V . Then f ∈ P .

Proof. Since pn → f the sequence pn is a Cauchy sequence in P and so it has a limit in P . Thus f is in
P.

As mentioned above, this corollary shows in particular that polynomials of degree ≤ D cannot approxi-
mate any continuous functions which are not polynomials of degree ≤ D.

0.0.1 The Stone Weierstrass Theorem

In the previous section we saw that polynomials are dense in C[a, b]. Now we will discuss the Stone-
Weierstrass theorem which gives an anologous result for C(K) where K is any compact metric space (it also
hold for compact Hausdorf spaces but we do not discuss non-metric topologies in this course). We start by
defining multivariate polynomials:
A monomial function m : Rn → R is a function of the form

x = (x1 , . . . , xn ) 7→ xα α2 αn
1 · x2 . . . · xn
1

where α = (α1 , . . . , αn ) ∈ Nn0 (here N0 = N ∪ {0}). We use the shortened notation xα to described this
function. The degree of a monomial is the sum of all indices of α which is denoted by |α| = ∥α∥1 . A
polynomial function p : Rn → R is a finite linear combination of monomials. The degree of a polynomials is
the maximal degree of a monomial in the linear combination which has a non-zero coefficient.
The Stone-Weierstrass theorem shows that multi-variate polynomials are dense in C(K) for compact
K ⊆ Rn . In fact, it applies to a wider family of functions called sub-algebras:

Definition 0.26. Let X be a metric space. We say that a subset A ⊆ C(X) is a subalgebra of C(X) if for
all f, g ∈ A and c ∈ R

1. f + g ∈ A

2. cf ∈ A

3. f · g ∈ A

Example 0.27. 1. Polynomials p : R → R are a sub-algebra.

2. Polynomials of degree ≤ D are not a sub-algebra.

3. Multi-variate polynomials p : Rd → R are a sub-algebra.

4. The trigonometric polynomials: functions which are finite linear combinations of the constant function
1, and the functions cos(nx) and sin(mx) for n, m ∈ N, are a sub-algebra. This can be seen using the
trigonometric identities

2 sin(x) sin(y) = cos(x − y) − cos(x + y)

2 sin(x) cos(y) = sin(x + y) + sin(x − y)
2 cos(x) cos(y) = cos(x − y) + cos(x + y)
8 CHAPTER 0. SOME MATH PRELIMINARIES

5. Linear combinations of functions fw : Rn → R of the form

fw (x) = e⟨w,x⟩

are a subalgebra.

Definition 0.28. An algebra A ⊆ C(K) separates points in K, if for any points x, y ∈ K with x ̸= y there
exists some f ∈ A such that f (x) ̸= f (y).
Theorem 0.29 (Stone-Weierstrass). Let K be a compact metric space, and let A be an algebra which
contains a non-zero constant function and separate points, then A is dense in C(K).
We will not prove this theorem, but we will practice using it.

Problem 0.30. Using the Stone-Weierstrass Theorem, answer the following questions:
1. Show that the univariate polynomials are dense on every closed interval [a, b] (that is, that Weierstrass
follows from Stone Weirstrass)?
2. Are the univariate polynomials dense on all of R?

3. Are the multivariate polynomials dense on any compact subset of Rd ?

4. Are the trigonometric polynomials dense on every compact subset of R?
5. Are functions of the form
N
X
d
R ∋ x 7→ cn e⟨wn ,x⟩
n=1

dense on any compact subset of Rd ?

Chapter 1

Fully Connected Neural Networks

Lesson 2
1.1 Introduction
1.1.1 Supervised Learning
The motivation for most questions discussed in this course come from a supervised learning problem: Let
K ⊆ Rd be a compact set, and f : K → Rℓ a continuous function. We have ‘no access’ to f , except via its
samples f (xi ), i = 1, . . . , N at some points xi , i = 1, . . . , N in K. Our aim is to find a good approximation
for f , by choosing an appropriate hypothesis class of parametric functions

H = {h(x; θ) : K × Rp → Rℓ }

and searching for the best approximation of f by h in terms of the given data, by solving an optimization
problem such as
N
X 2
minp L(θ) = [hθ (xi ) − f (xi )] .
θ∈R
i=1

Typically L(θ) is differentiable (at least at ‘most’ points), and the methods used for searching for the
minimizer of L(θ) are variations of the ‘gradient descent’ method. In its simple form, in gradient descent we
are given an initial guess θ0 for the minimum of L, and we iteratively update our guess for θ by going in the
direction in which L is reduced most:
θt+1 = θt − ∇L(θt ).
Once this procedure is terminated and some final θ∗ is reached, we choose hθ∗ as our approximation of f .
There are several theoretical (and practical) issues that can arise:
1. Optimization Can gradient descent (or a different algorithm) find a solution θ∗ which is a good
approximation of the true minimum?
2. Generalization Will a good approximation of f on the data xi give a good approximation for other
points in K?
3. Approximation Does our hypothesis class H contain a good approximation for f ?
In this course we focus only on the question of approximation. We would like to show that the hypothesis
classes we construct can approximate any continuous function. This property is called ‘universality’. In the
previous chapter we saw some examples of parametric function classes which can approximate all continuous
functions, at the limit where the number of parameters goes to infinity. In practice, we will focus mostly on
hypothesis classes called neural networks, which are popular in modern applications. Our first goal will be
to show that they too, like polynomials, can approximate all continuous functions. But before we do this,
we will start by defining these hypothesis classes:

9
10 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

1.1.2 Neural Network Functions

We refer to functions which are compositions of affine functions and activation functions as neural network
functions. Recall that an affine function h : Rw0 → Rw1 is a function of the form

h(x) = Ax + b, where A ∈ Rw1 ×w0 , x ∈ Rw0 and b ∈ Rw1

An activation function is basically any function σ : R → R. We extend σ to a function from Rw → Rw via

σ(x1 , . . . , xw ) = (σ(x1 ), σ(x2 ), . . . , σ(xw ))

Fixing some activation function σ, and natural numbers w0 , . . . , wL , wL+1 , a Neural Network Function (NNF)
with widths w0 , . . . , wL , wL+1 is defined to be a function h : Rw0 → RwL+1 of the form

hL+1 ◦ σ ◦ hL . . . ◦ σ ◦ h1 where hi : Rwi−1 → Rwi is affine ∀i = 1, . . . , L. (1.1)

Choices of activation function Possibly the most popular choice of activation function today is

σ(x) = ReLU (x) = max(x, 0).

A very popular choices of activation function in the past was the analytic sigmoid function
1
sigmoid(x) = .
1 + e−x
A smooth version of the ReLU can be obtained by considering
x
SiLU (x) = x · sigmoid(x) = .
1 + e−x
Another common option is the hyperbolic tangent

ex − e−x
tanh(x) =
ex + e−x
In the literature discontinuous functions like

1 if x > 0
sign(x) =
−1 if x ≤ 0

are also discussed though they are difficult to work with using gradient descent.

1.1.3 Neural Network Architectures

Neural Network Architectures We define a Neural Network Architecture to be a set of functions which
are all neural network functions with respect to some fixed activation function. Here are some examples

1. Fully connected neural networks Let X = Rw0 be our domain. Let σ : R → R be some function,
which we will call an activation function. Let

⃗ = (w0 , w1 , . . . , wL , wL+1 ) ∈ NL+1

w

for some L ∈ N. For fixed w,

⃗ σ this defines a hypothesis class

⃗ σ) = {h(x) = hL+1 ◦ σ ◦ hL . . . ◦ σ ◦ h1 (x) where hi : Rwi−1 → Rwi is affine ∀i = 1, . . . , L + 1}

FC (w;

The number L is called the depth of the network, and each number wℓ is called the width of the ℓ-th
layer. We usually think of the vector w ⃗ (and the activation function σ ) as hyper-parameters: once
they are fixed, we can use gradient descent to find the parameters which define the affine functions hi .
1.1. INTRODUCTION 11

(a) (b)
Figure 1.1: (a) The directed graph corresponding to the architecture FC(3, 2; 2, 1, σ). (b) The ‘trapezoid
function’ ha,b,c,d .

2. Fully connected neural networks with fixed width When studying the approximation power of
fully connected neural networks we will usually simplify things by assuming that all hidden layer have
the same width. The width vector w ⃗ is then described by four hyper-parameters

w
⃗ (W, L, win , wout ) = (w0 = win , w1 = W, w2 = W, . . . , wL = W, wL+1 = wout )

and accordingly these hyper-parameters define the hypothesis class

FC (W, L; win , wout , σ) = FC (w

⃗ (W, L, win , wout ) ; σ)

3. Convolutional Neural Networks are another example (which we will not discuss in this course) of
functions which are compositions of affine and activation functions. The affine functions are convolu-
tions rather than general linear transformations.

1.1.4 The ‘Neural’ Terminology

The source of terms such as neural networks, and activation functions comes from the origin of neural
networks as an attempt to create learning models which imitate the way the human brain work. For this
reason the neural networks we discuss in this course are sometimes called Artificial Neural Networks, to
differentiate them from the neural networks which compose our brain.
The general idea is that humans process information through a network of neurons which communicate
between themselves through electrical signals. Based on the electrical signals a neuron obtains from its
neighbors, the neuron decides whether to ‘fire’ or not. This decision in turn influences its neighbors etc.
Consider a neural network architecture of the form FC(W, L; win , wout , σ). We can associate with this
function a directed graph (V, E): the vertices in this graph are indexed by
(ℓ)
vi , ℓ = 0, . . . , L and i = 1, . . . , wℓ

Each vertex is called a neuron, and the collection of all vertices with superindex ℓ are called the ℓ-th layer.
The 0-th layer is called the input layer, the last layer is called the output layer, and the intermediate layers
are called ‘hidden layers’.
For a given vertex=neuron vjℓ , the incoming edges in the graph connect the neuron to all neurons in the
previous layer
(ℓ−1)
vi , i = 1 . . . wℓ−1
while the outgoing edges connect vjℓ to all neurons in the next layer
(ℓ+1)
vi , i = 1 . . . wℓ+1
12 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

when ℓ = 0 there are no incoming edges and when ℓ = L is maximal there are no outcoming edges. In
Figure 1.1(a) we visualize the directed graph associated with the architecture FC(W = 3, L = 2; win =
2, wout = 1, σ).
The function in (1.1) can be rewritten as a composition of functions, where we denote the input x ∈ Rw0
by x(0) and then recursively define
   
x(ℓ) = σ hℓ (x(ℓ−1) = σ A(ℓ) x(ℓ−1) + b(ℓ) . (1.2)

The final vector we obtain by this process x(L) is the output of the neural network function defined in (1.1).
Looking at the j-th coordinate of x(ℓ) in (1.2) we obtain
wℓ−1
!
(ℓ)
X (ℓ) (ℓ−1) (ℓ)
xj = σ Ajk xk + bk
k=1

(ℓ) (ℓ)
That is, the neuron vj aggregates the signals it obtains from its neighbors according to weights Ajk (which
are defined per edges) and bℓk (which is defined per vertex), and then decides whether to fire. In this context
the sigmoid and sign activation functions seem more natural. When using the sign function, the neuron
decides to fire (or activate) if the signal it obtained from its neighbors is above a certain threshold. with
sigmoid a smoother approach is taken, where the amount of activation varies continuously with the input.
Of course, in practice we are interested in which functions perform best in terms of learning, irrespective to
how well they resemble our understanding of ‘natural neural networks’.

1.1.5 Universality of Neural Network

Universality theorem We now turn to discuss the approximation power of neural networks. We’d like to
have an analogue of the Weierstrass theorem for polynomials- that is- we’d like to say that for every compact
set K ⊆ Rd , some neural network function space will be dense (with respect to the ‘uniform convergence’
norm defined in the first lesson) in
C(K) = {f : K → R is continuous }
Recall that for a normed vector space C, we say that a subspace P is dense in C if for every f ∈ C and ϵ > 0
there is some p ∈ P such that ∥f − p∥ < ϵ. Equivalently, this means that for every f there is a sequence of
pn ∈ P such that pn → f (that is, ∥f − pn ∥ → 0).
Problem 1.1. Two of the function classes below are not dense in C(K, R). Which are they?
1. The function class [
FC (W, L; win = d, wout = 1, σ)
(W,L)∈N2

with activation function σ(x) = x.

2. The function class [
FC (W, L; win = d, wout = 1, σ)
(W,L)∈N2

with activation function σ(x) = ReLU (x).

3. The function class [
FC (W, L = 1; win = d, wout = 1, σ)
W ∈N

with activation function σ(x) = ReLU (x). These networks are called shallow neural networks.
4. The function class [
FC (W, L = 1; win = d, wout = 1, σ)
W ∈N

with activation function σ(x) = x2 .

1.2. PROOF OF UNIVERSALITY OF SHALLOW NEURAL NETWORKS WITH ANALYTIC ACTIVATIONS13

Solution: The first is not dense as it contains only linear functions. The last is not dense as it contains
only degree two polynomials. The second and third function classes are dense as we will now discuss.
As it turns out, for ReLU activation functions, a single hidden layer is sufficient to obtain universal-
ity(=denseness), as the width is taken to infinity. Which other activation functions have this property?
Clearly this cannot occur for polynomial activation functions of some degree D because then FC (W, L = 1; win , wout , σ)
only contains polynomials p : Rwin → Rwout of degree ≤ D. The space of such polynomials is finite dimen-
sional, and by Corollary 0.25 functions from this space cannot approximate any functions from outside that
space.
Remarkably, this is the only restriction on the activation function. The well known universality theorem
for neural networks (perhaps the most well known result in neural network theory...) states
Theorem 1.2 ([Pinkus, 1999]). Let K ⊆ Rd be a compact set, and σ : R → R be a continuous function
which is not a polynomial. Then
[
FC (W, L = 1; win = d, wout = 1, σ)
W ∈N

is dense in C(K).
Due to this theorem, neural networks are often called ‘universal approximators’. That is: for any given
unknown continuous f , there is hope to approximate it using a neural network hypothesis class, as such
hypothesis classes can approximate any continuous function.
A standard reference for the theorem and it historical development, is in the review article by Allan Pinkus
[Pinkus, 1999], (who by the way is a retired professor from our very own Technion Math department). In
this course we will not present the full proof, but we will use parts of his proof to prove Theorem 1.2 for
anlaytic non-polynomial activations. Later on, we will present a different proof for ReLU activations, where
we will allow the depth of the network to grow and not only the width.

1.2 Proof of Universality of Shallow Neural Networks with ana-

lytic activations
Our goal in this section is to prove Theorem 1.2. We begin with some preliminaries.
First, let us reformulate out goal. In general, we would like to prove denseness of functions of the form
h2 ◦ σ ◦ h1 where h1 : Rd → RW and h2 : RW → R are affine and W can be arbitrarily large. In the proof
we will always only consider h2 which are linear, that is h2 (0) = 0. We can then write
y = σ ◦ h1 (x) = σ(Ax + b)
W
X
h2 (y) = cw y w
w=1

Denoting the rows of A by a(1) , . . . , a(W ) , we have that

yw = σ(⟨a(w) , x⟩ + bw )
W
X W
X
h2 (y) = cw yw = cw σ(⟨a(w) , x⟩ + bw )
w=1 w=1

We conclude
Lemma 1.3. Let K ⊆ Rd be a compact set, and σ : R → R be some function, if
span{σ (⟨a, x⟩ + b) | a ∈ Rd , b ∈ R} (1.3)
is dense in C(K), then [
FC (W, L = 1; win = d, wout = 1, σ)
W ∈N

is dense in C(K).
14 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

Closure Next, recall that if C is a normed space and P ⊆ C is a subspace, then the closure of P is denoted
by P̄ , and defined as the set

P̄ = {f ∈ C|∃(pn )n∈N ⊆ P such that ∥pn − f ∥ → 0}.

Note that saying that P is dense in C is equivalent to saying that C = P̄ . One can verify that

Proposition 1.4. Let C be a normed space and P ⊆ C a subspace, then

1. P̄ contains P , is closed, and is the smallest set having these two properties.

2. P̄ is a subspace of C.

Analytic functions Recall that if a function σ : R → R is analytic then it is continuous differentiable ∞

times, and all its derivatives are analytic. If σ is not a polynomial then all its derivatives will not be the
zero function. We then have

Lemma 1.5. If σ : R → R is analytic and non-polynomial, then there exists a point b ∈ R such that none
of the derivatives of σ at b vanish, that is

σ(b) ̸= 0, σ ′ (b) ̸= 0, σ (2) (b) ̸= 0, . . . (1.4)

Proof. For analytic functions, if there is a sequence tn which converges to some t, for which σ(tn ) = 0 for
all n, then σ(t) = 0 for all t ∈ R. It follows that if σ is not zero, then in the interval [0, 1] it can have a
finite number of zeros (otherwise, we can find a sequence tn on which σ is zero, and then take a converging
subsequence which would imply that σ = 0). We deduce that for all k = 0, 1, . . . the set

Zk = {b ∈ [0, 1]|σ (k) (b) = 0}

is finite and therefore the set ∪k∈{0}∪N Zk is countable, and so there exists some b ∈ [0, 1] which is not in this
set, and for this b we have (1.4).

We are now ready to prove Theorem 1.2 for the case d = 1. The general case d ≥ 1 will then follow
relatively easily.

Lemma 1.6 (Shallow universality for d = 1). Let K ⊆ R be a compact set, and σ : R → R be an analytic
function which is not a polynomial. Then
[
FC (W, L = 1; win = 1, wout = 1, σ)
W ∈N

is dense in C(K).

Proof. By Lemma 1.3, it is sufficient to show that the space

P = span{σ(at + b)| a, b ∈ R}

is dense, that is that P̄ = C(K). Let us fix some b for which σ and all its derivatives do not vanish as in
(1.4). We claim by induction that for every a ∈ R and every k = 0, 1, . . . the function

dk
fa(k) (t) = σ(at + b) = tk σ (k) (at + b)
dak

is in P̄ . For k = 0 this is obvious.

Let us now assume correctness for k and prove for k + 1. Using the induction
 hypothesis and the fact
(k) (k)
that P̄ is a subspaces, we have for every h ̸= 0 that h1 fa+h (t) − fa (t) is in P̄ . We need to show that
1.2. PROOF OF UNIVERSALITY OF SHALLOW NEURAL NETWORKS WITH ANALYTIC ACTIVATIONS15

(k+1)
they converge uniformly on K to fa (t) and therefore since P̄ is closed this function is also in P̄ . Indeed
we have for every t ∈ K that there exists some â ∈ [a − 1, a + 1] such that
1  (k)  1  (k) 
| fa+h (t) − fa(k) (t) − fa(k+1) (t)| = | fa+h (t) − fa(k) (t) − hfa(k+1) (t) |
h h
1 1 2 (k+2)
=| h fâ (t)|
h2
|h| (k+2)
≤ max |f (t)|,
2 (â,t)∈[a−1,a+1]×K â

where the existence of the maximum follows from the fact thatall derivatives of 
σ exists and are continuous,
(k) (k)
and the set [a − 1, a + 1] × K is compact. It follows that h1 fa+h (t) − fa (t) converges unifomly on K
(k+1) (k+1)
to fa (t) as required, and so fa ∈ P̄ for all a ∈ R and all k. In particular, this holds for a = 0, in
which case we see that for all k the function tk σ (k) (b) is in P̄ . Since σ (k) (b) ̸= 0 for all k we see that every
polynomial can be obtained as a linear combination of these functions, and since P̄ is a subspace of C(K) it
follows that all polynomials are contained in P̄ . From the denseness of polynomials it follows that P̄ = C(K)
and so we are done.
We can now conclude the proof of the theorem for general d ≥ 1.
Proof of Theorem 1.2. By Lemma 1.3 it is sufficient to show that the closure of

P = span{σ (⟨a, x⟩ + b) | a ∈ Rd , b ∈ R}

is equal to C(K). In Problem 0.30 we used Stone-Weierstrass to show that linear combinations of functions
of the form
Ea (x) = exp (⟨a, x⟩)
are dense in C(K). It is thus sufficient to show that all such functions are in P̄ . By the previous lemma,
For fixed a, and every ϵ > 0 we can approximate the continuousPexponential function on the compact set
N
Ka = {⟨a, x⟩|x ∈ K} to ϵ accuracy by an expression of the form n=1 cn σ(an t + bn ), and so for all x ∈ K
N
X
∥ exp(⟨a, x⟩) − cn σ(an ⟨a, x⟩ + bn )∥ ≤ ϵ
n=1

which implies that exp(⟨a, x⟩) is in P̄ and so we are done.

The full proof of Theorem 1.2 We proved Theorem 1.2 for the special case where the activation func-
tion is analytic and non-polynomial. The same proof works for C ∞ (R) non-polynomial functions, the only
difference being that proving that there exists a point on which all derivative do not vanish is more challeng-
ing. This can then be extended to all continuous non-polynomial functions, essentially by approximating the
smooth activations by continuous activations. The details can be found in [Pinkus, 1999].
16 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

Lesson Three
1.3 Universality of (deep) ReLU Neural Networks
Recall that for a fixed activation function σ : R → R and integer vector

⃗ = (w0 , w1 , . . . , wL , wL+1 ) ∈ NL+2 ,

w

we defined a hypothesis class

⃗ σ) = {h(x) = hL+1 ◦ σ ◦ hL . . . ◦ σ ◦ h1 (x) where hi : Rwi−1 → Rwi is affine ∀i = 1, . . . , L + 1}.

FC (w;

We also said that we will often focus on the case where all hidden layers have the same width. The width
vector w
⃗ is then described by four hyper-parameters

w
⃗ (W, L, win , wout ) = (w0 = win , w1 = W, w2 = W, . . . , wL = W, wL+1 = wout )

and accordingly these hyper-parameters define the hypothesis class

FC (W, L, win , wout , σ) = FC (w

⃗ (W, L, win , wout ) ; σ)

From now on we will focus mostly on the case where σ = ReLU . For short, we will denote ρ := ReLU ,
and when referring to the architectures above with ReLU activation we will drop the activation from the
notation, so that our architectures will just be denoted by FC (w)
⃗ and FC (W, L, win , wout ).
In this section we will prove the universality of neural networks with ReLU activations. What we will
do now is discuss in general some basic properties of ReLU activation neural networks functions. Once we
establish these, proving universality will be rather straightforward. The properties we will discuss will be
useful not only for this theorem but for our understanding of ReLU networks and various other results we
will see later on.

1.3.1 Basic approximation properties of ReLU networks

We now discuss some elementary useful properties of fully connected neural networks. For example, it would
be natural to hope that smaller networks will be contained in bigger networks. This is indeed the case (up
to a small caveat...)

Composition, concatenation, and linear combinations

1. Going wider can’t hurt Given w ⃗ = (w0 , . . . , wL+1 ) ∈ NL+2 , every NNF which is in FC(w)
⃗ is also in
FC([w0 , w1 , . . . , wj + n, wj+1 , . . . , wL+1 ]), for every 1 ≤ j ≤ L and every n ∈ N. Let

h(x) = hL+1 ◦ ρ ◦ hL . . . ◦ ρ ◦ h1 (x) where hi : Rwi−1 → Rwi is affine ∀i = 1, . . . , L

⃗ To see our claim is true, it is sufficient to show that there exist h̃j+1 : Rwj +n →
be a function in FC(w).
wj+1 wj−1
R and h̃j : R → Rwj +n such that

h̃j+1 ◦ ρ ◦ h̃j = hj+1 ◦ ρ ◦ hj

which can be obtained by setting

   
0n y
h̃j (x) = , and h̃j+1 = hj+1 (z).
hj (x) z

⃗ ′ ∈ NL+2 and w
We can deduce that if the first and last coordinates of w ⃗ ∈ NL+2 are the same, and
′
⃗ are larger, then FC(w)
all other coordinates of w ⃗ is contained in FC(w⃗ ′ ). In particular, for a given
⃗ ∈ NL+2 , we always have that FC(w)
w ⃗ ⊆ FC(W, L, w0 , wL+1 ) where W = max1≤i≤L wi .
1.3. UNIVERSALITY OF (DEEP) RELU NEURAL NETWORKS 17

2. Composition If h ∈ FC(W, L, win , wout ) and h′ ∈ FC(W ′ , L′ , win

′ ′
, wout ′
) and win = wout , then
h′ ◦ h ∈ FC(W ′′ , L′′ , win , wout
′
)
where
L′′ = L + L′ and W ′′ = max{W, W ′ }
This is because h and h′ are of the form
h(x) = hL+1 ◦ ρ ◦ hL . . . ◦ ρ ◦ h1 (x)
h′ (x) = h′L′ +1 ◦ ρ ◦ h′L′ . . . ◦ ρ ◦ h′1 (x)
and so
h′ ◦ h = h′L′ +1 ◦ ρ ◦ h′L′ . . . ◦ ρ ◦ h′1 ◦ hL+1 ◦ ρ ◦ hL . . . ◦ ρ ◦ h1
we get a fully connected network with ‘width vector’
⃗ = (win , W, . . . , W, W ′ , . . . , W ′ , wout
w ′
)
and since ‘going wider can’t hurt’ we can replace W, W ′ with W ′′ = max(W, W ′ ).
3. Concatenation If h1 and h2 are neural networks in FC(W1 , L, win , wout = w1 ) and FC(W2 , L, win , wout =
w2 ) respectively, then  
h1 (x)
h(x) = , h : Rwin → Rw1 +w2
h2 (x)
is in FC(W1 + W2 , L, win , w1 + w2 ).
4. Going deeper doesn’t hurt (too much) Given a NNF h ∈ FC(W, L; win , wout ) with L ≥ 1, so
h(x) = hL+1 ◦ ρ ◦ hL . . . ◦ ρ ◦ h1 (x)
we have for all L̃ ≥ L that h ∈ FC(W, L̃; win , wout ) since we can write
h(x) = hL+1 ◦ ρ ◦ I . . . ◦ ρ ◦ I ◦ ρ ◦ I ◦ ρ ◦ hL . . . ◦ ρ ◦ h1 (x)
and we are using the fact that
 
ρ(x) if x > 0 x if x > 0
ρ ◦ ρ(x) = = = ρ(x).
ρ(0) if x ≤ 0 0 if x ≤ 0
What happens if L = 0, so we are talking just of an affine function? This actually is not so straightfor-
ward. Let us focus only on the identity function x 7→ x which is in FC(W = n, L = 0, win = n, wout =
n) (the W is in fact meaningless since there are no hidden neurons at depth zero). This function cannot
in fact be expressed exactly in FC(W = n, L = 1, win = n, wout = n) as we saw in homework. There
are two tricks to overcome this: the first is to increase the width: note that
ρ(x) − ρ(−x) = x
so the identity function is in FC(W = 2n, L = 1, win = n, wout = n). By the composition rule,
we can compose the identity function with itself L times for any L ∈ N and obtain that it is in
FC(W = 2n, L, win = n, wout = n).
An alternative trick does not require increasing width, but only applies when restricting to compact
sets. That is, for any compact K ⊆ Rn and every L ∈ N we can find a function h ∈ FC(W =
n, L, win = n, wout = n) such that
h(x) = x, ∀x ∈ K.
This is done as follows: choose b ∈ Rn whose coordinates are all large enough so that
xi + bi ≥ 0, ∀i = 1, . . . , n, ∀x ∈ K.
and thus ρ(x + b) = x + b for all x ∈ K. Then apply the identity transformation as much as necessary
and conclude with the inverse translation x 7→ x − b.
18 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

1.3.2 Expressing functions as ReLU networks: first examples

Some functions can be not only approximated by ReLU networks, but actually can be exactly expressed as
neural networks. We will now see some simple but useful examples, which in particular will be useful for our
universality proof later on.
Problem 1.7. 1. Write the function (x1 , x2 ) 7→ max(x1 , x2 ) as a ReLU neural network. What are the
width and depth?
2. For any a < b < c < d show that the trapezoid function ha,b,c,d illustrated in Figure 1.1(b) can be
realized by a neural network.
We have

max(x1 , x2 ) = max(x2 − x1 , 0) + x1 = max(x2 − x1 , 0) + max(x1 , 0) − max(−x1 , 0)

so max ∈ FC(W = 3, L = 1, nin = 2, nout = 1). In homework you will show this can be extended to finding
the maximum of a d dimensional vector:
Lemma 1.8. The function h : Rd → R defined by h(x) = max(x) is expressible as a neural network in
FC(W, L, nin = d, nout = 1) with width W = 3d and depth L = ⌈log2 (d)⌉.
We note that we can also express the minimum function with a network of the same size. This follows
from the fact that
min(x) = − max(−x), ∀x ∈ Rd .
We now discuss how to create the trapezoid function (note there is more than one way to do this).
Lemma 1.9. For any a < b < c < d the trapezoid function ha,b,c,d illustrated in Figure 1.1(b) can be
expressed as a neural network in FC(W, L, nin = w, nout = 1) with depth L = 1 and width W = 4.
Proof. Let us relabel a, b, c, d as a1 , . . . , a4 , and choose some a5 > a4 . We guess that there exist α1 , . . . , α4
such that
X4
hα (x) = αi ρ(x − ai )
i=1

is the trapezoid function. Note that for any choice of α1 , . . . , α4 the obtained function is linear on the
intervals
(−∞, a1 ], [a4 , ∞) and [ai , ai+1 ], i = 1, . . . , 3,
Accordingly is is sufficient to find on each such interval two points on which the expected value is obtained.
Note that by construction the function hα is zero on (−∞, α1 ]. It is thus sufficent to find α1 , . . . , α4 such
that

hα (a2 ) = 1
hα (a3 ) = 1
hα (a4 ) = 0
hα (a5 ) = 0

By definition of the ReLU function ρ, this is equivalent to the equations

    
a2 − a1 0 0 0 α1 1
a3 − a1 a3 − a2 0 0  α2  1
   =  
a4 − a1 a4 − a2 a4 − a3 0  α3  0
a5 − a1 a5 − a2 a5 − a3 a5 − a4 α4 0

The matrix on the left hand side is non-singular, as its determinant is just the product of the non-zero
diagonal elements. Thus this equation has a unique solution and the hα obtained by using the vector α
solving the equation is the NNF we wanted.
1.3. UNIVERSALITY OF (DEEP) RELU NEURAL NETWORKS 19

We’d like to think of the trapezoid function we just constructed as an approximation of an indicator
function for the unit interval [b, c] by a continuous function (think of the case a = b − ϵ, d = c + ϵ). We can
now use this and the maximum function we constructed, to construct approximations of a indicator for a
high-dimensional cube:
Lemma 1.10. Let â, a, b̂, b ∈ Rk be such that âi < ai < bi < b̂i for all i = 1, . . . , k, then there exists a neural
network function h in FC(W = 4k, L = 1 + ⌈log2 (k)⌉, nin = k, nout = 1) such that
1. 0 ≤ h(x) ≤ 1 for all x ∈ Rk .
Qk
2. h(x) = 1 for all x in the cube C = i=1 [ai , bi ].
Qk
3. h(x) = 0 for all x outside the cube Ĉ = i=1 [âi , b̂i ].

We will say that such an h is a quasi-indicator of C with support in Ĉ.

Proof. For all i = 1, . . . , k let hi denote the trapezoid function hi = hâi ,ai ,bi ,b̂i . Each one of these functions
can be realized as a neural network, as can be the minimum function, and therefore so can

h(x) = min hi (xi )

i=1,...,k

which satisfies the conditions of the lemma. By Lemma 1.8 the minimum function is in FC(W, L, nin =
k, nout = 1) with width W = 3k and depth L = ⌈log2 (k)⌉ while each of the hi can be realized with width
four and depth 1 by Lemma 1.9. Using the concatenation and composition rules we see that the function
   
x1 h1 (x1 )
 x2   h2 (x2 ) 
 ..  7→  ..  7→ min{h1 (x1 ), h2 (x2 ), . . . , hk (xk )}
   
.  . 
xk hk (xk )

is in FC(W = 4k, L = 1 + ⌈log2 (k)⌉, nin = k, nout = 1).

Universality We now want to prove universality of ReLU networks, using the fact that they can approx-
imate cube indicators and minimum and maximum functions. For any set C ⊆ Rd we define its indicator
function to be 
1 if x ∈ C
1C (x) = .
0 if x ̸∈ C
For practice, let us prove the following theorem
Theorem (Universality of real indicator functions). Let f : [0, 1]d → R be a continuous, non-negative
function. For every ϵ > 0 there exist n = n(ϵ) cubes C1 , . . . , Cn and numbers c1 , . . . , cn such that

|f (x) − max ck 1Ck (x)| < ϵ, ∀x ∈ [0, 1]d

k=1,...,n

√ d
dℓ
Moreover, if f is ℓ Lipschitz then we can choose n(ϵ) ≤ 2ϵ +1 .

Proof. Let ϵ > 0. Since f is continuous on a compact set, it is uniformly continuous, and so there exists
some δ > 0 such that
∀x, y ∈ [0, 1]d if |x − y| ≤ δ then |f (x) − f (y)| ≤ ϵ.
Moreover, if f is ℓ Lipschitz then we can take δ = ϵ/ℓ, because this implies that if |x − y| < δ then

|f (x) − f (y)| ≤ ℓ|x − y| ≤ ℓδ ≤ ϵ.

Now, For every N we define a partition of [0, 1] into N intervals of the from Ik = [ k−1 k
N , N ] where
d d
k = 1, . . . , N . This partition induces a partition of all of [0, 1] into N cubes of the general form

Ck = Ik1 × Ik2 × . . . × Ikd , where k = (k1 , . . . , kd ) ∈ {1, . . . , N }d

20 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS
√
We choose N large enough so that 2Nd < δ. This means that the distance of any point in the cube Ck from
the center of the cube is less than δ. Let xk denote the center of the cube Ck . It follows that for ck = f (xk )
we have that for all x ∈ Ck
|f (x) − ck 1Ck (x)| = |f (x) − f (xk )| ≤ ϵ
while if x ̸∈ Ck we have that ck 1Ck (x) = 0. Thus we have that for all x ∈ [0, 1]d , the maximum of ck 1Ck (x)
over all k is obtained for some k∗ = k∗ (x) for which x ∈ Ck∗ . We obtain

|f (x) − max ck 1Ck (x)| = |f (x) − ck∗ 1Ck∗ (x)| < ϵ.

k=1,...,N

We now consider the number

√
of cubes needed for an ℓ-Lipschitz function. In out construction we used N d
d
cubes, and we required that 2N < δ = ϵ/ℓ. By rearranging we find that this is equivalent to the requirement
√ √
dℓ dℓ
that N > 2ϵ .
The nearest largest N to this number is smaller than 2ϵ + 1, and therefore in total we can
√ d
achieve ϵ approximation with ≤ 2ϵdℓ + 1 cubes.

Curse of Dimensionality Our proof achieved ϵ accuracy with approximately (1/ϵ)d cubes. This type
of phenomena where the complexity depends exponentially on the dimensionality is called the ‘curse of
dimensionality’.
We now prove universality for ReLU networks. The idea is to imitate the proof of the previous theorem,
based on the fact that we can express the maximum function and approximate the cube indicator function
used in the previous theorem.
Theorem 1.11 (Universality for ReLU networks). Let f : [0, 1]d → R be a continuous function. For every
ϵ > 0 there exist a neural network function h : Rd → R such that

|f (x) − h(x)| < ϵ, ∀x ∈ [0, 1]d

Moreover, if f is ℓ-Lipschitz then we can choose h to be in FC(W, L, d, 1) where

√ !d √ !
dℓ dℓ
W ≤ 4d +1 , L ≤ ⌈log2 (d)⌉ + ⌈d · log2 ( + 1 )⌉
2ϵ 2ϵ

Proof. Choose some ϵ > 0, we want to construct a NNF h s.t.

∥f − h∥C(K) < ϵ. (1.5)

Since f is continuous on a compact set it is bounded from below, so we can find some b ≥ 0 such that the
function f˜(x) = f (x) + b is non-negative. We will find a NNF h̃ for which

∥f˜ − h̃∥C(K) < ϵ

which implies that h(x) = h̃(x) − b satisfies (1.5). Note that h will be a NNF with the same width and depth
as h̃.
Since f˜ is continuous on a compact set it is uniformly continuous and so there exists some δ > 0 such
that
∀x, y ∈ [0, 1]d if |x − y| ≤ δ then |f (x) − f (y)| ≤ ϵ.
Moreover, if f is ℓ Lipschitz then f˜ will be ℓ Lipschitz as well, and we can take δ = ϵ/ℓ as we saw before.
Again as before, for every N we define a partition of [0, 1] into N intervals of the form Ik = [ k−1 k
N , N]
d d
where k = 1, . . . , N . This partition induces a partition of all of [0, 1] into N cubes of the general form

Ck = Ik1 × Ik2 × . . . × Ikd , where k = (k1 , . . . , kd ) ∈ {1, . . . , N }d

√
d
We choose N large enough so that 2N < δ, which means that the distance of xk from any point in Ck will
be less than δ.
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 21

Let xk denote the center of Ck , and denote ck = f (xk ). Let ϕk be a quasi-indicator of Ck supported in
Ĉk , where Ĉk is chosen so that its center is also xk , it contains Ck , and is close enough to Ck such that the
distance of any point in Ĉk from xk is still smaller than δ. We deduce that if ϕk (x) > 0 then x is in Ĉk and
so |x − xk | < δ which implies that |f (x) − ck | = |f (x) − f (xk )| < ϵ. It follows that for every x ∈ [0, 1]d the
maximum of ck ϕk (x) over all k will be obtained by some k∗ = k∗ (x) for which ϕk (x) > 0, and we have that

max(ck ϕk (x)) − f (x) = ϕk∗ (x)f (xk∗ ) − f (x) ≤ f (xk∗ ) − f (x) ≤ ϵ.

k

On the other hand, since the cubes cover all the domain, there exists some k∗∗ for which x ∈ Ck∗∗ , and thus

max(ck ϕk (x)) − f (x) ≥ ck∗∗ ϕk∗∗ (x) − f (x) = f (xk∗∗ ) − f (x) ≥ −ϵ

k

and so the function x 7→ maxk (ck ϕk (x)) is an ϵ approximation of f . This function can be realized as a neural
network through the construction
   
x1 c1 ϕ1 (x1 )
 x2   c2 ϕ2 (x2 ) 
 ..  7→   7→ max{c1 ϕ1 (x1 ), c2 ϕ2 (x2 ), . . . , cn ϕn (xn )}
   
..
 .   . 
xn cn ϕn (xn )

where n = N d denotes the number of cubes. By Lemma 1.10 the width of each ϕk is 4d and the depth is
⌈log2 (d)⌉, and so overall the width of the function we constructed would be 4nd and the depth would be
√ d
⌈log2 (d)⌉ + ⌈log2 (n)⌉. As in our previous claim, when f is ℓ-Lipschitz we can take n(ϵ) ≤ 2ϵdℓ + 1 and
so we can obtain ϵ approximation with width and depth bounded by
√ !d √ !
dℓ dℓ
W ≤ 4d +1 , L ≤ ⌈log2 (d)⌉ + ⌈d · log2 +1 ⌉
2ϵ 2ϵ

To conclude, we showed that ReLU networks can ‘imitate’ approximation by piecewise constant func-
tions. The original piecewise constant construction, as well as the ReLU imitation, suffer from the curse of
dimensionality. Later on in the course we will see that smoothness of f enables neural networks to ‘overcome’
the curse of dimensionality.

1.4 ReLU Networks, CPwL Functions and Depth Separation

1.4.1 ReLU networks are Continuous Piecewise Linear functions
A good reference for this topic is again [DeVore et al., 2021] and references therein. ReLU networks al-
ways product continuous functions, as they are compositions of affine functions and ReLU which are both
continuous. In fact, ReLU networks always produce Continuous Piecewise Linear (CPwL) functions, since
ReLU and affine functions are CPwL functions. Before we see this, we need to formally defined what CPwL
functions are. For this we will need some more definitions...
Definition 1.12. A closed convex polytope P ⊆ Rd is a set of the form

P = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0| i = 1, . . . , m where for all i ai ∈ Rd , bi ∈ R} (1.6)

As there name suggests, closed convex polytopes are always closed and convex (verify this). Examples
include
1. The whole space P = Rd (with m = 0 constraints, or with the constraint ⟨0, x⟩ + 1 ≥ 0).
2. The empty set is a polytope defined by the constraint ⟨0, x⟩ − 1 ≥ 0.
22 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

3. The positive quadrant

Q = {x ∈ Rd | xi ≥ 0, i = 1, . . . , d}.
This expression is of the same form as in (1.6) where ai = ei , bi = 0 and m = d.
4. The unit hyper cube
C = {x ∈ Rd | − 1 ≤ xi ≤ 1, i = 1, . . . , d}
which can be rewritten as in (1.6)

C = {x ∈ Rd |xi ≥ −1 and − xi ≥ −1, i = 1, . . . , d}

.
5. The plane
P = {(x1 , x2 , x3 )| x3 = 0}
which can be rewritten as in (1.6)

P = {x ∈ R3 | x3 ≥ 0 and − x3 ≥ 0}.

In general, using this same trick we see that closed convex polytopes can be defined by affine equalities
as well as affine inequalities.
Remark 1.13. From now on we will use the term polytope to denote a closed convex polytope.
Problem 1.14. Show that all bounded polytopes in R are points or closed intervals.
Definition 1.15. A polytope covering P of Rd is a finite collection of polytopes P = {P1 , . . . , PR } such
SR
that r=1 Pr = Rd
Problem 1.16. Which of the following is not a polytope covering of R2
1. The collection of polytopes

P1 = {(x, y)|x ≥ 0}, P2 = {(x, y)|x ≤ 0}, P3 = {(x, y)|y ≥ 0}, P4 = {(x, y)|y ≤ 0}

2. The collection of polytopes

P1 = {(x, y)|x ≥ 0}, P2 = {(x, y)|x ≤ 0}, P3 = {(x, y)|y ≥ 0}, P4 = {(x, y)|y < 0}

3. The collection of polytopes

P1 = {(x, y)|x ≥ 0}, P2 = {(x, y)|x ≤ 0}, P3 = {(x, y)|y ≥ 0}, P4 = {(x, y)|y ≤ 0}, P5 = {(1, 1)}

4. The collection of polytopes

P1 = {(x, y)|x ≥ −1}, P2 = {(x, y)|x ≤ 1}, P3 = {(x, y)|y ≥ 0}, P4 = {(x, y)|y ≤ 0}

Solution The second, because P4 is not closed.

We can finally define a CPwL function
Definition 1.17. We say that f : Rd → Rℓ is a CPwL function subordinate to the polytope covering
P = {P1 , . . . , PR } if f is continuous, and the restriction of f to each Pi is an affine function.
We say that f is a CPwL function if it is CPwL function subordinate to some polytope partition.
Remark 1.18. We follow the definition in [DeVore et al., 2021] and require explicitly that f is continuous,
though this follows from the other assumptions. On the other hand, we do not require as in [DeVore et al., 2021]
that the polytope covering is a partition (i.e., that the interiors of the polytopes do not intersect). This
makes the proof of Proposition 1.20 easier and does not hurt generality: if f is CPwL subordinate to some
covering, then this covering can be refined to a partition which f will be subordinate to. We will see this
soon.
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 23

Let us see some examples for CPwL functions. Perhaps the two most important examples for us are affine
functions, which are CPwL with respect to the trivial partition P = {Rd }, and the ReLU function. The
ReLU function is a linear function on each of the 2d quadrants of Rd . Formally, for every vector s ∈ {−1, 1}d
we can define the polytope
Qs = {x ∈ Rd | si xi ≥ 0, ∀i = 1, . . . , d}
The collection of all such polytopes form a polytope partition, and
  
1 + s1 0 0 ... 0 x1
 0 1 + s2 0 . . . 0   x2 
1  
ReLU (x) =  0 0 1 + s3 . . . 0  x3  , ∀x ∈ Qs . (1.7)
  
2 .. .
0   .. 

 0 0 0 .
0 0 0 0 1 + sd xd

Thus, ReLU is a CPwL function.

Problem 1.19. Show that the maximum functions from Rd to R is CPwL.

As we saw that affine functions and ReLU functions are both CPwL, we can now deduce that every NNF
is a CPwL function by showing that the composition of CPwL functions are also CPwL.
Proposition 1.20. If f : Rd → Rn and g : Rn → Rm are CPwL functions then g ◦ f is a CPwL functions.
Proof. By assumption f is subordinate to some polytope covering P = {P1 , . . . , PR } and g is subordinate
to some polytope covering Q = {Q1 , . . . , QS }. The restriction of f to each Pr is an affine function fr ,
and the restriction of g to each Qs is an affine function gs . We can now define a new polytope covering
{Tr,s }1≤r≤R,1≤s≤S by
Tr,s = {x ∈ Pr and fr (x) ∈ Qs }
We note that these sets do indeed cover all of Rd , that g ◦ f is continuous and its restriction to Tr,s is the
affine function gs ◦ fr , and finally that each Tr,s is a polytope, for if

Pr = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0, i = 1, . . . , m}, fr (x) = Ax + b

and
Qs = {y ∈ Rn |⟨cj , y⟩ + dj ≥ 0, j = 1, . . . , ℓ}
then

Tr,s = {x ∈ Pr and fr (x) ∈ Qs }

= {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0 and ⟨cj , Ax + b⟩ + dj ≥ 0, i = 1, . . . , m, j = 1, . . . ℓ}
d T
= {x ∈ R |⟨ai , x⟩ + bi ≥ 0 and ⟨A cj , x⟩ + [dj + ⟨cj , b⟩] ≥ 0, i = 1, . . . , m, j = 1, . . . ℓ}
24 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

Lesson 4
1.4.2 From coverings to partitions
We saw that any ReLU network is a CPwL subordinate to some polytope covering. This covering is not
unique. For example, the function f (x) = |x| is subordinate to the covering P = {(∞, 0], [0, 1], {1/2}, [1/2, ∞)}
but also to the covering P ′ = {(∞, 0], [0, ∞)}. Clearly, the second covering is more natural as it is minimal,
and forms a ‘partition’ of the space. We will now define the notion of a partition:
Definition 1.21. Let P ⊆ Rd . The interior of P , denoted by int(P ), are all points p ∈ P such that there
exists some open ball B with p ∈ B ⊆ P .
For example, the interior of [0, 1] ∈ R is (0, 1). More generally
Problem 1.22. Let P = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0, i = 1, . . . , m} be a polytope. Show that its interior is the
set
P = {x ∈ Rd |⟨ai , x⟩ + bi > 0, i = 1, . . . , m}
Definition 1.23. Let P = {P1 , . . . , PN } be a finite collection of polytopes in Rd . we say that P is a partition
of Rd if
1. i Pi = Rd .
S

2. Each Pi had non-empty interior.

3. int(Pi ) ∩ int(Pj ) is empty for all i ̸= j.
In the example above, we see that P ′ is a partition, while P is a covering but not a partition since {1/2}
has empty interior, and since the intersection of the interior of two intervals in P is not empty.
Proposition 1.24. If f : Rd → Rℓ is a CPwL function subordinate to a covering P, then it is also subordinate
to some partition P ′ .
Proof. We build P ′ from the given covering P = {P1 , . . . , PN }.
First note that if some Pj has empty interior then it is contained in the union of all other sets and therefore
it can be removed from P. This is because every point p ∈ Pj has a sequence of points pn converging to it
which are not in Pj , and so since all Pi cover Rd , the sequence is in ∪i: i̸=j Pi . Since this set is closed as a
finite union of closed sets, we have that p is also in this set. Thus we can assume without loss of generality
that all elements in P have non-empty interior.
Now, assume we have two Pi ̸= Pj whose interiors intersect. We can write

Pi = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0, i = 1, . . . , m}

and
Pj = {x ∈ Rd |⟨cj , x⟩ + dj ≥ 0, j = 1, . . . , ℓ}.
We will show how to defined a new finite collection of polytopes whose union is exactly Pi ∪ Pj and who do
not intersect.
The intersection Pi ∩ Pj is a polytope

Pi ∩ Pj = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0, i = 1, . . . , m and ⟨cj , x⟩ + dj ≥ 0, j = 1, . . . , ℓ}

The set Pi \ (Pi ∩ Pj ) is not necessarily a polytope, but it can be written as a finite union of the polytopes

Psi = {x ∈ Rd |⟨ai , x⟩ + bi ≥ 0, i = 1, . . . , m and ⟨sj cj , x⟩ + sj dj ≥ 0, j = 1, . . . , ℓ}

where s ∈ {−1, 1}ℓ . That is

Pi = ∪s∈{−1,1}ℓ Psi
and the polytope corresponding to s = (1, . . . , 1) is Pi ∩ Pj . Note that the interior of the different Pis do not
intersect.
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 25

𝑓𝑓 𝑥𝑥, 𝑦𝑦 = 0

𝑓𝑓 𝑥𝑥, 𝑦𝑦 = 0

𝑓𝑓 𝑥𝑥, 𝑦𝑦 = 𝑦𝑦

𝑓𝑓 𝑥𝑥, 𝑦𝑦 = 𝑥𝑥

Figure 1.2: In our definition f has four (convex) linear region, though it has three non-convex linear regions.

We can do the same thing to Pj and write it as a union of polytopes Ptj where t ∈ {−1, 1}m and Pi ∩ Pj
is the polytope corresponding to t = (1, . . . , 1), and such the interior of the Ptj do not intersect. Finally we
consider this new collection of polytopes of all Ptj and Psi and we find that their interiors do not intersect.
Thus, we have showed how we can reduce the number of intersections between polytopes by one, and by
repeating this process recursively we can transform a covering into a partition.
Definition 1.25. The number of linear regions of a CPwL function f is the smallest m such that f is
subordinate to a partition P = {P1 , . . . , Pm }.
Example 1.26. The function f (x) = |x| is subordinate to the partition P = {(∞, 0], [0, 1], [1, ∞)} but also
to the smaller partition P ′ = {(∞, 0], [0, ∞)} and therefore the number of linear regions is ≤ 2. Clearly the
number of linear regions cannot be 1 since f is not linear, and so the number of linear regions is two.
Example 1.27. The function in Figure 1.2 has four linear regions, though if we would have allowed non-
polytope partitions the number of regions would have been reduced to three.

1.4.3 Depth separation and counting linear regions

In this subsection we will address some of the questions mentioned in previous lessons: can we show that
neural networks have some expressive advantage over standard function bases (e.g., standard CPwL function
spaces)? Can we show that deep neural networks (L ≫ 1) have an expressive advantage over shallow
networks (L = 1)? These questions are motivated by the successfulness of deep learning in the past years,
in comparison with alternative function spaces or shallow networks.
In this subsection we will consider univariate neural networks with nin = 1 = nout . We will also restrict
our attention to the behavior of these functions on [0, 1]. Thus we are interested in the function space
Υ(W, L) = {f : [0, 1] → R|f = g|[0,1] for some g ∈ FC(W, L, 1, 1)}
Most of the results described here come from [Daubechies et al., 2021] unless mentioned otherwise.
As we saw, any function f ∈ FC(W, L, 1, 1) is a CPwL function f : R → R subordinate to a polytope
partition of R. A non-empty polytope in R with a non-empty interior is a closed interval (which may or
may not be bounded from the left or right). Based on this, it is not difficult to see that a univariate CPwL
function always has a finite sequence of breakpoints k1 < k2 . . . < kn , on which it is not differentiable, and
the restriction of f to the intervals (−∞, k1 ] and [ki , ki+1 , i = 1, . . . , n − 1] and [kn , ∞) is an affine univariate
function. In our case we focus on the function value on [0, 1], so f will be linear on the intervals [ki−1 , ki ]
where i = 1, . . . , n + 1 and k0 = 0, kn+1 = 1. The number of linear regions of f will be n in this case.
One natural question to ask is whether every CPwL univariate function on [0, 1] can be realized a neural
network? The answer to this is affirmitive. We then want to compare neural networks with more standard
CPwL bases:
26 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

Free knot splines For fixed n, let Σn be the set of CPwL functions determined by 2n + 2 parameters: n
knots 0 < k1 < . . . < kn < 1, n assigned values yi to each of the knots, and values y0 and yn+1 assigned to 0
and 1. These values then uniquely define a CPwL function on [0, 1] which attains these values and is affine
in the intervals defined by the knots. We refer to this function spaces as the space of free knot splines with
n knots. Note that a function in Σn can have a breakpoint (a non-differentiable point) only at a knot, but
a knot does not necessarily have to be a breakpoint. In fact Σn is exactly the set of all CPwL functions on
[0, 1] with n or less breakpoints, and in particular Σn ⊆ Σn+1 .

Counting parameters in Υ(W, L) We will compare function spaces Σn and Υ(W, L) in terms of the
number of their parameters on the one hand, and their expressive power on the other hand. Recall that Σn
is defined by 2n + 2 parameters. Let’s now count the number of parameters in Υ(W, L):
For fixed W, L the number of parameters which determine functions in Υ(W, L) is

n(W, L) = 2W + (L − 1)(W 2 + W ) + W + 1
= 3W + 1 + (L − 1)(W 2 + W )

When L = 1 we have that n(W, L) = 3W + 1. When L ≥ 2 we see that n(W, L) is proportional to LW 2 , as

for all integer W and L ≥ 2

3W + 1 + (L − 1)(W 2 + W ) ≤ 3W 2 + W 2 + 2(L − 1)W 2 = W 2 (2L + 2) ≤ 3LW 2

1
3W + 1 + (L − 1)(W 2 + W ) ≥ (L − 1)W 2 ≥ LW 2
2
In the following we’d like to compare the function space Σn and Υ(W, L). We consider the following questions:
can every CPwL univariate function be expressed as a NNF? If so, is it more efficient to parameterize CPwL
functions as free knot splines or as neural networks? In the following we will show that for shallow networks
these representations are more or less equivalent. We will then discuss deep networks where we will have
more interesting results...

1.4.4 Shallow univariate neural networks

We begin by discussing shallow networks, that is networks with L = 1. We prove the following

Proposition 1.28. For every W ∈ N we have

ΣW −1 ⊆ Υ(W, L = 1) ⊆ ΣW

Recall that n(W, L = 1) = 3W + 1 while functions in Σn are determined by 2n parameters. Thus this
theorem says that the number of parameters needed to express a CPwL functions via shallow neural networks
or via free knot splines is roughly the same.

Proof. Let us first show that Υ(W, L = 1) ⊆ ΣW . Recall that a function f in Υ(W, L = 1) is of the form

f (x) = h2 ◦ ReLU ◦ h1

where h1 : R → RW and h2 : RW → R are affine, and can be written as

h1 (x) = x⃗a − ⃗b and h2 (⃗y ) = ⟨⃗c, ⃗y ⟩ + d

so
W
X
f (x) = d + cj ρ(aj x − bj ) (1.8)
j=1

the breakpoints of f are exactly the points xj which solve the equation aj x − bj and so there are at most W
such solutions in (0, 1). Thus f ∈ ΣW .
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 27

Figure 1.3: The function H ◦s for s = 1, 2, 3, 4.

In the other direction: Let g ∈ ΣW −1 . The function g has W − 1 knots 0 < k1 < k2 < . . . < kW −1 < 1.
There exist some c, d ∈ R such that g(x) = cx + d for all x ≤ k1 . We claim that there exist c1 , . . . , cW −1
such that
WX−1
g(x) = cρ(x) + d + ci ρ(x − ki )
i=1

and thus g is in Υ(W, 1). Thus, we need to show that we can select c1 , . . . , cW −1 such that
W
X −1
g̃(x) := g(x) − cρ(x) − d = ci ρ(x − ki ), ∀x ∈ [0, 1]
i=1

Note that for all selection of the ci , the functions g̃ and the function on the right hand side both have
knots at k1 , . . . , kW −1 , and are zero on [0, k1 ]. At this point we essentially repeat the argument we used in
Lemma 1.9: it is sufficient to show that for an appropriate choice of the ci , the two functions are equal on
the points k2 < k3 < . . . < kW −1 < 1. This gives us W − 1 linear equations in the ci :
    
k2 − k1 c1 g̃(k2 )
k3 − k1 k3 − k2   c2  g̃(k3 )
    
k4 − k1 k4 − k2 k4 − k3   c3  g̃(k4 )
  = 
 .. .. . .   ..   .. 
 . . .  .   . 
1 − k1 1 − k2 1 − k3 · · · 1 − kW −1 cW −1 g̃(1)

This equation has a unique solution since it is a lower diagonal matrix and all diagonal elements are non-
zero.
Problem 1.29. Give an example of a univariate CPwL function with W breakpoints that is not in Υ(W, 1).

1.4.5 Deep Univariate Neural Networks

We’ve seen in Proposition 1.28 that shallow neural networks of width W are essentially the same as free
knot CPwL splines. What happens when L > 1? The following theorem, which is a simplified version of
Theorem 3.1 in [Daubechies et al., 2021], shows that also when L > 1, we can express all functions with n
breakpoints with n ∼ n(W, L):
Theorem 1.30. [[Daubechies et al., 2021]] There exists an absolute constant C > 0, such that for every
natural W ≥ 8 and n ≥ 16 (W − 2)2 , there exists an L ∈ N satisfying

n(W, L) ≤ Cn and Σn ⊆ Υ(W, L)

NNF with exponentially many knots Interestingly, for deep networks, it is possible to express some
functions with n ≫ n(W, L) breakpoints as we will now see. The following question is in the homework:
Problem 1.31. Consider the function

2x if 0 ≤ x ≤ 1/2
H(x) = .
2 − 2x if 1/2 ≤ x ≤ 1
28 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

1. Show that H ∈ Υ(2, 1) and that the function H ◦s (the composition of H with itself s times) is in
Υ(2, L = s).

2. Define for every s ∈ N the points

1 2
k0 = 0, k1 = s
, k2 = s . . . , k2s = 1.
2 2
Show that H ◦s (x) is the unique CPwL function which is affine on each interval [kj−1 , kj ], j = 1, . . . , 2s
and satisfies 
◦s 0 if j is even
H (kj ) =
1 if j is odd

3. How many breakpoints does H ◦s have?

We call the function H the ‘hat function’. The composition of H with itself s times is called the sawtooth
function(s), or sometimes Telgarsky’s function. These are illustrated in figure 1.3. The function H ◦s are
in Υ(2, s), so the number of parameters needed to express it grows linearly in s. However it has 2s − 1
breakpoints!!!
Here is a helpful way to see how many breakpoints H has easily:

Problem 1.32. say f : [0, 1] → R is CPwL and is affine in the intervals [kj−1 , kj ] defined by the points
0 < k1 < k2 < . . . < kn < 1. Show that f ◦ H is affine in the intervals defined by the points

k1 kn 1 kn k1
0< < ... < < <1− < ... < 1 − < 1.
2 2 2 2 2
Using this argument we can compute the knots of H ◦s . The calculation of H ◦s is then reduced to finding
the value of H ◦s at these knots.

Bounding the number of breakpoints We saw that deep networks can have exponentially many break-
points. The following gives an upper bound to the number of breakpoints

Proposition 1.33. Every f ∈ Υ(W, L) has less than (W + 1)L breakpoints.

Note that this bound is not completely optimal. For example in [Raghu et al., 2017] it is shown that
every f ∈ Υ(W, L) has no more than W L breakpoints. Recall that H ◦s is in Υ(W = 2, L = s) and has
2s − 1 = W L − 1 breakpoints, so this bound is very close to optimal.

Proof. We consider functions of the form

g = ρ ◦ hL ◦ ρ ◦ . . . ◦ ρ ◦ h1 (1.9)

where h1 : R → RW and hi : RW → RW , i = 1, . . . L are affine. We denote the functions as in (1.9) by

Υ̃(W, L). We denote the maximal number of breakpoints a function in Υ̃(W, L) can have by m(L).
Note that any function f ∈ Υ(W, L) is a composition of an affine hL+1 : RW → R with a function g
as defined in (1.9). Since hL+1 is smooth hL+1 ◦ g will not have more breakpoints than g has and so it is
sufficient to prove that m(L) < (W + 1)L . We prove this by induction.
When L = 1 we have that any function of the form ρ ◦ h1 can be written as
 
ρ(a1 x + b1 )
 ρ(a2 x + b2 ) 
ρ ◦ h1 (x) = 
 
.. 
 . 
ρ(aW x + bW )

the breakpoints of this function are the solutions of the equations ai x + bi = 0, and so m(1) ≤ W < W + 1.
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 29

Now let us assume that we know for some given L that m(L) < (W + 1)L . Let g be some function in
Υ̃(W, L + 1) so g = ρ ◦ hL+1 ◦ gL where gL is in Υ̃(W, L). We get
 
ρ(⟨a1 , gL (x)⟩ + b1 )
 ρ(⟨a2 , gL (x)⟩ + b2 ) 
g(x) = 
 
.. 
 . 
ρ(⟨aW , gL (x)⟩ + bW )

A function the the form ρ(⟨ai , gL (x)⟩ + bi ) could have a breakpoint in every one of the original breakpoints
of gL . It could also have a ‘new’ breakpoint between every pair of consecutive breakpoints (if gL (ki ) > 0 and
gL (ki+1 ) < 0 or vice versa), or between 0 and the first breakpoint, or between 1 and the last breakpoint.
All in all each one of the ρ(ai gL (x) + bi ) can have up to m(L) + 1 new breakpoints, and so altogether these
functions could have up to W (m(L) + 1) new breakpoints, as well as the original m(L) breakpoints of gL .
Altogether we will have no more than W (m(L) + 1) + m(L) breakpoints. Since m(L) is an integer which is
strictly smaller than (W + 1)L we have that

m(L+1) ≤ W (m(L)+1)+m(L) = m(L)(W +1)+W ≤ (W + 1)L − 1 (W +1)+W = (W +1)L+1 −1 < (W +1)L+1

 

Summary To summarize our discussion of univariate ReLU networks: we saw that shallow neural networks
are more or less the same as free knot linear splines (Proposition 1.28). Deep networks can also express all
free knot splines with n(W, L) parameter (Theorem 1.30), however, they can also express some functions,
such as ‘sawtooth functions’, with a number of breakpoints which is exponential in L (but not all such
functions, see proof in [Dym et al., 2020] ). In general, univariate networks with width W and depth L will
have less that (W + 1)L breakpoints.
The attractiveness of the latter results as that they point to an expressive advantage of deep neural
networks over a ‘standard function base’-free knot linear splines. It also points to an advantage over shallow
neural networks- a network with depth one, or with fixed depth, would need its width to grow exponentially
with s to express the function H ◦s , rather than the linear growth we have observed. This type of results are
sometimes called ‘depth separation’ results. There are many similar arguments in various papers, see e.g.,
[Telgarsky, 2016, Eldan and Shamir, 2016].
Possible criticisms of these arguments are that the functions for which deep neural networks have an
advantage over shallow ones don’t necessarily seem to be the functions we are interested in learning. Another
argument which has been made is that highly oscillating functions such as the sawtooth function are difficult
to learn using gradient descent (see e.g., [Malach and Shalev-Shwartz, 2019, Hanin and Rolnick, 2019]). One
could also wonder to what extent the univariate case discussed here is representative of the multivariate case.
We will discuss this next.
30 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

1.4.6 Linear regions of multivariate neural networks

Up to now we have focused on counting linear region of univariate neural networks, that is, functions in

FC (W, L = 1; win = d, wout = 1)

with d = 1. We now want to focus on the case where d > 1.

In terms of counting linear regions, the main difference between multivariate and univariate networks is
that shallow multivariate networks can also have significantly more linear regions than parameters. In fact,
we are already familiar with such an example:

Example 1.34. Recall that the function x 7→ ReLU (x) which is in FC(W = d, L = 1, nin = d, nout = d),
has 2d linear regions.
The ReLU function is a linear function on each of the 2d quadrants of Rd . Formally, for every vector
s ∈ {−1, 1}d we can define the polytope

Qs = {x ∈ Rd | si xi ≥ 0, ∀i = 1, . . . , d}

The collection of all such polytopes form a polytope partition, and

  
1 + s1 0 0 ... 0 x1
 0 1 + s 0 . . . 0
2   x2 
  
1
 0 0 1 + s . . . 0 x
ReLU (x) =  3   3  , ∀x ∈ Qs . (1.10)
  
2 . .. .
0   .. 
  
 0 0 0
0 0 0 0 1 + sd xd

In the homework we saw that, if the restriction of a CPwL function f to each partition element is
a different affine function, then there is no smaller polytope partition which f is subordinate to. In our
context, since the restriction to each of the 2d polytopes Qs is a different affine function, the number of
linear regions of ReLU is exactly 2d .
The number of linear regions of shallow univariate networks is strongly related to the hyperplane ar-
rangement problem. Let us describe this problem:

Hyperplane arrangements Recall that a hyperplane in Rd is a set of the form

H = {x ∈ Rd |⟨a, x⟩ − b = 0}

where a ∈ Rd is non-zero and b ∈ R. A hyper-plane arrangement is a collection of m hyperplanes Hi in Rd ,

defined by pairs (ai , bi ) ∈ Rd \ {0} × R. Now consider the open set
m
[
U = Rd \ Hi
i=1

We’d like to ask the following question: how many connected components does U have? Note that U is a
union of a finite number of convex open sets Us with empty intersection: For every s ∈ {−1, 1}m define

Us = {x ∈ Rd |si (⟨ai , x⟩ − bi ) > 0, ∀i = 1, . . . , m}

all in all there are 2m possible choices of s, but some of the sets Us may be empty. The number of linear
regions is the number of Us which are not empty.
Example When d = 1, consider the hyperplanes Hi = {x ∈ R|x = i} for i = 1, 2, 3, 4. The set U has 5
connected components. In general we see that given m hyperplanes in R, the complement will have m + 1
connected component, unless some of the hyperplanes are equal in which case we will have less hyperplanes.

Problem 1.35. How many connected components does the complement of a hyper-plane arrangement with
m hyperplanes in Rd have when
1.4. RELU NETWORKS, CPWL FUNCTIONS AND DEPTH SEPARATION 31

1. d = 2 and m = 2.
2. d = 2 and m = 3.
Answer Could always be as little as two if all hyperplanes are taken to be the same. When d = 2, m = 2
the maximal number is four, while when m = 3 the maximal number is seven, as we shall soon see.
In general, the number of connected components in a hyperplane arrangement are given by the following
theorem (which we will not prove):
Theorem 1.36 ([Zaslavsky, 1975]). A hyperplane arrangement with m hyperplanes in Rd has at most
d  
X m
ν(d, m) := (1.11)
j=0
j

linear regions. Additionally, there are m hyperplanes in Rd with exactly ν(d, m) linear regions (in fact, this
happens for Lebesgue almost every (ai , bi ), i = 1, . . . , m. )
Remark 1.37. When d > m, the summation in (1.11) includes expressions m


j with j > m. This number
is zero by definition.
Let us consider some examples: when d = 1 we saw previously that m hyperplanes will have
   
m m
ν(1, m) = + =m+1
0 1
connected components, unless some hyperplanes are identical in which case there will be less connected
components. When d = 2 and m = 3, the maximal number of connected components will be
     
m m m
ν(2, m = 3) = + + = 1 + 3 + 3 = 7,
0 1 2
while when m = 2, d = 2 there will be only four. Finally, when m = d, there can be at most
d   d  
X m X d
ν(d, m = d) = = = 2d
j=0
j j=0
j

connected components. For example, the d hyperplanes {x ∈ Rd |xi = 0} divide Rd into 2d connected
components.
The relationship between the number of linear regions in a hyperplane arrangement and the number of
linear regions of a shallow ReLU network are given by the following proposition:
Proposition 1.38. If f ∈ FC(W, L = 1, nin = d, nout ), then f has at most
d  
X W
ν(d, W ) =
j=0
j

linear regions.
Note that the number of linear regions does not depend on nout at all.
Proof. We can write f = h2 ◦ ρ ◦ h1 . Denoting h1 (x) = Ax + b, and denoting the rows of A by a1 , . . . , aW ,
we have that  
⟨a1 , x⟩ + b1
h2 ◦ ρ(Ax + b) = h2 ◦ ρ 
 .. 
. 
⟨aW , x⟩ + bW
Denoting d = nin , we can define a polytope covering of R , indexed by s ∈ {−1, 1}W by
d

Ps = {x ∈ Rd |si (⟨ai , x⟩ + bi ) ≥ 0, i = 1, . . . , W }
32 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

and the restriction of f to each Ps is a linear function. We can remove from the partition {Ps }s∈{−1,1}W all
polytopes Ps whose interior is empty, and still remain with a partition. The number of linear regions in this
partition is exactly the number of connected components of Rd \ ∪i {x ∈ Rd | ⟨ai , x⟩ + bi = 0}. The result
then follows from Theorem 1.36.
We’ve seen that for shallow networks, the number of linear regions can grow exponentially with the
input dimension. However, it is still true that you can get much more linear regions with deep networks.
For example, while Proposition 1.38 implies that f ∈ FC(W, L, nin , nout ) will have no more than W nin + 1
linear regions when L = 1 (you will verify this for homework), when we allow L > 1 there exist f ∈
h i(L−1)nin
FC(W, L, nin , nout ) with ∼ nWin W nin linear regions (see [Montufar et al., 2014] for more details).
1.5. APPROXIMATING POLYNOMIALS AND SMOOTH FUNCTIONS 33

1 1 0.07

0.9 0.9
0.06
0.8 0.8

0.7 0.7 0.05

0.6 0.6
0.04
0.5 0.5
0.03
0.4 0.4

0.3 0.3 0.02

0.2 0.2
0.01
0.1 0.1

0 0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1

(a) (b) (c)

Figure 1.4: (a) Swift convergence of the approximations fm (x) of x2 (b) the functions f1 and f2 and (c) the function
f1 − f2 is a scaling of the sawtooth function H ◦ H.

1.5 Approximating polynomials and smooth functions

We saw that functions like the sawtooth function can be expressed with deep neural networks significantly
more efficiently than with shallow networks. We will now show how this can be leveraged to obtain similar
results for approximation of the function x2 . We will then build upon this further to approximate monomials,
polynomials, and smooth functions in general. This discussion is taken from [Yarotsky, 2017].
The sawtooth function will actually turn out to be a useful tool in our discussion. Recall that the
sawtooth function H ◦s can be implemented with width 2 and depth s despite having 2s − 1 breakpoints. It
is linear on the intervals [ki , ki+1 ] where
1 2
k0 = 0, k1 = , k2 = s . . . , k2s = 1
2s 2
and H ◦s (kℓ ) is 0 if ℓ is even and one if ℓ is odd.

1.5.1 Approximating x2
Let us consider the problem of approximating x2 with a ReLU network. In Theorem 1.11 we showed that
we can approximate a function f : [0, 1]d → R which is ℓ-Lipschitz to ϵ accuracy (uniformly on [0, 1]d ) by a
function in FC(W, L, d, 1) where
√ !d √ !
dℓ dℓ
W ≤ 4d + 1 , L ≤ ⌈log2 (d)⌉ + ⌈d · log2 ( + 1 )⌉
2ϵ 2ϵ

In particular, if we want to approximate x2 on [0, 1], we note that x2 is Lipschitz with Lipschitz constant
ℓ = 2, and we can obtain an ϵ approximation with ∼ 1/ϵ width and ∼ log(1/ϵ) depth. We now will see that
we can do much better than this. As a first step, let us consider approximations with shallow networks, or
equivalently, with functions in ΣN .
Proposition 1.39. Let gN be the unique CPwL function which satisfies gN (k/N ) = (k/N )2 for all k =
0, . . . , N , and is affine on the intervals [ k−1 k
N , N ], k = 1, . . . N . Then
 2
2 1
max |x − gN (x)| ≤
x∈[0,1] 2N
Proof. We will use the following lemma
Lemma 1.40. Let g(x) = g(x|a, b) be the linear interpolation of x2 at a, b, that is
1 
(b − x)a2 + (x − a)b2

g(x) =
b−a
then    2  2
a+b a+b b−a
max |g(x) − x2 | = g − =
x∈[a,b] 2 2 2
34 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

Proof of the Lemma. The continuous function q(x) = g(x) − x2 = g(x) − x2 is maximized and minimize at
a or b or at a point x ∈ (a, b) with q ′ (x) = 0. We have that q(a) = 0 = q(b). Solving the equation

b2 − a 2
0 = q ′ (x) = − 2x
b−a
a+b
we obtain that the derivative is zero at the midpoint 2 . At this point we have
2
a2 + b2
  
a+b a+b 1
1
q = − = 2a2 + 2b2 − a2 − b2 − 2ab = (b − a)2
2 2 2 4 4

So the minimum of q is obtained at a and b, and the minimal value of q is zero, while the maximum is
obtained at the center and the maximal values is 41 (b − a)2 . This concludes the proof of the lemma.

Returning to our definition of gN we see that

max |f (x) − gN (x)| = max max |f (x) − g(x|k/N, (k + 1)/N )

x∈[0,1] k=0,...,N −1 x∈[ k
, k+1
N N ]
 2  2
1 1
= max =
k=0,...,N −1 2N 2N

This concludes the proof of the proposition

1 2


We see that with N knots we can get an approximation of 2N . Stated differently, to achieve ϵ accuracy
1 2

1/2
we need to take N such that 2N < ϵ so N > (1/(4ϵ)) . Thus we can achieve the same approximation
rate with a univariate shallow network with width W = N + 1 and depth L = 1 by Proposition 1.28. Thus
we already get a better approximation rate than what we had from our standard Lipschitz bound (ϵ1/2 width
and parameters vs. 1/ϵ width and (1/ϵ)2 log(1/ϵ) parameters.).
We will now see that we can do much better with deep networks: denote fm = g2m : that is, fm is the
CPwL function with knots in 0, 21m , 22m , . . . , 1 and whose value at these points is
   2
k k
fm = , k = 0, 1, . . . , 2m .
2m 2m

By our previous discussion we have that

1
max |fm (x) − f (x)| ≤ .
x∈[0,1] 22m+2

This is a great approximation rate but of course the function fm have 2m knots and so expensive to compute
using free knot splines or shallow networks. However, this can be done much more efficiently with deep
networks, using the sawtooth function we studied earlier:

Lemma 1.41. Let fm denote the Piecewise linear interpolation of x2 at the points k2−m , k = 0, . . . , 2m as
defined above, and let H denote the sawtooth function, then

H ◦m (x)
fm−1 (x) − fm (x) = , ∀x ∈ [0, 1]
22m

Proof. Let us consider the difference fm−1 (x) − fm (x). This function has knots at the points 2km . The knots

2
where k is even are also knots of fm−1 and therefore at these knots fm−1 ( 2km ) = 2km = fm ( 2km ), and the
difference between the functions is zero at these points. When k is odd, we can repeat the computation we
did in Lemma 1.40: Let us denote a = k−1 k+1 k 1
2m and b = 2m , then 2m = 2 (a + b) and
     2
k k 1 2 1 1 1
fm−1 − fm = (a + b2 ) − (a + b) = (b − a)2 = 2m
2m 2m 2 2 4 2
1.5. APPROXIMATING POLYNOMIALS AND SMOOTH FUNCTIONS 35

and so altogether we have

    
k k 0 if k is even
fm−1 − fm = 1
2m 2m 22m if k is odd

This is exactly the sawtooth function H ◦m up to scaling, that is

H ◦m (x)
fm−1 (x) − fm (x) = . (1.12)
22m
An illustration of this result is shown in Figure 1.4.
Applying (1.12) recursively, we obtain (note that f0 (x) = x)
m
X H ◦s (x)
fm (x) = f0 (x) + (f1 (x) − f0 (x)) + . . . + (fm (x) − fm−1 (x)) = x −
s=1
22s

We can summarize our results as follows

Theorem 1.42. There exists some natural numbers W0 , L0 , such that the function f (x) = x2 can be ap-
proximated to ϵ accuracy in [0, 1] with a NNF in Υ(W0 , L0 log(1/ϵ))

Remark Recall that a network with width W and depth L has ∼ W 2 L parameters, so the total number
of parameters is linear in log(1/ϵ).
1
Proof. We saw that fm (x) approximate x2 with an error rate of 22m+2 , and we can reorder (1.12) to obtain
H ◦s
fs = fs−1 − 22s , and so we can recursively define

H(x) F2 H ◦2 (x) F3 Fm−1 H ◦m−1 (x)

         
y H(y)
x7→ 7→ 7→ . . . 7→ 7→ fm (x), where Fs =
f0 (x) f1 (x) fm−1 (x) z z − y/22s

which shows that fm can be constructed with a neural network with fixed width W0 and depth mL0 . To
obtain ϵ accuracy we need to have
2−2m−2 < ϵ
or equivalently  
1
m > 1/2 log2 −1
ϵ
so we can choose m = 1/2 log2 (1/ϵ) to get width and depth as required by the theorem.
36 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

New Lesson
1.5.2 Approximating multiplication
An important consequence of the previous result is that the product function (x, y) 7→ xy can also be
approximated by neural networks with exponential accuracy: in general, this can be done by noting

1
(x + y)2 − x2 − y 2


xy =
2

and then using our approximation of the squaring function. Recall that our approximation of x2 was obtained
on [0, 1]. We will want to obtain approximation for xy on [−M, M ]2 . To do this note that we can rewrite
the previous equation as
2  2  2 !
M2

|x + y| |x| |y|
xy = − − . (1.13)
8 2M 2M 2M

The advantage of this is that we are now applying the squaring function to inputs in the interval [0, 1].

Proposition 1.43. There exists (W1 , L1 ) ∈ N2 , such that for all M > 0 and ϵ > 0, there is an NNF
N N× : R2 → R satisfying

1. for all x, y with |x|, |y| < M we have |N N× (x, y) − xy| < ϵ.

2. if x = 0 or y = 0 then N N× (x, y) = 0.

3. N N× is in FC(W1 , L1 (1 + log(1/ϵ) + log(M )), 2, 1).

Proof. Choose some ϵ > 0 and M > 0. Recall that there exists (W0 , L0 ) ∈ N2 such that for all ϵ̃ > 0 there
exists s ∈ FC(W0 , L0 log(1/ϵ̃), 1, 1) such that |s(x) − x2 | < ϵ̃ for all x ∈ [0, 1]. Now set

8ϵ
ϵ̃ = .
3M 2

and let s be the function in FC(W0 , L0 log(1/ϵ̃), 1, 1) such that |s(x) − x2 | < ϵ̃. We replace the squares in
(1.13) with s to obtain the function

M2
      
|x + y| |x| |y|
N N× (x, y) := s −s −s
8 2M 2M 2M

We can verify directly that this function satisfied (1) due to (1.13), satisfies (2) since s(0) = 0, and satisfies
(3) as N N× is in FC(W1 , L1 (1 + log(1/ϵ) + log(M )), 2, 1) and

|z| = ρ(z) + ρ(−z)

is a network of depth 1 and width 2.

We can think of this result as follows: up to now we knew that if f, g were NNFs then we can take linear
combinations of them and get another NNF. We can also concatenate or take compositions and get an NNF.
This result means that the same is almost true for the product f · g. While we cannot exactly express f · g
as an NNF, we can approximate it extremely well.
We now prove a similar lemma for the multi-dimensional product function

Proposition 1.44. For every s ∈ N there exist W2 = W2 (s), L2 = L2 (s) such that for every 1 > ϵ > 0,
there exists a function m ∈ FC(W2 , L2 (1 + log(1/ϵ)), din = s, 1) with

|x1 · x2 · . . . · xs − m(x)| < ϵ, ∀x = (x1 , . . . , xs ) ∈ [0, 1]s

1.5. APPROXIMATING POLYNOMIALS AND SMOOTH FUNCTIONS 37

Proof. For given ϵ > 0, let N N× be the function promised by Proposition 1.13 with respect to the parameters
ϵ̃ = ϵ/(s − 1) and M = 2. Define recursively the functions

m1 (x) = x1 , m2 (x) = N N× (m1 (x), x2 ), p3 (x) = N N× (m2 (x), x3 ) ..., ms (x) = N N× (ms−1 (x), xs ).

We can think of each mk as an approximation of the product of the first k entries of x and m := ms is the
final approximation we need. Note that we can apply Proposition 1.43 recursively to see that:
Since for all x ∈ [0, 1]s we have that |m2 (x) − x2 · m1 (x)| < ϵ̃ and both x2 and m1 (x) = x1 are in [0, 1],
we deduce that |m2 (x)| < 1 + ϵ̃ < 1 + 1/(s − 1) < 2.
Since |m2 (x)| < 2 we know that for all x ∈ [0, 1]s we have |m3 (x) − x3 (x)m2 (x)| < ϵ̃, and therefore
|m3 (x)| < 1 + 2/(s − 1) < 2
continuing recursively with this process we see that for all j = 1, . . . , s − 1,

|ms+1 (x) − xs+1 ms (x)| < ϵ̃.

Using this we can see that the error of the approximation m = ms is bounded for all x ∈ [0, 1]s by

|x1 · . . . · xs − ms (x) ≤ |ms (x) − xs ms−1 (x)| + |xs ms−1 (x) − xs xs−1 ms−2 (x)| + . . .
+ |xs xs−1 . . . x3 m2 (x) − xs xs−1 . . . x2 m1 (x)|
s−1
X
≤ |mi+1 (x) − xi+1 mi (x)|
i=1
≤ (s − 1)ϵ̃ = ϵ

A simple way to construct ms as a neural networks is through the architecture

     
m1 (x) = x1 m2 (x) = N N× (m1 (x), x2 ) m3 (x) = N N× (m2 (x), x3 )
 x2   x3   x4 
x 7→  →
7 →
7  . . . 7→ ms (x)
     
..   ..   ..
 .   .   . 
xs xs xs

The width of this construction does not depend on ϵ and the depth is proportional to s log(1/ϵ̃) = s log(s −
1) + s log(1/ϵ).

1.5.3 Approximation of univariate smooth functions

We now consider approximation of functions from the function space

Fn = {f : [0, 1] → R| |f (k) (x)| ≤ 1, k = 0, . . . , n and x ∈ [0, 1]}.

We will prove the following

Theorem 1.45. Let n ∈ N. There exist W = W (n), L = L(n) such that for every ϵ ∈ (0, 1) and every
f ∈ Fn , there exists f˜ ∈ FC(W, L(1 + (1/ϵ)1/n log(1/ϵ)), din = 1, dout = 1) with

|f (x) − f˜(x)| < ϵ, ∀x ∈ [0, 1]

Remark 1.46. Note that this result can be used, in a sense, for any n times continuously differentiable f :
since the derivatives are continuous they are bounded on a bounded interval, and so there will be some M
for which
|f (k) (x)| ≤ M, ∀k = 0, . . . , n and x ∈ [0, 1].
We then have that M 1
f is in Fn . If we use the theorem to obtain a neural network f˜ which approximates
1 ϵ ˜
M f to within an error of M , then M f will approximate f to within an error of ϵ.
38 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

The idea of this proof is as following: we first consider approximation of f by a function space of ‘piecewise
polynomials’, and then use what we showed so far to efficiently approximate these piecewise polynomials.
Let us first define our piecewise polynomials. Assume that for some given N , we are given an N -partition
of unity: this term we will use to mean a collection of functions ϕ0 , . . . , ϕN : [0, 1] → R which are non-negative
and satisfy
XN
ϕj (x) = 1, ∀x ∈ [0, 1] and ϕj (x) = 0 if |x − j/N | < 1/N
j=0

One example of such a partition which is useful for us are the CPwL functions ϕj defined by the require-
ment that they are linear on the intervals [k/N, (k + 1)/N ] for all k = 0, . . . , N − 1, and satisfy

1 if k = j
ϕj (k/N ) =
0 ̸ j
if k =
PN
clearly these functions are non-negative, are zero where they should be, and since j=0 ϕj (x) = 1 for
x = 0, 1/N/2/N, . . . , 1, and is affine between these points, we see that this equality holds for all x ∈ [0, 1].

Proposition 1.47. For any n ∈ N, there exists some C = C(n) such that for every ϵ > 0 and every f ∈ Fn
there exists N ≤ 1 + C(n)ϵ−1/n polynomials p0 , p1 , . . . , pN of degree ≤ n such that

N
X
|f (x) − ϕj (x)pj (x)| < ϵ, ∀x ∈ [0, 1]
j=0

Proof. Assume we are given n, given f ∈ Fn and given ϵ > 0. Assume we pick some N . For given
j = 0, . . . , N , we define pj to be the Taylor expansion of order n − 1 of f around j/N . Then we know that
for all x ∈ [0, 1] with |x − j/N | ≤ 1/N , there exists some c ∈ [0, 1] such that

1 1
|f (x) − pj (x)| ≤ (x − j/N )n f (n) (c) ≤ (1/N )n
n! n!

We want the expression on the right hand side to be smaller than ϵ, which equivalently means
 1/n
1
N≥ .
ϵn!

For such a value of N we get for all x ∈ [0, 1] that

N
X N
X
|f (x) − ϕj (x)pj (x)| = | ϕj (x)(f (x) − pj (x))|
j=0 j=0
N
X
≤ ϕj (x)|f (x) − pj (x)| ≤ ϵ
j=0

We see that functions in Fn can be approximated to ϵ accuracy with N ∼ (1/ϵ)1/n polynomials of degree
≤ n − 1. All in all this function space is spanned by nN ∼ C(n)(1/ϵ)1/n parameters.
We now turn to prove Theorem 1.45, where we see that we can do almost as well with neural networks.
The idea behind this claim is as follows: the construction we just saw is based on products of functions we can
easily build with neural networks: they are a product of hat functions with polynomials, which themselves
are linear combinations of products of linear functions. Since we known how to swiftly approximate products,
we can successfully ‘imitate’ the approximation we just saw with neural networks.
1.5. APPROXIMATING POLYNOMIALS AND SMOOTH FUNCTIONS 39

Proof of Theorem 1.45. For given ϵ > 0, let N < C21/n (1/ϵ)1/n be such that the piecewise polynomials
PN
P (x) := j=0 ϕj (x)pj (x) defined in Proposition 1.47 are an ϵ/2 approximation of f . We can rewrite P as

N n−1
X X
P (x) = aj,k ϕj (x)(x − j/N )k
j=0 k=0
| {z }
Pj,k (x)

and note that since we took pj to be the Taylor expansion of f at j/N and the derivatives of f are bounded
by 1, we have that |aj,k | ≤ 1. We will show that we can approximate each Pj,k with a neural network
hj,k up to accuracy of ϵ̃ = 2n(Nϵ +1) . For fixed j, k, we know from Proposition 1.44 that there is some
mk+1 ∈ FC(W2 , L2 (1+log(1/ϵ̃)+log(k+1)), din = k+1, 1) which can approximate the function x1 x2 . . . xk+1
to accuracy of ϵ̃. We thus have that
 
j j j
|Pj,k (x) − mk+1 ϕj (x), x − , x − , . . . , x − | ≤ ϵ̃
N N N
| {z }
hj,k

and hj,k can be written as

 
ϕj (x)
(x − j/N ) 
j j j

x 7→   7→ mk+1 ϕj (x), x − , x − , . . . , x − = hj,k (x)
 
..
 .  N N N
(x − j/N )

which is a neural network with width independent of ϵ̃ and depth logarithmic in 1/ϵ̃ and hence in 1/ϵ. We
PN Pn−1
can the approximate f by h = j=0 k=0 aj,k hj,k (x) with error

N n−1
X X
|f (x) − h(x)| ≤ |f (x) − P (x)| + |P (x) − h(x)| ≤ ϵ/2 + |aj,k ||Pj,k (x) − hj,k (x)|
j=0 k=0
N n−1
X X
≤ ϵ/2 + ϵ̃ = ϵ.
j=0 k=0

The network h is a sum of (N + 1)n ∼ (1/ϵ)1/n networks hj,k with fixed width W and depth proportional to
log(1/ϵ). In the homework you will show that this addition can be done with fixed width and depth which
grows like (N + 1)n. This concludes the claim.

1.5.4 Additional results

Approximation of multivariate smooth functions The paper [Yarotsky, 2017] focuses on the more
general case of multivariate smooth functions. The function class Fd,n it discusses is functions f : [0, 1]d → R
which have continuous partial derivatives of order ≤ n all bounded by one. The construction
PN used in this
case the story is similar to the 1D case: the function f is approximated by expression j=1 ϕj (x)pj (x) where
pj are multivariate polynomials of degree ≤ n − 1 and ϕj is a partition of unity supported on sets with small
diameter δ. The number of parameters in this construction is ∼ (1/ϵ)d/n , that is, it increases exponentially
with the dimension and decreases exponentially with the smoothness, a known phenomena in approximation
theory. Thus the ‘curse of dimensionality’ can be countered by smoothness. Neural network approximation
in the multidimensional case again performs similarly to the piecewise polynomials up to a logarithmic factor
∼ (1/ϵ)d/n (1 + log(1/ϵ)).
‘Super approximation’ of univariate functions For the function space F1,1 = F1 the theorem we
saw guarantees ϵ approximation with ∼ (1/ϵ) parameters. However [Yarotsky, 2017] showed that this can be
improved to ∼ (1/(ϵ log(1/ϵ)) and this was later improved even further to ∼ 1/ϵ2 (see [DeVore et al., 2021].
Theorem 8.11). More generally, in [Lu et al., 2021] it is shown that approximation of functions on a d-
40 CHAPTER 1. FULLY CONNECTED NEURAL NETWORKS

d
dimensional cube [0, 1]d with s derivatives can be obtained with ∼ (1/ϵ) 2s (up to logarithmic factors). We
stress that unlike the previous results where neural networks achieved slightly worse rates than piecewise
polynomials, these rates are actually better than what piecewise polynomials and other standard function
bases can do...
Chapter 2

Invariant Learning and

Approximation Theory

2.0.1 Preliminaries
Definition 2.1 (Group). A pair (G, ·), where G is a set and · : G × G → G is called a group if
1. Associativity For all a, b, c ∈ G,
(a · b) · c = a · (b · c)
.

2. Identity There exists an element e ∈ G such that

a · e = a = e · a, ∀a ∈ G.

3. Inverse element For every a ∈ G there exists some element b ∈ G such that

a · b = e = b · a.

We denote b by a−1 .
Examples: The pair (Rn×n , +) is a group whose identity element is the zero matrix. The pair (Rn×n , ·)
is not a group (where · denotes matrix multiplication). The pair (GL(n)), ·) is a group whose identity element
is the identity matrix In , where
GL(n) = {A ∈ Rn×n | det(A) ̸= 0}
A subgroup of (G, ·) is a group (H·) with the same operation ·, and where H is a subset of G. Subgroups of
GL(n) include

O(n) = {R ∈ Rn×n | RRT = In }

SO(n) = {R ∈ Rn×n | RRT = In , det(R) = 1}
SL(n) = {A ∈ Rn×n | det(A) = 1}

The set of bijections from [n] := {1, . . . , n} to [n] is denoted by Sn . The bijections are called permutations.
They are a group with respect to composition.

41
42 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

New Lesson
Remark 2.2. In the following we will use the convention that a vector v ∈ Rn is actually a degenerate matrix
v ∈ Rn×1 (a ‘column vector’). This allows expressing all vector operations in terms of matrix multiplication.
For example the inner product of two vectors v, u ∈ Rn is given by

⟨v, u⟩ = v T u.

The matrix v T ∈ R1×n is called a ‘row vector’.

We will also use the notation

1n = (1, . . . , 1)T and 1n×n = 1n 1Tn

for the n by 1 and n by n all-one matrices.

Definition 2.3 (Group Action). Let (G, ·) be a group with an identity element e, and let S be a set. We
say that ρ : G × S → S is a group action if
1. For all s ∈ S,
ρ(e, s) = s.

2. for all g, h ∈ G and s ∈ S we have

ρ(g, ρ(h, s)) = ρ(g · h, s)

Remark 2.4. We will use the notation

g. s = ρ(g, s).
With this notation the requirements of a group action can be written more conveniently as

e.s = s and g.(h.s) = (g · h).s

Example: A natural attempt to define a group action of Sn on Rn would be

[σ.x]i = xσ(i) , σ ∈ Sn , x ∈ Rn , i = 1, . . . , n.

However as it turns out this is not a group action in our definition because

[τ.(σ.x)]i = [σ.x]τ (i) = xσ◦τ (i)

which generally may not be equal to

[(τ ◦ σ). x]i = xτ ◦σ(i)
The correct way to define a group action of Sn on Rn is via the group action

[σ.x]i = xσ−1 (i) , ∀σ ∈ Sn , x ∈ Rn , i = 1, . . . , n

Note that
[σ.(τ.x)]i = [τ.x]σ−1] (i) = xτ −1 ◦σ−1 (i) = x(σ◦τ )−1 (i) = [(σ ◦ τ ).x]i
Example Similarly, we can define an action of Sn on Rd×n by

[σ(X)]ij = Xiσ−1 (j)

Definition 2.5. Let G be a group acting on a set S. The orbit of s ∈ S is denoted by [s] and is defined as
the set of all element in S related to s by a group transformation, that is

[s] = {g.s| g ∈ G}.

We denote s ∼ s′ if [s] = [s′ ]. One can verify that this is an equivalence relation. The collection of all orbits
is denoted by S/G.
 43

Example 2.6. The group G = {−1, 1} acts on R by multiplication. We have that [x] = [y] if and only if
|x| = |y|, so we can identify R/G with [0, ∞).
Example 2.7. The group of permutations G = Sn acts on Rd×n as described above. We have that

X = (x1 , . . . , xn ) ∼ Y = (y1 , . . . , yn )

if and only if
(x1 , . . . , xn ) = (yσ(1) , . . . , yσ(n) ). (2.1)
This means that we have equality as sets:

{x1 , . . . , xn } = {y1 , . . . , yn } (2.2)

The converse is not completely true. For example, in the case d = 1 if we choose

x1 = 1, x2 = 1, x3 = 2 and y1 = 1, y2 = 2, y3 = 2

Then we will have equality in (2.2) but not in (2.1). This can be remedied by introducing the concept
of ‘multisets’, where order does not matter (like with sets) but repetitions are allowed (unlike sets). For
multisets (denoted by double curly brackets) we will have that

{{1, 1, 2}} ̸= {{1, 2, 2}}

and in general we will have that (2.1) if and only if we have the corresponding multiset equality

{{x1 , . . . , xn }} = {{y1 , . . . , yn }}.

Definition 2.8. Let G be a group acting on a real vector space V . We say that the action σ : G × V → V
is linear if for all g ∈ G the map V ∋ v 7→ g.v ∈ V is linear
Example 2.9. The group Rd acts on Rd×n via

g. (x1 , x2 , . . . , xn ) = (x1 + g, x2 + g, . . . , xn + g), ∀g ∈ Rd , (x1 , . . . , xn ) ∈ Rd×n .

For g ̸= 0 the map g : Rd×n → Rd×n is not linear as

g. (0 + 0) = g. (0) ̸= 2g = g. (0) + g. (0).

The group O(d) acts on Rd×n via matrix multiplication R. X = RX. Clearly this action is linear.
Example 2.10 (Multisets). The action of Sn on Rn is linear: for every σ ∈ Sn and x, y ∈ Rn and λ ∈ R we
have
(σ. (λx))j = (λx)σ−1 (j) = λ(x)σ−1 (j) = λ(σ. (x))j
and
(σ. (x + y))j = (x + y)σ−1 (j) = xσ−1 (j) + yσ−1 (j) = (σ. x)j + (σ. y)j

Matrix notation Since the action of σ ∈ Sn on vectors in Rn is linear, there is some matrix Pσ ∈ Rn×n
satisfying
σ(x) = Pσ x, ∀x ∈ Rn .
We can find P = Pσ explicitly by noting that for all i and j

1 if j = σ −1 (i)
 
1 if σ(j) = i
Pij = [P ej ]i = (σ(ej ))i = (ej )σ (i) =
−1 =
̸ σ −1 (i)
0 if j = 0 ̸ i
if σ(j) =

A matrix P induced by a permutation σ is called a permutation matrix. Note that P ∈ Rn×n is a

permutation matrix if and only if Pij ∈ {0, 1} for all 1 ≤ i, j ≤ n and each row and column of P has exactly
one non-zero entry. In particular we have that the rows and columns of P sum to one, or in other words
44 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

P 1n = 1n and 1Tn P = 1Tn . We also see that the columns of P form an orthonormal basis, and therefore P is
a unitary matrix.
Since the action of permutations is a well-defined group action we deduce that Pτ ◦σ = Pτ Pσ because

Pτ ◦σ x = (τ ◦ σ). x = τ. (σ. (x)) = Pτ σ. (x) = Pτ Pσ x, ∀x ∈ Rn

and if Ax = 0 for all x then A = 0 (verify).

So far we have described the action of Sn on Rn . The corresponding action on Rd×n can be written as
(for a permutation σ ∈ Sn and X ∈ Rd×n , using Xi∗ to denote the i-th row of X)

X1∗ PσT
   
σ. (X1∗ )
σ. (X2∗ ) X2∗ PσT 
σ. (X) =   =  ..  = XPσT
   
..
 .   . 
σ. (Xd∗ ) Xd∗ PσT

Definition 2.11 (Invariant). Let (G, ·) be a group, let S, T be sets, and ρ : G × S → S a group action . We
say that f : S → T is invariant if
f (ρ(g, s)) = f (s), ∀g ∈ G, s ∈ S

Example: P The function ∥x∥ is invariant with respect to the action of both O(n) and Sn on Rn . The
functions x 7→ i xi is Sn invariant but not O(n) invariant.

Problem 2.12. Is there a function f : Rd×n → R which is SO(d) invariant but not O(d) invariant? Is there
a function which is O(d) invariant and not SO(d) invariant?

Definition 2.13 (Intertwining). Let (G, ·) be a group, let S be a set, and ρ : G × S → S a group action .
We say that f : S → S is intertwining if

f (ρ(g, s)) = ρ(g, f (s)), ∀g ∈ G, s ∈ S

Example The function f (x) = ∥x∥x is O(d) intertwining because

f (Rx) = ∥Rx∥Rx = R (∥x∥x) = Rf (x)

Definition 2.14 (Equivariant). Let (G, ·) be a group, let S1 , S2 be sets, and ρi : G × Si → Si , i = 1, 2 be

group actions. We say that f : S1 → S2 is equivariant if

f (ρ1 (g, s)) = ρ2 (g, f (s)), ∀g ∈ G, s ∈ S

Examples If we take S1 = S2 and ρ1 = ρ2 then we get an intertwining map. If we take ρ2 to be the

trivial action ρ2 (g, s) = s we get an invariant map.
Here is an example which is neither intertwining nor invariant. O(d) acts on Rd×n by ρ1 (R, X) = Rx
and on Rd×d via ρ2 (R, Y ) = RY RT . The mapping f (X) = XX T is equivariant because

f (ρ1 (R, X)) = f (RX) = (RX)(RX)T = RXX T RT = ρ2 (R, f (X)).

The following proposition is very useful for the construction of equivariant neural networks, since it means
that we can construct equivariant networks by compositions of equivariant functions.

Proposition 2.15. Let (G, ·) be a group acting on S1 , S2 , S3 through group actions ρ1 , ρ2 , ρ3 respectively. If
f1 : S1 → S2 and f2 : S2 → S3 are equivariant then f2 ◦ f1 is equivariant.

Proof. For every g ∈ G, s ∈ S1 we have

f2 ◦ f1 (ρ1 (g, s)) = f2 (ρ2 (g, f1 (s)) = ρ3 (g, f2 ◦ f1 (s))

 45

2.0.2 Permutation equivariance for multisets

We will now focus for a while on construction of permutation equivariant networks for multisets and their
theoretical properties. As described above, multisets can be identified with the orbit of a matrix element
X = (x1 , . . . , xn ) ∈ Rd×n with respect to the action of the permutations Sn on Rd×n as described above

(σ(X))ij = Xiσ−1 (j)

In geometric applications d = 3 and X is a discretization of a 3D object. In this context it is often called a

point cloud. Among the first papers to address such data was the famous PointNet paper [Qi et al., 2017].
The paper builds an architecture for point clouds which is permutation equivariant/invariant. It also gives
a more ad-hoc solution for rigid motions which we will not discuss.
PointNet’s strategy to construct permutation equivariant functions can be seen as a simple generalization
of fully connected neural networks: recall that neural networks are functions of the form

hL+1 ◦ ρ . . . h2 ◦ ρ ◦ h1 (2.3)

where ρ could be ReLU or any other elementwise activation function, and the hi are affine functions. The
point net architecture has the same structure, where

hi : Rci−1 ×n → Rci ×n

are linear affine functions applied pointwise

hi (x1 , . . . , xn ) = (A(x1 ) + b, . . . , A(xn ) + b) = AX + b1Tn

where A = Ai is a matrix in Rci ×ci−1 and b ∈ Rci . Clearly each hi are equivariant with respect to the action
of the permutation group: if P is a permutation matrix then using the fact that P T is also a permutation
matrix and that 1Tn P = 1Tn for every permutation matrix, we obtain

hi (XP T ) = AXP T + b1Tn = (AX + b1Tn )P T = hi (X)P T

The activation function ρ could be any function ρ : R → R which is extended to a mapping ρ : Rci ×n →
ci ×n
R by elementwise application (ρ(X))ij = ρ(Xij ). This map is clearly equivariant=intertwining because
for every permutation τ we have that

(τ ◦ ρ(X))ij = ρ(X)iτ −1 (j) = ρ(Xiτ −1 (j) ) and (ρ ◦ τ (X))ij = ρ(τ X)ij = ρ(Xiτ −1 (j) )

Thus by Proposition 2.15 functions obtained by composition of these pointwise applied functions as in
(2.3) are permutation equivariant functions from Rc0 ×n to RcL+1 ×n .
To obtain a permutation invariant function PointNet uses the permutation invariant ‘max pooling’: a
permutation invariant function on Rd×n (in our case d = cL+1 ) is given by applying the maximum function
row-wise (we call this function maxrow )
   
X11 X12 . . . X1n max[X11 , X12 , . . . , X1n ]
X21 X22 . . . X2n  max[X21 , X22 , . . . , X2n ]
maxrow  . = .
   
.. ..
 .. .   . 
Xd1 Xd2 ... Xdn max[Xd1 , Xd2 , . . . , Xdn ]

A popular permutation invariant alternative is ‘sum pooling’ where the maximum over each row is replaced
by summation over each row. After pooling was applied and an invariant function was achieved, the function
is composed with a standard fully connected network. To summarize, the PointNet architecture includes
functions of the form

Hpointnet = {f (maxrow (h(x1 ), h(x2 ), . . . , h(xn )))|h : Rd → Rm , and f : Rm → Rnout are neural networks}
(2.4)
Specifying the hyper-parameters d, n, m, nout determines a function space Hpointnet . In implementation we
take f and h to be neural networks with prescribed width and depth.
46 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

Deep sets and characterization of linear equivariant functions In Deep Sets [Zaheer et al., 2017]
the authors suggested that, since we are looking for expressions of the form (??), where the hi are linear
(actually affine) equivariant functions, we might as well look for all possible linear equivariant functions.
We now turn to characterize all linear permutation equivariant functions, first from Rn → Rn and then
′
eventually from Rc×n to Rc ×n .

Problem 2.16. Find linear mappings L : Rn → Rn which are intertwining with respect to the action of Sn .

Solution: The map In (v) = v is intertwining because

In (σ. v) = σ. (v) = σ. (In (v)), ∀v ∈ Rn , σ ∈ Sn

Similarly the linear map  

n
X
S(x) = 1n 1Tn x =  xj  1n
j=1

is intertwining because for every permutation σ and corresponding permutation matrix P = Pσ

σ. (S(x)) = σ(1n 1Tn x) = P 1n 1Tn x = 1n 1Tn x = 1n 1Tn P x = S(σ. x)

Finally, we note that the space of intertwining linear mappings

L = {A ∈ Rn×n | APσ = Pσ A ∀σ ∈ Sn }

is a linear subspace of Rn×n . It follows that linear combinations of In and S = 1n×n are intertwining. We
will now see that these are the only linear intertwining maps.

Proposition 2.17. L : Rn → Rn is a linear mapping which is intertwining with respect to the action of Sn ,
if and only if it is of the form
L = αIn + β1n×n

Remark: Equivalently, linear equivariant mappings L : Rn → Rn are of the form

n
!
X
L(x) = αx + β xi 1n
i=1

Proof. In our previous discussion we saw that any linear combination of In and 1n×n is intertwining. We
now prove the reverse:
Assume L is linear and intertwining, we need to show that Lii = L11 and Lij = L12 for all 1 ≤ i ≤ n, 1 ≤
j ≤ n with i ̸= j.
For given j, let σ be the transposition of j and 1 (the permutation that swaps between j and 1 and fixes
all other indices) and let P = Pσ . So P ej = e1 and P e1 = ej . Then

Ljj = ⟨ej , Lej ⟩ = ⟨ej , LP e1 ⟩ = ⟨ej , P Le1 ⟩ = ⟨P T ej , Le1 ⟩ = ⟨P T P e1 , Le1 ⟩ = ⟨e1 , Le1 ⟩ = L11 .

Moreover, if a ̸= b we can define σ with σ(1) = a, σ(2) = b. Let P denote the corresponding permutation
matrix. Then
P (ea ) = e1 , P (eb ) = e2
and we get

L1,2 = ⟨e1 , Le2 ⟩ = ⟨e1 , LP eb ⟩ = ⟨e1 , P Leb ⟩ = ⟨P T e1 , Leb ⟩ = ⟨P T P ea , Leb ⟩ = ⟨ea , Leb ⟩ = La,b

Now that we characterized all linear equivariant functions from Rn to Rn , we discuss how to handle
several copies of Rn :
 47

Proposition 2.18. A function L : Ra×n → Rn is linear and equivariant with respect to the action of Sn , in
and only if it is of the form
X a
L(X) = L(i) (Xi,∗ ) (2.5)
i=1
(i) n n
where each L : R → R is linear and intertwining.

Remark: Note that for convenience of notation we allow L to be applied to row vectors instead of
column vectors.
Remark: Equivalently, linear equivariant mappings L : Ra×n → Rn are of the form
 
Xa a
X Xn
L(X) = αi (Xi∗ )T + βi  Xij  1n
i=1 i=1 j=1

Proof. First assume that L is of the form (2.5). We need to show that for all X ∈ Ra×n and permutation σ

L(σ. X) = σ. (LX)

Indeed
a a a a
!
X X X X
(i) (i) (i) (i)
L(σ. X) = L ((σ. X)i,∗ ) = L (σ. (Xi,∗ )) = σ. L (Xi,∗ ) = σ. L (Xi,∗ ) = σ. L(X)
i=1 i=1 i=1 i=1

where we used the fact that permutation of L is equivalent to permuting each of the rows.
In the other direction, Assume L : Ra×n → Rn is linear and equivariant. The linearity implies that L
can be decomposed as
Xa
L(X) = L(i) (Xi,∗ )
i=1

where each L(i) is linear. We need to show that each L(i) is also equivariant. Due to the equivariance of L,
we have for all permutations σ, for all x ∈ Rn and for every X whose j-th row is xT and all other rows are
zero
σ. (L(j) xT ) = σ. (LX) = L(σ. (X)) = L(j) (σ. (xT ))
and so each L(j) is equivariant and we are done.

New Lesson
Finally we have

Proposition 2.19. L : Ra×n → Rb×n is a linear mapping which is equivariant with respect to the action of
Sn , if and only if it is of the form  
L(1)
L(2) 
L= . 
 
 .. 
L(b)
a×n n
where L(i) : R → R is linear and equivariant.

Proof. L is linear if and only if  

L(1)
L(2) 
L= . 
 
 .. 
L(b)
48 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

where each L(i) are linear. Moreover by equivariance of L we have that

   
σL(1) (X) L(1) (σX)
σL(2) (X) L(2) (σX)
= σL(X) = L(σX) =
   
 ..   .. 
 .   . 
σL(b) (X) L(b) (σX)

which shows that each L(i) is equivariant.

Remark: Piecing all of this together, linear equivariant mappings L : Ra×n → Rb×n are of the form
P   
a (1) Pa (1) Pn T
α Xi∗ + β j=1 ij 1n
X
 i=1 i i=1 i

L(X) = 
 .. 
P .   

a (b) Pa (b) Pn T
i=1 αi Xi∗ + i=1 βi j=1 Xij 1n

We denote the space of all such mappings by L(n, a, b). Note that this space is determined by 2a · b
parameters. In contrast, Pointnet considers only functions of the form X = (x1 , . . . , xn ) 7→ (Ax1 , . . . , Axn )
(j)
where A ∈ Rb×a . This functions space has a · b parameters which correspond to choosing all βi = 0.
The deep set architecture, like the point net architecture, consist of functions of the form

hL+1 ◦ ρ . . . h2 ◦ ρ ◦ h1 (2.6)

where the linear part of hi : Rdi−1 ×n → Rdi ×n is in L(n, di−1 , di ). This ensures that all such functions are
permutation equivariant.

2.0.3 Equivariant Universality

In Chapter 1 we discussed universality of fully connected neural networks and more refined approximation
properties. We now discuss the notion of equivariant universality which is the analogue of universality for
equivariant networks.
Assume that we have a function class H which consists of continuous functions h : V1 → V2 which are all
equivariant with respect to the actions ρ1 , ρ2 of G on V1 and V2 (these are defined in order to learn a function
f with the same equivariant structure). We say that H is Equivariantly Universal if for any K ⊆ V1 , any
continuous equivariant f : V1 → V2 can be approximated uniformly in K by functions h ∈ H. Invariant
universality is the special case where the action ρ2 is trivial ρ2 (g, x) = x. In the course we will only discuss
the invariant case.
We now begin by discussing a general methodology for proving invariant universality, and then move
on to consider universality of the pointnet architecture defined above (with sum pooling though, and not
max-pooling).

2.0.4 Separating Invariants and Universality

Definition 2.20. Let G be a group acting on a set V . We say that α : V → Rm is a separating invariant
mapping if

1. Invariance α is invariant, that is if w, v ∈ V and w ∼ v then

α(v) = α(w).

2. Separation If α(v) = α(w) then w ∼ v.

We will sometimes say that the functions α1 , . . . , αm are invariant and separating, instead of saying that
α is invariant and separating.
 49

Example 2.21. Consider the action of O(1) = {−1, 1} on R. The mapping α(x) = x2 is invariant and
separating .
Similarly for the action of O(d) on Rd the mapping α(x) = ∥x∥ is invariant and separating (see that you
know why). Can you think of any other invariants for this group action?

For the action of O(d) on Rd×n is the mapping

α(x1 , . . . , xn ) = (∥x1 ∥, . . . , ∥xn ∥)

invariant and separating ? What about the mapping α(X) = X ?(the first is not separating, the second is
not invariant).
If α is invariant then F ◦ α is invariant as well. The next theorem show that when α is separating these
are in fact all possible invariants

Proposition 2.22. Let G be a group acting on a set V and let α : V → Rm be a separating invariant
mapping. A function f : V → R is G-invariant if and only if there exists some F : Rm → R such that

f (x) = F (α(x)). (2.7)

Proof. The invariance of α means that we can define a function α̃[v] = α(v) on the quotient space V /G
and this definition does not depend on the choice of the representative in the orbit [v]. Similarly, since f is
invariant there exists f˜ : V /G → R with
f˜([v]) = f (v).
The fact that α is separating implies that α̃ is injective, so for all v ∈ V

f (v) = f˜[v] = f˜ ◦ α̃−1 ◦α̃[v] = F ◦ α(v). (2.8)

| {z }
F

Note that f ◦ α̃−1 is defined on α(V ) and we think of F is some extension of this function to all of Rm .

Typically our invariant functions f and α are continuous, and we would like to say that the function F
in Proposition 2.22 is also continuous. This is indeed the case once we add some minor assumptions:

Proposition 2.23 (Without proof). Let G be a group acting on a metric space V , and let α : V → Rm be a
continuous separating invariant mapping. For every continuous G-invariant function f : V → R and every
compact K ⊆ V , there exists some continuous F = FK : Rm → R such that

f (x) = F (α(x)), ∀x ∈ K. (2.9)

Sketch of proof. The proof is simple but relies on some facts from topology which are not in the course’s
prerequisites, and can be found in [Munkres, 2000]. The general idea is that under the standard definition
of the quotient topology for V /G, the maps α̃, f˜ defined as in the previous theorem will be continuous, as is
the quotient map q(v) = [v]. We need to have the map α̃−1 continuous as well. The map α̃ is continuous
and a bijection. In general this does not imply continuity of the inverse but it does in our case where the
domain q(K) is compact. Thus the functions in (2.8) are continuous, and F is a continuous extension of
f˜ ◦ α̃−1 from its compact domain to all of Rm .

Proposition 2.23 can be used to construct universal invariant hypothesis classes. In particular functions
classes of the form
Hinv = {h ◦ α(x)|h is fully connected. }
will be universal. We can also construction universal invariant function classes of the form

Hinv = {h ◦ hinv (x)|h is fully connected. hinv comes from a family of invariant functions }

where the collection of possible hinv includes α or at least can approximate α. This is based on the following
lemma:
50 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

Lemma 2.24. [Don’t need proof for exam] Let G be a group acting on a metric space V , and let α : V → Rm
be a continuous separating invariant mapping. Let K ⊆ V be a compact set and assume that αn : V → Rm
are continuous invariant functions which converge uniformly to α in C(K, Rm ). Then for every continuous
invariant f : V → R there exists neural network functions Fn : Rm → R such that Fn ◦ αn converges to f
uniformly on C(K).
Proof. Since α(K) is compact it is contained in some closed ball B̄R ⊆ Rm . Since ∥αn − α∥C(K,Rm ) → 0
there exists some r > 0 such that ∥αn − α∥ ≤ r for all n. It follows that αn (K) ⊆ B̄R+r for all n. Let
F : Rm → R be the function satisfying (2.9) as promised in Proposition 2.23. Let Fn : Rm → R be neural
network functions which approximate F uniformly on B̄R+r .
Choose some ϵ > 0, we need to show that there exists some N such that for all n > N

max |(Fn ◦ αn )(x) − (F ◦ α)(x)| < ϵ

x∈K

Note that for every n ∈ N and x ∈ K,

|(Fn ◦ αn )(x) − (F ◦ α)(x)| = |(Fn ◦ αn )(x) − (F ◦ αn )(x)| + |(F ◦ αn )(x) − (F ◦ α)(x)|

≤ ∥Fn − F ∥B̄R+r + |(F ◦ αn )(x) − (F ◦ α)(x)| (2.10)

We choose N large enough such that

1. For all n ≥ N we have ∥Fn − F ∥B̄R+r ≤ ϵ/2.

2. Since F is continuous it is uniformly continuous on B̄R+r . We choose some δ > 0 such that F (y1 ) −
F (y2 )| < ϵ/2 whenever ∥y1 −y2 ∥ ≤ δ and then choose N large enough so that maxx∈K |∥αn (x)−α(x)∥ <
δ. This implies that |(F ◦ αn )(x) − (F ◦ α)(x)| ≤ ϵ/2 for all x ∈ K.
Due to (2.10) this concludes our argument.
We will now consider separating invariants for the action of permutations on multisets and then use them
to show universality of point-net/deep sets/ other models.

Continuous Separating Invariants for the action of Sn on Rn We consider three different types of
separating invariants for the action of Sn on Rn :
1. Sorting The sorting mapping sort(x) sorts a vector x ∈ Rn by size, e.g.,

sort(1, 3, 2, 7, 4) = (1, 2, 3, 4, 7).

This mapping is clearly permutation invariant and separating. It is also continuous piecewise linear
(you will see in homework).
2. Elementary symmetric polynomials The elementary symmetric polynomials are defined as
n
X X
e0 (x) = 1, e1 (x) = xi , e2 (x) = xi xj ,
i=1 1≤i<j≤n
X
e3 (x) = xi xj xk , . . . en (x) = x1 · x2 · . . . · xn
1≤i<j<k≤n

Clearly these polynomials are continuous and invariant to permutations. We prove that they are
separating using the proof in [Zaheer et al., 2017]
Theorem 2.25. The mapping e : Rn → Rn defined by

e(x) = (e1 (x), . . . , en (x))

is separating with respect to the action of Sn on Rn .

 51

Proof. Given x, y ∈ Rn , we need to show that if e(x) = e(y) then [x] = [y].
We use x, y to define two polynomials
n
Y n
Y
Px (t) = (t − xi ) and Py (t) = (t − yi )
i=1 i=1

the roots of Px (respectively Py ) are exactly the entries of x (or y) and they are equal as polynomials
if and only if x and y are equal up to permutation. We can rewrite

Px (t) = a0 + a1 t + . . . + an tn
Py (t) = b0 + b1 t + . . . + bn tn

and note that

ak = (−1)n−k ek (x), k = 0, 1, . . . , n
n−k
bk = (−1) ek (y), k = 0, 1, . . . , n

It follows that if e(x) = e(y) then ak = bk , k = 0, 1, . . . , n and therefore Px = Py which implies that x
and y are equal up to permutation.

3. Power sum polynomials The symmetric power sum polynomials are defined as
n
X n
X n
X n
X
p0 (x) = 1, p1 (x) = xi , p2 (x) = x2i , p3 (x) = x3i , . . . pn (x) = xni .
i=1 i=1 i=1 i=1

It turns out that these polynomials hold the same information as the elementary symmetric polyno-
mials. Indeed, note that
p0 = e0 and p1 = e1 .

Moreover
n
!2 n
X X X
2
p1 (x) = xi = x2i + 2 xi xj = p2 (x) + 2e2 (x)
i=1 i=1 1≤i<j≤n

so
2s2 (x) = p1 (x)2 − p2 (x).

In general Newton’s identities (which we will not prove) state that

k
X
kek (x) = (−1)k−i ek−i (x)pi (x).
i=1

In particular if pk (x) = pk (y) for all k = 1, . . . , n then ek (x) = ek (y) for all k = 1, . . . , n which means
that x and y are equivalent up to permutation according to the previous theorem. Thus we see that
the power sum polynomials are also continuous separating invariants.

Remark 2.26. A related but stronger result which we will not need here is that the algebra generated by the
elementary symmetric polynomials (equivalently, the algebra generated by the power sum polynomials) is in
fact equal to the algebra of all Sn invariant polynomials. In other words, for every polynomial p : Rn → R
which is Sn invariant there is some polynomial q : Rn+1 → R such that

p(x) = q(e0 (x), e1 (x), . . . , en (x))

52 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

Universal hypothesis classes for the action of Sn on Rn It follows immediately from our discussion
above that taking α : Rn → Rm to be a continuous separating invariant mapping such as the (i) sorting, (ii)
elementary polynomials or (iii) power sum polynomials defined above, that functions in

H = {h ◦ α|h : Rm → R is a neural network}

can approximate any continuous Sn invariant function uniformly on compact subsets of Rn .

We now prove universality of the pointnet architecture with sum-pooling. This can also be used to show
universality of the deep set architecture.
Recall that we denote elements in Rd×n by X = (x1 , . . . , xn ) where each xi is a vector in Rd . We prove
Theorem 2.27. For every n, and every compact K ⊆ Rn , every f : Rn → R which is continuous and Sn
invariant can be approximated uniformly on K by functions in
n
!
X
Hpointnet−sum = {F h(xi ) |h : R → Rn , and F : Rn → R are neural networks}
i=1

Proof. Consider the mapping m : R → Rn defined by

m(x) = (x, x2 , . . . , xn ).

and define p(x) to be the mapping

n n n n
!
X X X X
p(x) := m(xi ) = xi , x2i , . . . xni
i=1 i=1 i=1 i=1

Pnm : R →
which is continuous invariant and separating. Note that universality of neural networks implies that
Rn can be approximated on compact sets by a neural network h : R P → Rn , and as a result p(x) = i=1 m(xi )
n
can be approximated on compact sets by expression of the form i=1 h(xi ). The claim now follows from
Lemma 2.24:

Continuous Separating Invariants for the action of Sn on Rd×n We now turn to consider separating
invariants (and universality) for the action of Sn on Rd×n where now d > 1. A natural approach to generalize
the one-dimensional sort function is by using lexicographical sorting, where e.g., we sort according to the
first coordinate from small to large, and break equalities by sorting according to the second coordinate from
small to large, e.g.    
1 5 5 8 7 7 1 5 5 7 7 8
lexsort = .
6 5 4 1 2 3 6 4 5 2 3 1
This type of mapping is indeed both permutation invariant and separating but it is not continuous. In
contrast, we can get polynomial invariants which are continuous separating invariants.
We consider Sn polynomial invariants for Rd×n which are obtained from polynomial invariants of Rn by
a process called polarization. For given k = 0, . . . , n and w ∈ Rd we define
n
X
T
q(X; w, k) = pk (w X) where pk (t1 , . . . , tn ) = tki .
i=1
n
these are indeed invariant as for all permutation matrices P , since pk : R → R are permutation invariant:

q(XP T ; w, k) = pk (wT XP T ) = pk (wT X).

Note that for each k, w, the function q(X; w, k) is a multivariate polynomial from Rd×n of degree k ≤ n. We
claim that this infinite family of polynomial is separating in the following sense:
Lemma 2.28. If X, Y ∈ Rd×n and

q(X; k, w) = q(Y ; k, w), ∀k = 0, . . . , n and w ∈ Rd

then X = σ. Y for some σ ∈ Sn .

 53

To prove this lemma we will need a sub-lemma

Lemma 2.29. Let A(i) ∈ Rn×d , i = 1, . . . , m be non-zero matrices, and denote

Si = {w ∈ Rd | A(i) w = 0}

Then the union ∪m d

i=1 Si does not cover all of R .

Proof of Lemma 2.29. This can be done using measure considerations, by showing that each Si has Lebesgue
measure zero and therefore so does there union.
Alternatively, we can do this inductively. Denote T0 = Rd and

Ti = Ti−1 \ Si , i = 1, . . . , m.

Note that Tm is the complement of ∪m i=1 Si . We want to show Tm isn’t empty. To do this we will recursively
show that each Ti is open and not empty. For T0 this is clear. Now assuming that Ti−1 is open and non-empty
we see that Ti is also open since it is the intersection of two open sets: Ti−1 and the complement of Si . Now
let us show that Ti is not empty: if Ti = Ti−1 we are done. Otherwise, there exists some w ∈ Ti−1 ∩ Si .
Since A(i) ̸= 0, there exists some row of A(i) which we denote by aTj which is not zero. It follows that for
every ϵ > 0,
aTj (w + ϵaj ) = ϵ∥aj ∥2 ̸= 0 and therefore A(w + ϵaj ) ̸= 0,
and so w + ϵaj will not be in Si . Since Ti−1 is open, for small enough ϵ the vector w + ϵaj will be in Ti−1
and so will be in Ti = Ti−1 \ Si which concludes the proof.

Proof of Lemma 2.28. We assume that X, Y are such that X ̸= σ. Y for all σ ∈ Sn and we will prove that
there exist k, w such that pk (wT X) ̸= pk (wT Y ). Indeed for fixed σ let us consider the set

Bσ = {w ∈ Rd |wT X = wT σ. (Y )} = {w ∈ Rd |wT (X − σ. (Y )) = 0}.

Note that by assumption for each σ we have that X − σ. Y ̸= 0 and so by Lemma 2.29 there exists w̄ which
is not in ∪σ∈Sn Bσ . Since the power-sum polynomials are separating on Rn and w̄T X ̸∼ w̄T Y , it follows that
there exists some k such that pk (w̄T X) ̸= pk (w̄T Y ).

The next step is to find a finite number of separating invariants using this lemma. Recall that P(d, n),
the space of multivariate polynomials b : Rd → R of degree ≤ n is a linear space of dimension m = m(n, d) =
n+d


d . We will consider some basis b1 , . . . , bm for this space. They induce permutation invariant polynomials
defined on Rd×n by
Xn
Bk (X) = bk (xi ).
i=1

We prove

Theorem 2.30. Let b1 , . . . , bm : Rd → R be polynomials which span the space of polynomials, then the
polynomial mappings
n
X
Bℓ (X) = bℓ (xi ), ℓ = 1, . . . , m (2.11)
i=1

are invariant and separating with respect to the action of Sn on Rd×n

Proof. Invariance is clear. To show separation, let X, Y ∈ Rd×n be such that Bℓ (X) = Bℓ (Y ), ℓ = 1, . . . , m.
We will show that this implies that pk (wX) = pk (wY ) for all k and w, which in turn implies that X = σ. Y
for some σ ∈ Sn , according to the previous lemma.
We note that for every w ∈ Rd and k = 0, . . . , n the polynomial

k
x 7→ wT x
54 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

(k,w)
is a polynomial on Rd of degree k ≤ n, and therefore there exist coefficients cℓ , ℓ = 1, . . . , m such that
m

k X (k,w)
wT x = cℓ bℓ (x), ∀x ∈ Rd
ℓ=1

It follows that
n n X
m m
X
k X (k,w)
X (k,w)
pk (wT X) = w T xi = cℓ bℓ (xi ) = cℓ Bℓ (X)
i=1 i=1 ℓ=1 ℓ=1

and
m
(k,w)
X
pk (wT Y ) = cℓ Bℓ (Y ).
ℓ=1

Since by assumption Bℓ (X) = Bℓ (Y ) for all ℓ it follows that pk (wT X) = pk (wT Y ) for all k, w and therefore
X = σ. Y for some σ ∈ Sn as required.
Remark 2.31. It is possible to obtain m̃ = n(2nd + 1) << m(n, d) continuous separating invariants by
taking random w(1) , . . . , w(2nd+1) , and defining the invariants to be
T
X 7→ qk (w(j) X), k = 1, . . . , n, j = 1, . . . , 2nd + 1.

For more details see [Dym and Gortler, 2022]. In this construction we can also replace the power sum
polynomials with the sorting function.
 55

New Lesson
An immediate consequence of Theorem 2.30 is the universality of point-net with sum-pooling for the case
d > 1:
Theorem 2.32. For every d, n, and every compact K ⊆ Rd×n , every f : Rd×n → R which is continuous
and Sn invariant can be approximated uniformly on K by functions in
n
!
X
Hpointnet−sum = {F h(xi ) |h : Rd → Rm , and F : Rm → R are neural networks}
i=1

Sketch of proof.
PnThe proof is the same of the proof of Theorem 2.27: we use the fact that thempolynomi-
als Bℓ (X) = i=1 bℓ (xi ) in (2.11) are separating, and the fact that the function x 7→ (bℓ (x))ℓ=1 can be
approximated by neural networks of the form h : Rd → Rm due to universality of neural networks.

2.0.5 Networks for sets and multi-sets

We’ve constructed functions B : Rd×n → Rm which are invariant and separating with respect to the action
of Sn . As we discussed, equivalence classes in Rd×n can be identified with multi-sets with n elements in Rd .
Let us denote the space of all such multisets by Sn (Rd ). Note that since B is invariant, it induces a function
B̂ on Sn (Rd ): for a given multiset we can choose any ordering of its elements and define
B̂({{x1 , . . . , xn }}) = B(x1 , . . . , xn ).
The permutation invariance implies that the definition of B̂ does not depend on the order we chose.
Next, we note that the fact that B is separating implies that B̂ is injective on Sn (Rd ).
We will often want to extend our functions to spaces of multisets of varying but bounded sizes. Let us
denote by S≤n (Rd ) the collection of all multisets of at most n elements from Rd . We would like to define a
function B̃ : S≤n (Rd ) → Rm which is injective.
This goal is achieved relatively easily using the power sum polynomials we considered previously: assume
that b1 , . . . , bm span the space of polynomials of degree at most n in Rd . We have showed that the function
B = (B1 , . . . , Bm ) defined by
n
X
Bj (x1 , . . . , xn ) = bj (xi )
i=1
d×n ′
is invariant and injective on R . Note that if n < n, this same function is also invariant and injective
′
with respect to the action of Sn′ on Rd×n . Accordingly, we can define b0 (x) = 1 and B̃ = (B̃0 , . . . , B̃m ) to
be
n′
X
B̃j {{x1 , . . . , xn′ }} = bj (xi ) (2.12)
i=1
and we can then prove
Proposition 2.33. The function B̃ : S≤n (Rd ) → Rm+1 is injective.
Proof. Assume that B̃{{x1 , . . . , xn′ }} = {{x1 , . . . , xn′′ }}) for some n′ , n′′ ≤ n. Then in particular
′ ′′
n
X n
X
′
n = B0 (xi ) = B0 (yi ) = n′′
i=1 i=1

and then the fact that (2.12) holds for j = 1, . . . , m implies that x1 , . . . , xn′ and y1 , . . . , yn′ are related by a
permutation and so the multisets containing these points are equal.
Remark 2.34 (Dimension optimality). In general, for any continuous injective function B : Sn (Rd ) → Rm
or B : S≤n (Rd ) → Rm the dimension m must satisfy m ≥ nd (see [Wagstaff et al., 2022] for the d = 1 case
and [Joshi et al., 2023, Amir et al., 2023] for the general case). When the set elements are assumed to come
from a finite or countable set (we can think of this as d = 0) then we can actually get m = 1 as discussed in
[Zaheer et al., 2017, Xu et al., 2018, Amir et al., 2023].
56 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

2.1 Graph Neural Networks and Graph Isomorphism test

Our presentation here mostly follows [Xu et al., 2018]. We consider learning tasks over graphs. A graph is
defined as usual through a finite set of n nodes V which we denote by {1, . . . , n}, and a set of unordered
pairs of nodes E ⊆ V × V which we call edges. These can be encoded by the adjacency matrix A, where
Au,v = 1 if (u, v) ∈ E and otherwise Auv = 0. Additionally, we have a specified vector valued label per
node xv ∈ Rd , which can be represented using a d × n matrix X. Thus our graph can be represented by two
matrices G = (A, X).
We would like to learn functions of the form
G 7→ F (G) ∈ Rk (2.13)
or of the form
G 7→ (fv (G))v∈V (2.14)
For example, we can think of a graph representing a molecule, where the nodes V represent atoms, and
the edges represent atoms which are linked by a chemical bond. The node features xv in this case could
represent the type of atom (hydrogen, oxygen, etc.). The function we would like to learn could be certain
properties of the molecules e.g., is the molecule toxic? Is it effective for treatment of a given disease? Is
it soluble in water? The answer to these three question could be encoded as a binary vector in R3 , and a
function answering these questions can be encoded by a function F as in (2.13) whose input is a graph and
output is an R3 vector. For applications of graph neural networks for chemistry see e.g. [Reiser et al., 2022].
Another example could be a graph representing a social network such as LinkedIn, where nodes represent
users, and edges between nodes represent users who are friends. The node features xv could represent known
data on users (e.g., age, number of degrees) and a node valued function fv (G) such as the one described in
(2.14) could represent the likeliness that the user corresponding to node v will be a good job candidate.

2.1.1 Symmetries of graphs

We would like to design hypothesis classes for approximating F and f in (2.13) and (2.14) respectively, which
respect the permutation symmetry of graphs. Note that relabeling the nodes of a graph G = (A, X) using a
permutation τ corresponds to the following action
(τ. (A, X)) = (τ. A, τ. X)
where
(τ. (A))ij = Aτ −1 (i),τ −1 (j) and (τ.X)ij = Xiτ −1 (j)
We have
Lemma 2.35. For every A ∈ Rn×n , X ∈ Rd×n and permutation τ ∈ Sn , we have that
τ. A = Pτ APτT , τ.X = XPτT
and the action defined by τ is a well defined group action.
Proof. For every permutation σ and A ∈ Rn×n we have that
(σ. A)ij = (Pσ APσT )ij = (Pσ A)iσ−1 (j) = (AT PσT )σ−1 (j),i = ATσ−1 (j),σ−1 (i) = Aσ−1 (i),σ−1 (j)
We note that this is a group action because
τ. (σ. A) = Pτ (σ. A)PτT = Pτ Pσ APσT PτT = Pτ ◦σ APτT◦σ = (τ ◦ σ). A

A function F defined in (2.13) will typically be permutation invariant

F (Pσ APσT , XPσT ) = F (σ. (A, X)) = F (A, X)
and the function f defined in (2.14) will typically be permutation equivariant
f (Pσ APσT , XPσT ) = f (σ. (A, X)) = σ. (f (G)) = f (G)PσT
2.1. GRAPH NEURAL NETWORKS AND GRAPH ISOMORPHISM TEST 57

Equivariant operations on graphs To construct hypothesis classes which consist only of graph-equivariant
functions, we need to identify equivariant operations we can use. One simple example: we can extend any
ρ : R → R to an elementwise function on X and A and this will be permutation equivariant.
Here is a more interesting example: the function h : Rn×n ⊕ Rn×d → Rn×d defined by

h(A, X) = (A, XA)

is permutation equivariant because for every permutation τ and corresponding permutation matrix P = Pτ .

h (τ. (A, X)) = h(P AP T , XP T ) = XP T P AP T = XAP T = τ.(h(A, X)).

When A represents an adjacent matrix, the operation (A, X) 7→ Y = XA can be understood as a ‘message
passing’ procedure, where Yv is the sum of all features in X belonging to its neighbors. The set of neigbors
of a node v is defined as
N (v) = {u ∈ V |(u, v) ∈ E} = {u ∈ V |Au,v = 1}.
Note that
n
X X
(XA)i,v = Xiu Auv = Xiu = S({{Xiu | u ∈ N (v)}})
u=1 u∈N (v)

where S denotes the summation function which is well defined on multisets (it does not depend on the order
of the elements).
This ‘message passing’ interpretation can be generalized: let us denote the spaces of n × n adjacency
matrices by
An = {A ∈ {0, 1}n×n , Aii = 0 and Aij = Aji ∀1 ≤ i < j ≤ n}
This is a subset of Rn×n and for every A ∈ An and permutation τ ∈ Sn we have that τ. A ∈ An so that the
action of the permutation group on this subset is well defined. We then have

Proposition 2.36. Let (A, X) ∈ An ⊕ Rd×n and let m be a function which maps finite multisets with
elements in Rd into Rc . Then the function h : (A, X) ∈ An ⊕ Rd×n → Rc×n defined by

(h(A, X))v = m{{Xu | Au,v = 1}} = m{{Xu | u ∈ N (v)}}

is permutation equivariant.

Proof. For every permutation τ and node v ∈ V we have that

(h(τ. (A, X)))v = m{{(τ. X)u | (τ. A)u,v = 1}}

= m{{Xτ −1 (u) | Aτ −1 (u),τ −1 (v) = 1}}
= m{{Xu | Au,τ −1 (v) = 1}}
= (h(A, X))τ −1 (v) = (τ. h(A, X))v

Proposition 2.36 gives us a general method to construct graph-equivariant functions using functions on
multisets. We can take the function m to be the summation function as above, or take m to be more
complicated multiset valued functions such as the injective multiset functions we discussed previously. Note
that since different nodes generally have neighborhoods of different sizes, we will typically require functions
which are will defined on multisets of different cardinalities.

Message Passing Neural Networks Message passing neural networks are a family of (arguably, the
most) popular equivariant graph neural networks. They iteratively use the graph structure to redefine node
labels. A message passing neural network is initialized via

Xv(0) = Xv
58 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY

(k) (k−1)
and then we recursively define Xv from Xv via
 
a(k)
v = AGGREGAT E (k)
{
{Xu
(k−1)
, u ∈ Nv }
}
 
Xv(k) = COM BIN E (k) Xv(k−1) , a(k)
v . (2.15)

We can think of this process is applying an equivariant function to obtain.

(A, X (k) ) = h(A, X (k−1) )

We can apply this procedure recursively K times, which ultimately gives us a permutation equivariant
function
f (A, X) = (A, X (K) ).
If our final goal is to achieve a permutation invariant function we add an additional readout function
 
F (A, X) = READOU T {{Xv(K) | v ∈ V }}

and the obtained function F is invariant.

As our notation suggests, the functions AGGREGAT E and READOU T are required to be well defined
on finite multisets. Once the number of iterations K, and the functions AGGREGAT E (k) , COM BIN E (k)
and READOU T , are defined, the function F is a well defined, permutation invariant function.
Several well known GNN architectures can be cast in this framework. For example, the pooling variant
of GraphSAGE [Hamilton et al., 2017] uses the aggregation function
 
a(k)
v = max{{ReLU W Xu
(k−1)
, u ∈ Nv }}

where W is some given matrix (which is learned in practice). This is a well defined multiset function, as the
same function
yu = ReLU (W Xu(k−1) )
is applied to all neighbors of v, and the maximum, which is applied row-wise to the matrix whose columns
are yu , u ∈ N (v) is a permutation invariant operation.
The COMBINE function in GraphSAGE is taken to be
  
Xv(k) = ReLU B · CON CAT Xv(k−1) , a(k)
v ,

where B is a learnable matrix.

𝐺𝐺 𝐺𝐺’

Figure 2.1: Two graphs which are not isomorphic (are not related by a permutation) but cannot be separated
by any message passing neural network
2.1. GRAPH NEURAL NETWORKS AND GRAPH ISOMORPHISM TEST 59

Approximation Power It would be natural to inquire what the expressive power of message passing
neural networks (MPNN) is, and to hope that like pointnet architecture for point clouds, it will be universal
in the sense that it can approximate any continuous permutation invariant function on graphs. As we saw,
this question is very strongly linked to the question of finding separating invariants for the group action (in
our case, permutation and graphs). Thus one could inquire whether MPNN can separate any graphs up to
permutation equivalence.
To be more precise, can we define F (A, X) via a message passing procedure with some specified itera-
tion number K, and some multiset valued functions AGGREGAT E (k) , COM BIN E (k) , k = 1, . . . , K and
READOU T , such that F (A, X) = F (A′ , X ′ ) if and only if A′ = P AP T , X ′ = XP T for some appropriate
permutation matrix P ?
It turns out that the answer to this question is negative. In general, since F is permutation invariant by
construction we always have that if A′ = P AP T , X ′ = XP T then F (A, X) = F (A′ , X ′ ). The converse is
not true: Figure 2.1 shows an example of two graphs G, G′ which are not isomorphic. Here we can take A
and A′ to be the adjacency matrices of the two graphs and X and X ′ to just be a all one vector. We note
that for every node v or v ′ in either graph we have the same initial coloring Xv = 1 or Xv′ = 1, and the
neighborhoods of all nodes contain exactly two nodes, so that the multisets encountered in the first step of
the message passing procedure are just {{1, 1}}. We can see that the message passing procedure gets ‘stuck’,
where no matter what we do all nodes in both graphs will assume the same value.
The fact that separation of graphs fails is not surprising. The problem of telling whether two graphs are
related by a permutation is known as the Graph Isomorphism Problem (GI). There is no known polynomial
time algorithm to solve this problem, though it is also not known to be NP-hard. It is one of the examples
of a problem which may be NP-intermediate.
In general, the separation power of MPNNs is strongly related to the Weisfeiler-Lehman (WL) graph
isomorphism tests which we did not have time to define this year. In general, MPNNs separation power is
bounded from above by the WL tests: they cannot separate graphs which the WL test cannot separate. An
MPNN which uses injective multiset functions, and injective COMBINE functions, will be equivalent to the
WL test in terms of graph separation abilities. For more on this see [Morris et al., 2019, Xu et al., 2018].
60 CHAPTER 2. INVARIANT LEARNING AND APPROXIMATION THEORY
Bibliography

[Amir et al., 2023] Amir, T., Gortler, S. J., Avni, I., Ravina, R., and Dym, N. (2023). Neural injective
functions for multisets, measures and graphs via a finite witness theorem.

[Daubechies et al., 2021] Daubechies, I., DeVore, R., Foucart, S., Hanin, B., and Petrova, G. (2021). Non-
linear approximation and (deep) relu networks. Constructive Approximation, pages 1–46.

[DeVore et al., 2021] DeVore, R., Hanin, B., and Petrova, G. (2021). Neural network approximation. Acta
Numerica, 30:327–444.

[Dym and Gortler, 2022] Dym, N. and Gortler, S. J. (2022). Low dimensional invariant embeddings for
universal geometric learning. arXiv preprint arXiv:2205.02956.

[Dym et al., 2020] Dym, N., Sober, B., and Daubechies, I. (2020). Expression of fractals through neural
network functions. IEEE Journal on Selected Areas in Information Theory, 1(1):57–66.

[Eldan and Shamir, 2016] Eldan, R. and Shamir, O. (2016). The power of depth for feedforward neural
networks. In Conference on learning theory, pages 907–940. PMLR.

[Hamilton et al., 2017] Hamilton, W., Ying, Z., and Leskovec, J. (2017). Inductive representation learning
on large graphs. Advances in neural information processing systems, 30.

[Hanin and Rolnick, 2019] Hanin, B. and Rolnick, D. (2019). Deep relu networks have surprisingly few
activation patterns. Advances in neural information processing systems, 32.

[Joshi et al., 2023] Joshi, C. K., Bodnar, C., Mathis, S. V., Cohen, T., and Liò, P. (2023). On the expressive
power of geometric graph neural networks. arXiv preprint arXiv:2301.09308.

[Lu et al., 2021] Lu, J., Shen, Z., Yang, H., and Zhang, S. (2021). Deep network approximation for smooth
functions. SIAM Journal on Mathematical Analysis, 53(5):5465–5506.

[Malach and Shalev-Shwartz, 2019] Malach, E. and Shalev-Shwartz, S. (2019). Is deeper better only when
shallow is good? Advances in Neural Information Processing Systems, 32.

[Montufar et al., 2014] Montufar, G. F., Pascanu, R., Cho, K., and Bengio, Y. (2014). On the number of
linear regions of deep neural networks. Advances in neural information processing systems, 27.

[Morris et al., 2019] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and
Grohe, M. (2019). Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of
the AAAI conference on artificial intelligence, volume 33, pages 4602–4609.

[Munkres, 2000] Munkres, J. R. (2000). Topology, volume 2. Prentice Hall Upper Saddle River.

[Pinkus, 1999] Pinkus, A. (1999). Approximation theory of the mlp model in neural networks. Acta numerica,
8:143–195.

[Qi et al., 2017] Qi, C. R., Su, H., Mo, K., and Guibas, L. J. (2017). Pointnet: Deep learning on point sets
for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and
pattern recognition, pages 652–660.

61
62 BIBLIOGRAPHY

[Raghu et al., 2017] Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Sohl-Dickstein, J. (2017). On
the expressive power of deep neural networks. In international conference on machine learning, pages
2847–2854. PMLR.
[Reiser et al., 2022] Reiser, P., Neubert, M., Eberhard, A., Torresi, L., Zhou, C., Shao, C., Metni, H., van
Hoesel, C., Schopmans, H., Sommer, T., et al. (2022). Graph neural networks for materials science and
chemistry. Communications Materials, 3(1):93.
[Simmons, 1963] Simmons, G. F. (1963). Introduction to topology and modern analysis, volume 44. Tokyo.
[Telgarsky, 2016] Telgarsky, M. (2016). Benefits of depth in neural networks. In Conference on learning
theory, pages 1517–1539. PMLR.

[Wagstaff et al., 2022] Wagstaff, E., Fuchs, F. B., Engelcke, M., Osborne, M. A., and Posner, I. (2022).
Universal approximation of functions on sets. Journal of Machine Learning Research, 23(151):1–56.
[Xu et al., 2018] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2018). How powerful are graph neural
networks? In International Conference on Learning Representations.

[Yarotsky, 2017] Yarotsky, D. (2017). Error bounds for approximations with deep relu networks. Neural
Networks, 94:103–114.
[Zaheer et al., 2017] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola,
A. J. (2017). Deep sets. Advances in neural information processing systems, 30.
[Zaslavsky, 1975] Zaslavsky, T. (1975). Facing up to arrangements: Face-count formulas for partitions of
space by hyperplanes: Face-count formulas for partitions of space by hyperplanes, volume 154. American
Mathematical Soc.