Before I ask my actual question, I just want to verify that the following is correct:

A multi-layer neural network with an identity activation function is equivalent to a single layer (also with identity activation function) neural network? This is mathematically obvious unless I am missing something.

Moving on to my actual question:

I generated some synthetic data for training. The independent variable is a 100 element array for each sample. The first sample is $$ S_0 = [0 \ \ 1\ \ 2\ \ 3\ \ \ldots\ \ 99] $$

There are 1500 training samples. Each training sample follows this relation $$ S_i = S_0 + i*100 \ \ \ \forall i = 1,\ldots,1499 $$

The training labels are simply:

$$ \ell_i = i $$

I am using pytorch, with MSE as the objective function, and batch gradient descent as the optimization method.

The 4 layer network contains 100, 500, 250, 1 node(s), respectively. The 1 layer network contains 1 node, the output node.

The first plot below shows the MSE error vs. epoch # for 1 layer network. The second plot shows the MSE error vs. epoch # for the the 4 layer network. The y-axis is on a log-scale, and you can see that the 1 layer network converges to a value that is about 3-4 orders of magnitude larger than the 4 layer network. Shouldn't they be converging to the same value because of what is in italics at the top of this post?

This result is very puzzling to me and I do not understand why this is the case.

enter image description here

enter image description here


For starters, let us show that indeed the underlying relationship of this dataset of size $M$ is linear. We are given that the data is generated by the relationship

\begin{align} S_i &= S_0 + 100 i \boldsymbol{1}^T \tag*{$\forall i \in \lbrace 0, 1, \cdots, M-2, M-1 \rbrace$} \end{align}

where $\boldsymbol{1} \in \lbrace 1 \rbrace^{100}$ and $S_0 = [0, 1, \cdots, 98, 99]$. We are also told the label $l_i$ for $S_i$ is $l_i = i$. With the definitions above, it is clear that the analytical solution to this model is indeed $l_i = S_i w$, where $w = [w_0, w_1, \cdots, w_{99}]^T = [10^{-2}, 0, \cdots, 0]^T$. We see this because

\begin{align} l_i &= S_i w \\ &= S_0 w + 100 i \boldsymbol{1}^T w \\ &= 100 i w_0 \\ &= i \end{align}

Thus, the data can indeed be captured by a linear model and consequentially one can model it exactly using a single layer neural network with linear activations.

Now the question is, why are you struggling to converge to the unique global minimum of your corresponding optimization? While this data described above looks quite simple, it is actually interesting to see that the data produces a poorly conditioned optimization problem. We first note that your single layer neural network with linear activation is effectively defined as

\begin{align} f(S) = Sw + b \end{align}

where $w$ and $b$ need to be estimated using the data. For simplicity, I will define $\hat{S} = [S, 1]$ and $\hat{w}^T = [w^T, b]$, making the neural net $f(\hat{S}) = \hat{S} \hat{w}$. Since you are training with a Mean Squared Error (MSE) cost function, we know the optimization problem to solve is

\begin{align} \min_{\hat{w}} \frac{1}{2N} \left(X \hat{w} - L\right)^T \left(X \hat{w} - L\right) \end{align}

where $X^T = [S_0^T, S_1^T, \cdots, S_{M-1}^T]$ is a stacked set of the inputs and $L^T = [l_0, l_1, \cdots, l_{M-1}]$ is a stacked vector of all the output labels. This cost function is convex since the hessian is $H = X^T X$, which is clearly positive semi-definite. Since this function is a paraboloid, we can investigate the condition number of the hessian $H$ to gain insight into how easy it will be to traverse the error surface with first order optimization methods.

Performing a simple computation, one can find for $M = 1500$ that $\text{cond}(H) = O\left(10^{21}\right)$, which is very large. This is telling us that the ellipsoid isosurfaces for the error surface have extremely skewed shapes. An example of this and the optimization progress can be seen in the visual below:

High Condition Number Isosurfaces with sample gradient descent

As one can imagine based on the visual, the extremely skewed shapes greatly impact convergence to the actual local (global) minimum and can require many more iterations. In our actual example, since the condition number is so large, the skew is much, much worse than what's shown in the visual.

Anyway, the situation affecting convergence in the above example is largely due to a poorly conditioned optimization problem. The poor convergence rates in the first image make me skeptical about the optimization code being used because a simple momentum-based gradient descent with line searches, which I wrote in a few minutes to investigate this problem, converges to $O(10^{-2})$ error in less than 10 iterations. However, even with a properly coded optimization algorithm, first order optimization methods should struggle to converge quickly for this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.