Proof of Gradient Descent

I’ve organized this in Notion several times before. Here I’m re-organizing based only on what I learned at BoostCamp.

Previous notes on gradient descent are at the links below. https://naem1023.notion.site/Gradient-descent-429308fbd0184aaab90c0ac50e90b526 https://naem1023.notion.site/ML-68740e6ac0db42e9a01b17c9ab093606

Gradient descent

Purpose

In the previous post I only built an algorithmic structure for linear regression using gradient descent. This time I’ll look at how it’s used mathematically.

Use in linear regression


The goal of linear regression is to minimize the L2 norm between the actual data values y and the predictions yhat.

This could in theory be computed via the Moore-Penrose pseudoinverse, but that’s almost never practical. Let’s find yhat through gradient descent instead.

Cost function for linear regression

Most blog posts explain what the cost function is and then walk through gradient descent, which made this part hard to understand. For instance, the Notion notes linked above work through differentiation of J(theta_0, theta_1).

BoostCamp’s approach via the L2 norm made it much clearer.


Since the ultimate goal is finding an ideal yhat, using the squared L2 norm as the cost function instead of the L2 norm itself is fine.

What we want is to find the beta that minimizes the cost function. Gradient descent is the method we’ve chosen for that.

In other words, we need to compute the gradient vector of the cost function, to feed into the algorithm from the previous post.

Partial derivative of the cost function w.r.t. the k-th element of beta

The partial derivative w.r.t. the k-th element of beta is: 

Note that unlike a plain L2 norm, computing the mean here matters.

In the formula, this symbol:  means the transpose of the k-th column vector of matrix X.

Gradient vector of the cost function

The gradient vector w.r.t. beta looks like the partial derivatives for each k-th element of beta laid out in a gradient vector: 

Simplifying gives:  After all the complexity, the result is just X-transpose multiplied — the derivative of X*beta w.r.t. beta.

Gradient descent algorithm that minimizes the cost function

At step t, updating beta for step t+1 works like this:


As intended by gradient descent, we subtract the gradient vector from the t-th beta in the direction that minimizes the cost function.

Substituting the gradient vector computed above flips the sign: 

Cost function using the squared L2 norm

Computing with just the L2 norm gave a messy gradient vector. Squaring it removes the root, so it should be cleaner.


Final gradient descent algorithm

1
# norm: function that computes l2 norm
2
# lr: learning rate
3
# T: number of training steps
4

5
for t in range(T):
6
  error = y - X @ beta
7
  grad = - transpose(X) @ error
8
  beta = beta - lr * grad

Convergence guarantees of gradient descent

With an appropriate number of steps and learning rate, convergence is always guaranteed for differentiable convex functions.

The cost function of linear regression is convex w.r.t. beta, so convergence is guaranteed.

However, nonlinear regression is not guaranteed to have a convex cost function w.r.t. beta, so convergence is not guaranteed.


SGD (Stochastic Gradient Descent)

SGD uses only a subset of the data instead of all of it for updates.

It’s not a silver bullet, but in deep learning where cost functions are usually non-convex, SGD has been empirically shown to outperform standard gradient descent.

The professor mentioned that SGD, which uses only a portion of the data, has been empirically shown to produce results probabilistically similar to full gradient descent.


The subset of data used is called a mini batch. By convention, using a single data point is called SGD, while using a subset is called mini batch SGD.

Efficiency


Since we use a mini batch (Xb, yb) instead of the full data (X, y), computation is reduced by a factor of b/n.

Additionally, splitting the data means GPU memory can be used more efficiently.

How it works

Standard gradient descent uses all data to compute nabla theta L, as shown below:


SGD uses a mini batch D(b) to compute the gradient vector:


This provides a direction similar to standard gradient descent.


Also, since D(b) changes at every step, the objective function also changes at every step. So even if we reach a local minimum, the objective function changes, meaning there’s a probabilistic chance of escaping local minima.

Comparison with gradient descent

 SGD might be less efficient than gradient descent on convex problems. But for typical machine learning objective functions, it’s more efficient.