Regression §

Derivation: the objective is $\mathcal{L}(\theta) = (X\theta - y)^T(X\theta - y)$. Taking the gradient and setting it to zero:

If $X^T X$ is invertible (i.e., $X$ has full column rank $d$), the solution is unique.

When to use the closed form: for small $d$ (say $d < 10^4$), the normal equation or QR decomposition is faster than any iterative method. For large $d$ (deep learning: $d > 10^6$), the $O(d^3)$ cost is infeasible, and the loss must be minimized iteratively with gradient descent, which defines the epoch, the learning rate, and the convergence rate.

What the fit looks like: the figure below shows 15 samples of $y = 2 + 1.5x + \text{noise}$ with the least-squares line $\hat{y} = 0.90 + 1.66x$ and the residuals (the vertical segments between each point and the line). The normal equation is the unique line that makes the sum of the squared residual lengths minimal.

Try it yourself: drag the line through the points and watch the MSE change; the dashed line is the least-squares optimum.

Example problem:

Why tr(H) counts parameters: $H$ is the orthogonal projection onto the column space of $X$. An idempotent matrix has only eigenvalues $0$ and $1$, so $\text{tr}(H)$ — the sum of the eigenvalues — counts the $1$s, i.e. the dimension of the column space. Each of those dimensions can absorb one independent direction of noise: the more of them, the more noise the fit can memorize.

Bias-variance tradeoff: the expected prediction error decomposes as:

• Underfitting (high bias): the model is too simple; increasing capacity (more parameters, higher degree) reduces bias.
• Overfitting (high variance): the model is too complex; it fits noise in the training data. Reducing the effective number of parameters (regularization, more data) reduces variance.

The learning curve: the standard diagnostic is to plot the training and validation loss against training progress. The figure below shows the typical shape: the training loss keeps falling (the model keeps memorizing), while the validation loss bottoms out and then rises — the point where the two diverge is where the model starts fitting noise.

The train/validation split and these diagnostics are general machine-learning concepts; see Learning Paradigms and Models for their treatment in the context of neural networks.

Example problem:

Ridge: with orthonormal features, each coefficient shrinks smoothly: $\beta_j(\lambda) = \beta_j^{OLS} / (1 + \lambda / \sigma_j^2)$. The effective number of parameters becomes $\text{tr}(H_\lambda) = \sum_j \sigma_j^2 / (\sigma_j^2 + \lambda) < d$ — regularization literally reduces the degrees of freedom the model can use to fit noise. Ridge is the same L2 penalty used as weight decay in neural network training.

Lasso: with orthonormal features, each coefficient is soft-thresholded: $\beta_j(\lambda) = \text{sign}(\beta_j^{OLS}) \max(|\beta_j^{OLS}| - \lambda, 0)$. Coefficients smaller than the threshold become exactly zero — the lasso performs feature selection, keeping at most $\min(n, d)$ features. With correlated features it tends to pick one from each group; the elastic net fixes this by adding the ridge term, which keeps correlated groups together.

Coefficient paths: the figure below shows the four coefficients of a fit as $\lambda$ grows from 0 (plain least squares) to 2.5. Ridge shrinks everything smoothly toward zero; the lasso drives the small coefficients exactly to zero at $\lambda = |\beta_j^{OLS}|$.

Choosing λ: the penalty strength $\lambda$ is a hyperparameter, chosen by validation loss or cross-validation (next section).

Example problem:

Why R² lies: $R^2$ is computed on the training data. When $d \geq n$, interpolation gives $\text{SS}_{res} = 0$ and $R^2 = 1$ no matter how much of the fit is noise — a training $R^2$ of 1 is a red flag, not an achievement. Adjusted $R^2$ corrects for $p$: it can be negative (the model is worse than predicting the mean) and saturates at 1 under interpolation, so neither metric can judge an over-parameterized model — only a held-out estimate can.

k-fold cross-validation: $k = 5$ or $10$ in practice. Each fold is used for validation exactly once, so the estimate uses all the data. It is the standard way to choose $\lambda$ (regularization strength), the polynomial degree, and other capacity knobs.

The split protocol:

1. Train: fit the model.
2. Validate: choose hyperparameters ($\lambda$, degree, early-stopping point).
3. Test: a single final evaluation on data never used for any decision.

Example problem:

Feature engineering: the only difference from linear regression is the columns of $X$: instead of $x$, the model sees $(x, x^2, \ldots, x^k)$. Everything else — the closed form, the hat matrix, regularization — carries over.

The degree as a capacity knob: the figure below fits polynomials of degree 1, 3 and 10 to 12 noisy samples of $y = \sin x$. Degree 1 underfits (the line cannot bend); degree 3 tracks the curve; degree 10 has 11 parameters for 12 points, so it interpolates the samples — and diverges wildly outside the data range.

Ill-conditioning: as $k$ grows, the columns $x, x^2, \ldots, x^k$ become nearly collinear and the normal equation becomes numerically unstable. In practice, scale $x$ to $[-1, 1]$ or use orthogonal polynomials.

Connection to kernel methods: the ridge solution can be written in dual form as $f(x) = \sum_i \alpha_i K(x_i, x)$ with $K(x, x') = x^T x'$: the prediction depends on the data only through inner products. Replacing the inner product with a kernel (e.g. the RBF $K(x, x') = e^{-\|x - x'\|^2 / 2\sigma^2}$) gives a nonlinear model without writing the features explicitly; a polynomial kernel of degree $k$ is exactly polynomial regression of degree $k$.

When to prefer a nonlinear model: when a linear model leaves systematic structure in the residuals (the fit bends in a consistent direction). But choose the smallest $k$ that the validation loss supports (see Model selection) — the degree-10 fit above is the failure mode of turning the knob too far.

Example problem:

(a) $\text{rank}(X) \leq n = 100$, and since the rows are independent, $\text{rank}(X) = 100$. Hence $\text{tr}(H) = \text{rank}(X) = 100$: the model has 100 effective degrees of freedom — exactly enough to interpolate the 100 training points (zero training loss).

(b) Overfitting: after iteration 50 the model starts fitting the noise in the training data; the validation loss rises while the training loss keeps falling. Remedies: regularization (ridge or lasso), more data, or early stopping at iteration 50.

(c) Lasso: it drives the ~290 irrelevant coefficients exactly to zero (sparsity), keeping only the ~10 informative ones. Ridge would shrink them toward zero but never to zero, leaving all 300 features active.