Universal Approximation - Are ReLUs discriminatory?

Question

In Cybenko's elegant proof of the Universal Approximation Theorem (UAT) he proves that single hidden layer neural networks (with linear output layer) are universal approximators whenever their activation functions are (what he calls) discriminatory. He then shows that bounded measureable sigmoidal functions are discriminatory, completing the proof. In particular, continuous sigmoidal functions work as well.

Later Leshno et al. proves that locally bounded piecewise continuous (l.b.p.c.) activation functions yield the UAT if and only if they are nonpolynomial.

My Question(s):

What kinds of functions are discriminatory? Polynomials certainly aren't (Leshno et al.) and continuous sigmoids are (Cybenko). Are ReLUs discriminatory?

Together, the above results imply that for l.b.p.c. functions, that discriminatory implies non-polynomial. Is the converse true?

Answer 1

Yes, ReLUs are discriminatory. See for example the nice, simple proof in Lemma 3.15 of these notes by Leonardo Ferreira Guilhoto: http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf

Regarding whether an unbounded function like a ReLU can be discriminatory, note that you can construct a bounded, continuous function as the difference of two ReLUs:

$f(x) = ReLU(W x + b_1) - ReLU(W x + b_2)$

and an appropriate choice of $b_1, b_2$ makes this difference f a sigmoidal function, as defined in Cybenko, so function f is discriminatory.

By definition a function is discriminatory if the zero measure is the only signed Borel measure $\mu$ such that:

$\int f(W x + b) d \mu (x) = 0$ for all W, b

Applying this to the difference of ReLUs above shows that both integrals over each ReLU must have measure zero if integral of f has measure zero.

Answer 2

I think ReLUs does not satisfy Cybenko theory requirements, i.e. are unbounded. There is another recent paper showing UAT type theorem for ReLU feed forward deep networks using wavelet approximation property https://arxiv.org/abs/1509.07385