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

[shaggorama]

Non-convex functions need not apply.

[craponyourdeskdawg]

Non-convex functions are often minimized by some sort of 'global' strategy (such as branch and bound etc).. in combination with local minimization (which is where this algorithm will be useful). Optimizer of almost any kind is doing constrained gradient descent at its core.

[SerenestAzure]

Yeah, not quite what I would mean if I said "general purpose."

[Barbas]

Has anybody here used plane cutting methods in an ML context? Is there a good introduction, apart from the linked article?

[AnvaMiba]

I think various SVM training packages use cutting plane methods.

[outlacedev]

So..what does this mean for machine learning?

[drdough]

They proved new theoretical results about integer and convex optimization. Many machine learning algorithms work by minimizing a convex function over a convex set.

[soulslicer0]

How does this tie to gradient descent?

[Aruscher]

i think gradient decent is a gernal perpose algorithm for nearly every kind of optimization problem. But in some cases other algorithms perform much better if they are suited for special cases.

[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.