Gradient descent
|
|
Gradient descent is an optimization algorithm that approaches a local maximum of a function by taking steps proportional to the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the negative of the gradient, one approaches a local minimum of that function.
This algorithm is also known as steepest descent, or the method of steepest descent, not to be confused with the method for approximating integrals with the same name, see method of steepest descent.
Description of the method
Gradient descent is based on the observation that if the real-valued function <math>F(\mathbf{x})<math> is defined and differentiable in a neighborhood of a point <math>\mathbf{a}<math>, then <math>F(\mathbf{x})<math> increases fastest if one goes from <math>\mathbf{a}<math> in the direction of the gradient of <math>F<math> at <math>\mathbf{a}<math>, <math>\nabla F(\mathbf{a})<math>. It follows that, if
- <math>\mathbf{b}=\mathbf{a}+\gamma\nabla F(\mathbf{a})<math>
for <math>\gamma>0<math> a small enough number, then <math>F(\mathbf{a})\leq F(\mathbf{b})<math>. With this observation in mind, one starts with a guess <math>\mathbf{x}_0<math> for a local maximum of <math>F<math>, and considers the sequence <math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots<math> such that
- <math>\mathbf{x}_{n+1}=\mathbf{x}_n+\gamma \nabla F(\mathbf{x}_n),\ n \ge 0.<math>
We have <math>F(\mathbf{x}_0)\le F(\mathbf{x}_1)\le F(\mathbf{x}_2)\le \dots,<math> so hopefully the sequence <math>(\mathbf{x}_n)<math> converges to the desired local maximum. Note that the value of the step size <math>\gamma<math> is allowed to change at every iteration.
Let us illustrate this process in the picture below. Here <math>F<math> is assumed to be defined on the plane, and that its graph looks like a hill. The blue curves are the contour lines, that is, the regions on which the value of <math>F<math> is constant. A red arrow originating at a point shows the direction of the gradient at that point. Note that the gradient at a point is perpendicular to the contour line going through that point. We see that gradient descent leads us to the top of the hill, that is, to the point where the value of the function <math>F<math> is largest.
- Missing image
Gradient_descent.gif
alt An illustration of the gradient descent method.
To have gradient descent go towards a local minimum, one needs to replace <math>\gamma<math> with <math>-\gamma<math>.
Comments
Note that gradient descent works in spaces of any number of dimensions, even in infinite-dimensional ones.
Two weaknesses of gradient descent are:
- The algorithm can take many iterations to converge towards a local maximum/minimum, if the curvature in different directions is very different
- Finding the optimal <math>\gamma<math> per step can be time-consuming. Conversely, using a fixed <math>\gamma<math> can yield poor results. Conjugate gradient is often a better alternative.
A more powerful algorithm is given by the BFGS method which consists in calculating on every step a matrix by which is multiplied the gradient vector to go into a "better" direction, combined with a more sophisticated linear search algorithm, to find the "best" value of <math>\gamma<math>.