# “Understanding Machine Learning: From Theory to Algorithms” the universal approximation theorem

I'm readying on "Understanding Machine Learning: From Theory to Algorithms" the Universal approximation theorem:

..."Networks are universal approximators. That is, for every fixed precision parameter, $$\epsilon >0$$, and every Lipschitz function $$f : [−1; 1]^{n} \rightarrow [−1; 1]$$, it is possible to construct a network such that for every input $$\textbf{x} \in [−1; 1]^{n}$$, the network outputs a number between $$f(x) − \epsilon$$ and $$f(x) + \epsilon$$".

It seems to me that the function $$f : [−1; 1]^{n} \rightarrow [−1; 1]$$ is Boolean.

I think that the n-dimensional unit hypercube $${\displaystyle [-1,1]^{n}}$$ can be replaced with a compact set of $$\mathbb{R} ^ {n}$$ but the codomain makes me puzzled.

I was expecting a function: $$f : \mathbb { R } ^ { n } \rightarrow \mathbb { R }$$

• I think the question is best suited for CrossValidated. – Shubham Panchal Jul 11 '19 at 3:16
• Did you mean to use semicolons in the intervals? The book you're referring to uses commas throughout. Are you using semicolons to indicate the discrete set (hence "is Boolean"? I'm not familiar with that notation... – Ben Reiniger Jul 11 '19 at 15:14

Yes, it is applicable to a Boolean function and you can modify the result to compact set.

A result where the codomian is $$[-1, 1]$$ would cover regression and not restricting ourself to boolean.

You might or might not have a result for $$f: \mathbb{R}^n \to \mathbb{R}$$. A theorem states what conditions it requires in order to hold, for conditions that are not promised by a theorem, you have to check carefully whether the same conclusion can still apply. In particular, if the proof uses compactness, then you can't replace $$[-1,1]$$ with $$\mathbb{R}$$.

There are different versions of the theorem; see wikipedia's for example.

Some counterexamples will help focus the boundaries of what is and what is not possible. I won't be too formal with this, but I think it could be made so with some effort. Let's assume we're using the ReLU activation function, so that everything in the end is piecewise-linear and continuous. With a fixed network architecture, the number of hinge points in the final function is bounded (in a network with just one hidden layer, it is at most twice the number of hidden neurons). So, $$f: \mathbb{R}\to[-1,1],\ f(x)=\sin(x)$$ cannot be approximated: beyond all hinge points we have a single linear function, which cannot wiggle like $$\sin$$. You'll have the same problem with an open domain, using something akin to $$\sin(1/x)$$. So we need a compact domain.

You also obviously need continuity if you want approximation in the sense that every input is close to the right output: a jump discontinuity can be approximated with a very high slope, but only in the sense that the measure of the poorly-approximated points can be made as small (but positive) as desired.

And now, the continuous image of a compact set is compact, so the range is necessarily compact already. (So here you could safely expand the theorem to have codomain $$\mathbb{R}$$.)