Linear regression — OLS & regularization

The place where every bias-variance lever from lesson 1 has a closed-form analogue. If you can't derive OLS in four lines and explain why ridge has a unique solution but lasso does feature selection, the rest of these interviews will be uphill.

OLS from first principles

Design matrix X ∈ ℝ^{n×p}, targets y ∈ ℝ^n. Assume y = Xβ + ε with ε ~ (0, σ²I). The squared-error loss is L(β) = ‖y − Xβ‖² = (y − Xβ)ᵀ(y − Xβ). Take the gradient and set to zero — four lines:

Those are the normal equations. The Hessian 2XᵀX is PSD, so the stationary point is a minimum — unique exactly when XᵀX is invertible, i.e., the columns of X are linearly independent.

The geometric reading is sharper than the algebra. Xβ̂ lives in the column space of X; OLS picks the closest such combination to y, so the residual y − Xβ̂ is perpendicular to every column of X — exactly Xᵀ(y − Xβ̂) = 0. OLS is orthogonal projection of y onto the column space of X.

Gauss-Markov & the assumptions you must name

Under four conditions OLS is the BLUE — Best (minimum-variance) Linear Unbiased Estimator.

Gauss-Markov is a conditional statement: among linear unbiased estimators, OLS has smallest variance. It does not say OLS is best overall — biased estimators (ridge, lasso) can have lower MSE. That gap is the entire point of regularization.

Normal equations vs gradient descent

Conditioning matters: κ(XᵀX) = κ(X)². Near-collinear columns make XᵀX nearly singular, and direct inversion amplifies floating-point noise. QR / SVD work on X directly and avoid the squaring. Ridge fixes it analytically by adding λI.

Multicollinearity — the failure mode that motivates regularization

Suppose features 3 and 4 are almost identical. The fits … + 5x_3 − 4x_4 … and … + 105x_3 − 104x_4 … make near-identical predictions because the difference of the coefficients is what acts on x_3 ≈ x_4. OLS can't choose; small data perturbations swing β̂ across this huge equivalent set. Predictions stay fine; coefficients become uninterpretable and high-variance.

Diagnostic: variance inflation factor VIF_j = 1/(1 − R²_j), where R²_j is the R² of regressing feature j on the others. VIF=1 means orthogonal; VIF≫10 is the conventional alarm. Fixes: drop one, combine them, or regularize.

Ridge regression — L2

Three views: (1) constrained — minimise ‖y − Xβ‖² s.t. ‖β‖² ≤ t(λ); (2) Bayesian — MAP under Gaussian prior β ~ N(0, τ²I) with λ = σ²/τ²; (3) bias-variance — λ↑ shrinks β̂ toward 0, raising bias and lowering variance.

The miracle: XᵀX + λI is positive definite for any λ > 0, even when XᵀX is singular. Ridge always has a unique solution. The analytic fix for multicollinearity — correlated features are shrunk together rather than fighting.

Lasso regression — L1

No closed form: the L1 penalty is non-differentiable at zero. Standard solver is coordinate descent with soft-thresholding:

where ρ_j = x_jᵀ(y − X_{−j}β_{−j}) is the partial residual correlation. The max(·, 0) is the crucial piece: when |ρ_j| ≤ λ, the coordinate is set exactly to zero. That's how lasso does feature selection.

Geometrically: the L1 ball is a diamond with corners on the axes; the L2 ball is a smooth sphere. Loss contours are ellipses centred at OLS, and the penalized optimum is where the smallest contour touches the constraint set. For the diamond, the touch point is very often a corner — coordinates are exactly zero. For the sphere, the touch point is generically interior — all coefficients nonzero, just shrunk.

Same OLS optimum, same loss contours, different penalty geometry. L2's smooth ball admits tangency anywhere on its surface — generically off-axis, so all coefficients shrink but stay nonzero. L1's diamond has corners on the axes, and the smallest reachable contour very often hits a corner — exact zero, feature selection by geometry.

Caveat: with several highly-correlated features, lasso arbitrarily picks one and zeros the others; the choice can flip across re-samples. Elastic net handles this case.

Elastic net

Zou & Hastie 2005. The L2 piece groups correlated features (shrinks them toward each other instead of arbitrary one-survivor selection); the L1 piece preserves feature selection. Two hyperparameters: total strength and L1/L2 mix.

Bayesian re-statement

Prior on β + MAP ⇒ penalty in log-space. Gaussian prior → L2 (ridge); Laplace prior → L1 (lasso). The Laplace has heavier tails and a sharper peak at zero — that's why it pushes coefficients all the way to zero rather than just shrinking. Regularization strength is inverse prior variance; "add a penalty" becomes "encode a prior belief that most coefficients are small".

Interactive · ridge vs lasso coefficient path

Synthetic dataset, 10 features: x0–x2 carry signal, x3 carries signal and is 95% correlated with the noise twin x4, x5–x9 are pure noise. Move λ along a log scale, flip between ridge / lasso / elastic-net.

When linear is enough

Against the modern reflex to reach for XGBoost: linear models with thoughtful preprocessing are often competitive on small clean tabular data, and they are the only models with closed-form standard errors — CIs on predictions, coefficients, and contrasts for free. The recipe: (1) encode categoricals well — one-hot for low cardinality, target / mean encoding with CV for high (lesson 10); naïve label-encoding into a linear model is almost always wrong; (2) hand-craft cross-features for known interactions — linear models don't discover interactions, that's tree-shaped intelligence; (3) regularize — ridge by default, elastic net if p > n or features correlated. When not to: large p with unknown interaction structure, heavy non-linearities, or anywhere you can afford XGBoost and don't need CIs.

Trade-offs at a glance

Interview prompts you should be ready for