Nonlinearity of deep learning

NOTE

This is part of the 8th homework, titled Deep Learning II, for the course Machine Learning (IN2064) in the Winter Semester 2024/25 at TUM.

Problem 3:

You are trying to solve a regression task and you want to choose between two approaches:

1. A simple linear regression model.
2. A feed forward neural network $f_W(x)$ with $L$ hidden layers, where each hidden layer $l\in \{1,\dots ,L\}$ has a weight matrix $W_l\in {\mathbb{R}}^{D\times D}$ and a ReLU activation function. The output layer has a weight matrix $W_{L+1}\in {\mathbb{R}}^{D\times 1}$ and no activation function. In both models, there are no bias terms. Your dataset $\mathcal{D}$ contains data points with nonnegative features $x_n$ and the target $y_n$ is continuous:

$$\mathcal{D}=\{(x_n,y_n){\}}_{n=1}^N,x_n\in {\mathbb{R}}_{\ge 0}^D,y_n\in \mathbb{R}$$

Let $w_{LS}^{\ast }\in {\mathbb{R}}^D$ be the optimal weights for the linear regression model corresponding to a global minimum of the following least squares optimization problem:

$$w_{LS}^{\ast }=\arg \underset{w\in {\mathbb{R}}^D}{\min }{\mathcal{L}}_{LS}(w)=\arg \underset{w\in {\mathbb{R}}^D}{\min }\frac{1}{2}\sum _{n=1}^N(w^{\top }{x}_n-y_n{)}^2$$

Let $W_{NN}^{\ast }=\{W_1^{\ast },\dots ,W_{L+1}^{\ast }\}$ be the optimal weights for the neural network corresponding to a global minimum of the following optimization problem:

$$W_{NN}^{\ast }=\arg \underset{W}{\min }{\mathcal{L}}_{NN}(W)=\arg \underset{W}{\min }\frac{1}{2}\sum _{n=1}^N(f_W(x_n)-y_n{)}^2$$

a) Assume that the optimal $W_{NN}^{\ast }$ you obtain are non-negative. What will the relation ($<,\le ,=,\ge ,>$) between the neural network loss ${\mathcal{L}}_{NN}(W_{NN}^{\ast })$ and the linear regression loss ${\mathcal{L}}_{LS}(w_{LS}^{\ast })$ be? Provide a mathematical argument to justify your answer.

b) In contrast to (a), now assume that the optimal weights $w_{LS}^{\ast }$ you obtain are non-negative. What will the relation ($<,\le ,=,\ge ,>$) between the linear regression loss ${\mathcal{L}}_{LS}(w_{LS}^{\ast })$ and the neural network loss ${\mathcal{L}}_{NN}(W_{NN}^{\ast })$ be? Provide a mathematical argument to justify your answer.

Solution: a)

In general, the following relation holds: ${\mathcal{L}}_{NN}(W_{NN}^{\ast })\le {\mathcal{L}}_{LS}(w_{LS}^{\ast })$, since the described neural network can, in the worst-case scenario, be equivalent to the linear regression model. In cases where there is nonlinearity between features $x_n$ and their labels $y_n$, it can outperform linear regression due to the nonlinearity achieved through the ReLU activation functions in all but the last layer.

However, we are assuming that the optimal weights $W_{NN}^{\ast }$ of the neural network are non-negative. Recall the ReLU activation function: $\text{ReLU}(z)=\max (0,z):z\in \mathbb{R}$ This means that if we constrain the domain of the input $z\ge 0$, then the ReLU function becomes equivalent to the identity function, i.e., we can remove it from our considerations. From the task description, we know that dataset $\mathcal{D}$ contains only non-negative features $x_n$. This means that outputs of all the layers will be non-negative as we assumed that the optimal weights $W_{NN}^{\ast }$ are non-negative too. Thus, our network becomes equivalent to the regression model, given that $L+1$ linear maps can be composed into a single one. Therefore, the relation between losses is as follows:

$${\mathcal{L}}_{NN}(W_{NN}^{\ast })={\mathcal{L}}_{LS}(w_{LS}^{\ast })$$

Solution: b)

Here the situation is a bit different as we assume the optimal weights for the linear regression model $w_{LS}^{\ast }$ are non-negative. That means that the optimal linear map between the feature space and label space only does scaling and stretching. Since the relationship between $x_n$ and $y_n$ can be nonlinear, then it would follow that the loss of the neural network at its global minimum can be lower than the loss of the optimal linear regression model. However, that is not the case if there are no bias terms in our network and all the input features $x_n$ are nonnegative. This is because each layer in effect is actually only a linear map, where negative weights are equivalent to multiplying by zero since, the ReLU activation function will set all negative values to zero either way. A composition of linear functions is a linear function thus the upper bound on loss is given by the loss of the optimal regression model.

This upper-bound can be reached by the neural network as it can represent any linear regression model by setting the weights of all hidden layers to identity matrices ($W_l=I$ for $l\in 1,\dots ,L$) and setting the output layer weights $W_{L+1}$ equal to $w_{LS}^{\ast }$. This means that the neural network’s hypothesis space strictly includes the linear regression model’s hypothesis space. Therefore, the relation between losses is: ${\mathcal{L}}_{NN}(W_{NN}^{\ast })={\mathcal{L}}_{LS}(w_{LS}^{\ast })$