Linear Regression OLS

Linear regression (OLS) assumes $y = Xw + \varepsilon$ and minimizes the residual sum of squares $L(w) = \Vert y - Xw\Vert_2^2$. Differentiating gives $\frac{\partial L}{\partial w} = 2X^T(Xw - y)$; setting it to zero yields the normal equation $X^TXw = X^Ty$, with closed-form solution $w = (X^TX)^{-1}X^Ty$ when $X$ has full column rank — complexity about $O(nd^2 + d^3)$, so gradient descent ($O(nd)$ per step) wins in high dimensions. The 5 Gauss-Markov assumptions: (1) linearity in parameters, (2) zero conditional mean $E[\varepsilon \mid X] = 0$ (exogeneity), (3) homoscedasticity $Var(\varepsilon) = \sigma^2 I$, (4) independent errors, (5) no perfect multicollinearity ($rank(X) = d$); normally distributed errors additionally validate small-sample t/F inference.

baseline for regression tasks; interview staples include whiteboard-deriving the normal equation, discussing what to do when $X^TX$ is singular (pseudo-inverse, ridge with $\lambda I$, dropping collinear features), and comparing OLS vs gradient descent complexity.

$L(w)$ is convex quadratic (Hessian $= 2X^TX \succeq 0$), so the normal equation reaches the unique global optimum in one shot without tuning a learning rate; unlike non-parametric $k$NN, OLS yields interpretable coefficients ($w_j$ = marginal effect of $x_j$ holding others fixed). When assumptions break (collinearity → ill-conditioned $X^TX$; heteroscedasticity → wrong standard errors), switch to ridge or weighted least squares.

Whiteboard the normal equation: expand $L(w) = \Vert y - Xw\Vert^2$, take the gradient, set it to 0, and arrive at $w = (X^TX)^{-1}X^Ty$; what condition makes $X^TX$ invertible?

What are the 5 OLS assumptions? What happens to unbiasedness, efficiency and consistency when each is violated?

What if $X^TX$ is singular or ill-conditioned? Compare pseudo-inverse, ridge $w = (X^TX + \lambda I)^{-1}X^Ty$ and dropping collinear features.

State the Gauss-Markov theorem: under the 5 assumptions OLS is BLUE — why is normality not among them?

Derive the normal equation's complexity (building $X^TX$ is $O(nd^2)$, inversion $O(d^3)$) and explain why high-dimensional sparse settings prefer gradient descent.