Implementing Ridge Regression with a Black-Box OLS Routine

Reported in interviews at Two Sigma

Problem statement

You have access to a black-box vanilla regression routine that solves ordinary least squares (OLS): given a design matrix $X$ and response vector $y$, it returns $\hat{\beta} = (X^{\top}X)^{-1}X^{\top}y$. You cannot modify the routine's internals.

You want to fit a Ridge regression model, which solves:

$$\min_{\beta} \|y - X\beta\|^2 + \lambda\|\beta\|^2$$

where $X$ is an $n \times p$ design matrix, $y$ is an $n \times 1$ response vector, and $\lambda \geq 0$ is a regularization parameter you choose.

How do you use the black-box OLS routine to produce the Ridge estimator? Describe the transformation, show it is equivalent to Ridge regression, and state the resulting closed-form solution.

Show hint

Can the penalty term be rewritten so that it looks like extra squared residuals of some made-up observations?

Relevant roles: ML Engineer, Applied Scientist, Research Scientist and Data Scientist.

Related free problems