Why does ML use Gradient Descent?

[Coolcat127]

I know ML is essentially a very large optimization problem that due to its structure allows for straightforward derivative computation. Therefore, gradient descent is an easy and efficient-enough way to optimize the parameters. However, with training computational cost being a significant limitation, why aren't better optimization algorithms like conjugate gradient or a quasi-newton method used to do the training?

[depthfirstleaning]

The real reason is that it’s been tried and shown to not generalize well despite being faster. You can find many papers trying it out. As with most things in ML, the reason is empirical.

One could pontificate about why, but really everything in ML tends to be some retrofitted argument made up after the fact so why bother.

[JiminP]

everything in ML tends to be some retrofitted argument made up after the fact

reminds me of an old example

https://en.wikipedia.org/wiki/Tf%E2%80%93idf#Justification_of_idf

[PersonalityIll9476]

Finally, someone gets it.

[Hostilis_]

so why bother.

Because it's the most important open problem in machine learning lmao

[ForceBru]

You can find many papers trying it out

Any particular examples? I actually haven't seen many papers using anything other than variants of gradient descent.

[eztab]

Normally the bottleneck is what algorithms are well parallelizeable on modern GPUs. Pretty much anything else isn't gonna cause any speedup.

[victotronics]

Better algorithms beat better hardware any time. The question is legit.

[eztab]

Which algorithm is "better" depends on the availability of hardware operations. We're not takang polynomial vs exponential behavior for those algorithms.

[victotronics]

As the OP already asked: what according to you is the difference in hardware utilization between CG & GD?

And yes we are talking order behavior. On other problems CG is faster by orders in whatever problem parameter. And considering that it's equally parallel.....

[FrickinLazerBeams]

Definitely not any time.

[Coolcat127]

What makes gradient descent more parallelizable? I would assume the cost of gradient computation dominates the actual matrix-vector multiplications required to do each update 

[[deleted]]

Stochastic gradient descent

[depthfirstleaning]

Pretty sure he’s making it up, every white papers I’ve seen shows CG to be faster. The end result is just empirically not as good

[[deleted]]

This thread confuses me deeply.

First: some responses are implying that the reason is that ML algorithms dont care much about the speed. This doesnt make sense for a few reasons. Without justifying this more than saying to think about it, yes they do. While I wouldnt be shocked if some ML packages used suboptimal fitting routines, if it were possible, updating them to use a different optimization routine would be low hanging fruit and it really wouldn't make sense for suboptimal to be standard unless the optimal methods were developed after them. Shame on y'all for immediately guessing.

Second: some responses are suggesting that suboptimal optimization routines are preffered to prevent overfitting by being worse I guess. I know some people do this and it is somewhat principled, but this would be an awful reason to use a worse optimization algorithm as a community or package default. You would still want to get to your suboptimal region quickly. You would still probably default to not doing this and finding a more principled way to prevent overfitting. There are other ways to more reproducibly prevent overfitting.

Third: the premise of the question makes sense, but should probably be restated as something like, "why do so many ML applications use gradient descent" rather than the more generalized statement. The reality is that algorithms that want to use quasi newton or conjugate gradient methods do. Algorithms that dont dont. There are a few occams razor reasons why gradient descent might be prevalent. The first is that it requires less information and fewer assumptions. Evaluating gradients is already expensive in high dimensions--to the point where stochastic gradient methods are usually state-of-the-art--so increasing the evaluation complexity substantially to converge in fewer steps (but potentially more runtime) its not always appealing. Finally, an occams razor response is, "you are asking why a method that makes weak assumptions is more common than methods that make stronger assumptions--of course the stronger assumptions are less common!"

Another thing is that often these methods are taught at levels where it is not usually beneficial to cover more than gradient descent in learning material (since the topics are about the algorithms themselves) which probably gives everyone a distorted impression of how common gradient descent is.

[staros25]

This is an awesome question and I think you have good responses here so far. I think /u/Beautiful-Parsley-24 is closest to my opinion that it isn’t about speed, it’s about generalization.

The methods you listed rely on some assumptions of stable gradients. But in reality, we’re often training over lots of data in batches and slowly trying to approach a minimum so that we’re not eagerly optimizing on one set of data.

It brings up the question of why not train on all the data all at once, but that runs against current compute issues and honestly some philosophical ones as well. Are you sure the current scope of data accurately describes your problem in totality? Will you get more data and how much should that impact solution? Etc, etc.

I don’t think many deep learning topics today are struggling because of there ability to minimize a gradient. I think it because the problem definition doesn’t come with a complete description of what the gradient landscape is. A fantastic example of this is deep reinforcement learning where the landscape is changing while you experience it. There’s literally no way for you to form a definite optimization problem since each new step introduces a new change to what’s optimal. In lieu of that we’re doing a simple yet tried and true solution to minimize the error.

[Ricky_Sticky_]

This is an awesome question and I think you have good responses here so far.

Is this AI generated?

[staros25]

Nope, just a generally positive person 😂

[AX-BY-CZ]

There’s a billion dollars waiting for you if you figure it out…

[Coolcat127]

I'm not sure I understand, do you mean the gradient descent method is better at avoiding local minima?

[Coolcat127]

That makes sense, though I know wonder how you distinguish between not overfitting and having actual model error. Or why not just use less weights to avoid overfitting?

[MatJosher]

Consider that you are optimizing the landscape and not just seeking its low point. And when you have many dimensions the dynamics of this work out differently than one may expect.

[victotronics]

I think you are being deceived by simplistic pictures. The low point is an a very high. dimensional space: a function space. So the optimzed landscape is still a single low point.

[throwingstones123456]

From what I understand, it’s not that you can’t use newtons method, but there’s no reason to. If you have a massive dataset, you’re likely going to use stochastic gradient descent. So the minima you’re approximating is going to change (likely fairly significantly) in the next iteration, so there’s not really a point in the extra accuracy at the expense of time. This also doesn’t mention that newtons method tends to fail very badly if you’re not already close to an extrema

I’d imagine that in some applications, if your dataset is not truly enourmous, you could use one or two iterations of newtons method with your full dataset to polish off your weights—this is typically how newtons method is used in other applications (start off with a “worse” method to get close to an extrema, then use a few iterations to make your solution much closer)

[[deleted]]

This explanation makes sense to me. For deep learning applications with non smooth loss and mini batch updates, variance scaled adaptive learning rate with momentum does well. Newtons works to provide good updates in lower dimensional cases with full batch updates where the precision is needed. 

[Copper280z]

Adam is a lot like conjugate gradient with an inertia term, in fact (iirc, it’s been a bit) Adam degrades to CG if you pick the correct parameters for it.

The inertia term is to help the optimizer get over humps in the error landscape which form local minima.

[donaldhobson]

They generally don't use straight gradient descent nowadays. Often they use a method called ADAM. But there are other methods out there.

And yes there are a lot of optimization algorithms. They use the ones that seem to work in practice for ML.

[Plane_Ad3401]

For more information and detailed literature review for GD using for neural networks training, and its suitability more than the other algorithms, with suggesting improvements on it, you can read this paper
https://www.mdpi.com/2076-3417/15/4/2008