19. Gradient Descent Optimization

Today's optimization method is the machine at the heart of data science, machine learning, and artificial intelligence. We will study it on $\large f(x,y)$ surfaces because we can visualize these, but it is typically used on much larger problems involving more independent variables and huge piles of data. We will return to this method in the "Data in STEM" course in the Fall, but it will be good to get an introduction here.

Remember, the key fact about the gradient is that it points in the direction of steepest ascent. This means $\large -\nabla f$ points in the direction of steepest descent. We take advantage of this fact in an algorithm called gradient descent.

The basic steps of the algorithm are:

1. Start at a point on a surface.
2. Compute the gradient at that point.
3. Take a small step in the direction opposite the gradient (a small step downhill).
4. Repeat until we reach a minimum.

Note: we could use $\large \nabla f$ instead of $\large -\nabla f$ and search for a max instead of a min, but we are usually using this method to minimize errors.

Here are a few illustrations of the method:

The basic steps above, when converted to our math notation, look like this:

1. Pick an initial point $\large \left(x_0,y_0\right)$.
2. Compute $\large \nabla f\left(x_0,y_0\right)$.
3. Move a small distance in the direction $\large -\nabla f\left(x_0,y_0\right)$. Call this new point $\large \left(x_1,y_1\right)$.
4. Repeat until $\large \left|\nabla f\right|$ is small.

In a more abbreviated form, the algorithm looks like this:

$$\large \vec{x}_{n+1}=\vec{x}_n-\alpha \nabla f\left(\vec{x}_n\right), \,\,\,\, n=0,1,2,\dots$$

The parameter $\large \alpha$ controls the size of the steps we take.

In the video below, we go through a few steps of the algorithm:

Tomorrow's class:

• Some of the potential issues and difficulties
• Practice doing the algorithm by hand

Section Outcomes:

I can:

• Do 1-2 steps of the gradient descent algorithm
• Visualize the algorithm on a plot
• Run the algorithm in Python (this will be Lab #7)