OLS on a desert island

Without any package imports, how would you compute OLS?

Solution

This is a pretty open-ended question, but however you go about solving it, you’ll have to demonstrate knowledge of computational linear algebra algorithms. Here are some options:

1. Just solve the linear system: It is rather simple to write code to do simple Gaussian elimination to solve the system $X^\top X \beta = X^\top y$ for $\beta$.
2. Gradient descent: The most basic optimization algorithm. Just take steps $$\hat\beta^{(t+1)} = \hat\beta^{(t)} - \alpha X^\top (y - X\hat\beta^{(t)})$$
3. Quasi-Newton's method: If you wanted to go a step further than gradient descent, you could do Newton's method. However, you would need to invert $X^\top X$, which is more costly than just solving the linear system. Instead you may try to approximate the inverse cheaply and use a Quasi-Newton method. Perhaps the simplest is a diagonal approximation. However, note that you cannot pick just any approximation, such as taking the diagonal elements of $X^\top X$ and inverting that. In order to get convergence you need to ensure that the approximate Hessian majorizes the true Hessian. This difficulty makes it not obvious how to pick an approximation that is better than gradient descent without being more computationally costly than other approaches.
4. QR: You can solve the linear regression by the $QR$ decomposition. This can be solved with the Graham-Schmidt method, which only requires dot products and back substitution. Once you have found $Q,R$ s.t. $X = QR$, then $\hat\beta = R^{-1} Q^\top y$. This can be easily solved by back-substitution since $R$ is upper-triangular. For details see Chapter 3.2 in ESL.
5. Cholesky: You could also compute a Choleksy decomposition $X^\top X = LL^\top$. Then you just need one forward-substitution and one back substitution to solve for $\hat\beta$.

I’m sure there are other approaches, but these are the ones that came to mind for me.