2
$\begingroup$

In the following lines, I do not understand what it means to have a high cost for local minima than a global minima?

Local minima can be problematic if they have high cost in comparison to the global minimum. One can construct small neural networks, even without hidden units, that have local minima with higher cost than the global minimum. If local minima with high cost are common, this could pose a serious problem for gradient-based optimization algorithms.

$\endgroup$

1 Answer 1

13
$\begingroup$

An optimization algorithm's goal is to minimize a cost function $C$. Some optimization techniques (such as gradient-based methods) are only guaranteed to find a local minimum rather than the global minimum of $C$. So if $C$ looks like the picture below, a gradient-based method might find the local minimum $x_0$, which has much higher cost than the global minimum $x^*$.

In this example, you could avoid the problem by running the optimization several times with random starting points. But as the quotation mentions, this is not effective when there are many high-cost local minima.

enter image description here

$\endgroup$
1
  • $\begingroup$ Tiny (perhaps straightforward) addition from my side, in case the last line of your quote is still unclear: Many algorithms (especially gradient-based ones, as you mention) try to find the global minimum by finding the direction in model space in which $C(x)$ decreases most rapidly. This explains why it can get stuck in $C(x_{0})$ in the illustration above, that direction does not exist. This is what the authors meant in "If local minima with high cost are common, this could pose a serious problem for gradient-based optimization algorithms.". There are many such places to get stuck. $\endgroup$
    – Floris
    Sep 7, 2018 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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