Least squares and the matrix \(X^TX\)

Companion to Lecture 2, Sections 7–8. Data: \(x \sim \mathcal{N}(0, I_d)\), \(y = \langle \theta^*, x\rangle + \mathcal{N}(0, \sigma^2)\), \(\|\theta^*\| = 1\). We solve \((C + \lambda I)\,\hat\theta = X^TY/P\), with \(C = X^TX/P\) and eigenvalues \(\eta_1 \ge \dots \ge \eta_d \ge 0\). Test MSE \(= \sigma^2 + \|\hat\theta - \theta^*\|^2\).

rank of \(X^TX\) \(= \min(P, d)\)
largest eigenvalue \(\eta_{\max}\)
smallest eigenvalue \(\eta_{\min}\)
condition number \(\eta_{\max}/\eta_{\min}\)
train MSE
test MSE
Eigenvalues of \(C = X^TX/P\), largest to smallest (log scale)
\(\eta_i > 0\)\(\eta_i = 0\) exactly (drawn on the bottom edge)
Each component of the fitted \(\hat\theta\) against the true \(\theta^*\), with \(\lambda = 0\)
\((\theta^*_j, \hat\theta_j)\)perfect fit \(\hat\theta = \theta^*\)

\(\lambda = 0\), and \(\mathrm{rank}\, X^TX \le \min(P, d)\).

\(P < d\): \(d - P\) zero eigenvalues, so infinitely many \(\theta\) fit the data. We show the minimum-norm one, which gradient descent from \(\theta = 0\) reaches (Section 10): implicit regularization.

\(P \approx d\): \(\eta_{\min}\) is tiny, the noise is amplified by \(1/\eta_{\min}\), and \(\hat\theta\) shoots off (watch the axis).

\(P \gg d\): all \(\eta_i \to 1\) and \(\hat\theta \to \theta^*\).

Try: \(d = 60\), \(P\) = 30, 60, 70, 600. Then \(\sigma = 0\) at \(P = d\).

condition number of \(C\)
of \(C + \lambda I\): \((\eta_{\max}+\lambda)/(\eta_{\min}+\lambda)\)
test MSE at \(\lambda = 0\)
test MSE at this \(\lambda\)
train MSE at this \(\lambda\)
Eigenvalues before and after adding \(\lambda\) (log scale)
\(\eta_i\), eigenvalues of \(C\)\(\eta_i + \lambda\), eigenvalues of \(C + \lambda I\)level \(\lambda\)
Fitted \(\hat\theta_\lambda\) against the true \(\theta^*\)
\((\theta^*_j, \hat\theta_{\lambda, j})\)perfect fit
Error of the fit against \(\lambda\), same dataset (vertical line: current \(\lambda\))
test MSEtrain MSEnoise floor \(\sigma^2\)

\(\lambda\) lifts every eigenvalue by \(\lambda\) (Section 8, interlude): \(C + \lambda I\) is always invertible and better conditioned.

Small \(\lambda\): the unstable fit of tab 1 (high variance). Large \(\lambda\): \(\hat\theta \to 0\) (high bias), both errors \(\to \sigma^2 + 1\). The test error has a minimum in between; the train error only grows, so \(\lambda\) is chosen on a validation set (Lecture 3, Sections 3 and 5).

Try: \(P = d = 60\), slide \(\lambda\). Then \(P = 600\): \(\lambda\) barely helps.

ratio \(P/d\)
regime
test MSE, \(\lambda = 0\) (average)
test MSE, this \(\lambda\) (average)
Error against the number of patterns \(P\), for fixed \(d\) (average over 5 datasets; curves clipped at the top)
test MSE, \(\lambda = 0\)test MSE, this \(\lambda\)train MSE, \(\lambda = 0\)\(\sigma^2\), and \(P = d\)
Smallest eigenvalue \(\eta_{\min}\) of \(C\) against \(P\) (one dataset, log scale)
\(\eta_{\min} > 0\)\(\eta_{\min} = 0\) (drawn on the bottom edge)

The open question of Section 7.

\(P < d\): train MSE \(= 0\), but \(\eta_{\min} = 0\): the data cannot pin down \(\theta^*\) (minimum-norm fit, as in tab 1). \(P = d\): \(\eta_{\min}\) is closest to 0, and the test error peaks. \(P \gg d\): both errors reach the noise floor.

With \(\lambda > 0\) the peak disappears (tab 2). What matters is \(P/d\), not \(P\).

Try: change \(d\): the peak follows \(P = d\). Set \(\sigma = 0\): it vanishes.