0
$\begingroup$

I came across an excercise on deep learning from here. It goes as follows: Consider a simple MLP with a single hidden layer of $d$ dimensions in the hidden layer and a single output. Show that for any local minimum there are at least $d!$ equivalent solutions that behave identically.

As the network is a MLP with one hidden layer, the equation would be: $O = W^{(2)}(W^{(1)}x + b_1) + b_2$

Assuming I am correct, where do I need to go from here to get to the solution?

$\endgroup$
2
$\begingroup$

If one permutes the connections of the hidden layer ($d!$ ways to do that), and move and rename connections appropriately, then one effectively has the same MLP with the exact same minima, yet the configuration has changed (in a trivial sense). Thus there are (at least) $d!$ configurations only trivialy different with the exact same minima.

To see it in your notation, effectively the hidden layer output is the following sum:

$$O_{\text{hidden}} = \sum_{i=1}^d w_{\pi_i} \cdot x + b_{\pi_i}$$

Where $\pi_i$ is some order of the connections. For example $\pi_i = i$

But for $d$ items there are $d!$ permutations thus $d!$ order functions $\pi(i) = \pi_i$. Yet the difference is only in re-ordering the configuration and is trivial. The rest follow from that.

This is one reason why Neural Networks are non-convex models.

See also: Explanation of why Neural Networks are non convex

$\endgroup$
1
  • $\begingroup$ Excellent explanation $\endgroup$ – Jayaram Iyer May 6 at 4:23

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.