Answers.Body: <p>Like the accepted answer, I'm assuming you are referring to (literature refering to) Leshno et al, 1993. That paper only concerns 1-layer neural networks, and those are simply of the form
  <span class="math-container">$$x\mapsto\sum_{j=1}^Na_j\sigma(w_j\cdot x+\theta_j)\qquad(N\in\mathbb N,a_j\in\mathbb R,w_j\in\mathbb R^n,\theta_j\in\mathbb R).$$</span>
  I think of them as sums of scaled, dilated and rotated versions of the activation function <span class="math-container">$\sigma$</span>. If the activation function is a polynomial of degree <span class="math-container">$k$</span> then every 1-layer neural network will be a polynomial of degree <span class="math-container">$k$</span> (and no higher). It is easy to construct a function that cannot be approximated (uniformly on the unit cube) by polynomials of degree <span class="math-container">$k$</span>. Generically, polynomials of degree <span class="math-container">$k+1$</span> cannot be approximated by polynomials of degree <span class="math-container">$k$</span>.</p>
  <p>For example, take <span class="math-container">$n=1$</span> (one input dimension). Then <span class="math-container">$f(x)= x^3$</span> cannot be approximated by 2nd degree polynomials: the latter are all parabolas. So <span class="math-container">$f$</span> cannot be approximated (uniformly on <span class="math-container">$[-1,1]$</span>) by 1-layer neural networks with activation function <span class="math-container">$\sigma(x)=x^2$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-03T02:29:15.203Z
