Least Squares Regression

Definition

Design matrix $X\in {\mathbb{R}}^{n\times d}$ (points as rows), outputs $Y\in {\mathbb{R}}^n$. Least squares solves ${\min }_w\Vert Y-Xw{\Vert }^2$; an intercept is absorbed by a column of ones. The normal equations are $X^{t}Xw=X^{t}Y$.

Formula

$$\begin{array}{rl}& \mathrm{rank}(X)=d:w=(X^{t}X{)}^{-1}{X}^{t}Y\\ & \mathrm{rank}(X)<d:w=(X^{t}X{)}^{+}{X}^{t}Y\\ & A^{+}=\sum _{{\lambda }_i\ne 0}\frac{1}{{\lambda }_i}{v}_i{v}_i^t\end{array}$$

• Convex; the Hessian $X^{t}X$ is positive semi-definite.
• Rank deficient: $w+v$ with $Xv=0$ are also solutions; they agree on the training points, not on test points. The minimum norm solution is one natural choice.
• $d\ll n$ harmless; $d\gg n$ overfitting or benign overfitting. Fixed design excess risk of OLS: ${\sigma }^{2}d/n$.

Appears in

• Lecture 5, setup
• Lecture 5, Theorem 2 (least squares solution, full rank)
• Lecture 5, Theorem 3 (least squares solution, rank deficient)
• Lecture 5, n vs. d
• Lecture 5, excess risk of OLS
• Lecture 3, many minimizers when d ≫ n
• Lecture 8, GD converges to the minimum norm solution
• Lecture 8, Theorem 4 (excess risk in both regimes)

Related concepts

• Ridge Regression
• Lasso