Linear Regression
Simple on paper, brutal in interviews. Most candidates fail when asked to derive OLS or explain heteroscedasticity.
Closed-form solution (OLS)
Linear regression assumes y = Xβ + ε, where y ∈ ℝᴺ, X ∈ ℝᴺˣᵈ, β ∈ ℝᵈ, and residual errors ε ~ N(0, σ²I).
To find optimal β, minimize Sum of Squared Errors (SSE):
L(β) = ||y - Xβ||² = (y - Xβ)ᵀ(y - Xβ) = yᵀy - 2βᵀXᵀy + βᵀXᵀXβ
Taking derivative wrt β and setting to 0:
∇_β L(β) = -2Xᵀy + 2XᵀXβ = 0 ⇒ (XᵀX)β = Xᵀy ⇒ β = (XᵀX)⁻¹Xᵀy
This normal equation gives the exact global minimum because SSE is strictly convex.
The 5 Gauss-Markov assumptions
For OLS to be BLUE (Best Linear Unbiased Estimator):
- Linearity: Relationship between X and mean of y is linear in parameters.
- Strict Exogeneity:
E[ε | X] = 0(residuals have zero mean, independent of X). - No Multicollinearity:
XᵀXis full rank (invertible). - Homoscedasticity: Constant error variance
Var(ε_i | X) = σ². - No Autocorrelation: Residual errors are uncorrelated across observations
Cov(ε_i, ε_j) = 0.
If residuals have non-constant variance (heteroscedasticity), OLS estimates remain unbiased but standard errors are wrong and confidence intervals fail. Use Robust Standard Errors (White's HC) or Weighted Least Squares (WLS).
OLS vs Gradient Descent
| Factor | Closed-Form OLS | Gradient Descent |
|---|---|---|
| Equation | β = (XᵀX)⁻¹Xᵀy | β := β - α ∇L(β) |
| Time Complexity | O(d³ + Nd²) | O(k · Nd) for k iterations |
| Memory | Needs XᵀX in memory (O(d²)) | Mini-batch (O(B · d)) |
| Hyperparameters | None | Learning rate α, batch size, iterations |
| Scaling Required | No | Yes (critical for convergence) |
Large Features (d > 100k) | Fails (inversion slow/impossible) | Scales easily (SGD / Adam) |
Say this out loud
"Linear regression minimizes sum of squared residuals. The closed-form OLS solution is β = (XᵀX)⁻¹Xᵀy, which is BLUE under Gauss-Markov assumptions. For small to medium feature counts, OLS is instant and non-parametric. But when feature count d is very large, d³ matrix inversion becomes prohibitive, so we switch to Mini-Batch Gradient Descent with feature scaling."
Follow-ups to expect
- What happens if residual distribution is non-normal? OLS estimates are still unbiased and BLUE, but exact hypothesis tests (t-tests, F-tests, p-values) require normality in small samples.
- How do you detect heteroscedasticity? Plot residuals vs fitted values (look for a funnel/cone shape) or run Breusch-Pagan / White test.
- How do you fix multicollinearity? Drop redundant features, combine them using PCA, or apply L2 regularization (Ridge regression).
Check yourself
What is the computational complexity of solving OLS via the normal equation β = (XᵀX)⁻¹Xᵀy for N samples and d features?