Answers.LastActivityDate: 2023-10-03T02:29:15.203Z
Answers.UserDisplayName: Teun
Answers.Body: <p>The paper <a href="https://archive.nyu.edu/jspui/bitstream/2451/14329/1/IS-92-13.pdf" rel="nofollow noreferrer">Multilayer feedforward networks with a nonpolynomial activation function can approximate any function</a> (by Leshno et al., 1993) provides a theorem claiming this and the (quite long) proof of the theorem in the appendix.</p>
  <p>After a quick reading, it seems to me that they do not provide a very intuitive explanation of why the non-polynomiality of the (bounded, non-constant, and not necessarily continuous) activation function is <em>necessary and sufficient</em> (it's an <a href="https://en.wikipedia.org/wiki/If_and_only_if" rel="nofollow noreferrer"><em>if and only if</em></a> result, see the last paragraph on p. 4) for a single-layer neural network to approximate any continuous function.</p>
  <p>The theorem (p. 10) formally states that the set of all possible functions that the neural network can compute, denoted by <span class="math-container">$\Sigma_n$</span>, is <a href="https://encyclopediaofmath.org/wiki/Dense_set" rel="nofollow noreferrer"><em>dense</em></a> in <span class="math-container">$C(\mathbb{R}^n)$</span>, the set of continuous functions from <span class="math-container">$\mathbb{R}^n$</span> to <span class="math-container">$\mathbb{R}$</span> (and being dense in <span class="math-container">$C(\mathbb{R}^n)$</span> is the equivalent mathematical statement to &quot;neural networks can approximate any continuous function&quot;). To understand this, you need to understand what a dense (sub)set is. To understand that, you need to understand what a <a href="https://en.wikipedia.org/wiki/Closure_(topology)" rel="nofollow noreferrer">closure of a set <span class="math-container">$S$</span></a> is: intuitively, it's the set of all points <span class="math-container">$S$</span> plus the points near the set <span class="math-container">$S$</span>.</p>
  <p>To prove this theorem (p. 12), they proceed in 7 steps, so it's a long proof.</p>
  <p>For example, in step 1, they show (or just state) that, if the activation function <span class="math-container">$\sigma$</span> is a polynomial, then <span class="math-container">$\Sigma_n$</span> is not dense in <span class="math-container">$C(\mathbb{R}^n)$</span>. They conclude that <span class="math-container">$\Sigma_n$</span>, with such an activation function, would be a set of polynomials, which is not dense in <span class="math-container">$C(\mathbb{R}^n)$</span> (not sure why this is the case, but there is an old question <a href="https://math.stackexchange.com/q/3884806/168764">here</a> that asks exactly this; I think that understanding this would be a great step for <em>intuitively</em> understanding the theorem).</p>
  <p>I don't plan to go over all the steps now, but, if you spend some time reading this paper, you should have the answer of why the non-polynomiality of the activation function is necessary and sufficient for the neural network to approximate any continuous function of the form <span class="math-container">$f : \mathbb{R}^n \rightarrow \mathbb{R}$</span>. If that is not very useful, you could try reading the other related (but even longer) paper <a href="https://pinkus.net.technion.ac.il/files/2021/02/acta.pdf" rel="nofollow noreferrer">Approximation theory of the MLP model in neural networks</a> (by Pinkus, 1999).</p>
  <p>So, I wouldn't say that non-polynomiality is a complexity requirement, but really a theoretical requirement for approximating continuous functions.</p>
  <p>(By the way, I think there's a typo on page 6. They write <span class="math-container">$f_\omega : \mathbb{R} \rightarrow \mathbb{R}^n$</span> to denote the function the neural network computes, but I am pretty sure they meant <span class="math-container">$f_\omega : \mathbb{R}^n \rightarrow \mathbb{R}$</span>; in fact, previously, they assume that the neural network has <span class="math-container">$n$</span> inputs and <span class="math-container">$1$</span> output).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-15T13:35:44.683Z
Answers.LastActivityDate: 2021-11-15T15:02:21.897Z
Answers.LastEditDate: 2021-11-15T15:02:21.897Z
Answers.UserDisplayName: nbro
Body: <p>Across multiple pieces of literature describing MLPs or while describing the universal approximation theorem, the statement is very specific on the activation function being non-polynomial.</p>
  <p>Is there a reason why it cannot be a higher-order polynomial? Is it just an attempt to use the least complex solution or we really cannot use higher-order polynomial?</p>
  <p>I can understand the reason for the non-linear, but I am clueless about the non-polynomial requirement.</p>
  
Tags: <neural-networks><activation-functions><universal-approximation-theorems>
Title: Why does the activation function for a hidden layer in a MLP have to be non-polynomial?
UserDisplayName: niil87
ThreadText: # Why does the activation function for a hidden layer in a MLP have to be non-polynomial?
  
  (Asked by: username_0 on 2021-11-15)
  
  Across multiple pieces of literature describing MLPs or while describing the universal approximation theorem, the statement is very specific on the activation function being non-polynomial.
  
  Is there a reason why it cannot be a higher-order polynomial? Is it just an attempt to use the least complex solution or we really cannot use higher-order polynomial?
  
  I can understand the reason for the non-linear, but I am clueless about the non-polynomial requirement.
  
  **Tags:** neural-networks, activation-functions, universal-approximation-theorems
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2021-11-15. Score: 3 | Accepted answer
  
  The paper [Multilayer feedforward networks with a nonpolynomial activation function can approximate any function](https://archive.nyu.edu/jspui/bitstream/2451/14329/1/IS-92-13.pdf) (by Leshno et al., 1993) provides a theorem claiming this and the (quite long) proof of the theorem in the appendix.
  
  After a quick reading, it seems to me that they do not provide a very intuitive explanation of why the non-polynomiality of the (bounded, non-constant, and not necessarily continuous) activation function is *necessary and sufficient* (it's an [*if and only if*](https://en.wikipedia.org/wiki/If_and_only_if) result, see the last paragraph on p. 4) for a single-layer neural network to approximate any continuous function.
  
  The theorem (p. 10) formally states that the set of all possible functions that the neural network can compute, denoted by $\Sigma\_n$, is [*dense*](https://encyclopediaofmath.org/wiki/Dense_set) in $C(\mathbb{R}^n)$, the set of continuous functions from $\mathbb{R}^n$ to $\mathbb{R}$ (and being dense in $C(\mathbb{R}^n)$ is the equivalent mathematical statement to "neural networks can approximate any continuous function"). To understand this, you need to understand what a dense (sub)set is. To understand that, you need to understand what a [closure of a set $S$](https://en.wikipedia.org/wiki/Closure_(topology)) is: intuitively, it's the set of all points $S$ plus the points near the set $S$.
  
  To prove this theorem (p. 12), they proceed in 7 steps, so it's a long proof.
  
  For example, in step 1, they show (or just state) that, if the activation function $\sigma$ is a polynomial, then $\Sigma\_n$ is not dense in $C(\mathbb{R}^n)$. They conclude that $\Sigma\_n$, with such an activation function, would be a set of polynomials, which is not dense in $C(\mathbb{R}^n)$ (not sure why this is the case, but there is an old question [here](https://math.stackexchange.com/q/3884806/168764) that asks exactly this; I think that understanding this would be a great step for *intuitively* understanding the theorem).
  
  I don't plan to go over all the steps now, but, if you spend some time reading this paper, you should have the answer of why the non-polynomiality of the activation function is necessary and sufficient for the neural network to approximate any continuous function of the form $f : \mathbb{R}^n \rightarrow \mathbb{R}$. If that is not very useful, you could try reading the other related (but even longer) paper [Approximation theory of the MLP model in neural networks](https://pinkus.net.technion.ac.il/files/2021/02/acta.pdf) (by Pinkus, 1999).
  
  So, I wouldn't say that non-polynomiality is a complexity requirement, but really a theoretical requirement for approximating continuous functions.
  
  (By the way, I think there's a typo on page 6. They write $f\_\omega : \mathbb{R} \rightarrow \mathbb{R}^n$ to denote the function the neural network computes, but I am pretty sure they meant $f\_\omega : \mathbb{R}^n \rightarrow \mathbb{R}$; in fact, previously, they assume that the neural network has $n$ inputs and $1$ output).
  
  
  ---
  
  ### Answer by username_1 on 2023-10-03. Score: 1
  
  Like the accepted answer, I'm assuming you are referring to (literature refering to) Leshno et al, 1993. That paper only concerns 1-layer neural networks, and those are simply of the form
  $$x\mapsto\sum\_{j=1}^Na\_j\sigma(w\_j\cdot x+\theta\_j)\qquad(N\in\mathbb N,a\_j\in\mathbb R,w\_j\in\mathbb R^n,\theta\_j\in\mathbb R).$$
  I think of them as sums of scaled, dilated and rotated versions of the activation function $\sigma$. If the activation function is a polynomial of degree $k$ then every 1-layer neural network will be a polynomial of degree $k$ (and no higher). It is easy to construct a function that cannot be approximated (uniformly on the unit cube) by polynomials of degree $k$. Generically, polynomials of degree $k+1$ cannot be approximated by polynomials of degree $k$.
  
  For example, take $n=1$ (one input dimension). Then $f(x)= x^3$ cannot be approximated by 2nd degree polynomials: the latter are all parabolas. So $f$ cannot be approximated (uniformly on $[-1,1]$) by 1-layer neural networks with activation function $\sigma(x)=x^2$.
  
  
  ---
  
  