I understand what Gradient Descent does. Basically it tries to move towards the local optimal solution by slowly moving down the curve. I am trying to understand what is the actual difference between the plan gradient descent and the newton's method?
From Wikipedia, I read this short line "Newton's method uses curvature information to take a more direct route." What does this intuitively mean?
If you simply compare Gradient Descent and Newton's method, the purpose of the two methods are different.
Gradient Descent is used to find(approximate) local maxima or minima (x to make min f(x) or max f(x)). While Newton's method is to find(approximate) the root of a function, i.e. x to make f(x) = 0
In this sense, they are used to solve different problems. However, Newton's method can also be used in the context of optimization (the realm that GD is solving). Because finding maxima or minima can be approached by finding f'(x) = 0 which is exactly Newton's method is used for.
In conclusion, two methods can be used in optimization: 1)GD and 2)find x so f'(x)=0 and Newton's method is just a way to solve that second problem.
Put simply, gradient descent you just take a small step towards where you think the zero is and then recalculate; Newton's method, you go all the way there.
Edit 2017: The original link is dead - but the way back machine still got it :) https://web.archive.org/web/20151122203025/http://www.cs.colostate.edu/~anderson/cs545/Lectures/week6day2/week6day2.pdf
this power point the main ideas are explained simply http://www.cs.colostate.edu/~anderson/cs545/Lectures/week6day2/week6day2.pdf
I hope this help :)
At a local minimum (or maximum)
x
, the derivative of the target functionf
vanishes:f'(x) = 0
(assuming sufficient smoothness off
).Gradient descent tries to find such a minimum
x
by using information from the first derivative off
: It simply follows the steepest descent from the current point. This is like rolling a ball down the graph off
until it comes to rest (while neglecting inertia).Newton's method tries to find a point
x
satisfyingf'(x) = 0
by approximatingf'
with a linear functiong
and then solving for the root of that function explicitely (this is called Newton's root-finding method). The root ofg
is not necessarily the root off'
, but it is under many circumstances a good guess (the Wikipedia article on Newton's method for root finding has more information on convergence criteria). While approximatingf'
, Newton's method makes use off''
(the curvature off
). This means it has higher requirements on the smoothness off
, but it also means that (by using more information) it often converges faster.