Difference between OLS and Gradient Descent in Linear Regression

Question

I understand what Ordinary Least Squares and Gradient Descent do but I am just confused about the difference between them.

The only difference I can think of are-

1. Gradient Descent is iterative while OLS isn't.
2. Gradient Descent uses a learning rate to reach the point of minima, while OLS just finds the minima of the equation using partial differentiation.

Both these methods are very useful in Linear Regression but they both give us the same results: the best possible values for the intercept and coefficients.

What is the difference between them and why are there two methods for Linear Regression?

Answer 1

Gradient Descent is more general in that it can apply to any optimization problem (including non-linear regression) by an iterative process. In this context, we are optimizing $$ \hat{\beta} =\arg\min_{\beta} \ (y - X\beta)^2$$

OLS is a special case where it has been proven that there is an analytical expression for the global minimum: $$ \hat{\beta} = (X'X)^{-1} X' y $$

Gradient Descent is made possible by advances in computing, whereas OLS was derived mathematically.

Answer 2

Carl Friedrich Gauss was the first to properly describe OLS in 1809 in "Theoria motus corporum coelestium in sectionibus conicus solem ambientium". People tried to predict the motion of the dwarf planet Ceres back in these days and Gauss was the first to calculate it's motion based on very few data using OLS. Obviously there were no computers in 1809, so that expensive iterative calculations as used in gradien descent were painful. The need for "easy" ways to sole problems like OLS using pen and paper motivated solutions like using the matrix solution to OLS $(X'X)^{-1} X'y = \hat{\beta} $.

So gradient descent is "only" one way to solve OLS. The OLS solution in matrix algebra also allows to investigate interesting properties of OLS (and related methods). When you look - for instance - at books such as Davidson/MacKinnon "Econometric Theory and Methods", you will find that the matrix solution to OLS allows to investigate it's properties in detail.

Find some R example of OLS matrix solution vs. gradient descent below. Note the maxiter argument which is the number of required updates in gradient descent. It is no problem to do a lot of updates using computers. However, when you use pen and paper, doing thousands of updates is not a nice solution.

x0 <- c(1,1,1,1,1) 
x1 <- c(1,2,3,4,5)
x2 <- c(8,4,3,1,8)
x <- as.matrix(cbind(x0,x1,x2))
y <- as.matrix(c(3,7,5,11,14))

x
y

# (X'X)^-1 X'y
beta1 = solve(t(x)%*%x) %*% t(x)%*%y 

# R's regression command
beta2 = summary(lm(y ~ x[, 2:3]))

# Gradient decent
m <- nrow(y)
grad <- function(x, y, theta) {
  gradient <- (1/m)* (t(x) %*% ((x %*% t(theta)) - y))
  return(t(gradient))
}

# Gradient update
grad.descent <- function(x, maxiter){
  theta <- matrix(c(0, 0, 0), nrow=1) 
  alpha = 0.01 # learning rate
  for (i in 1:maxiter) {
    theta <- theta - alpha  * grad(x, y, theta) 
    #print(theta)
  }
  return(theta)
}


# Gradien descent
print(grad.descent(x,10000))
# Matrix OLS solution
beta1 
# R's regression command
beta2