<p>Yes, ReLUs are discriminatory. See for example the nice, simple proof in Lemma 3.15 of these notes by Leonardo Ferreira Guilhoto:
<a href="http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf" rel="nofollow noreferrer">http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf</a></p>

<p>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:</p>

<p><span class="math-container">$f(x) = ReLU(W x + b_1) - ReLU(W x + b_2)$</span></p>

<p>and an appropriate choice of <span class="math-container">$b_1, b_2$</span> makes this difference f a sigmoidal function, as defined in Cybenko, so function f is discriminatory. </p>

<p>By definition a function is discriminatory if the zero measure is the only signed Borel measure <span class="math-container">$\mu$</span> such that:</p>

<p><span class="math-container">$\int f(W x + b) d \mu (x) = 0$</span>
for all W, b</p>

<p>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.</p>

CC BY-SA 4.0
2019-06-24T05:27:52.877Z
2019-06-24T05:27:52.877Z
Dean Alderucci
<p>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 
<a href="https://arxiv.org/abs/1509.07385" rel="nofollow noreferrer">https://arxiv.org/abs/1509.07385</a></p>

CC BY-SA 3.0
2018-04-11T18:24:56.233Z
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
CC BY-SA 3.0
2018-04-11T18:44:33.477Z
Looking through the paper I see no mention of the notion of discriminatory which is what I am specifically asking about.
Christian Bueno
CC BY-SA 3.0
2018-04-11T18:20:07.243Z
2018-04-11T18:20:07.243Z
jaco
<p>In <a href="https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf" rel="noreferrer">Cybenko's elegant proof</a> 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) <em>discriminatory</em>. He then shows that bounded measureable sigmoidal functions are discriminatory, completing the proof. In particular, continuous sigmoidal functions work as well.</p>

<p>Later <a href="https://pdfs.semanticscholar.org/ae37/354fc5138bf6ae683cf3fba014571d4540c3.pdf" rel="noreferrer">Leshno et al.</a> proves that locally bounded piecewise continuous (l.b.p.c.) activation functions yield the UAT if and only if they are nonpolynomial. </p>

<p><strong>My Question(s):</strong> </p>

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

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

<machine-learning>
Universal Approximation - Are ReLUs discriminatory?
Christian Bueno
# Universal Approximation - Are ReLUs discriminatory?

(Asked by: username_0 on 2018-04-04)

In [Cybenko's elegant proof](https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf) 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.](https://pdfs.semanticscholar.org/ae37/354fc5138bf6ae683cf3fba014571d4540c3.pdf) 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?

**Tags:** machine-learning


---

## 2 answers

### Answer by username_1 on 2019-06-24. Score: 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 by username_2 on 2018-04-11. Score: -1

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>

> **Comments:**
> **username_0**: 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.  
> **username_0**: Looking through the paper I see no mention of the notion of discriminatory which is what I am specifically asking about.  

---

