"Understanding Machine Learning: From Theory to Algorithms" the universal approximation theorem

Question

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 }$

Answer 1

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}$.

Answer 2

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}$.)