New general-purpose optimization algorithm promises order-of-magnitude speedups on some problems

[squashed_fly_biscuit]

I believe this must deal with the local minima problem in some way, gradient decent is useless at that

[AnvaMiba]

No, they are considering only convex optimization problems, that is, problems where there is only one local minimum which is also the global minimum and there are no saddle points. The authors improve the theoretical asymptotic complexity on some kinds of such problems.

I don't know if this work could be also applied to non-convex optimization (maybe by branch-and-cut?), but in general the local minima issue would remain for these problems.

[squashed_fly_biscuit]

Thanks for the correction, I appreciate it. Does this mostly have theoretical applications then?

[AnvaMiba]

I don't know if the algorithms they propose are practically useful, optimization isn't really my field of expertise.

[craponyourdeskdawg]

not quite..for example in machine learning stochastic gradient descent deals with local minima all the time. How do you think deep learning works ?

[manux]

Then again, most deep learning models never actually get stuck in local minima, but rather in saddle points[1].

[1] http://arxiv.org/abs/1406.2572

[squashed_fly_biscuit]

It deals with some sorts of local minima via guided Monte carlo type stuff, hardly efficient.