Gradient descent, ridge and KNN regression
Three tools from the week 2 lab: walk downhill when you don't want (or can't use) a formula, shrink the coefficients so the model stops chasing noise, and compare against the no-formula alternative, KNN.
Gradient descent returns in weeks 3 and 4 (logistic regression and neural networks have no formula, so it’s the only way). The ridge penalty returns as tree pruning’s \(\alpha|T|\) and a network’s weight decay. Learn them properly here.
Book: what to read for this stage
ISLP 6.2.1 ridge regression (including why you standardise) and 6.2.3 selecting the tuning parameter: read. 6.2.2 the lasso: skim (the slides only name it). 6.1.1, 6.1.2 subset selection and 6.3, 6.4: skip. 3.5 comparison of linear regression with KNN: read, it’s what lab Q2 asks you to discuss. Gradient descent isn’t in chapters 3 or 6; ISLP 10.7 covers it later.
Slide typo
Eq. (60): the ridge penalty is \(\lambda\|\beta\|^2 = \lambda\sum_{j=1}^{p}\beta_j^2\), squared, and the sum starts at \(j = 1\), so the intercept is not penalised.
1. Gradient descent
Start from a guess and repeatedly step downhill:
\[\beta^{(t+1)} = \beta^{(t)} - \eta\,\nabla\mathrm{RSS}(\beta^{(t)}).\]
The gradient points uphill, so subtract it. \(\eta\) is the learning rate; each pass over the data is an epoch. For linear regression \(\nabla\mathrm{RSS} = -2\sum_i(y_i - \hat y_i)\tilde x_i\): each point pushes \(\beta\) along its own \(\tilde x_i\), in proportion to its residual.
Worked example (one parameter). Centred data from stage 5: \(S_{xy} = 6\), \(S_{xx} = 10\), model \(\hat y = \beta x\). \(\mathrm{RSS}'(\beta) = -2(S_{xy} - \beta S_{xx}) = -2(6 - 10\beta)\). With \(\eta = 0.01\) from \(\beta = 0\):
| \(t\) | \(\beta\) | gradient | next \(\beta\) |
|---|---|---|---|
| 0 | 0 | \(-12\) | \(0.12\) |
| 1 | 0.12 | \(-9.6\) | \(0.216\) |
| 2 | 0.216 | \(-7.68\) | \(0.2928\) |
Each step closes 20% of the gap to the answer 0.6, because \(\beta^{(t+1)} - 0.6 = (1 - 2\eta S_{xx})(\beta^{(t)} - 0.6) = 0.8(\beta^{(t)} - 0.6)\).
Two lessons for the lab. The learning rate must be small enough: here GD converges only if \(|1 - 2\eta S_{xx}| < 1\), i.e. \(\eta < 1/S_{xx}\); too big and the steps overshoot and blow up, too small and it crawls. Inputs on wildly different scales make \(S_{xx}\) huge for some of them, which is why the lab normalises every column first. And because the RSS is a single convex bowl, any starting point reaches the same minimum (lab Q1’s ten random starts all agree).
With \(S_{xx} = 10\) in the one-parameter model above, what is the largest learning rate for which gradient descent still converges? (Give the boundary value.)
Need \(|1 - 2\eta \times 10| < 1\), i.e. \(0 < \eta < 0.1\).
2. Ridge regression
When \(n\) isn’t much bigger than \(p\), or inputs are nearly collinear, least squares has high variance: \(\mathrm{var}(\hat\beta) = \sigma^2(\mathbf X^T\mathbf X)^{-1}\) blows up. Shrinkage keeps every input but pulls the coefficients towards 0, trading a little bias for a lot less variance:
\[\hat\beta^{\text{ridge}} = \arg\min_\beta\ \underbrace{\sum_i\Big(y_i - \beta_0 - \sum_j\beta_jx_{ij}\Big)^2}_{\mathrm{RSS}} + \lambda\sum_{j=1}^{p}\beta_j^2.\]
- \(\lambda = 0\): ordinary least squares. \(\lambda \to \infty\): every \(\beta_j \to 0\), the model predicts \(\bar y\).
- Increasing \(\lambda\) makes the model less flexible: bias up, variance down, training RSS up. Test MSE is U-shaped in \(\lambda\).
- The intercept isn’t penalised (it just sets the level).
- Standardise the inputs first. The penalty treats every \(\beta_j\) alike, but a coefficient’s size depends on its input’s units. OLS doesn’t care about units; ridge does.
- Closed form (centred data): \(\hat\beta^{\text{ridge}} = (\mathbf X^T\mathbf X + \lambda I)^{-1}\mathbf X^T\mathbf y\). Adding \(\lambda I\) makes the matrix invertible even under collinearity or with \(p > n\).
- The lasso uses \(\lambda\sum|\beta_j|\) instead and sets some coefficients exactly to 0.
Worked example. One centred input: minimise \(\sum(y_i - \beta x_i)^2 + \lambda\beta^2\). Derivative \(-2(S_{xy} - \beta S_{xx}) + 2\lambda\beta = 0\) gives \(\hat\beta^{\text{ridge}} = \dfrac{S_{xy}}{S_{xx} + \lambda}\). With \(S_{xy} = 6\), \(S_{xx} = 10\): \(\lambda = 0 \to 0.6\), \(\lambda = 5 \to 0.4\), \(\lambda = 10 \to 0.3\), \(\lambda = 90 \to 0.06\). It shrinks smoothly but never reaches 0.
As \(\lambda\) increases from 0 in ridge regression, tick what happens.
Ridge shrinks towards zero but never exactly reaches it (that’s the lasso). The intercept isn’t penalised.
3. Choosing \(\lambda\) (and everything else) on validation data
\(\lambda\), the polynomial degree, KNN’s \(K\): none can be chosen by training error (the most flexible option always wins there; for ridge, training error always picks \(\lambda = 0\)). So fit on the training set for each candidate, pick the one with the lowest validation error, and report the test error once. Try \(\lambda\) on a log scale (e.g. np.logspace(-3, 2, 10)), since the order of magnitude is what matters.
You choose ridge’s \(\lambda\) by the smallest training MSE. What do you get?
The penalty can only make the fit to the training data worse. That’s why validation data are needed.
4. KNN regression vs linear regression
KNN regression predicts the average of the \(K\) nearest neighbours’ responses (stage 4). Compare it with linear regression (ISLP 3.5, lab Q2):
- If the truth is close to linear, linear regression wins: low variance, and it extrapolates sensibly.
- If the truth is strongly non-linear and there is plenty of data, a well-chosen \(K\) can win.
- With many inputs KNN suffers from the curse of dimensionality: in high dimensions every point is far from every other, so the “nearest” neighbours aren’t really near.
- Linear regression is interpretable; KNN is a black box. KNN needs normalised inputs.
You have 20 inputs and 300 observations, and the relationship looks roughly linear. Which would you expect to predict better?
Roughly linear truth plus many inputs (the curse of dimensionality) both favour linear regression.
Stage test
(4 marks, exam format 3.) Write the ridge regression objective, explain what \(\lambda\) does to the model’s flexibility, bias and variance, and say why the inputs should be standardised first.
Ridge regression minimises \(\sum_{i=1}^n\big(y_i - \beta_0 - \sum_{j=1}^p\beta_jx_{ij}\big)^2 + \lambda\sum_{j=1}^p\beta_j^2\), the RSS plus a penalty on the squared coefficients (not the intercept). With \(\lambda = 0\) it is least squares; as \(\lambda\) grows the coefficients are shrunk towards zero, so the model becomes less flexible: its bias increases and its variance decreases, which can lower the test error when least squares overfits (small \(n\), many or collinear inputs). Test error is U-shaped in \(\lambda\), so \(\lambda\) is chosen on a validation set. Inputs should be standardised because the penalty charges every \(\beta_j^2\) equally, but the size of \(\beta_j\) depends on the units of \(x_j\); without standardising, inputs measured in small units would be shrunk much more than others.
Why does the RSS of linear regression let gradient descent reach the same answer from any starting point (with a small enough learning rate)?
Convex: no other valleys to get stuck in. (Neural networks, in stage 17, are not convex.)
\(X_3 = X_1 + X_2\) exactly. Which statement is true?
That’s one of the main reasons ridge exists.
KNN regression on \(x = (1, 2, 3, 4, 5, 6)\), \(y = (1.0, 1.5, 2.5, 3.0, 5.0, 6.0)\). Predict at \(x_0 = 5.2\) with \(K = 2\).
Nearest are \(x = 5\) (0.2 away) and \(x = 6\) (0.8 away): \((5.0 + 6.0)/2 = 5.5\).