Gradient Descent

What is gradient descent?

Gradient descent is an iterative optimization algorithm that can be used to find a minimum of a function \(f(\theta)\). At each iteration, it takes a step in the direction of the negative gradient \(\nabla f(\theta)\). The algorithm can also be used to find a maximum. In that case, the algorithm should take a step in the direction of the gradient.

How does gradient descent work?

The gradient descent algorithm is as follows:

Gradient Descent Algorithm

Input: Choose starting value \(\theta_0\), learning rate \(\epsilon\) and take \(i=0\).

Algorithm:

1. Calculate \(\nabla f(\theta_i)\).

2. Update \(\theta_{i+1}=\theta_i-\epsilon \nabla f(\theta_i)\).

3. 1. stop if \(i\) large or \(|\theta_{i+1}-\theta_{i}|\) small enough.

   2. else: update \(i\) to \(i+1\) and go back to (1).

Binder

If you want to experiment with the gradient descent algorithm, you can use the provided Jupyter Notebook. You can run the notebook directly in your browser by using Binder; simply click on the following button to open the notebook: