Optimization in the context of machine learning

https://blog.algorithmia.com/introduction-to-optimizers/

by bourbakis • 8 years ago

143 26 8 years ago

blog.algorithmia.com

enthdegree2• 8 years ago

newton's method?

mkl3• 8 years ago

Newton's method finds zeros of functions, which is different from optimisation (finding maximums or minimums). If you use Newton's method on a function which is the derivative of some other function you're trying to optimise, then it will find critical points, which may be the optimums you're looking for (or inflection points, saddles, etc.).

snovv_crash2• 8 years ago

This is why you actually do something like Levenberg-Marquardt, which combines a gradient descent with a trust region of quadratic optimization, which is varied depending on if the cost function is decreasing or not. And of course it is iterative, so a single bad step doesn't destroy everything. The advantage comes from faster convergence in practice.

hnuser355• 8 years ago

I don’t know any of machine learning but I’ve heard folks in some fields will prefer a gradient descent algorithm even though it doesn’t have nice convergence speed because the Hessian (Hessian approximation) will be too huge or difficult to calculate

salty_biscuits• 8 years ago

There are always tricks to keep the problem size small for quadratic methods(such as L-BFGS). In ML stochastic gradient descent (a bad name for doing gradient descent on batches of the data at a time) seems to have a bit of magic in it's ability to go uphill to escape local minima as well as letting the problem scale to much larger sets of data.

knicholes• 8 years ago

Newton's method requires calculating the second derivative, which is quite a bit more expensive than SGD, especially with many parameters.

nagVenkat• 8 years ago

By Newton’s method, do you mean simple gradient descent?

enthdegree2• 8 years ago

no.

taeric• 8 years ago

This is... Misnamed? Optimization solvers are a different topic than what has grown to dominate machine learning. Isn't it?

mkl3• 8 years ago

Yes, it's talking about optimisation in the context of machine learning, which is a narrow slice of optimisation as a field.

dang• 8 years ago

I've pinched that phrase to make a less misleading title. Hope that's ok!

david_draco2• 8 years ago

For a bit of a wider view, see for example the OpenOpt problem tree: https://web.archive.org/web/20150206060441/http://openopt.or... Probably most interesting is "Non-Linear Problems (NLP)" there, and if you click in, you can see algorithms.

david_draco2• 8 years ago

I am surprised the SGD extensions of https://arxiv.org/abs/1704.04289 have not been picked up yet (via https://www.inference.vc/everything-that-works-works-because...).

moultano• 8 years ago

It's interesting work, but I don't think it's relevant to real world models, because real world models violate the conditions they assume at the outset. Namely, real models are not run until anything near convergence on the training set. Everyone uses early stopping to prevent them from overfitting, which they happily do if left to train forever.

sgt101• 8 years ago

Has there been any progress in the art around this issues? The idea of optimise until it stops making sense to optimise is terribly unsatisfying. I think it means "don't optimise this, but move to another state in a way that is approximately optimisation" or "optimise to this special state". Is there art to define "this special state" which is the generalising classifier. There wasn't anything (for sure) in 1997, although we thought that there were two types of risk minimisation - structural risk (size of classifier) and empirical risk (error on datasets) but no one had an idea of how to use these ideas well. I did some work where I pruned optimised ensembles using GA's to get better generalisation vs direct trained, but everyone hated it because it was inefficient.

Then people looked at deep networks and the structural risk minimisation stuff went out of the window I guess.

blt• 8 years ago

To avoid getting stuck in local minima, we make sure we use the proper learning rate

This sentence is extremely misleading. It implies that gradient descent always reaches a global minimum if the "proper" learning rate is used. Guarantees of that form are only available for restricted families of function such as Lipschitz-smooth convex functions.

rq1• 8 years ago

And you don’t necessarily want a global minimum of an universal approximator...

aldanor2• 8 years ago

Wanted to share a wonderful addition to scipy I’ve recently discovered for myself (since the topic kind of fits):

https://docs.scipy.org/doc/scipy/reference/optimize.minimize...

This was added in 1.0+, along with a few other trust-* methods, basically a quite modern miltivariate constrained optimization method, deals pretty well with noisy functions you typically encounter in ML.

aldanor2• 8 years ago

Ooook thanks for downvotes then..

DrNuke• 8 years ago

It always depends on your problems, your targets and your metrics. The most critical aspect for many industrial applications is false positives, so that machine learning extreme / redundant optimisation becomes cheaper for the business in the long term.

mlevental• 8 years ago

something i've never understood: all of the ml frameworks (tf, pytorch, etc.) are seemingly pretty good at optimization of at least a particular set of cost functions (convex quadratic? but i know that with activation functions ml cost functions aren't really convex quadratic) so why aren't there general optimization libraries built on top of them? like why are GAMS and AMPL still a thing? is it simply because they're more general? and also as a corollary how good are the optimizers baked into the ml frameworks relative to tools like GAMS and AMPL?

tmyklebu• 8 years ago

It might be instructive for you to try solving the linear programs in netlib[0] with stochastic gradient descent. ;)

The short version of the story is that different optimisation problems have different kinds of structure, and the user will want solutions of different quality and have different amounts of patience depending on the context. Practical optimisation is largely about finding ways to exploit the structure of a problem to get solutions of some quality in some amount of time. No known optimisation algorithm dominates all others.

In many machine learning contexts, you want a low-precision solution to a problem with an objective that's expensive to compute but can be reasonably approximated by random sampling. Often, when you use a linear program solver, you want a solution to a linearly-constrained problem where the geometry of the constraints may not be "easy" and any violation renders a solution completely useless.

Good LP solvers can solve "typical" well-formulated LPs with hundreds of thousands of variables and constraints in a matter of seconds on modern hardware[1]. These algorithms can't solve many of the problems you're going to feed into your deep learning framework at all. Conversely, your deep learning framework will have a hell of a time solving LPs.

As for why GAMS and AMPL are a thing, they're interfaces to solvers, not solvers themselves. You use them because they can handle pulling the data out of the database, translating your GAMS/AMPL program into a formulation suited to the solver you choose, running the solver, and handing back the results. It's straightforward but tedious to do this all on a case-by-case basis; GAMS and AMPL automate much of the uninteresting work.

[0] http://www.netlib.org/lp/ [1] http://plato.asu.edu/ftp/lpcom.html

Optimization in the context of machine learning

Related Stories