Skip to main content
154 votes

Why is Newton's method not widely used in machine learning?

Gradient descent maximizes a function using knowledge of its derivative. Newton's method, a root finding algorithm, maximizes a function using knowledge of its second derivative. That can be faster ...
jwimberley's user avatar
  • 3,984
138 votes
Accepted

Why use gradient descent for linear regression, when a closed-form math solution is available?

The main reason why gradient descent is used for linear regression is the computational complexity: it's computationally cheaper (faster) to find the solution using the gradient descent in some cases. ...
Aksakal's user avatar
  • 61.7k
81 votes

Why is Newton's method not widely used in machine learning?

More people should be using Newton's method in machine learning*. I say this as someone with a background in numerical optimization, who has dabbled in machine learning over the past couple of years. ...
Nick Alger's user avatar
  • 1,221
75 votes
Accepted

Why do neural network researchers care about epochs?

In addition to Franck's answer about practicalities, and David's answer about looking at small subgroups – both of which are important points – there are in fact some theoretical reasons to prefer ...
Danica's user avatar
  • 25k
70 votes

Why is Newton's method not widely used in machine learning?

A combination of two reasons: Newton method attracts to saddle points; saddle points are common in machine learning, or in fact any multivariable optimization. Look at the function $$f=x^2-y^2$$ ...
Aksakal's user avatar
  • 61.7k
55 votes
Accepted

How is the cost function from Logistic Regression differentiated

Adapted from the notes in the course, which I don't see available (including this derivation) outside the notes contributed by students within the page of Andrew Ng's Coursera Machine Learning course. ...
Antoni Parellada's user avatar
50 votes
Accepted

How does the Adam method of stochastic gradient descent work?

The Adam paper says, "...many objective functions are composed of a sum of subfunctions evaluated at different subsamples of data; in this case optimization can be made more efficient by taking ...
user20160's user avatar
  • 32.8k
43 votes

Why is Newton's method not widely used in machine learning?

I recently learned this myself - the problem is the proliferation of saddle points in high-dimensional space, that Newton methods want to converge to. See this article: Identifying and attacking the ...
Cam.Davidson.Pilon's user avatar
43 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

They say an image is worth more than a thousand words. In the following example (courtesy of MS Paint, a handy tool for amateur and professional statisticians both) you can see a convex function ...
Jan Kukacka's user avatar
  • 11.5k
40 votes
Accepted

How could stochastic gradient descent save time compared to standard gradient descent?

Short answer: In many big data setting (say several million data points), calculating cost or gradient takes very long time, because we need to sum over all data points. We do NOT need to have exact ...
Haitao Du's user avatar
  • 37.1k
38 votes
Accepted

Who invented stochastic gradient descent?

Stochastic Gradient Descent is preceded by Stochastic Approximation as first described by Robbins and Monro in their paper, A Stochastic Approximation Method. Kiefer and Wolfowitz subsequently ...
David Kozak's user avatar
  • 1,842
37 votes

What's the difference between momentum based gradient descent and Nesterov's accelerated gradient descent?

It seems to me that the OP's question was already answered, but I would try to give another (hopefully intuitive) explanation about momentum and the difference between Classical Momentum (CM) and ...
Oren Milman's user avatar
  • 1,332
36 votes
Accepted

Gradient descent doesn't find solution to ordinary least squares on this dataset?

The short answer is that your step size is too big. Instead of descending the canyon wall, your step is so big that you're jumping across from one side to higher up on the other! Cost function below: ...
Matthew Gunn's user avatar
  • 22.5k
36 votes
Accepted

Why not use the third derivative for numerical optimization?

I am interpreting the question as being "Why does Newton's method only use first and second derivatives, not third or higher derivatives?" Actually, in many cases, going to the third derivative does ...
jbowman's user avatar
  • 40k
35 votes
Accepted

How does minibatch gradient descent update the weights for each example in a batch?

Gradient descent doesn't quite work the way you suggested but a similar problem can occur. We don't calculate the average loss from the batch, we calculate the average gradients of the loss function. ...
Hugh's user avatar
  • 4,069
