How to count the maxwidth and layers' number of a feedforward neural network?

Question

Definition $\phi$ is a feedforward neural network (FNN)$$\phi = W_L(\sigma(W_{L-1}(\sigma(\cdots > \sigma(W_1(x))\cdots))))$$ with affine linear maps $W_l:\mathbb{R}^{N_l-1}\to \mathbb{R}^{N_l},l\in \{1,2,\cdots,L\}$, and ReLU activation function $\sigma = \max(0,x)$,acting component-wise, i.e $\sigma(x_1,\cdots,x_N)=(\sigma_1,\cdots,\sigma_N)$.

Suppose FNN $\psi_i\in NN(\#input =1;maxwidth\leq m_i,\#layer \leq n_i),x\in [0,1],i=1,2$, which means that the maxwidth of all hidden layers $\leq m_i$,the number of hidden layers $\leq n_i$.

Now construct a FNN $$\phi(x) = \psi_1(x) + \psi_2(x-\psi_1(x))$$

$\phi$ is a summation of two FNN, and $x-\phi_1(x)$ is stacked in to $\psi$.

According to the definition of FNN above. it seems not obvious that whether $\phi$ is a FNN, because the numbers of all hidden layers of two FNNs may not be the same, so the affine transform of two FNN may not correspond to each other to compose of a new affine map from a layer to the next one.

And concerning the $x$ in $x- \psi_1(x)$, how does it transformed to the end of $\psi_1$ so that the $x$ can minus $\psi_1(x)$? I'm not sure whether I'm wrong with it. Is it correct that $x $ is understood as $ \sigma(\cdots \sigma(x))$ could answer the privious question? And what's the maxwidth $\phi$?

The problem comes from a step in a paper I'm reading about the approximation of neural networks:Deep Network Approximation Characterized by Number of Neurons.

Thanks for reading! Any help would be appreciated.

Answer 1

You are right, it is not immediately clear why $\phi$ can be realized as a neural network. The catch is that we can construct a ReLU network with a single hidden layer that computes the identity function. If we compose two such identity networks with each other, then we obtain a ReLU network with two hidden layers computing the identity function. Continuing in this fashion, there are ReLU networks of arbitrary depth that compute the identity.

Now you can build a ReLU network with the same depth as $\psi_1$ computing the identity and then obtain a well-defined network computing $x-\psi_1(x)$. Next, compose $\psi_2$ with the new network computing $x-\psi_1$. In general, this new network has greater depth than $\psi_1$ (since $\psi_1$ itself appears here), so we cannot readily add them together to obtain $\phi$. However, we can create yet another new network by composing $\psi_1$ with a ReLU network that computes the identity and has the same depth as $\psi_2$. This way, this new network still computes $\psi_1$ but has depth = depth($\psi_1$) + depth($\psi_2$) just like the network computing $\psi_2(x-\psi_1(x))$. In particular, now we can add them together to obtain $\phi$.