Gradient descent

From Wikipedia, the free encyclopedia

For the analytical method called "steepest descent", see Method of steepest descent.

Gradient descent is a first-order optimization algorithm. To find a local minimum of a function using gradient descent, one takes 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.

[edit] Description

Illustration of gradient descent

Gradient descent is based on the observation that if the real-valued function $F(\mathbf{x})$ is defined and differentiable in a neighborhood of a point $\mathbf{a}$ , then $F(\mathbf{x})$ decreases fastest if one goes from $\mathbf{a}$ in the direction of the negative gradient of $F$ at $\mathbf{a}$ , $-\nabla F(\mathbf{a})$ . It follows that, if

$\mathbf{b}=\mathbf{a}-\gamma\nabla F(\mathbf{a})$

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

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

We have

$F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \dots,$

so hopefully the sequence $(\mathbf{x}_n)$ converges to the desired local minimum. Note that the value of the step size $γ$ is allowed to change at every iteration.

This process is illustrated in the picture to the right. Here $F$ is assumed to be defined on the plane, and that its graph has a bowl shape. 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 negative gradient at that point. Note that the (negative) gradient at a point is orthogonal to the contour line going through that point. We see that gradient descent leads us to the bottom of the bowl, that is, to the point where the value of the function $F$ is minimal.

[edit] Examples

Gradient descent has problems with pathological functions such as the Rosenbrock function shown here. The Rosenbrock function has a narrow curved valley which contains the minimum. The bottom of the valley is very flat. Because of the curved flat valley the optimization is zig-zagging slowly with small stepsizes towards the minimum.

The gradient ascent method applied to $F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)$ :

Gradient descent can also be used to solve a system of nonlinear equations. Below is an example that shows how to use the gradient descent to solve for three unknown variables, x₁, x₂, and x₃. This example shows one iteration of the gradient descent.

Consider a nonlinear system of equations:

There must be an initial assumption as to what the solutions for x₁, x₂, and x₃ are. In this case assume that all the solutions are zero. The next step is to form the Jacobian matrix of the given system of equations.

Plug in the initial assumption of zero into the Jacobian matrix and original system to get the answers below.

Now the gradient and z₀ must be found. This is done by using the formula below and the previous two calculations made. The value for z₀ is found by simply calculating the p-norm of the gradient, where p is equal to 2.

Now the value for z must be found.

The next step is to find solutions for g₁, g₂, and g₃. First there must be a value chosen for α₁. Set α₁ to zero and α₃ to one.

There is a condition that must be met when the solutions for g₁ and g₃ are found. That condition is that g₃ must be less than g₁ and if this is true we accept α₁ and α₃. If this is not true then a different value must be chosen for α₃, one which will satisfy this condition. Try choosing a smaller value for α₃ like 1/2 or 1/4.

To find α₂ all that needs to be done is to divide α₃ by 2 → α₂ = α₃ / 2 . With α₂ found, g₂ can be calculated.

The next step is to form a Newton polynomial, Newton's forward divided difference interpolating polynomial.

Using all the calculations of α₁, α₂, α₃, g₁, g₂, and g₃ the unknown values of h₁, h₂, and h₃ can be found, which is shown below.

With all the values for h₁, h₂, and h₃ known, the next step is to plug them into the polynomial and solve for α. A value for g₀ must be found and must satisfy the condition of being less than g₁ and g₃. If this condition is met then use the following equation below to solve for x⁽¹⁾ which involves the initial x⁽⁰⁾, α which becomes α₀, and z.

And now there is a set of solutions that satisfy the system of nonlinear equations.

[edit] Comments

Gradient descent works in spaces of any number of dimensions, even in infinite-dimensional ones. In the latter case the search space is typically a function space, and one calculates the Gâteaux derivative of the functional to be minimized to determine the descent direction.

Two weaknesses of gradient descent are:

The algorithm can take many iterations to converge towards a local minimum, if the curvature in different directions is very different.
Finding the optimal $γ$ per step can be time-consuming. Conversely, using a fixed $γ$ can yield poor results. Methods based on Newton's method and inversion of the Hessian using conjugate gradient techniques are 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 line search algorithm, to find the "best" value of $γ.$

Gradient descent is in fact Euler's method for solving ordinary differential equations applied to a gradient flow. As the goal is to find the minimum, not the flow line, the error in finite methods is less significant.

[edit] A computational example

The gradient descent algorithm is applied to find a local minimum of the function f(x)=x⁴-3x³+2 , with derivative f'(x)=4x³-9x². Here is an implementation in the C programming language.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main ()
{
	// From calculation, we expect that the local minimum occurs at x=9/4
	// The algorithm starts at x=6
 
	double xOld = 0;
	double xNew = 6;
	double eps = 0.01; // step size
	double precision = 0.00001;
	while (fabs(xNew - xOld) > precision)
	{
             xOld = xNew;
             xNew = xNew - eps*(4*xNew*xNew*xNew-9*xNew*xNew);
	}
 
	printf ("Local minimum occurs at %lg\n", xNew);
 
}

With this precision, the algorithm converges to a local minimum of 2.24996 in 70 iterations.

A more robust implementation of the algorithm would also check whether the function value indeed decreases at every iteration and would make the step size smaller otherwise. One can also use an adaptive step size which may make the algorithm converge faster.

[edit] See also

[edit] References

Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. ISBN 0-387-24348-8

Gradient descent

From Wikipedia, the free encyclopedia

Contents

[edit] Description

[edit] Examples

[edit] Comments

[edit] A computational example

[edit] See also

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages