# Does MLP always find local minimum

In linear regression we use the following cost function which is a convex function:

We Use the following cost function

in logistic regression because the preceding cost function is not convex whenever the hypothesis (h) is logistic function. We have changed the equation of cost function to have a convex shape to find its global (the only one which exists). There is a fact that I can not understand. In Multi Layer Perceptrons ANNs I have seen a lot that they can be stuck in local minimums. Why is that? We have used this cost function for each perceptron and gotten the rules for updating the values for the weights in back propagation algorithm; So why do we stuck?

• Because it follows from the behavior of gradient descent on nonlinear models? Try reducing your learning rate and occasionally adding some uniformly distributed noise to get unstuck. With big neural networks, it is more likely that you will be wandering around a saddle point than a local extremum because the models are overspecified, leading to multiple solutions. You might like this presentation. – Emre May 6 '17 at 21:09
• I meant, I saw this behavior in a book, not in my code – Media May 6 '17 at 21:15
• If you're interested in applying convex optimization to neural networks, read about homotopy/relaxation methods; e.g., Training Recurrent Neural Networks by Diffusion – Emre May 6 '17 at 21:28

The loss functions are only simple convex functions with respect to the weight parameters (and specific data) when there is a single layer. More exactly, they can proven to be always convex with respect to the weights in the simple models (linear or logistic regression), but not with respect to weights of deeper networks.

You can prove that there must be more than one minimum in a network with 2 or more layers - and thus the loss function cannot be convex - by considering swapping the weights around when you have found a minimum value. Unlike with a single layer network, it is possible to swap the weights around that feed into the hidden layer whilst maintaining the same output. For example, you can swap the weights between input and hidden layer so that values of neuron output 1 and neuron output 2 are reversed. Then you can also swap the weights feeding out of those neurons to the output so that the network still outputs the same value. The network would have a different set of weights, but generate the same outputs, and so this new permutation of weights is also at a minimum for the loss function. It is the "same" network, but the weight matrices are different. It is clear that there must be very many fully equivalent solutions all at the true minimum.

Here's a worked example. If you have a network with 2 inputs, 2 neurons in the hidden layer, and a single output, and you found that the following weight matrices were a minimum:

$W^{(1)} = \begin{bmatrix} -1.5 & 2.0 \\ 1.7 & 0.4 \end{bmatrix}$

$W^{(2)} = \begin{bmatrix} 2.3 & 0.8 \end{bmatrix}$

Then the following matrices provide the same solution (the network outputs the same values for all inputs):

$W^{(1)} = \begin{bmatrix} 1.7 & 0.4 \\ -1.5 & 2.0 \end{bmatrix}$

$W^{(2)} = \begin{bmatrix} 0.8 & 2.3 \end{bmatrix}$

As we said the first set of 6 parameters was a solution/minimum, then the second set of 6 parameters must also be a solution (because it outputs the same). The loss function therefore has 2 minima with respect to the weights. In general for a MLP with one hidden layer containing $n$ neurons, there are $n!$ permutations of weights that produce identical outputs. That means that there are at least $n!$ minima.

Although this does not prove that there are worse local minima, it definitely shows that the loss surface must be much more complex than a simple convex function.

• Would you please provide a link or at least a brief reason for proof of having more than one minimum in deeper networks, I can not understand this, and that is my question – Media May 6 '17 at 21:17
• @Media: That is what my second paragraph is about - it is a rough sketch of the proof. Could you explain more where you get stuck? The basic point is with more than one layer, there is more than one set of weights with the same output. This applies to all possible weights including those that output a minimum to the loss function. Therefore there is no unique weight matrix that gives a minimum. – Neil Slater May 6 '17 at 21:24