Overview

Gradient descent

Until now every fit had a formula behind it, or a solver that we did not have to think about. From this week on that is no longer true.

Pages

Gradient descent	The algorithm, the learning rate, convexity
Stochastic gradient descent	Batches, epochs, learning curves, early stopping
Exercises

Goals

The goal of this week is to

1. understand gradient descent,
2. understand stochastic gradient descent,
3. know improved versions of (stochastic) gradient descent,
4. understand why early stopping in gradient descent has a similar effect as regularization, and
5. understand how the XOR problem can be solved with feature engineering and gradient descent.

Why we need this

Least squares has the closed form \(\hat\beta = (X^\top X)^{-1}X^\top y\). Logistic and Poisson regression have no closed form, but their log-likelihood is concave, so any solver finds the maximum reliably.

Neural networks have neither. There is no formula, and the loss has many local minima. We therefore need a method that uses only the gradient, and we need to know when it fails.

The idea

We want to minimize \(\mathcal L(\theta)\). The gradient \(\nabla\mathcal L(\theta)\) points in the direction of steepest increase. So we take a small step in the opposite direction and repeat.

\[ \theta \leftarrow \theta - \eta\,\nabla\mathcal L(\theta) \]

The step size \(\eta\) is called the learning rate. It is the most important hyper-parameter in this course.