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.

Test Your Knowledge: Practice Questions for "Linear Regression OLS"

Single choice pitfall questions with instant feedback and mistake tracking.