# Universal Approximation - Are ReLUs discriminatory?

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?

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.

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

• As mentioned, Cybenko proves that it is enough for the function to have his "discriminatory" property, and then proves continuous sigmoidal functions (which are bounded) satisfy that property. He is silent on whether unbounded functions like ReLUs can be discriminatory. – Christian Bueno Apr 11 '18 at 18:24
• Looking through the paper I see no mention of the notion of discriminatory which is what I am specifically asking about. – Christian Bueno Apr 11 '18 at 18:44