Gradient descent

Gradient Descent with 2D domain and visualized different start vectors - trajectory of gradient descent

Introduction

The gradient method, also called steepest descent method, is a method used in Numerics to solve general Optimization problems. Here one starts (at the example of a minimization problem) from an approximate value. From this one proceeds in the direction of the negative gradient (which indicates the direction of steepest descent from this approximate value) until one no longer achieves numerical improvement.

Wiki2Reveal

This page can be displayed as Wiki2Reveal slides. Single sections are regarded as slides and modifications on the slides will immediately affect the content of the slides.

Remark Convergence

The method often converges very slowly, since it approaches the optimuÏm with a strong zigzag course. For the solution of symmetric positive definite linear system of equations, the method of conjugate gradients offers an immense improvement here. Gradient descent is possible with the hill climbing algorithm (hill climbing).

The optimization problem

The gradient method is applicable when the minimization of a real-valued differentiable function ${\textstyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ is involved; i.e., the optimization problem

$${\underset {x\in \mathbb {R} ^{n}}{\rm {min}}}\ f(x).$$

This is a problem of Optimization without constraints, also called unconstrained optimization problem.

Essential steps

• Gradient points in the direction of the steepest increase.
• The negative gradient therefore points in the direction in which the function values of ${\textstyle f}$ decrease.
• It can happen that one jumps over the local minimum of the function ${\textstyle f}$ during an iteration step. Then one would decrease the step size accordingly to further minimize and more accurately approximate the function value of ${\textstyle f}$.

Termination condition

• Termination condition for the gradient descent method would be when we have found a location ${\textstyle x^{(k)}\in \mathbb {R} ^{n}}$ with the iteration at which the gradient of ${\textstyle f}$ is 0

$$\nabla (f)(x^{(k)})=0\in \mathbb {R} ^{n}$$ .

In general, the gradient of a place ${\textstyle x^{(k)}\in \mathbb {R} ^{n}}$ for the ${\textstyle k}$-th iteration step is defined as follows via the partial derivatives:

$$\nabla (f)(x^{(k)}):=\left({\frac {\partial f}{\partial x_{1}}}(x^{(k)}),\cdots ,{\frac {\partial f}{\partial x_{n}}}(x^{(k)})\right)$$ .

Example of a gradient

Sei ${\textstyle f(x_{1},x_{2}):=x_{1}^{3}\cdot x_{2}+x_{2}^{2}}$:

$\nabla (f)(x_{1},x_{2})=\left({\frac {\partial f}{\partial x_{1}}}(x_{1},x_{2}),{\frac {\partial f}{\partial x_{2}}}(x_{1},x_{2})\right)=\left(3x_{1}^{2}x_{2},x_{1}^{3}+2x_{2}\right)$.

This allows us to calculate the gradient at a given point in the domain of definition:

$$\nabla (f)(1,2)=(6,5)$$

Example - normalized gradient

Using a gradient different from the zero vector ${\textstyle \nabla (f)(1,2)=(6,5)}$, one can create a normalized "negative" gradient:

$d^{(j)}:=-{\frac {\nabla \left(f(1,2)\right)}{\left\|\nabla \left(f(1,2)\right)\right|}}={\frac {(-6;-5)}{\sqrt {36+25}}}=\left(-{\frac {6}{\sqrt {61}}};-{\frac {5}{\sqrt {61}}}\right)$

The procedure

A simplified step size calculation is used as an introduction to the gradient descent procedure.

• The procedure terminates if the gradient is the zero vector.
• If the gradient is not the zero vector, the negative gradient is first normalized to length 1 and multiplied by the step size ${\textstyle \alpha _{j}}$.
• The step size is halved if after the iteration step the function value (e.g. cost) does not decrease.
• Another termination condition for the iteration is if the step size falls below an accuracy limit ${\textstyle \varepsilon >0}$ (i.e. ${\textstyle \alpha _{j}<\varepsilon }$).

Start of the optimization

As starting point a point ${\textstyle x^{(0)}}$ is chosen from the definition domain of the function ${\textstyle f}$, for which one wants to approximate local minima with the gradient descent method.

Direction of the steepest descent

Starting from a starting point ${\textstyle x^{(0)}}$ resp. from the current point ${\textstyle x^{(j)}}$ for the next iteration step, the direction of steepest descent is determined by ${\textstyle -Grad\left(f(x^{(j)})\right)}$, where ${\textstyle Grad\left(f(x^{(j)})\right)\in \mathbb {R} ^{n}}$ is the Gradient of ${\textstyle f}$ at the location ${\textstyle x^{(j)}\in \mathbb {R} ^{n}}$. This points in the direction of the "steepest increase". The negative sign in front of the gradient ensures that one moves with the iteration steps in the direction of the strongest decrease (e.g. minimization of the cost function/error function ${\textstyle f}$).

Normalization of the direction vector

The simplified interation procedure terminates at the condition if ${\textstyle \left\|\nabla \left(f(x^{(j)})\right)\right\|<\varepsilon }$. Otherwise, the direction vector is normalized for the following iteration step (this is optional to normalize the step size in the learning algorithm) :

$d^{(j)}:=-{\frac {\nabla \left(f(x^{(j)})\right)}{\left\|\nabla \left(f(x^{(j)})\right)\right\|}}$

</math> with Euclidean norm $\|x\|:=\|(x_{1},\ldots ,x_{n})\|:={\sqrt {\sum _{k=1}^{n}x_{k}^{2}}}$

Iteration step

Gradient Descent - Trajectory of Points

Formally, one notates this iteration step as follows:

$x^{(j+1)}=.{\begin{cases}x^{(j)}+\alpha ^{(j)}d^{(j)},&{\text{if }}f(x^{(j)}+\alpha ^{(j)}d^{(j)})<f(x^{(j)}){\text{ }}{\text{ (enhancement) }}{\text{ }}x^{(j)},&{\text{other }}\end{cases}}$

If there is no improvement, the step size is decreased (e.g., halved).

Setting the step size

The step size is used for the next iteration step until the cost function ${\textstyle f}$ increases with the subsequent step. In this introductory example, the step size ${\textstyle \alpha ^{(j)}}$ is halved. Formal

$\alpha ^{(j+1)}=.{\begin{cases}\alpha ^{(j)},&{\text{if }}f(x^{(j)}+\alpha ^{(j)}d^{(j)})<f(x^{(j)}){\text{ (enhancement) }}\\{\frac {\alpha ^{(j)}}{2}},&{\text{other }}\end{cases}}$

Alternative step size reduction

In general, the step size reduction can also be replaced by a factor ${\textstyle \delta }$ with ${\textstyle 0<\delta <1}$ over

$$\alpha ^{(j+1)}:=\alpha ^{(j)}\cdot \delta$$

can be replaced.

Step size definition per iteration step

Here ${\textstyle \alpha ^{(j)}>0}$ is the step size in the jth iteration step. This step size must be determined in each step of the iteration procedure. In general, there are different ways to do this, such as regressing the step size determination on a one-dimensional optimization problem. The here chosen step size optimization is chosen as an introduction to the topic.

Gradient descent in spreadsheet

In the following ZIP file from GitHub is a LibreOffice file with an example gradient descent for the cost function:

$$f(x_{1},x_{2}):=\sin(x_{1})+\cos(x_{2})+3$$.

The cost function has infinitely many local minima on its domain of definition ${\textstyle \mathbb {R} ^{2}}$. By definition, the minimum of the cost function is -1. In each table row, we perform an iteration step and check that the cost function is actually decreasing after the iteration step.

• ZIP file from GitHub
• GradientDescent repository on GitHub

Regression to a one-dimensional optimization problem

One method is to determine ${\textstyle \alpha ^{(j)}}$ by minimizing the function on the (one-dimensional) "ray" ${\textstyle x^{(j)}(\alpha )}$ that points in the direction of the negative gradient starting from ${\textstyle x^{(j)}}$. The one-dimensional function to be minimized ${\textstyle M}$ is defined as follows.

$$M:\mathbb {R} ^{+}\rightarrow \mathbb {R} ,\qquad \alpha \mapsto M(\alpha ):=f\left(x^{(j)}(\alpha )\right)f\left(x^{(j)}+\alpha d^{(j)}\right)$$

mit ${\textstyle x^{(j)}(\alpha )=x^{(j)}+\alpha d^{(j)}.}$

One computes in this case the ${\textstyle x^{(j+1)}:=x^{(j)}(\alpha _{o})}$ with ${\textstyle \alpha _{o}>0}$ such that ${\textstyle M(\alpha _{o})}$ becomes minimal. i.e.:

$$f\left(x^{(j+1)}\right)={\underset {\alpha >0}{\min }}\ {f\left(x^{(j)}(\alpha )\right)}.$$

This is a simple, one-dimensional optimization problem for which there are special methods of Step size determination.

Step sizes and iterated step size reduction

Another method is to make ${\textstyle \alpha ^{(j)}}$ dependent on the minimization of the function ${\textstyle f}$, i.e., on the condition ${\textstyle f(x^{(j+1)})<f(x^{(j)})}$. If with the iteration step the function value with a starting step size ${\textstyle \alpha _{0}>0}$ is not decreased, one decreases the step size e. B. with ${\textstyle \alpha _{k+1}:=\alpha _{k}\cdot s}$ with $0<s<1$ further until the step size starting from ${\textstyle x^{(j)}}$ in the direction of the negative gradient actually yields a function value ${\textstyle f(x^{(j)}+\alpha _{k}d^{(j)})<f(x^{(j)})}$ and sets ${\textstyle x^{(j+1)}=x^{(j)}+\alpha _{k}d^{(j)}}$.

If one has reached a place ${\textstyle x^{(j+1)}\in \mathbb {R} ^{n}}$ with ${\textstyle \nabla \left(f(x^{(j+1)})\right)=\mathbf {0} \in \mathbb {R} ^{n}}$ in the iteration procedure, possibly a local extreme place of ${\textstyle f}$ is present (check or abort of the iteration procedure).

Termination condition

A key criterion for a termination condition is that ${\textstyle d^{(j)}=-\nabla \left(f(x^{(j)})\right)=\mathbf {0} \in \mathbb {R} ^{n}}$. As in real one-dimensional analysis, there must be no local minimum at this point ${\textstyle x^{(j)}\in \mathbb {R} ^{n}}$ (one-dimensional saddle point, multidimensional, e.g., saddle surface). If for ${\textstyle f:U\rightarrow \mathbb {R} }$ is twice continuously differentiable and the Hessian matrix is positive definite at this point, there is sufficient criterion for a local minimum in ${\textstyle x^{(j)}\in \mathbb {R} ^{n}}$. This is output and the iteration is terminated.

If the algorithm is executed on a computer, a possible further termination criterion is the step length, if this becomes smaller than a lower limit ${\textstyle \varepsilon >0}$ with the condition ${\textstyle \alpha ^{(j)}<\varepsilon }$.

Furthermore, the gradient descent procedure can be terminated if the improvement of the optimization of ${\textstyle f}$ in the interation steps becomes smaller than a lower bound.

Such termination criteria algorithmically ensure that the gradient descent procedure does not end up in an infinite loop of iterations.

CAS4Wiki Start-Link - Derivatives and Gradient: Derivatives and Gradient

Videos

• contour lines, gradient, vector field, vector analysis, ... Youtube video (07/21/2015) by Daniel Jung.
• gradient and total differential Youtube video (21.07.2015) by Daniel Jung

See also

• Numerical Analysis
• Gradient Descent

Page Information

You can display this page as Wiki2Reveal slides

Wiki2Reveal

The Wiki2Reveal slides were created for the Numerical Analysis' and the Link for the Wiki2Reveal Slides was created with the link generator.

• This page is designed as a PanDocElectron-SLIDE document type.
• Source: Wikiversity https://en.wikiversity.org/wiki/Gradient%20descent
• see Wiki2Reveal for the functionality of Wiki2Reveal.