33 votes

For convex problems, does gradient in Stochastic Gradient Descent (SGD) always point at the global extreme value?

Gradient descent methods use the slope of the surface. This will not necessarily (or even most likely not) point directly towards the extreme point. An intuitive view is to imagine a path of descent ...
Sextus Empiricus's user avatar
32 votes

The "Amazing Hidden Power" of Random Search?

One limitation of random search is that searching over a large space is extremely challenging; even a small difference can spoil the result. Émile Borel's 1913 article "Mécanique Statistique et ...
Sycorax's user avatar
  • 92.3k
29 votes

Why is Newton's method not widely used in machine learning?

You asked two questions: Why don't more people use Newton's method, and why do so many people use stochastic gradient descent? These questions have different answers, because there are many algorithms ...
Elizabeth Santorella's user avatar
29 votes
Accepted

What does "vanilla" mean?

Vanilla means standard, usual, or unmodified version of something. Vanilla gradient descent means the basic gradient descent algorithm without any bells or whistles. There are many variants on ...
shimao's user avatar
  • 26.3k
28 votes
Accepted

Why second order SGD convergence methods are unpopular for deep learning?

Should we go toward second order methods for deep learning? TL;DR: No, especially now when the pace of innovation is slowing down, and we're seeing less new architectural innovations, and more ways ...
DeltaIV's user avatar
  • 18.1k
26 votes

Why do neural network researchers care about epochs?

It is indeed quite unnecessary from a performance standpoint with a large training set, but using epochs can be convenient, e.g.: it gives a pretty good metric: "the neural network was trained for 10 ...
Franck Dernoncourt's user avatar
26 votes
Accepted

When are genetic algorithms a good choice for optimization?

Genetic algorithms (GA) are a family of heuristics which are empirically good at providing a decent answer in many cases, although they are rarely the best option for a given domain. You mention ...
lacerbi's user avatar
  • 5,216
26 votes

Why not use the third derivative for numerical optimization?

I don't really see what the statistical aspect of this question is, so I'll answer the optimization part. There are 2 parts to convergence: iteration cost & iteration count Pretty much every ...
user541686's user avatar
  • 1,185
26 votes
Accepted

Why is the second derivative required for newton's method for back-propagation?

My guess at your confusion: Newton's method is often used to solve two different (but related) problems: Find $x$ such that $f(x) = 0$ Find $x$ to minimize $g(x)$ A connection between the two ...
Matthew Gunn's user avatar
  • 22.5k
25 votes
Accepted

Gradient for logistic loss function

My answer for my question: yes, it can be shown that gradient for logistic loss is equal to difference between true values and predicted probabilities. Brief explanation was found here. First, ...
Ogurtsov's user avatar
  • 554
24 votes
Accepted

Gradient backpropagation through ResNet skip connections

Add sends the gradient back equally to both inputs. You can convince yourself of this by running the following in tensorflow: ...
Hugh Perkins's user avatar
  • 4,797
24 votes

Why use gradient descent for linear regression, when a closed-form math solution is available?

In short, suppose we want to solve the linear regression problem with squared loss $$\text{minimize}~ \|Ax-b\|^2$$ We can set the derivative $2A^T(Ax-b)$ to $0$, and it is solving the linear system $$...
Haitao Du's user avatar
  • 37.1k
23 votes
Accepted

Gradient Ascent vs Gradient Descent in Logistic Regression

https://en.wikipedia.org/wiki/Gradient_descent: To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or of the ...
Franck Dernoncourt's user avatar
22 votes

How can it be trapped in a saddle point?

Take a look at the image below from Off Convex. In a convex function (leftmost image), there is only one local minimum, which is also the global minimum. But in a non-convex function (rightmost image),...
Antimony's user avatar
  • 839
21 votes

How does rectilinear activation function solve the vanishing gradient problem in neural networks?

Here is a heuristic explanation: Each gradient update in backprop consists of a number of multiplied factors. The further you get towards the start of the network, the more of these factors are ...
Tom Walker's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible