Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.

Gradient descent is also known as steepest descent, or the method of steepest descent. When known as the latter, gradient descent should not be confused with the method of steepest descent for approximating integrals.

Description of the method

We describe gradient descent here in terms of its equivalent (but opposite) cousin, gradient ascent. Gradient ascent is based on the observation that if the real-valued function $F(\backslash mathbf\{x\})$ is defined and differentiable in a neighborhood of a point $\backslash mathbf\{a\}$, then $F(\backslash mathbf\{x\})$ increases fastest if one goes from $\backslash mathbf\{a\}$ in the direction of the gradient of $F$ at $\backslash mathbf\{a\}$, $\backslash nabla\; F(\backslash mathbf\{a\})$. It follows that, if

$\backslash mathbf\{b\}=\backslash mathbf\{a\}+\backslash gamma\backslash nabla\; F(\backslash mathbf\{a\})$

for $\backslash gamma>0$ a small enough number, then $F(\backslash mathbf\{a\})\backslash leq\; F(\backslash mathbf\{b\})$. With this observation in mind, one starts with a guess $\backslash mathbf\{x\}\_0$ for a local maximum of $F$, and considers the sequence $\backslash mathbf\{x\}\_0,\; \backslash mathbf\{x\}\_1,\; \backslash mathbf\{x\}\_2,\; \backslash dots$ such that

$\backslash mathbf\{x\}\_\{n+1\}=\backslash mathbf\{x\}\_n+\backslash gamma\_n\; \backslash nabla\; F(\backslash mathbf\{x\}\_n),\backslash \; n\; \backslash ge\; 0.$

We have $F(\backslash mathbf\{x\}\_0)\backslash le\; F(\backslash mathbf\{x\}\_1)\backslash le\; F(\backslash mathbf\{x\}\_2)\backslash le\; \backslash dots,$ so hopefully the sequence $(\backslash mathbf\{x\}\_n)$ converges to the desired local maximum. Note that the value of the step size $\backslash gamma$ is allowed to change at every iteration.

Let us illustrate this process in the picture below. Here $F$ 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 $F$ 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 ascent leads us to the top of the hill, that is, to the point where the value of the function $F$ is largest.

To have gradient descent go towards a local minimum, one needs to replace $\backslash gamma$ with $-\backslash gamma$.

Comments

Note that gradient descent works in spaces of any number of dimensions, even in infinite-dimensional ones.

Two weaknesses of gradient descent are:

1. The algorithm can take many iterations to converge towards a local maximum/minimum, if the curvature in different directions is very different.
2. Finding the optimal $\backslash gamma$ per step can be time-consuming. Conversely, using a fixed $\backslash gamma$ 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 the gradient vector is multiplied to go into a "better" direction, combined with a more sophisticated linear search algorithm, to find the "best" value of $\backslash gamma.$

See also

• Stochastic gradient descent
• Newton's method
• Optimization
• Line search
• Delta rule

Optimization algorithms

Gradientenabstiegsverfahren | Найшвидшого спуску метод