Body: <p>A fully connected Neural Network architecture can be characterized by a vector <span class="math-container">$\mathbf a = (a_0,a_1,\ldots,a_L)\in\mathbb N^{L+1}$</span> and an activation function <span class="math-container">$\sigma :\mathbb R\to\mathbb R$</span>. In this setting, <span class="math-container">$a_0$</span> is the input dimension and <span class="math-container">$a_L$</span> the output dimension of the network. <span class="math-container">$L$</span> represent its depth (the number of hidden layers) and <span class="math-container">$W:=\max_{1\le i\le L} a_i$</span> represents its width (the hidden layer with the highest number of neurons).<br />
  With that formalism, given a set of parameters <span class="math-container">$\boldsymbol\theta := \Big((A_l,b_l)\Big)_{l=1}^L \in \Big(\mathbb R^{a_1\times a_0}\times\mathbb R^{a_1}\Big)\times\cdots\times\Big(\mathbb R^{a_L\times a_{L-1}}\times\mathbb R^{a_L}\Big)$</span>, the function realized by a neural network with architecture vector <span class="math-container">$\mathbf a$</span>, activation function <span class="math-container">$\sigma$</span> and parameters <span class="math-container">$\boldsymbol \theta$</span> is given by
  <span class="math-container">$$\mathcal F_{\boldsymbol\theta} : x\in\mathbb R^{a_0}\mapsto \mathcal A_{(A_L,b_L)}\circ\sigma\circ\cdots\circ\sigma\circ \mathcal{A}_{(A_1,b_1)}(x) $$</span>
  Where <span class="math-container">$\mathcal{A}_{(A_l,b_l)}(x):= A_l x + b_l$</span> and <span class="math-container">$\sigma$</span> is applied componentwise. This mathematical formulation of Fully Connected Neural Networks is taken from, e.g., <a href="https://arxiv.org/abs/1809.03062" rel="nofollow noreferrer">this paper by Berner et al. (2020)</a> (page 3).</p>
  <p>My question is now the following : consider a neural network with architecture vector <span class="math-container">$\mathbf a$</span>, depth <span class="math-container">$L$</span>, width <span class="math-container">$W$</span> activation function <span class="math-container">$\sigma$</span> and <em>fixed</em> parametrization <span class="math-container">$\boldsymbol\theta$</span>. For any other architecture vector <span class="math-container">$\mathbf a'$</span> with depth <span class="math-container">$L'\ge L$</span>, number of neurons in each layer satisfying <span class="math-container">$a_l'\ge W\ \forall 1\le l\le L-1$</span> and activation function <span class="math-container">$\sigma$</span>, is it possible to find a parametrization <span class="math-container">$\boldsymbol \theta'$</span> such that
  <span class="math-container">$$ \mathcal F_{\boldsymbol\theta} (x)= \mathcal F_{\boldsymbol\theta'}(x)\ \ \forall x\in\mathbb R^{a_0 }\ ?$$</span></p>
  <p>(of course, we need to assume <span class="math-container">$a_0' = a_0$</span> and <span class="math-container">$a_{L'}' = a_L$</span>). In words, I am asking : <strong>can Neural Networks with more computation units in each layer AND more hidden layers represent ALL neural networks with fewer computation units and hidden layers ?</strong></p>
  <p>Intuitively, I am pretty sure that the answer is yes : for instance, if we don't increase the depth but only the number of neurons in each hidden layer, we can simply reproduce the smaller network with a properly chosen subset of the units, and set everything else to zero. The problem if we add more layers and do as I just said is that we now need to have the identity function from the <span class="math-container">$L$</span>-th to <span class="math-container">$L'$</span>-th layer, which is not feasible exactly for any reasonable activation function (I am mostly interested in ReLU, in which case a good approximation on a compact set is possible, but not an exact equality). Because deeper networks are more expressive, I would bet that the result still holds in that case.</p>
  <p>I would appreciate an answer containing a proof and/or a reference (I am fine with adding more assumptions if needed). Thank you in advance.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-18T12:15:23.623Z
Comments.Text: So, you're really interested just in the case where all activation functions are equal (in both neural networks) and cannot be changed from layer to layer?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-07-20T11:33:14.447Z
Comments.Text: @nbro yes, exactly, the activation function is the same throughout all layers for both networks (it could be a ReLU activation for instance)
Comments.UserDisplayName: Stratos supports the strike
Tags: <neural-networks><papers><math><deep-neural-networks>
Title: Can a Fully Connected Neural Network represent all Neural Networks of smaller size?
UserDisplayName: Stratos supports the strike
ThreadText: # Can a Fully Connected Neural Network represent all Neural Networks of smaller size?
  
  (Asked by: username_0 on 2023-07-13)
  
  A fully connected Neural Network architecture can be characterized by a vector $\mathbf a = (a\_0,a\_1,\ldots,a\_L)\in\mathbb N^{L+1}$ and an activation function $\sigma :\mathbb R\to\mathbb R$. In this setting, $a\_0$ is the input dimension and $a\_L$ the output dimension of the network. $L$ represent its depth (the number of hidden layers) and $W:=\max\_{1\le i\le L} a\_i$ represents its width (the hidden layer with the highest number of neurons).  
  With that formalism, given a set of parameters $\boldsymbol\theta := \Big((A\_l,b\_l)\Big)\_{l=1}^L \in \Big(\mathbb R^{a\_1\times a\_0}\times\mathbb R^{a\_1}\Big)\times\cdots\times\Big(\mathbb R^{a\_L\times a\_{L-1}}\times\mathbb R^{a\_L}\Big)$, the function realized by a neural network with architecture vector $\mathbf a$, activation function $\sigma$ and parameters $\boldsymbol \theta$ is given by
  $$\mathcal F\_{\boldsymbol\theta} : x\in\mathbb R^{a\_0}\mapsto \mathcal A\_{(A\_L,b\_L)}\circ\sigma\circ\cdots\circ\sigma\circ \mathcal{A}\_{(A\_1,b\_1)}(x) $$
  Where $\mathcal{A}\_{(A\_l,b\_l)}(x):= A\_l x + b\_l$ and $\sigma$ is applied componentwise. This mathematical formulation of Fully Connected Neural Networks is taken from, e.g., [this paper by Berner et al. (2020)](https://arxiv.org/abs/1809.03062) (page 3).
  
  My question is now the following : consider a neural network with architecture vector $\mathbf a$, depth $L$, width $W$ activation function $\sigma$ and *fixed* parametrization $\boldsymbol\theta$. For any other architecture vector $\mathbf a'$ with depth $L'\ge L$, number of neurons in each layer satisfying $a\_l'\ge W\ \forall 1\le l\le L-1$ and activation function $\sigma$, is it possible to find a parametrization $\boldsymbol \theta'$ such that
  $$ \mathcal F\_{\boldsymbol\theta} (x)= \mathcal F\_{\boldsymbol\theta'}(x)\ \ \forall x\in\mathbb R^{a\_0 }\ ?$$
  
  (of course, we need to assume $a\_0' = a\_0$ and $a\_{L'}' = a\_L$). In words, I am asking : **can Neural Networks with more computation units in each layer AND more hidden layers represent ALL neural networks with fewer computation units and hidden layers ?**
  
  Intuitively, I am pretty sure that the answer is yes : for instance, if we don't increase the depth but only the number of neurons in each hidden layer, we can simply reproduce the smaller network with a properly chosen subset of the units, and set everything else to zero. The problem if we add more layers and do as I just said is that we now need to have the identity function from the $L$-th to $L'$-th layer, which is not feasible exactly for any reasonable activation function (I am mostly interested in ReLU, in which case a good approximation on a compact set is possible, but not an exact equality). Because deeper networks are more expressive, I would bet that the result still holds in that case.
  
  I would appreciate an answer containing a proof and/or a reference (I am fine with adding more assumptions if needed). Thank you in advance.
  
  **Tags:** neural-networks, papers, math, deep-neural-networks
  
  > **Comments:**
  > **username_1**: So, you're really interested just in the case where all activation functions are equal (in both neural networks) and cannot be changed from layer to layer?  
  > **username_0**: @username_1 yes, exactly, the activation function is the same throughout all layers for both networks (it could be a ReLU activation for instance)  
  
  ---
  
  ## 0 answers
  
  