Say I have some data and some graph fitting function. Just using gradient descent will find one particular local solution.

Now what I want to do is also put "feelers" out for other solutions. In essence I want to run the gradient descent many times in parallel to find different local solutions. And select the best one.

Once it has one, it could put it's feelers out again, by running another gradient descent with a random difference in variables. (Say a short difference, a medium distance, and a long distance).

Then it could run all these other trials and see if it can find another local minimum. (But keeping the local minimum it already found).

This way, hopefully over time it can eventually arrive at the best fit.

To visualise this imagine climbing to the top of a mountain. Then dropping people randomly around that mountain to see if they climb up to another mountain that is higher.

Well my question is, what is this kind of procedure called? In APIs like tensor flow would you have to implement something like this yourself?

Another related question is that in higher dimensions, are things less likely to get stuck in local minima? So this is not needed?


I think you'd call this SGD with multiple restarts (see here for people doing that kind of stuff).

I'm going to assume you're talking about running SGD in the context of training a deep neural network. The problem is doing one run of SGD until it has converged is often sufficiently computationally expensive that you're likely to get some pretty serious diminishing returns. In general if your optimisation problem is not convex then you're not even guaranteed to converge to a minima, just a stationary point.

I think there is some evidence that stochastic component of SGD allows it to avoids saddle points. There is also some evidence that local minima for linear deep neural networks are close to the global minima. but I am not aware of any evidence that suggests high dimensionality means you're less likely to get stuck in a local minima for nonconvex problems.


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.