6
$\begingroup$

The problem with gradient descent algorithms, e.g. the Levenberg–Marquardt algorithm, is that they will converge into a minimum that is nearest to the initial guess, so when starting from different positions you will end up in different minima.

Is there a gradient based algorithm that gives similar results no matter where it starts? e.g. one that will escape shallow minimum, and therefore is more likely to converge into a global minimum, or at least a local minimum that is similar to the global. This could be achieved by giving the gradient descent "inertia", so as the alternative moves down the partial derivatives, it gains momentum, and then once all the partial derivatives equal zero (i.e. a minimum), the algorithm continues to move in the direction it was going before, but starts to slow down, as it is now going up the partial derivatives. This would help it escape local minimum and find global minimum.

Does an algorithm like this exist? (That's not a global optimization algorithm like the genetic algorithm or particle swarm optimization)

$\endgroup$
  • 1
    $\begingroup$ It would seem that by definition the answer has to be no: because a gradient is by definition a local quantity but the global maximum is (obviously) a global property, no algorithm "that's not a global optimization algorithm" will efficiently find optima for a reasonably large class of functions. $\endgroup$ – whuber May 26 '14 at 14:41
5
$\begingroup$

This is more of a workaround than a direct solution, but a common way to avoid local minima is to run your algorithm several times, from different starting locations. You can then take the best outcome or the average as your final result.

The reason why you might want to take the average rather than the best is to avoid overfitting. Many model types where local minima are a problem have lots of parameters: decision trees, neural networks, etc. Simply taking the best outcome risks obtaining a model that won't generalise well to future data. Taking the average guards against this.

You can get into arbitrarily complex ways of doing the averaging. Have a look at

$\endgroup$
  • $\begingroup$ This is a good solution, thanks. Just a shame it just takes so much time. $\endgroup$ – Blue7 May 26 '14 at 21:48
  • 1
    $\begingroup$ That depends on the context. A nice feature of this approach is that it's embarrassingly parallel, so it scales very easily on many computing architectures: multicore PCs, computing clusters, etc. Assuming that fitting one model is doable, you can fit an ensemble of dozens/hundreds of models without taking much more time. $\endgroup$ – Hong Ooi May 27 '14 at 7:52
6
$\begingroup$

This could be achieved by giving the gradient decent "inertia", so as the algorithm alliterative moves down the partial derivatives, it gains momentum, and then once all the partial derivatives equal zero (i.e a minimum), the algorithm continues to move in the direction it was going before, but starts to slow down, as it is now going up the partial derivatives. This would help it escape local minimum and ...

enter image description here

... then head straight back in again, from the other side.

(Here the green is the global min, the red a nearby local min.)

If you have multiple local minima and the global minimum isn't "wide" enough for you to conveniently blunder into from almost anywhere, such simple ideas won't really help much.

$\endgroup$
2
$\begingroup$

I think Stochastic Gradient Descent is pretty good at avoiding being stuck in a local minumum. The parameters are estimated for every observation, this gives SGD more randomness, and therefore it is more likely to jump out of a local minimum.

$\endgroup$

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.