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	Linear and logistic regression, the learning rate, convex and non-convex losses
Stochastic gradient descent	Batches, improved versions of gradient descent, early stopping
The XOR problem	Vector features, chosen and learned
More than two classes	The softmax, linear classification of MNIST
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 the softmax and be able to fit a multinomial logistic regression with gradient descent,
5. understand why early stopping in gradient descent has a similar effect as regularization, and
6. 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\). Already for logistic regression such a formula does not exist. However, its log-likelihood is concave, so a maximum exists and is unique. For richer models there is in general no formula either, and the loss can have many local minima.

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.