Chapter 4 — Derivations

Generalization is where interviewers stop asking "what is the formula" and start asking "prove that it has to be true". Screens and onsite loops ask for the core three: the bias–variance decomposition with its two vanishing cross terms, the optimism of training error (\sigma^2(1 - p/n) against \sigma^2(1 + p/n)), and degrees of freedom as \operatorname{tr} (S). Senior loops add ridge in the SVD basis, the lasso's KKT conditions, what K-fold CV really estimates, and why early stopping, input noise and dropout are ridge in disguise. Research and quant loops go one level further. They ask you to prove that \lambda = \sigma^2/\tau^2 is the best possible penalty, that some \lambda > 0 always beats least squares, that the minimum-norm interpolator's risk blows up at p = n, and how much data survives importance weighting. The 19 cards below cover all of it. Each one gives the statement, every step of the derivation, the one move that does the work, the slip candidates make, and how the question is really asked. Where a card can check itself, its last step does so on the chapter's running example: the six pilot days and July 20, the 30-day season rerun 500 times, or the 100 stations. How to practice: read only the statement, derive it on a blank page against a timer, then check every step and number here. Re-derive anything you missed 48 hours later (the protocol is at the end). Chapter 1's cards (the normal equation, unbiasedness, \mathbb{E}[\text{RSS}] = (n - p)\sigma^2, the LOOCV shortcut for OLS) are not repeated. When a card leans on one, it says so in one line.

The toolkit

Four moves do every derivation in this chapter. Hook: S-E-A-T — pull up a seat at the whiteboard, and try the letters in order.

• S — SVD: rotate to the basis where the problem decouples. Write X = UDV^\top. Every linear smoother in this chapter (least squares, ridge, gradient descent from zero, the pseudo-inverse) becomes a separate scalar problem along each direction u_j, scaled by its singular value d_j.

X

the design matrix: one row per day, one column per feature

U

the left singular vectors: orthonormal patterns across the days, stacked as columns

D

the diagonal matrix of singular values d_j, strongest first

V^\top

V transposed (transpose: rows become columns)

V

the right singular vectors: orthonormal directions in weight space

X^\top X

the Gram matrix: sums of squares and cross-products of the feature columns

(X^\top X + \lambda I)^{-1}

the matrix inverse inside the ridge solution: it undoes X^\top X + \lambda I

\lambda

the ridge penalty strength: bigger means more shrinkage

I

the identity matrix: 1s on the diagonal, 0s elsewhere

(D^2 + \lambda I)^{-1}

a diagonal matrix with entries 1/(d_j^2 + \lambda): inverting is just dividing

z_j

the least-squares coefficient along SVD direction j

\mathbf u_j

column j of U: one pattern across the days (bold = a vector)

\mathbf y

the vector of observed daily rides above average, in thousands

d_j

the j-th singular value: how strongly the features vary along direction j

j

which SVD direction, counted from the strongest

• E — Expectation over the noise or the prior. The noise has mean zero and covariance \sigma^2I; a prior on the weights has covariance \tau^2I. Independence turns the expectation of a product into a product of expectations, and the tower rule averages in two stages.

\mathbb E

expected value: the average over repeated draws of the noise (or the prior, or the data)

\boldsymbol\varepsilon

the noise vector: each day's random departure from the true curve

\mathbf 0

the all-zeros vector

\sigma^2

the noise variance: 0.09 for the daily rides, 4 for the stations

U \perp V

U and V are independent: knowing one tells you nothing about the other

U

here any random quantity (not the SVD matrix)

V

here a second random quantity

g

any random quantity whose average we want

\mathbb E[g \mid X]

the average of g with X held fixed: the first of the two stages

X

here whatever we average over first, such as the design

• A — Add and subtract the mean (Chapter 1's A, reused). Insert the quantity you wish were there, expand the square, and show the cross term is zero.

a

the quantity whose squared error we want, such as the new day's rides

c

what it is compared with, such as the prediction

b

the quantity we add and subtract: the mean we wish were there

2\,\mathbb E[(a - b)(b - c)]

the cross term: zero when a - b averages to 0 whatever b and c are

• T — Trace trick (Chapter 1's T, reused). A quadratic form in noise has expectation \sigma^2 times a trace, and the trace is cyclic.

A

any fixed square matrix, which turns the noise into a quadratic form

\text{tr}

the trace: the sum of a matrix's diagonal entries

B

any matrix whose products with A are square

H

the hat matrix of least squares, which projects onto the columns of X

p

the number of fitted coefficients: the rank of the projection

Which move does the work, card by card: S for Cards 6, 7, 8, 9, 13, 16; E for 1, 2, 4, 5, 8, 11, 14, 15, 17, 18; A for 1, 2, 5, 7, 8, 10; T for 3, 4, 12, 16, 18. Card 19 is counting. When you're stuck on an unfamiliar question, run down the letters. Can I rotate it into independent directions? What am I averaging over — the noise, the prior, the design? What mean should I add and subtract? Is there a quadratic form in the noise whose trace I can take?

Loss conventions, used on every card. These are Chapter 1's conventions:

• Ridge is \lVert y - Xw\rVert^2 + \lambda \lVert w\rVert^2.
• Lasso is \lVert y - Xw\rVert^2 + \lambda \lVert w\rVert_1, so the orthonormal-design soft threshold is \lambda/2.
• Elastic net is \lVert y - Xw\rVert^2 + \lambda_1\lVert w\rVert_1 + \lambda_2\lVert w\rVert^2.
• Gradient descent runs on \tfrac 12 \lVert y - Xw\rVert^2 with step \eta. Its ridge twin is \tfrac 12 \lVert y - Xw\rVert^2 + \tfrac 12 \lambda \lVert w\rVert^2, which has the same minimizer as the ridge form above.
• The intercept is never penalized. With an intercept, center y and the feature columns first; the intercept is then \bar{y} and adds one degree of freedom.
• scikit-learn's Ridge(alpha) uses the same scaling as ridge here. Lasso(alpha) minimizes (1/2n)\lVert y - Xw\rVert^2 + \alpha \lVert w\rVert_1, so this tab's \lambda for lasso equals 2n\cdot \alpha.

Notation used on every card.

Three \lambda scales. The toy (raw centered months, d^2 = 70), the season (standardized Legendre features, best \lambda \approx 5.6) and the stations (Bayes \lambda = 80) use different scales. Never compare \lambda values across them.

Formula sheet

Every formula the cards derive, in one place. Cover the block, say it, check.

Risk and the decomposition

Risk, empirical risk and the generalization gap

R

risk: the average loss on fresh days from the same distribution

f

a predictor: any function from day to predicted rides

\mathbb E_{(X,Y)}

the average over a fresh random day X and its rides Y

\ell

the loss on one prediction, such as squared error

Y

the rides on a random day

X

a random day (the input)

\hat R_n

empirical risk: the average loss over the n training days (hat = estimated from data)

n

the number of training days

\sum_{i=1}^{n}

add up over training days i = 1 to n

y_i

the observed rides on training day i

x_i

training day i's input (its date)

\mathbb E

expected value: the average over random training sets (and new days)

\hat f

the fitted predictor: the family member with the lowest training loss

f^*_{\mathcal F}

the family's best member: the lowest true risk (star = optimum)

\mathcal F

the family of models we search, such as all cubics

Bayes predictor and the noise floor (squared loss)

f_{\text{Bayes}}

the Bayes predictor: the best possible prediction for each day

\mathbb E[Y \mid X = x]

the average rides over all days like x (the conditional mean)

x

a particular day of the year

\text{Var}(Y \mid X)

how much rides scatter around that mean on a given day

\sigma^2

the noise variance: 0.09 for the rides, the floor no model can beat

Excess risk: Family, Sample, Search

\tilde f

what the optimizer actually returns (tilde = approximate)

R^*

the Bayes risk: the lowest risk any predictor can reach

\hat f_n

the exact training-loss minimizer on n rows

Bias–variance decomposition at a point

Y_0

the rides on the new day, including its noise

x_0

the new day where we predict, such as July 20

\hat f(x_0)

the fit's prediction at x_0; random, because the training set is random

\mathbb E\hat f(x_0)

that prediction averaged over many training seasons

f(x_0)

the true average rides at x_0

Capacity and optimism

Optimism of least squares: fixed X, then random Gaussian X

X

the design matrix: the n training inputs, one row each

\frac pn

coefficients per training row: p fitted coefficients over n rows

\sim

is distributed as

N(0, \Sigma)

a Gaussian with mean zero and covariance matrix \Sigma

\Sigma

the covariance matrix of one feature row

\frac{p}{n - p - 1}

the random-design penalty for p coefficients: it blows up as p nears n

\frac{p}{n - p - 2}

the same penalty when one more row is spent on the intercept

Degrees of freedom and the rent

\text{df}

degrees of freedom: how hard the fit chases its own noise

\text{Cov}(\hat y_i, y_i)

how much day i's fitted value moves with its own observed rides

\hat y_i

the fitted rides for training day i

\text{tr}(S)

the trace of S: the sum of its diagonal entries

S

the smoother matrix: turns observed rides into fitted values

\hat{\mathbf y}

the vector of fitted values for all training days

\mathbf y

the vector of observed rides

Cp, AIC, AICc and BIC: training error plus rent

C_p

Mallows' C_p: training MSE plus the optimism rent, with \sigma^2 known

\text{RSS}

residual sum of squares: the total squared training error

\text{AIC}

Akaike's criterion: log training error plus 2 per degree of freedom

\text{AICc}

AIC with a small-sample correction

\text{BIC}

the Bayesian criterion: charges \ln n per degree of freedom instead of 2

kNN: bias, variance and df

\text{Var}

variance over repeated training seasons

\hat f_k(x_0)

the k-nearest-neighbor prediction at x_0: the average rides of the k closest days

k

the number of neighbors averaged

\sum_{i \in N_k(x_0)}

add up over the k training days nearest to x_0

f(x_i)

the true curve at neighbor day x_i

f''(x_0)

the curvature of the true curve at x_0 (its second derivative)

h

the spacing between neighboring training days

m

the number of neighbors on each side, so k = 2m + 1

VC dimension and the shape of the bound

\text{VC}

VC dimension: the most points the family can label in every possible way

\mathbb R^d

d-dimensional input space

d

the number of input dimensions

\omega

the sine's frequency: the family's only parameter

x

a one-dimensional input point

O

"grows at most like": constants are dropped

h

the VC dimension (here not the day spacing)

\delta

the allowed failure probability: the bound holds with chance 1 - \delta

Ridge

Ridge in the SVD basis and its effective df

\hat{\mathbf w}_\lambda

the ridge weights at penalty \lambda (hat = fitted; bold = a vector)

X

the design matrix: one row per day, one column per feature

\lambda

the ridge penalty strength

\sum_{j}

add up over SVD directions j

\sum_j

add up over SVD directions j

\mathbf u_j

the j-th left singular vector of X: a pattern across the days

d_j

the j-th singular value of X: the strength of direction j

\frac{d_j^2}{d_j^2 + \lambda}

ridge's filter: the fraction of direction j it keeps, between 0 and 1

\text{df}(\lambda)

ridge's effective degrees of freedom: the sum of the filters

Ridge bias and variance

\boldsymbol\beta

the true coefficient vector

(X^\top X + \lambda I)^{-1}

the inverse of the penalized Gram matrix (the inverse undoes a matrix)

X^\top X

the Gram matrix: sums of squares and cross-products of the feature columns (^\top = transpose)

I

the identity matrix

Per-direction MSE, Hoerl–Kennard and the one-direction optimum

\text{MSE}_j(\lambda)

ridge's coefficient error along direction j: squared bias plus variance

\theta_j

the true coefficient along direction j: \boldsymbol\theta = V^\top\boldsymbol\beta

\frac{d}{d\lambda}

how fast what follows changes as you nudge \lambda: a slope, not a fraction to divide

\Big|_{\lambda = 0}

evaluated at \lambda = 0, which is plain least squares

\lambda_j^*

the best penalty for direction j alone (star = optimum)

j

which SVD direction, counted from the strongest

Posterior mean and the Bayes-optimal \lambda

\mathbf w

the weight vector, treated as random under the prior

N(\mathbf 0, \tau^2 I)

a Gaussian prior: each weight independent, mean 0, variance \tau^2

\tau^2

the prior variance: how big true effects typically are

\mathbb E[\mathbf w \mid \mathbf y]

the posterior mean: the average weights given the observed data

\text{Cov}(\mathbf w \mid \mathbf y)

the posterior covariance: the uncertainty left after seeing the data

\lambda^*

the Bayes-optimal ridge penalty: noise variance over prior variance

Lasso and elastic net

Lasso: KKT conditions, \lambda_{\max} and soft-thresholding

\mathbf x_j

column j of X: one feature's values across all rows

\hat{\mathbf w}

the fitted lasso weight vector

\mathbf y - X\hat{\mathbf w}

the residual vector: what the fit leaves unexplained

\lambda

the lasso penalty strength

\text{sign}

the sign: +1 for a positive number, -1 for a negative one

\hat w_j

the fitted weight on feature j

\lambda_{\max}

the smallest penalty at which every lasso weight is zero

\max_j

the largest over all features j

z_j

the least-squares weight on feature j (orthonormal design)

\Big(|z_j| - \frac\lambda2\Big)_+

shrink |z_j| by \lambda/2, stopping at zero (the + keeps only the positive part)

Elastic net: the grouping effect

\hat w_i

the elastic-net weight on feature i

\hat w_j

the elastic-net weight on a second feature j

\lVert\mathbf y\rVert_2

the length of the response vector (Euclidean norm)

\lambda_2

the elastic net's ridge (squared-norm) penalty strength

\rho_{ij}

the correlation between features i and j

\lVert\mathbf x_i\rVert

the length of feature column i, scaled to 1

\mathbf x_i

column i of X: feature i's values across all rows

Cross-validation

What K-fold estimates, and how noisy it is

\text{CV}_K

the K-fold cross-validation estimate of test error

K

the number of folds, such as 10

\text{Err}

the expected test error of a model trained on the given number of rows

\sum_{k=1}^{K}

add up over folds k = 1 to K

e_k

the validation error on fold k

s^2

the variance of one fold's error

\rho

the correlation between two folds' errors (their training sets overlap)

LOOCV and GCV for linear smoothers

\hat f^{(-i)}(x_i)

the prediction at day i from a fit that never saw day i

S_{ii}

day i's leverage: the weight its own rides get in its fitted value

\text{GCV}

generalized cross-validation: LOOCV with every leverage replaced by the average

\sum_i

add up over training days i

The lucky minimum

\hat e_c

configuration c's validation error estimate

\mu

the true error that every configuration shares

s

the noise level (standard deviation) of one validation estimate

Z_c

configuration c's luck: a standard normal draw

c

which configuration (hyperparameter setting)

C

how many configurations were tried

\min_c

the smallest over all configurations: the reported winner

\max_c

the largest over all configurations

Other regularizers

Early stopping as a spectral filter

\mathbf w_t

the gradient-descent weights after t steps, started from zero

1 - (1 - \eta d_j^2)^t

gradient descent's filter: the fraction of direction j fitted after t steps

\eta

the step size (learning rate)

\lambda

the ridge penalty that early stopping mimics

\frac{1}{\eta t}

one over (step size × number of steps t): the matching ridge penalty

Noise injection = ridge

\mathbf x_i

row i's feature vector (one day's inputs)

\tilde{\mathbf x}_i

row i's inputs after adding random jitter (tilde = noisy copy)

\boldsymbol\delta_i

the Gaussian noise added to row i's inputs

N(\mathbf 0, s^2 I)

Gaussian with mean zero and variance s^2 in every coordinate, all independent

s^2

the variance of the injected input noise

\mathbb E_\delta

the average over the injected noise

\tilde X

the design matrix with every row jittered

\mathbf w

the weight vector

\lVert\mathbf y - X\mathbf w\rVert^2

the clean sum of squared errors (squared length of the residual)

\lVert\mathbf w\rVert^2

the squared length of the weight vector: ridge's penalty

\lambda

the ridge penalty this noise is equivalent to

Dropout = per-feature ridge

\tilde x_{ij}

feature j of row i after dropout

x_{ij}

the original value of feature j on row i

\delta_{ij}

the dropout mask: 1 if the input is kept, 0 if it is dropped

q

the keep probability

\text{Bernoulli}(q)

a coin that lands 1 with probability q

\mathbb E_\delta

the average over the random dropout masks

\sum_j

add up over features j

w_j

the weight on feature j

Double descent, learning curves and shift

Minimum-norm interpolation and its risk (isotropic Gaussian X)

\hat{\mathbf w}

the minimum-norm interpolator: the shortest weight vector that fits every row exactly

X^+

the pseudo-inverse of X

(XX^\top)^{-1}

the inverse of the n \times n matrix of row inner products

(p > n)

more coefficients than rows: infinitely many exact fits

R

the test risk on a new isotropic Gaussian row

p < n - 1

fewer coefficients than rows: ordinary least squares

p > n + 1

past the interpolation threshold

\frac{n}{p - n - 1}

the variance term past the threshold: it falls as features are added

\lVert\boldsymbol\beta\rVert^2

the squared length of the true coefficients: the total signal

\frac np

the share of \boldsymbol\beta the fit can see: rows over coefficients

Learning curves: variance falls as 1/n; the power law

\text{bias}^2_{\mathcal F}

the squared bias of the family's best member: error more data can't remove

\text{err}(n)

the test error after training on n rows

a

the error floor the curve levels off at

b

the size of the reducible part

\alpha

the power-law exponent: how fast extra data pays off

Importance weights and effective sample size

w(x)

the importance weight of day x: how much likelier it is at test time than in training

p_{\text{test}}(x)

the density of day x at deployment

p_{\text{train}}(x)

the density of day x in the training data

\mathbb E_{\text{train}}

the average over days drawn as in training

w(X)

the weight of a random training day X

\mathbb E_{\text{test}}

the average over days drawn as at deployment

\text{ESS}

effective sample size: how many unweighted rows the weighted sample is worth

w_i

the importance weight of training row i

w

the importance weight, as a random quantity

Cards

Card 1 · Risk, empirical risk and the excess-risk split ★

Statement. Risk is the average loss on new draws; empirical risk is the average loss on the training rows. For a fit chosen by empirical risk minimization (ERM) over a family F, training error is optimistic on average. Above the noise floor, the excess risk splits three ways: Family, Sample, Search.

\mathbb E

expected value: the average over random training sets (and new days)

\hat R_n

empirical risk: the average loss over the n training days (hat = estimated from data)

n

the number of training days

R

risk: the average loss on fresh days from the same distribution

\hat f

the ERM fit: the family member with the lowest training loss

f^*_{\mathcal F}

the family's best member: the lowest true risk (star = optimum)

\mathcal F

the family of models searched, such as all cubics

\tilde f

what the optimizer actually returns (tilde = approximate)

R^*

the Bayes risk: the lowest risk any predictor can reach, set by the noise

Derivation.

1. Name the three functions. The ERM fit \hat{f} minimizes training loss over F. The best member f^*_F minimizes the true risk over F; it is fixed, because it does not depend on the data. The optimizer's output \tilde{f} is what the code actually returns.

\arg\min_{f \in \mathcal F}

the member f of the family that makes what follows smallest

f

any candidate predictor in the family

1. For a fixed f, empirical risk is unbiased. Each training row is a fresh draw from the same distribution, so each term has mean R(f) (E).

\sum_{i=1}^{n}

add up over training days i = 1 to n

\ell

the loss on one prediction, such as squared error

Y_i

training day i's rides, a random draw

X_i

training day i's input (date), a random draw

1. On every dataset, ERM beats the best member on the training rows, because that is how it was chosen. Take expectations and use step 2 for the fixed f*_F.

1. On every dataset, the best member beats ERM on true risk, because that is how it was chosen. Chain the two inequalities: the expected gap is never negative. Step 2 does not apply to \hat{f} itself, because \hat{f} was picked using the same rows it is scored on. That reuse is the whole source of optimism.

1. The noise floor for squared loss. Add and subtract m(x) = \mathbb{E}[Y \mid X = x] (A). The cross term vanishes by the tower rule, since \mathbb{E}[Y - m(X) \mid X] = 0 (E). So the best possible predictor is the conditional mean, and its risk is the average conditional variance, \sigma^2 for our ride counts.

Y

the rides on a random new day

X

that day's input (its date)

g

any predictor we might use

m(X)

the conditional mean: the average rides on days like X

\mathbb E[Y - m(X) \mid X]

the average leftover once the day is known: always 0

\text{Var}(Y \mid X)

how much rides scatter on a given day

\sigma^2

the noise variance: 0.09 for the daily rides (in thousands, squared)

1. Family, Sample, Search: add and subtract R(f^*_F) and R(\hat{f}), and the terms telescope. The Family term is \ge 0 because f^*_F is one candidate the Bayes predictor beats. The Sample term is \ge 0 because f^*_F minimizes risk over F. For squared loss, the Family term is \mathbb{E}[(f^*_F - m)^2]: the \text{bias}^2 of the best member of the family.

1. The Search term needs care. It is usually \ge 0 (the optimizer fell short of the training minimum). But \tilde{f} minimizes nothing about risk, so stopping short of the ERM can land on a function with lower risk than \hat{f}. That is early stopping, and Card 13 shows the mechanism. (The three-way split is Bottou and Bousquet's, 2008.)

1. One test set is itself an estimate. A test MSE averages n_{\text{test}} squared errors, so its standard error is their standard deviation over \sqrt{n_{\text{test}}}.

\text{SE}

standard error: how much the test score would wobble across test sets

\text{sd}

the standard deviation across test days

y_j

the rides on test day j

\hat f(x_j)

the fit's prediction for test day j

n_{\text{test}}

the number of test days

1. Check on the running example. On the six pilot days, the degree-5 curve has training MSE exactly 0. That is below the training MSE of the true curve itself, which is the mean of the six squared noises, (0.04 + 0.04 + 0.01 + 0.04 + 0.01 + 0.04)/6 = 0.03. On next year's six days the degree-5 curve scores 0.258 against the cubic's 0.0411, 6.27 times worse. And the cubic's 0.0411 has a standard error of 0.00779 on six days; this season's cubic scores 0.114 ± 0.00160 on 10,000 simulated days.

\hat R_6

the training MSE on the six pilot days

\hat f_5

the degree-5 polynomial fit

f

the true curve, \sin(2\pi x)

R_{\text{test}}

the MSE on next year's six days

\hat f_3

the cubic fit

Key move. Add and subtract (A) for the floor and the split; Expectation of a fixed function (E) for the optimism.

Common slip. Proving "\mathbb{E}[\hat{R}_n(\hat{f})] = R(\hat{f})" by step 2. Step 2 holds only for a function fixed before the data are seen. A second slip: calling the Search term "always positive". A third: forgetting that "generalization error" means the risk in some texts and the gap in others; say which one you mean.

How it's asked. "Your training R^2 is 0.97. Why can't I report it as expected production performance?" (Q2). A strong answer does steps 3–4 in two lines, names Family, Sample, Search, and adds that a held-out score is itself an estimate with a standard error (step 8).

Card 2 · The bias–variance decomposition ★

Statement. At a new point x_0 with Y_0 = f(x_0) + \varepsilon_0, the expected squared error of a fit, averaged over training sets and the new noise, splits into three parts. Hook: Noise you can't beat, Bias you chose, Variance you paid for.

\mathbb E_{D,\,\varepsilon_0}

the average over random training sets D and the new day's noise

Y_0

the rides on the new day: true value plus fresh noise

\hat f(x_0)

the fit's prediction at x_0; random, because the training set is random

x_0

the new day where we predict, such as July 20

\mathbb E_D

the average over training sets D

\mathbb E_D\hat f(x_0)

the prediction at x_0, averaged over many training sets

f(x_0)

the true average rides at x_0: 0.866 on July 20

Derivation.

1. Set up what is random. The training set D is random, so \hat{f}(x_0) is a random variable. The new day's noise \varepsilon_0 has mean 0 and variance \sigma^2, and it is independent of D, since it belongs to a day the model never saw.

\varepsilon_0

the new day's noise: mean 0, variance \sigma^2

\text{Var}

variance: the average squared distance from the mean

\varepsilon_0 \perp D

the new day's noise is independent of the training set

D

the training set: random, so the fit is random

1. Add and subtract f(x_0) and \mathbb{E}_D \hat f(x_0) (A). Call the three pieces a, b and c.

a

the new day's noise

b

minus the bias: a fixed number, not random

c

the fit's random wobble around its own average

1. Square and take expectations.

1. Kill the three cross terms (E). \mathbb{E}[a] = 0 because the noise has mean zero. \mathbb{E}[c] = 0 because c is a deviation from its own mean. \mathbb{E}[ac] = \mathbb{E}[a]\cdot \mathbb{E}[c] = 0 because a depends only on the new day and c only on D, and the two are independent.

1. What is left is the statement: \mathbb{E}[a^2] = \sigma^2, b^2 = \text{bias}^2, \mathbb{E}[c^2] = \text{variance}. Averaging over x_0 drawn from the test distribution gives the same split for the expected test MSE.

\text{bias}^2(x_0)

the squared gap between the average fit and the truth at x_0

\mathbb E_{x_0}

the average over new days x_0 drawn from the test distribution

1. By hand on the toy, the line at July 20 (m_0 = 4), with fixed training days. Least squares is linear in y, so \mathbb{E}_D \hat f is the line fitted to the true values f. On centered months, S_{\text{mf}} = \sum(m_i - 6)f(m_i) = -12 and S_{\text{mm}} = 70.

\mathbb E_D\hat f(4)

the line's average prediction at month 4 (July 20)

\bar f

the average of the true values over the six training days (bar = mean): 0

S_{mf}

\sum (m_i - 6) f(m_i): how the true values move with the centered month

S_{mm}

\sum (m_i - 6)^2: the spread of the training months, 70

1. The line's variance at m_0 comes from Chapter 1: \bar{y} and the slope are uncorrelated, \operatorname{Var} (\bar{y}) = \sigma^2/n and \operatorname{Var}(\text{slope}) = \sigma^2/S_{\text{mm}}.

\hat f(4)

the line's prediction at month 4

m_0

the prediction month, 4 (July 20)

\bar m

the average training month, 6

1. Add the noise. The same computation for the other three toy curves gives the full table. The cubic and degree 5 predict almost the same number at July 20 (0.791 and 0.801), but their expected errors differ, because degree 5 pays more variance.

1. Check by simulation over 500 seasons of 30 days, averaged over 10,000 test days. Degree 1 is almost all bias, degree 15 almost all variance. Its simulated \text{bias}^2 of 0.000976 is mostly Monte Carlo leakage of variance; the exact value is \approx 0. The three parts add up to the simulated test MSE within 0.00015 for degrees 1–15, and within 0.0062 at degree 0, where the finite test set's noise correlates with the large bias.

1. Bias and variance depend on where you look. For degree 15, the simulated variance at the June peak (x_0 = 0.25) is 0.0368 (exact 0.0372), but at the end of the year (x_0 = 0.99) it is 1.61 (exact 1.71). The edges are where flexible polynomials wobble. The line shows the mirror image: its \text{bias}^2 is 0.272 at the peak but 0.767 at the edge (exact values).

Key move. Add and subtract (A), then Expectation with independence (E) to kill the cross terms.

Common slip. Killing \mathbb{E}[ac] "because the noise has mean zero" without saying why the product factorizes. It factorizes only because the new noise is independent of the training data. On the training points it is not, and that is exactly the optimism of Card 3. A second slip: computing bias and variance of one fitted curve. The decomposition describes a procedure (family, n, \lambda) over repeated training sets, never a single curve.

How it's asked. "Derive expected test error at a point as noise plus \text{bias}^2 plus variance. Where exactly do the cross terms go?" (Q13). Or the toy on the board: "compute the line's \text{bias}^2 and variance at July 20" (Q14). A strong answer adds that for 0-1 loss there is no additive decomposition, and that variance can even help when the average prediction is on the wrong side of the boundary (Friedman, 1997; Domingos, 2000; Q38).

Card 3 · Training optimism for least squares ★★

Statement. For a correctly specified linear model with p coefficients and fixed X, training error is optimistic by \sigma^2p/n and new-noise error on the same x's is pessimistic by the same amount. For new Gaussian x's the penalty is much larger.

\frac pn

coefficients per training row: p fitted coefficients over n rows

X

the design matrix: the n training rows of features

\frac{p}{n - p - 1}

the random-design penalty: it blows up as p nears n

\frac{p}{n - p - 2}

the same penalty when one more row is spent on the intercept

Derivation.

1. Fixed X, y = X\beta + \varepsilon, \hat{y} = Hy with H the rank-p projection. Because X\beta is in the column space, HX\beta = X\beta, so the residual is pure projected noise. The trace trick gives Chapter 1's \mathbb{E}[\text{RSS}] = (n - p)\sigma^2 (Ch 1, Card 7) (T).

\mathbf y

the vector of observed responses

\hat{\mathbf y}

the fitted values, H\mathbf y

I

the identity matrix

H

the hat matrix: projects \mathbf y onto the columns of X (rank p)

\boldsymbol\varepsilon

the noise vector, one entry per row

\text{RSS}

residual sum of squares

\text{tr}

the trace: the sum of the diagonal entries

n - p

residual degrees of freedom: rows minus coefficients

1. In-sample test error: new noise \varepsilon^* at the same x's. The error is \varepsilon^* - H\varepsilon. The cross term vanishes because \varepsilon^* independent of ε, and H^\top H = H.

\mathbf y^*

fresh responses at the same inputs (new noise)

\boldsymbol\varepsilon^*

the fresh noise, independent of \boldsymbol\varepsilon

\lVert\mathbf y^* - \hat{\mathbf y}\rVert^2

the total squared error on the fresh responses (squared length)

H^\top H

H transposed times H; equal to H for a projection

n + p

rows plus coefficients

1. Divide by n. The gap between the two is 2\sigma^2p/n. Card 4 generalizes this to any fitting procedure.

\frac{2\sigma^2 p}{n}

the optimism: how much training error understates fixed-design test error

1. Random X, no intercept. A new row x \sim N(0, \Sigma) is independent of the training data. The prediction error is the new noise minus x^\top(\hat{w} - \beta). Average over x first (E), then over \varepsilon given X (T).

y_0

the response at a new random row

\mathbf x

a new random feature row, drawn as N(\mathbf 0, \Sigma)

\hat{\mathbf w}

the least-squares weights

\boldsymbol\beta

the true coefficients

\Sigma

the covariance matrix of a feature row

(X^\top X)^{-1}

the inverse of the Gram matrix (the inverse undoes a matrix)

1. Reduce to \Sigma = I by writing X = Z\Sigma^{1/2}, with Z having i.i.d. N(0, 1) entries. The \Sigma factors cancel inside the trace, and the problem is now the mean of an inverse Wishart matrix.

\Sigma^{-1/2}

the inverse square root of \Sigma: it undoes the feature correlations

Z

a matrix of independent standard normals, with X = Z\Sigma^{1/2}

(Z^\top Z)^{-1}

the inverse of Z's Gram matrix: an inverse-Wishart matrix

1. That mean is a multiple of the identity. For any orthogonal Q, ZQ has the same distribution as Z, so M = \mathbb{E}[(Z^\top Z)^{-1}] satisfies M = Q^\top MQ for every rotation. Only multiples of the identity commute with every rotation.

M

the average inverse-Wishart matrix, \mathbb E[(Z^\top Z)^{-1}]

Q

any rotation (orthogonal matrix)

\forall Q

for every rotation Q

c

the unknown constant on the diagonal

I_p

the p \times p identity matrix

1. Find c from one diagonal entry. By the block-inverse formula, the (1, 1) entry of (Z^\top Z)^{-1} is one over the residual sum of squares from regressing column 1 on the other p - 1 columns. That residual is a standard Gaussian vector projected onto an (n - p + 1)-dimensional space, so its squared norm is \chi^2 with n - p + 1 degrees of freedom.

\big[(Z^\top Z)^{-1}\big]_{11}

the top-left entry of the inverse

\mathbf z_1

column 1 of Z

H_{-1}

the projection onto the other p - 1 columns

\sim

is distributed as

\chi^2_{n - p + 1}

chi-squared with n - p + 1 degrees of freedom: a sum of that many squared standard normals

1. The mean of one over a \chi^2_k variable is 1/(k - 2): integrate against the \chi^2 density and use \Gamma(a + 1) = a\Gamma(a).

\chi^2_k

a chi-squared variable with k degrees of freedom

k

the degrees of freedom

\int_0^\infty

integrate over all positive values

x

the integration variable: a possible value of \chi^2_k

e

Euler's number, 2.718…

\Gamma

the gamma function: a smooth factorial, \Gamma(a + 1) = a\Gamma(a)

dx

integrate with respect to x

1. So c = 1/(n - p - 1), the trace is p/(n - p - 1), and the random-X risk follows. It explodes as p approaches n, which Card 16 picks up.

n - p - 1

the inverse-Wishart divisor: rows minus coefficients minus 1

1. With an intercept and p slopes, center the columns: \hat{y}(x) = \bar{y} + (x - \bar{x})^\top \hat{w}. The error splits into the noise mean \bar\varepsilon and the slope error. They are uncorrelated given X, because the centered columns are orthogonal to the ones vector. For Gaussian rows, \bar x \sim N(\mu, \Sigma/n) is independent of the centered matrix X_{c}, whose Gram matrix is Wishart with n - 1 degrees of freedom.

\hat y(\mathbf x)

the fitted model's prediction at new row \mathbf x, intercept included

\mathbb E[y \mid \mathbf x]

the true mean response at \mathbf x

\bar\varepsilon

the average training noise, which leaks into the intercept \bar y

\bar{\mathbf x}

the average training row (bar = mean)

N

a Gaussian (normal) distribution

\mathbf 0

the zero vector

1. Apply step 9 with n − 1 in place of n, scaled by (1 + 1/n), and collect.

\frac{p}{(n - 1) - p - 1}

step 9's penalty with n - 1 effective rows (one is spent on centering)

1. Check on the running example. Season, degree 9 (p = 10, n = 30, \sigma^2 = 0.09): theory 0.0600 for training error against 0.0612 simulated; fixed-X test theory 0.120 against 0.124 on random test days. The 100 stations (\sigma^2 = 4, n = 100, p = 80 slopes plus an intercept): random-X theory 22.0, checked at 21.96 ± 0.03 over 3,000 designs. That is three times the fixed-X value of 7.24, and worse than predicting the mean (14.5). Drill 2 (n = 100, p = 80, \sigma^2 = 1, no intercept) gives 0.2, 1.8 and 5.21; simulation gives 0.202, 1.80 and 5.19.

Key move. Trace trick (T), then rotational invariance plus one \chi^2 moment for the inverse Wishart.

Common slip. Quoting \sigma^2(1 + p/n) for new x's. That is the fixed-X result; with p/n = 0.8 it understates the stations' test error threefold. A second slip: forgetting the intercept, which moves 20.8 to 22.0.

How it's asked. "A degree-9 fit on 30 days reports training MSE 0.061 with \sigma = 0.3. What test MSE do you expect?" (Q15). Or "OLS on 100 stations × 80 descriptors has negative test R^2. Why?" (Q30). A strong answer says which X — fixed or random — before writing anything, and notes the random-X formula's pole at p = n - 1.

Card 4 · Degrees of freedom as covariance; Cp and AIC ★★

Statement. Degrees of freedom measure how hard a fit chases its own noise. For any fitting procedure, the training error's optimism is exactly 2\sigma^2\cdot \text{df}/n. For a linear smoother \hat{y} = Sy, \text{df} = \operatorname{tr} (S). Hook: Count it, Correlate it, Shatter it — this card is "Correlate it".

\text{df}

degrees of freedom: how hard the fit chases its own noise

\text{Cov}(\hat y_i, y_i)

how much day i's fitted value moves with its own observed rides

\hat y_i

the fitted value for training day i

y_i

the observed rides on training day i

\text{test}_{\text{in}}

in-sample test error: fresh noise at the same training days

S

the smoother matrix: maps observed rides to fitted values

\text{tr}(S)

the trace of S: the sum of its diagonal entries

Derivation.

1. Fixed x's, y_i = f_i + \varepsilon_i, and a new response y^*_i = f_i + \varepsilon^*_i at the same x_i, independent of the training data. Write both errors around the truth f_i (A).

y_i^*

a fresh response at day i: same truth, new noise

\varepsilon_i^*

the fresh noise at day i

f_i

the true mean rides at day i

\varepsilon_i

the training noise at day i

1. Square, take expectations and subtract. The (\hat{y}_i - f_i)^2 terms cancel, and \mathbb{E}[\varepsilon^{*2}] = \mathbb{E}[\varepsilon^2] = \sigma^2. The new-noise cross term is zero by independence (E). The training cross term is not, because \hat{y}_i was fitted to y_i.

\text{Cov}(y_i, \hat y_i)

how much day i's fitted value moves with its own observed rides

1. Average over i, and define df so that the optimism looks like least squares' 2\sigma^2p/n (Card 3). Nothing here assumed linearity: this holds for kNN, trees, anything.

\sum_i

add up over training days i

1. For a linear smoother with S fixed (it may depend on the x's, not on y), \operatorname{Cov} (\hat{y}, y) = S\cdot \operatorname{Cov} (y, y) = \sigma^2S. Sum the diagonal: \text{df} = \operatorname{tr} (S).

\text{Cov}(\hat{\mathbf y}, \mathbf y)

the covariance matrix between the fitted and observed vectors

S_{ii}

diagonal entry i of S: day i's leverage on its own fit

1. Three smoothers. OLS has S = H, a rank-p projection, so \text{df} = p. Ridge's df is \sum d^2/(d^2 + \lambda) (Card 6). kNN has S_{ii} = 1/k, because each training day is one of its own k neighbors, so \text{df} = n/k.

\text{tr}(H) = p

the trace of the hat matrix: p, one per fitted coefficient

\sum_j

add up over SVD directions j

d_j

the j-th singular value of X: the strength of direction j (Card 6)

\lambda

the ridge penalty strength

\frac{d_j^2}{d_j^2 + \lambda}

ridge's filter: the fraction of direction j it keeps (Card 6)

\text{df}_{k\text{NN}}

the degrees of freedom of k-nearest neighbors

k

the number of neighbors averaged

1. Non-linear fits: Stein's lemma. For Gaussian noise, integration by parts turns the covariance into an expected derivative. The key fact is that the Gaussian density's derivative is -(y - \mu)/\sigma^2 times the density itself.

\frac{d}{dy}

how fast what follows changes as you nudge y: a slope, not a fraction to divide

\phi_\sigma

the Gaussian density with standard deviation \sigma

y

one response value, the variable we integrate over

\mu

the response's true mean

1. Substitute, integrate by parts (the boundary term vanishes because \phi decays faster than g grows), and apply it to each y_i with the other responses held fixed. So \text{df} = \mathbb{E}[\sum \partial \hat{y}_i/\partial y_i], the expected divergence of the fit.

Y

a Gaussian response with mean \mu and variance \sigma^2

g

the fit's output as a function of that response

\int

integrate over all values of y

dy

integrate with respect to y

g'

the derivative of g: how fast the fit moves with the response

\frac{\partial\hat y_i}{\partial y_i}

how fast fitted value i moves as you nudge its own response, holding the rest fixed

1. The lasso as an application. On a region where the active set A and its signs do not change, the lasso fit is an OLS projection onto the active columns plus a constant shift. Its divergence is \lvert A\rvert, so \text{df} = \mathbb{E}[\text{number of non-zeros}] (Zou, Hastie and Tibshirani, 2007).

H_A

the projection onto the active columns

\lambda

the lasso penalty strength

X_A

the columns of X for the active features

(X_A^\top X_A)^{-1}

the inverse of the active columns' Gram matrix

\mathbf s_A

the signs of the active weights, each \pm 1

|A|

the number of non-zero weights

A

the active set: the features with a non-zero lasso weight

1. Put the rent back: unbiased estimates of in-sample test error. Mallows' Cp adds the optimism with a known \sigma^2. Gaussian AIC replaces \sigma^2 by the model's own \hat{\sigma}^2 = \text{RSS}/n inside a log. AICc adds a small-sample correction. BIC charges \ln n per df instead of 2.

C_p

Mallows' C_p: training MSE plus the optimism rent, with \sigma^2 known

\text{AIC}

Akaike's criterion: log training error plus 2 per degree of freedom

\text{AICc}

AIC with a small-sample correction

\text{BIC}

the Bayesian criterion: charges \ln n per degree of freedom instead of 2

1. Check on the season. Monte Carlo covariance df: degree 3 gives 3.98 (theory 4), degree 9 gives 9.99 (theory 10), and kNN with k = 5 gives 6.02 (theory 6), whose optimism is 0.0359 against 2 \times 0.09 \times 6/30 = 0.036. On this season, Cp picks degree 3 (0.0923 + 0.024 = 0.116). Gaussian AIC picks degree 15. Its log term rewards the fall in training MSE from 0.0923 to 0.0309 with 30 \ln(0.0923/0.0309) = 32.8, and that beats the extra rent of 2 \times 12 = 24. BIC charges \ln 30 = 3.40 per df (40.8) and AICc adds 41.8 at \text{df} = 16; both pick degree 3.

Key move. Trace trick (T): \operatorname{Cov} (Sy, y) = \sigma^2S, summed down the diagonal.

Common slip. Saying kNN "has no parameters, so it can't overfit": 1-NN has \text{df} = n = 30. A second slip: trusting Gaussian AIC at small n. Its rent is measured against the overfit model's own \hat{\sigma}^2, which shrinks as the model chases noise (0.031 against the true 0.09), so each drop in RSS looks three times more valuable than it is.

How it's asked. "kNN has no parameters, so it can't overfit. Rebut that with a number" (Q16). Or "the model card says ridge, 15 features, df 7.8; how do 15 features have 7.8 df?" (Q18). A strong answer gives the covariance definition, then \operatorname{tr} (S), then a Monte Carlo check: perturb y, refit, and regress \hat{y}_i on y_i.

Card 5 · kNN bias and variance ★

Statement. Predict at x_0 by averaging the k nearest training responses. On a fixed design, variance is \sigma^2/k exactly, and bias is the average of f over the neighbors minus f(x_0). For 2m + 1 symmetric neighbors at spacing h, the bias is second order, with sign set by the curvature.

\hat f_k(x_0)

the kNN prediction at x_0: the average rides of the k nearest training days

\sum_{i \in N_k(x_0)}

add up over the k training days nearest to x_0

f(x_i)

the true curve at neighbor day x_i

x_i

training day i's date

f''(x_0)

the curvature of the true curve at x_0 (its second derivative)

h

the spacing between neighboring training days, 1/30 on the season

m

the number of neighbors on each side, so k = 2m + 1

Derivation.

1. With fixed design points, the neighbor set N_{k}(x_0) is fixed; only the y's are random. The fit is an average of k independent responses.

\sum_{i \in N_k}

add up over the k neighbor days

1. Variance: k independent noises, each with variance \sigma^2, divided by k^2 (E).

1. Bias: the noise averages to zero, so the mean of the fit is the average of f over the neighbors.

1. Take a design point x_0 with symmetric neighbors x_0 + jh,\ j = -m, \ldots, m\ (k = 2m + 1). Taylor-expand f to second order around x_0.

f(x_0 + jh)

the true curve at the neighbor j steps from x_0

j

which neighbor, from -m to m

f'(x_0)

the slope of the true curve at x_0 (its first derivative)

O(h^3)

terms that shrink at least as fast as h^3: negligible for small spacing

1. Average over j. The linear term cancels by symmetry. The mean of j^2 over -m, \ldots, m is m(m + 1)/3, using \textstyle\sum j^2 \text{ from } 1 \text{ to } m = m(m + 1)(2m + 1)/6.

\sum_{j=-m}^{m}

add up over neighbors j = -m to m

1. Expected squared error at x_0 = \sigma^2 + \text{bias}^2 + \sigma^2/k (Card 2). Bias grows like k^2, variance falls like 1/k, so there is a best k. \text{df} = n/k (Card 4, step 5).

1. Check on the season at the June peak (x_0 = 0.25, a design point; h = 1/30; \sigma^2 = 0.09). The curvature is f'' = -(2\pi)^2 \sin(\pi/2) = -39.5, so the bias coefficient is -39.5/(900 \times 6) = -0.00731 per m(m + 1). Exact \text{bias}^2 + \sigma^2/k: k = 1: 0.0900; k = 3: 0.0302; k = 5: 0.0199; k = 7: 0.0202; k = 9: 0.0296. So k = 5 is best (Drill 1; simulated 0.0198 at k = 5). At k = 5 (m = 2), the exact bias is −0.0433 against the quadratic approximation -0.00731 \times 6 = -0.0439. Over all test days of the season, k = 5 is also best, with test MSE 0.124.

\sum_{j=-2}^{2}

add up over the 5 neighbors, two on each side of June's peak

\pi

pi, 3.14159…: \sin(2\pi x) completes one cycle per year

Key move. Expectation (E) for the variance; Taylor plus the symmetric sum for the bias.

Common slip. Forgetting that the bias at a peak is negative: averaging around a maximum always pulls the prediction down, with sign f''. A second slip: at the edge of the data (x_0 = 0.99) the neighbors are one-sided, the linear term no longer cancels, and the bias becomes first order in h. That is why kNN is worst at the boundary.

How it's asked. "How do bias and variance change with k in kNN, and how would you choose k?" A strong answer writes \sigma^2/k and the curvature bias, gives \text{df} = n/k (Q16), and says that in d dimensions the neighbor radius grows like (k/n)^{1/d}, the curse of dimensionality (Ch 8 owns it).

Card 6 · Ridge in the SVD basis; effective df ★★

Statement. Rotate into the SVD basis and ridge multiplies the least-squares coordinate along each direction by d_j^2/(d_j^2 + \lambda). Hook: shrink the weak directions most. The effective df is the sum of those factors.

U

the left singular vectors: orthonormal patterns across the days, as columns

D

the diagonal matrix of singular values d_j

V^\top

V transposed; the columns of V are orthonormal directions in weight space

\hat{\mathbf w}_\lambda

the ridge weights at penalty \lambda

\lambda

the ridge penalty strength

\mathbf u_j

column j of U: one pattern across the days

\text{df}(\lambda)

ridge's effective degrees of freedom

(X^\top X + \lambda I)^{-1}

the inverse of the penalized Gram matrix

Derivation.

1. Ridge minimizes \lVert y - Xw\rVert^2 + \lambda \lVert w\rVert^2. Set the gradient to zero (Ch 1, Section 10). X^\top X + \lambda I is invertible for any \lambda > 0, even when p > n.

\mathbf w

the weight vector we optimize over

-2X^\top(\mathbf y - X\mathbf w) + 2\lambda\mathbf w

the gradient of the ridge loss: the vector of slopes, one per weight

1. Substitute the full SVD, X = UDV^\top with V square and orthogonal; directions beyond the rank get d_j = 0. Then X^\top X = VD^2V^\top and \lambda I = V\lambda IV^\top, so the inverse is easy (S).

X^\top X

the Gram matrix of the features

V

the right singular vectors: orthonormal directions in weight space (V^\top V = I)

(D^2 + \lambda I)^{-1}

a diagonal matrix with entries 1/(d_j^2 + \lambda)

1. Multiply out. In the rotated coordinates V^\top w, ridge is a diagonal operation.

\mathbf v_j

column j of V: direction j in weight space

1. Compare with least squares, whose coordinate along v_j is z_j = u_j^\top y/d_j. Ridge's coordinate is the same number times the filter d_j^2/(d_j^2 + \lambda).

z_j

the least-squares coefficient along direction j

1. The fitted values follow by multiplying by X. Each u_j-component of y is kept with weight d_j^2/(d_j^2 + \lambda). Least squares keeps weight 1; the null model keeps weight 0.

1. Why the weak directions are the right ones to shrink. The least-squares coordinate z_j has noise variance \sigma^2/d_j^2, so a small d_j means a noisy coordinate. Ridge shrinks exactly those.

1. Effective df: the smoother is S_{\lambda} = U \operatorname{diag} (d_j^2/(d_j^2 + \lambda)) U^\top, so its trace is the sum of the filters (Card 4). It slides smoothly from \operatorname{rank} (X) at \lambda = 0 to 0 as \lambda \to \infty. With an unpenalized intercept, add 1.

S_\lambda

ridge's smoother matrix at penalty \lambda

\text{rank}(X)

the number of independent columns of X

1. Two identities interviewers like. First, ridge is least squares on augmented data: append \sqrt{\lambda}\cdot I below X and zeros below y. Second, the push-through identity gives the dual form, which needs only an n \times n inverse (a preview of kernels, Ch 11).

\lVert\mathbf y - X\mathbf w\rVert^2

the squared length of the residual: the sum of squared errors

\lVert\mathbf w\rVert^2

the squared length of the weights: ridge's penalty

\sqrt\lambda I

\sqrt\lambda times the identity: the fake rows appended below X

(XX^\top + \lambda I)^{-1}

the n \times n inverse of the dual form

1. Check on the toy line (centered months, intercept unpenalized). The slope direction has d^2 = S_{\text{mm}} = 70. At \lambda = 70 the shrink factor is 0.5, the slope halves from −0.194 to −0.0971, and \text{df} = 1 + 0.5 = 1.5. On the season's standardized degree-15 design at the CV-chosen \lambda = 5.62, the strongest direction (d^2 = 47.6) keeps 0.894 of its least-squares value. The two weakest (d^2 = 1.47 and 0.591) keep 0.207 and 0.0952. The df is 1 + \textstyle\sum \text{filters} = 12.44; a Monte Carlo covariance check gives 12.45.

\sum_{j=1}^{15}

add up over the 15 directions of the degree-15 design

Key move. SVD (S): one matrix inverse becomes 15 scalar divisions.

Common slip. Saying ridge "shrinks all coefficients by the same factor". That is true only for an orthonormal design (factor 1/(1 + \lambda)). In general the factor differs by direction, and a raw coefficient can even grow as \lambda rises when directions mix. A second slip: comparing \lambda across designs. The filter depends on \lambda relative to d^2, so standardization, n and the basis all change what a given \lambda means.

How it's asked. "Derive ridge, then show what it does to each principal direction. Which directions does it shrink most, and why are those the right ones?" (Q17). A strong answer adds step 6 (variance \propto 1/d^2), the df formula (Q18), and that PCR is the hard-threshold version: filter 1 or 0.

Card 7 · Ridge bias, variance and the Hoerl–Kennard theorem ★★★

Statement. Ridge is biased toward zero, with smaller variance than least squares. Along each SVD direction, the coefficient MSE is a \text{bias}^2 that grows with \lambda plus a variance that shrinks with \lambda. The total MSE has a negative slope at \lambda = 0, so some \lambda > 0 always beats least squares (Hoerl and Kennard, 1970).

\text{MSE}(\lambda)

ridge's expected squared coefficient error at penalty \lambda

\lVert\hat{\mathbf w}_\lambda - \boldsymbol\beta\rVert^2

the squared distance from the ridge weights to the truth

\theta_j

the true coefficient along direction j: \boldsymbol\theta = V^\top\boldsymbol\beta

\frac{d\,\text{MSE}}{d\lambda}

how fast the MSE changes as you nudge \lambda

\Big|_{\lambda = 0}

evaluated at \lambda = 0, which is plain least squares

Derivation.

1. Substitute the truth y = X\beta + \varepsilon into the ridge formula. Write A = X^\top X for short.

A

shorthand for the Gram matrix X^\top X

(A + \lambda I)^{-1}

the inverse of the penalized Gram matrix

1. Mean and bias. Use (A + \lambda I)^{-1}A = I - \lambda(A + \lambda I)^{-1}, which follows from adding and subtracting \lambda I inside A (A).

1. Variance: a linear map M = (A + \lambda I)^{-1}X^\top of noise with covariance \sigma^2I has covariance \sigma^2MM^\top (E).

1. Rotate (S): with A = VD^2V^\top and \theta = V^\top \beta, both matrices become diagonal. Direction j has bias -\lambda \theta_j/(d_j^2 + \lambda) and variance \sigma^2d_j^2/(d_j^2 + \lambda)^2. The MSE is the sum over directions, because the trace of a matrix is invariant under rotation.

\text{MSE}_j(\lambda)

direction j's share of the coefficient MSE

1. Differentiate one direction with the quotient rule. The numerator simplifies to 2d_j^2(\lambda \theta_j^2 - \sigma^2).

\frac{d\,\text{MSE}_j}{d\lambda}

how fast direction j's MSE changes as you nudge \lambda

1. At \lambda = 0 every direction's derivative is -2\sigma^2/d_j^4 < 0, whatever \beta is. The sum is negative, so MSE falls as \lambda leaves 0. Some \lambda > 0 has strictly lower MSE than least squares. The \text{bias}^2 enters only at second order (it starts as \lambda^2), while the variance falls at first order.

1. The one-direction optimum: step 5 is zero at \lambda_j^* = \sigma^2/\theta_j^2, negative below it and positive above it. Noise over signal, and independent of d_j. One shared \lambda cannot hit every \lambda_j^*, which is why Card 8 needs a prior to make one \lambda optimal.

\lambda_j^*

the best penalty for direction j alone (star = optimum)

1. Check on the toy slope (d^2 = 70, best-line slope \theta = -12/70 = -0.171, \sigma^2 = 0.09). \lambda^* = 0.09/0.171^2 = 3.0625. The slope's MSE falls only from 0.001286 to 0.001232, a gain of 4.2%: a strong signal needs little shrinkage (Drill 4). The derivative at 0 is -2 \times 0.09/70^2 = -3.67 \times 10^{-5}, matching a numerical difference. Drill 3 (\theta = 1, \sigma^2 = 0.25, d = 1): \lambda^* = 0.25, MSE 0.04 + 0.16 = 0.20 against 0.25. On the season's degree-15 fit the same trade appears in prediction error. Least squares is almost all variance: 0.288, with an exact \text{bias}^2 of about 0 (the simulated 0.000976 is mostly Monte Carlo leakage of variance), so its test MSE is 0.379. Ridge at \lambda = 5.62 buys \text{bias}^2 0.0122 and cuts the variance to 0.0353, for a test MSE of 0.137.

\lambda^*

the best penalty for the toy slope

\Big|_0

evaluated at \lambda = 0

Key move. SVD (S) to make every matrix diagonal, then the add-and-subtract identity (A + \lambda I)^{-1}A = I - \lambda(A + \lambda I)^{-1}.

Common slip. Concluding that ridge beats least squares by a lot in every problem. The theorem guarantees only some \lambda > 0 with some gain, and the best \lambda depends on the unknown \theta. On the toy the gain is 4%. A second slip: forgetting that the theorem is about coefficient MSE. For prediction MSE the weights change from 1 to d_j^2, but the sign argument at \lambda = 0 still holds.

How it's asked. "OLS is BLUE. Prove that a biased estimator can still beat it" (Ch 1, Q50, deepened here). Or "what happens at \lambda = 0 and at the maximum of the regularization slider?" (Q8). A strong answer derives step 6 in three lines, then says that \text{bias}^2 starts at second order, which is why a little shrinkage is almost free.

Card 8 · Ridge = posterior mean; Bayes-optimal λ = σ²/τ² ★★

Statement. With a Gaussian prior on the weights and Gaussian noise, the posterior is Gaussian. Its mean is ridge with \lambda = noise over prior, \sigma^2/\tau^2. Because the posterior mean minimizes expected squared error among all estimators, no \lambda (and no other estimator) does better on average over the prior.

\mathbf w

the weights, now random: drawn from the prior

\tau^2

the prior variance: how big a typical true effect is (0.05 for the stations)

\mathbf y \mid \mathbf w

the responses given the weights: the likelihood

\mathbf w \mid \mathbf y

the weights given the data: the posterior

\big(X^\top X + \tfrac{\sigma^2}{\tau^2}I\big)^{-1}

ridge's inverse with \lambda = \sigma^2/\tau^2

Derivation.

1. Write the log posterior: log likelihood plus log prior, up to constants.

p(\mathbf w \mid \mathbf y)

the posterior density of the weights

1. Expand and collect the terms in w. The quadratic term has precision matrix P = X^\top X/\sigma^2 + I/\tau^2.

P

the posterior precision matrix: the inverse of its covariance

1. Complete the square. A Gaussian with mean \mu and precision P has log density -\tfrac12(w - \mu)^\top P(w - \mu) = -\tfrac12 w^\top P w + w^\top P\mu + \text{const}. Match the linear terms.

\boldsymbol\mu

the posterior mean of the weights

\text{Cov}(\mathbf w \mid \mathbf y)

the posterior covariance

P^{-1}

the inverse of the precision: the posterior covariance

1. For a Gaussian posterior, mean = mode, so this is also the MAP estimate, and the MAP objective (multiply step 1 by -2\sigma^2) is the ridge objective with \lambda = \sigma^2/\tau^2.

1. The posterior mean is optimal among all estimators. For any estimator \delta(y) and any PSD weight matrix M (M = \Sigma gives test-error risk on new stations), add and subtract \mu = \mathbb{E}[w \mid y] (A). The cross term vanishes because \mathbb{E}[w - \mu \mid y] = 0 (E). So the conditional risk is smallest at \delta = \mu, for every y, and therefore on average.

\boldsymbol\delta

any estimator of the weights built from \mathbf y

M

any positive semi-definite weighting matrix, such as \Sigma for test error

1. The same result by the recipe Rotate, filter, split, sum (S). The prior is rotation-invariant, so \theta = V^\top w \sim N(0, \tau^2I) too. Along direction j the least-squares coordinate is z_j = \theta_j + \text{noise} with variance \sigma^2/d_j^2. Shrink it by a factor c and split the error.

c

the shrink factor applied to z_j

z_j

the least-squares coordinate along direction j: \theta_j plus noise of variance \sigma^2/d_j^2

\theta_j

the true coefficient along direction j, random under the prior

1. Minimize over c. The optimal filter is exactly ridge's d_j^2/(d_j^2 + \lambda) with \lambda = \sigma^2/\tau^2, in every direction at once, and the minimized risk is the posterior variance along that direction.

c_j^*

the best shrink factor for direction j

\min_c

the smallest error over all shrink factors

1. Check on the dense stations: 80 standardized descriptors, every \beta_j \sim N(0, 0.05), \sigma^2 = 4, n = 100, no intercept. \lambda^* = 4/0.05 = 80, and the exact average risk curve is minimized at \lambda = 80. The risk there is 5.21 (simulated over 500 draws: 5.20). Least squares scores 20.7 (theory 20.8, Card 3), and predicting zero scores 4 + 80 \times 0.05 = 8.0. A \lambda ten times too large gives 6.24 and ten times too small gives 6.30, so the curve is flat near its minimum. Ridge with CV-chosen \lambda scores 5.32 and lasso with CV 5.62: when every effect is small, the Gaussian prior is the right one.

\lambda^*

the Bayes-optimal penalty: noise variance over prior variance

R

the average test risk on new stations at the penalty in brackets

R_{\text{OLS}}

least squares' average test risk

Key move. Complete the square for the posterior; add and subtract the posterior mean (A) for optimality; Expectation over the prior (E).

Common slip. Writing \lambda = \tau^2/\sigma^2 (upside down). Read it as "how loud the noise is relative to how big effects are": more noise → more shrinkage. A second slip: saying the Laplace prior's posterior mean is the lasso. The lasso is the posterior mode; the mean of the Bayesian lasso is never exactly zero (Card 9).

How it's asked. "Every descriptor has a small effect, N(0, 0.05); noise variance 4. What \lambda minimizes expected test error, averaged over plausible \beta? Prove it" (WP1). A strong answer derives steps 1–3, proves optimality in one line (step 5), and adds that \tau^2 unknown → empirical Bayes or CV. The CV-chosen \lambda has median 80 on these draws.

Card 9 · Lasso: Laplace MAP, KKT, soft-thresholding, λ_max ★★

Statement. The lasso is the MAP estimate under a Laplace prior. Its optimality (KKT) conditions say a weight is exactly zero unless its feature's correlation with the residual reaches \lambda/2. All weights are zero once \lambda \ge \lambda_{\max} = 2\max_j\lvert x_j^\top y\rvert. With an orthonormal design the solution soft-thresholds. Hook: L1 kills, L2 shrinks.

\hat w_j

the fitted lasso weight on station descriptor j

\mathbf x_j

column j of X: one descriptor's values across the stations

\hat{\mathbf w}

the fitted lasso weight vector

\mathbf y - X\hat{\mathbf w}

the residual: what the fit leaves unexplained

\lambda

the lasso penalty strength

\text{sign}

the sign: +1 for a positive number, -1 for a negative one

X^\top X = I

an orthonormal design: unit-length, uncorrelated columns

z_j

the least-squares weight on feature j (orthonormal design)

\Big(|z_j| - \frac\lambda2\Big)_+

shrink |z_j| by \lambda/2, stopping at zero (the + keeps only the positive part)

Derivation.

1. Laplace prior p(w_j) \propto \exp(-\lvert w_j\rvert/b). Write -2\sigma^2 times the log posterior, as in Card 8, step 4: the lasso objective appears with \lambda = 2\sigma^2/b.

b

the Laplace prior's scale: the typical size of a true weight

\lVert\mathbf w\rVert_1

the L1 norm: the sum of the absolute weights

\mathbf w

the weight vector, with a Laplace prior

1. |w| has a kink at zero, so use its subdifferential: the set of slopes of lines that touch |w| from below. It is {sign(w)} away from zero and the whole interval [−1, 1] at zero.

\partial|w|

the subdifferential of |w|: every slope of a line touching it from below

w

one weight

1. The objective is convex, so \hat{w} is optimal exactly when 0 lies in its subdifferential, coordinate by coordinate. Let r = y - X\hat{w} be the residual.

\mathbf r

the residual vector, \mathbf y - X\hat{\mathbf w}

\partial\lVert\hat{\mathbf w}\rVert_1

the subdifferential of the L1 norm at the fit

\Longleftrightarrow

if and only if

\partial|\hat w_j|

the subdifferential of |\hat w_j|: its sign if non-zero, anything in [-1, 1] at zero

j

which feature

1. Read off the two cases. An active weight has its residual correlation pinned at exactly \pm \lambda/2. An inactive weight is allowed any correlation up to \lambda/2 in size: a feature must "pay" \lambda/2 of correlation before it may enter.

1. \lambda_{\max}: \hat{w} = 0 is optimal when every inequality holds at r = y. The smallest \lambda for which that happens is \lambda_{\max}. As \lambda falls below it, features enter one at a time along a piecewise-linear path.

\forall j

for every feature j

\lambda_{\max}

the smallest penalty at which every lasso weight is zero

\max_j

the largest over all features j

1. Orthonormal design (S): with X^\top X = I and z = X^\top y (the least-squares answer), Pythagoras splits the loss. y - Xz is orthogonal to the column space, so the problem separates into one scalar problem per coordinate.

\mathbf z

the least-squares weights, X^\top\mathbf y for an orthonormal design

w_j

a candidate weight on feature j

1. Solve \min\,(z - w)^2 + \lambda\lvert w\rvert. For w > 0, setting the derivative -2(z - w) + \lambda to zero gives w = z - \lambda/2, valid when z > \lambda/2; symmetrically for w < 0. Otherwise 0 is optimal, since 0 \in -2z + \lambda[-1, 1] exactly when \lvert z\rvert \le \lambda/2. That is soft-thresholding.

\hat w

the lasso solution for one coordinate

z

that coordinate's least-squares value

\Big(|z| - \frac\lambda2\Big)_+

|z| - \lambda/2 if that is positive, else 0

1. Bias of the survivors: every non-zero weight is moved toward zero by the full \lambda/2, however large it is. The relaxed lasso refits the selected set without the penalty; the adaptive lasso reweights the penalty by 1/\lvert\text{initial estimate}\rvert.

\theta_j

the true weight on feature j

1. Check. Drill 10: z = (3, 0.8, -1.5), \lambda = 2, so subtract 1 and stop at zero: (2, 0, -0.5), confirmed by sklearn with \alpha = \lambda/(2n). \lambda_{\max} = 2 \times 3 = 6. Stations, replicate 0: \lambda_{\max} = 512 (sklearn's \alpha_{\max} = 512/200 = 2.56, and every coefficient is zero there). CV chooses \lambda = 53.7. Over 50 replicates, CV-lasso keeps 14.6 non-zeros on average, 6.24 of them noise features.

\text{soft}_{\lambda/2 = 1}

soft-thresholding at 1: move each value toward 0 by 1, stopping at 0

\alpha_{\text{sklearn}}

scikit-learn's alpha parameter for the same fit

Key move. Rotate to an orthonormal basis (S), then the subgradient condition, the same soft-threshold step as Ch 2's proximal operator.

Common slip. Using the threshold \lambda instead of \lambda/2 (that is the \tfrac12\lVert\cdot\rVert^2 convention), or passing this tab's \lambda straight to sklearn's Lasso(alpha), which needs \lambda/(2n). A second slip: claiming the Bayesian lasso is sparse. The posterior mode is sparse; the posterior mean never is.

How it's asked. "Derive the condition under which lasso sets a coefficient exactly to zero, and the \lambda above which every coefficient is zero" (Q19). A strong answer writes step 4, then step 5, then the orthonormal picture. It adds that among correlated features the KKT conditions can be met by many splits, which is where Card 10 starts.

Card 10 · Elastic net and the grouping effect ★★★

Statement. Adding \lambda_2\lVert w\rVert^2 to the lasso makes the objective strictly convex. Identical features then get identical weights, and highly correlated features get nearly identical weights (Zou and Hastie, 2005). The lasso alone can split a duplicated feature any way at all. Hook: lasso picks, ridge spreads, elastic net groups.

\min_{\mathbf w}

the smallest value over all weight vectors

\lambda_1

the L1 (lasso) penalty strength

\lambda_2

the L2 (ridge) penalty strength

\hat w_i

the fitted weight on feature i

\hat w_j

the fitted weight on feature j

\lVert\mathbf y\rVert_2

the length of the response vector

\rho_{ij}

the correlation between features i and j

Derivation.

1. Duplicated column, x_1 = x_2 = x. The fit depends only on the sum s = w_1 + w_2. For a fixed sum with both weights of the same sign, the L1 term is \lvert s\rvert whatever the split.

\mathbf x

the duplicated feature column

w_1

the weight on copy 1

w_2

the weight on copy 2

s

the total weight w_1 + w_2: all the fit depends on

1. Only the L2 term cares about the split. Add and subtract s/2 (A): w_1^2 + w_2^2 = s^2/2 + 2(w_1 - s/2)^2, minimized uniquely at w_1 = w_2. With \lambda_2 > 0 the split is forced to be equal; with \lambda_2 = 0 (lasso) every same-sign split ties.

1. Solve for the total s with \lVert x\rVert^2 = 100 and x^\top y = 100 (least squares on one copy gives 1). Ridge charges \lambda s^2/2; the lasso charges \lambda \lvert s\rvert; the elastic net charges both.

s_{\text{ridge}}

the total weight under ridge

s_{\text{lasso}}

the total weight under the lasso

s_{\text{EN}}

the total weight under the elastic net

\lVert\mathbf x\rVert^2

the column's squared length, 100

\mathbf x^\top\mathbf y

the column's inner product with the response, 100

\lambda

the single penalty when only one kind is used

1. The general bound. Take two features, both active with the same sign, unit-norm columns (\lVert x_i\rVert = 1) and correlation \rho = x_i^\top x_j. Write the KKT condition for each.

\mathbf x_i

the unit-length column of feature i

\mathbf x_j

the unit-length column of feature j

1. Subtract. The \lambda_1 terms cancel because the signs agree. Cauchy–Schwarz bounds what is left.

\lVert\mathbf x_i - \mathbf x_j\rVert

how far apart the two feature columns are

\lVert\mathbf r\rVert

the length of the residual

1. Two facts finish it. First, \lVert x_i - x_j\rVert^2 = 2 - 2\rho for unit-norm columns. Second, \lVert r\rVert \le \lVert y\rVert, because the objective at \hat{w} is no larger than at w = 0, and the penalties are non-negative.

\rho

the correlation \mathbf x_i^\top\mathbf x_j between the two features

1. As \rho \to 1 the two weights are forced together. Zou and Hastie state the bound with \lVert y\rVert_1; it follows from this one, since \lVert y\rVert_2 \le \lVert y\rVert_1. One more identity: the elastic net is a lasso on augmented data, [X;\ \sqrt{\lambda_2}\, I] and [y;\ 0]. So it can select up to p features even when p > n, where the lasso stops at n.

\sqrt{\lambda_2}I

the fake rows that turn the L2 penalty into extra data

1. Check. Drill 11 (\lambda = \lambda_1 = \lambda_2 = 20): ridge (0.4545, 0.4545); lasso total 0.9 with sklearn returning the split (0.9, 0); elastic net (0.409, 0.409). On the 100 stations, whose 10 true features sit in two blocks with within-block correlation 0.8, CV elastic net keeps 9.84 of the 10 true features against the lasso's 8.38. Its bootstrap selection frequency for true features averages 0.945 against 0.763. Its test MSE is 4.67 against 4.78, lower in 82% of replicates. The price is more false positives: 9.76 against 6.24.

Key move. Add and subtract the half-sum (A) for the duplicate; subtract two KKT conditions for the bound.

Common slip. Saying the lasso "picks the better of two identical features". There is no better one: the solution is not unique, and which copy the solver returns depends on coordinate order. A second slip: forgetting the bound needs both weights non-zero with the same sign.

How it's asked. "Bootstrapped lasso picks a different member of the 'population within 250 m / 500 m / 1 km' block every time; the VP wants the driver" (Q20). A strong answer explains non-uniqueness, derives the grouping bound, and recommends reporting the block, with selection frequencies or stability selection.

Card 11 · What K-fold CV estimates: bias, variance, 1-SE ★★

Statement. Each K-fold fit sees only (K − 1)/K of the rows, so CV estimates the error of a smaller training set and is pessimistic. Fold errors are positively correlated, so the naive standard error is too small. The minimum over many configurations is optimistic. Hook: the 3 Ls — Less data, Lots of noise, Lucky minimum.

\text{CV}_K

the K-fold cross-validation estimate of test error

K

the number of folds, such as 10

\text{Err}

the expected test error of a model trained on the given number of rows

\bar e

the average of the K fold errors (bar = mean)

s^2

the variance of one fold's error

\rho

the correlation between two folds' errors: their training sets share rows

\min_c

the smallest over configurations c: the reported winner

\hat e_c

configuration c's validation error estimate

\mu

the true error every configuration shares

s

the noise level (standard deviation) of one validation estimate

\max_c

the largest over configurations

Z_c

configuration c's luck: a standard normal draw

Derivation.

1. Less data. Fold k's model is trained on n(K − 1)/K rows and scored on unseen rows. Its expected score is the risk at that smaller size. Averaging over folds does not change the expectation.

e_k

the validation error of fold k

\sum_k

add up over the K folds

1. With a learning curve \text{Err}(m) = a + b/m (Card 18), the bias is b/(n(K - 1)). It is largest for small K and flexible models (large b), and vanishes for LOO only as 1/n^2.

b

the learning-curve coefficient in \text{Err}(m) = a + b/m: large for flexible models

1. Lots of noise. Let the K fold errors have common variance s^2 and pairwise correlation \rho. They are positively correlated because any two training sets share (K - 2)/(K - 1) of their rows. Expand the variance of the mean (E).

1. The naive SE s/\sqrt{K} understates the truth by \sqrt{1 + (K - 1)\rho}. Worse, in practice s is estimated from the fold errors themselves, and their spread is deflated: the expected sum of squared deviations is Ks^2 - K\cdot \operatorname{Var} (\bar{e}) = (K - 1)(1 - \rho)s^2.

1. The last form of step 3 is also the bagging formula. Averaging B models whose predictions have variance \sigma^2 and correlation \rho leaves \rho \sigma^2 + (1 - \rho)\sigma^2/B: only the uncorrelated part averages away (Ch 10 owns ensembles).

B

the number of bagged models

\sum_{b=1}^{B}

add up over bagged models b = 1 to B

\hat f_b(x)

bagged model b's prediction at day x

\rho\sigma^2

the correlated part (\sigma^2 here = one model's prediction variance): bagging never removes it

\frac{(1 - \rho)\sigma^2}{B}

the uncorrelated part, which averages away as B grows

\rho

the correlation between two bagged models' predictions

1. The 1-SE rule. Let m* minimize the CV curve. Choose the simplest model (smallest df) whose CV error is within one standard error of the minimum. It trades a statistically invisible loss for a simpler model.

\hat m_{1\text{SE}}

the model chosen by the one-standard-error rule

m

a candidate model, such as a polynomial degree

m^*

the model with the lowest CV error

\text{SE}(m^*)

the standard error of that minimum CV score

1. Lucky minimum. Suppose C configurations all have the same true error \mu, and their validation estimates have independent noise of size s. The reported winner is the minimum, whose expectation lies below \mu by s times the expected maximum of C standard normals (by symmetry, \min Z = -\max(-Z)).

z

the integration variable: a possible value of the maximum

C

the number of configurations tried

\phi

the standard normal density

\Phi

the standard normal CDF: the chance a draw is below z

dz

integrate with respect to z

1. Check by formula. Drill 15 (\text{Err}(m) = 1 + 20/m,\ n = 100): truth 1.200; 5-fold 1.250; 10-fold 1.222; LOO 1.202. Drill 17 (K = 10, \rho = 0.3): \sqrt{3.7} = 1.92× with s known (simulation 1.93); \sqrt{3.7/0.7} = 2.30× with s estimated (simulation 2.37, a little higher because \mathbb{E}[\text{sample SD}] < \sqrt{\mathbb{E}[\text{sample variance}]}). Drill 14 (C = 10, \mu = 0.200, s = 0.010): 0.200 - 0.010 \times 1.539 = 0.185 (simulation 0.185).

1. Check on the season (500 seasons, degree 3). Less data: mean 10-fold estimate 0.115 against mean test MSE 0.106 (+0.0085; 5-fold +0.0109). Lots of noise: the SD of the CV estimate across seasons is 0.0356, 1.25 times its mean naive SE of 0.0285. Its correlation with that season's own test error is only 0.03. Lucky minimum: min-CV minus the chosen degree's true error averages −0.0055. On this season (replicate 0) the 10-fold minimum and the 1-SE choice are both degree 3, so the rule only matters on seasons like replicate 13 (Q21's chart): the minimum is at degree 5 (0.0737, SE 0.0149) and degree 3 scores 0.0879 \le 0.0886, so the rule ships degree 3. Over 500 seasons the rule picks degree 3 in 436 and lowers mean test MSE from 0.112 to 0.109. Bagging check (50 bootstrap 1-NN fits): one bootstrap fit has variance \sigma^2 = 0.102, two fits correlate at \rho = 0.416, so the formula gives 0.0437 against 0.0439 observed, down from 0.0912 for 1-NN on the full season (test MSE 0.184 → 0.136). The formula assumes each bagged fit is sane: bagging degree-12 polynomials explodes instead (median bagged test MSE 341 against 0.151 for one fit), because bootstrap samples miss edge days and the polynomial extrapolates.

Key move. Expectation (E): the mean of a fold error, the variance of a mean of correlated terms, and the mean of a minimum.

Common slip. Reporting the minimum CV error as the expected error of the chosen model, which is the lucky minimum. Whether it ends up optimistic depends on how many configurations were tried. On the stations, a 19-value \lambda search gives best_score_ a bias of +0.09 (Less data wins); a 760-configuration search gives −0.83. Nested CV stays honest to slightly pessimistic in both cases (+0.19, +0.25). A second slip: computing the CV standard error as if folds were independent.

How it's asked. "Here is a season's 10-fold CV curve with SE bars, minimum at degree 5, degree 3 within one SE. Which do you ship?" (Q21). Or "is GridSearchCV.best_score_ an honest estimate?" (Q23), or "500 configs, one validation set: how big a bias?" (Q35). A strong answer names all 3 Ls with their signs and ends with tune inside, test outside: nested CV.

Card 12 · LOOCV and GCV for linear smoothers ★★

Statement. For least squares and for ridge at a fixed \lambda penalized least-squares fit \hat{y} = Sy whose penalty does not depend on the rows), the leave-one-out residual is the ordinary residual inflated by 1/(1 - S_{ii}). LOOCV costs one fit. GCV replaces each leverage with the average, \operatorname{tr} (S)/n.

\hat f^{(-i)}(x_i)

the prediction at day i from a fit that never saw day i

\text{LOOCV}

leave-one-out CV: the average squared error on each left-out day

\text{GCV}

generalized CV: LOOCV with every leverage replaced by the average

Derivation.

1. Let \hat{w}_{(-i)} minimize the penalized loss on all rows except i, and let \tilde{y}_i = x_i^\top \hat{w}_{(-i)} be its prediction at the left-out row. Build a new response vector z: y with y_i replaced by \tilde{y}_i.

L_{-i}

the penalized loss on every row except row i

\sum_{j \ne i}

add up over all rows j other than i

y_j

row j's response

\mathbf x_j

row j's feature vector

\lambda

the ridge penalty, held fixed

\mathbf z

the response vector with y_i swapped for its leave-one-out prediction

\tilde y_i

the leave-one-out prediction at row i

y_1

the first row's response

y_n

the last row's response

1. Fitting to z gives back \hat{w}_{(-i)}. For any w, the loss on z is L_{-i}(w) plus one non-negative term. At \hat{w}_{(-i)} that term is zero and L_{-i} is at its minimum, so nothing can do better.

L_{\mathbf z}

the penalized loss on all rows, with responses \mathbf z

\mathbf x_i

row i's feature vector

\hat{\mathbf w}_{(-i)}

the weights fitted without row i

1. The fit to z is the same linear smoother applied to z. Read off row i, then substitute y_i = \tilde{y}_i + (y_i - \tilde{y}_i).

(S\mathbf z)_i

entry i of the smoother applied to \mathbf z

S_{ij}

how much row j's response counts in row i's fitted value

1. Subtract from y_i and the shortcut appears. For OLS this is Chapter 1's e_i/(1 - h_{ii}) (Ch 1, Card 13, by Sherman–Morrison); here it holds for ridge too.

1. GCV (Craven and Wahba, 1979): replace every S_{ii} by its average, \operatorname{tr} (S)/n (T). The resulting formula needs only the trace. It is a good approximation when leverages are similar and a bad one when a few rows have far more leverage than the rest.

\bar S

the average leverage, \text{tr}(S)/n

1. The mean as a special case: S = (1/n)11^\top has S_{ii} = 1/n, so every LOO residual is the residual times n/(n - 1), and LOOCV is (n/(n - 1))^2 times the training MSE.

\bar y

the average response: the mean model's prediction

1. Check on the toy line. Leverages are 0.524, 0.295, 0.181, 0.181, 0.295, 0.524 (they sum to 2 = p). Day A's residual −0.271 becomes -0.271/(1 - 0.524) = -0.570. LOOCV is 0.258 for the line, and 1.44 \times 0.547 = 0.787 for the mean (Drill 9); brute-force refits agree exactly. Ridge on the season's degree-15 design: the shortcut matches brute force to 3.2 \times 10^{-11}. GCV fails on this season: it picks \lambda = 0.316, with test MSE 0.522, because the edge days have far higher leverage than the average \text{df}/n. LOO and 10-fold both pick \lambda = 5.62 (test 0.137).

\lambda_{\text{GCV}}

the ridge penalty GCV picks

\lambda_{\text{LOO}}

the ridge penalty LOOCV picks

Key move. The replace-the-point trick (steps 1–3), then the trace (T) for GCV.

Common slip. Applying the shortcut to kNN. Leaving a day out changes its neighbor set, so the formula returns a (k - 1)-NN prediction, not the kNN LOO error. It also fails for ridge when the scaler or \lambda is refit inside each fold. A second slip: assuming \text{GCV} \approx \text{LOOCV} always. They agree only when leverages are nearly equal.

How it's asked. "Which K would you use for 30 days, for 30 million rows, and for ridge specifically?" (Q24). A strong answer says that for ridge LOOCV is free (steps 1–4), so the choice of K is about bias and variance, not cost; it warns that GCV breaks with unequal leverages; and it uses 5- or 10-fold for anything non-linear.

Card 13 · Early stopping as spectral filtering ★★★

Statement. Gradient descent from zero on \tfrac 12 \lVert y - Xw\rVert^2 fits each SVD direction gradually. After t steps, direction j has been filtered by 1 - (1 - \eta d_j^2)^t, which looks like ridge's d_j^2/(d_j^2 + \lambda) with \lambda \approx 1/(\eta t). Stopping early is a penalty you set with a clock.

\mathbf w_t

the gradient-descent weights after t steps, started from zero

1 - (1 - \eta d_j^2)^t

gradient descent's filter: how much of direction j is fitted after t steps

\eta

the step size (learning rate)

\frac{1}{\eta t}

one over (step size × number of steps t): the matching ridge penalty

\lambda

the ridge penalty strength

Derivation.

1. The gradient of \tfrac 12 \lVert y - Xw\rVert^2 is -X^\top(y - Xw). Start at w_0 = 0 (with y centered, so the intercept is \bar{y}).

\mathbf w_{t+1}

the weights after one more step

\mathbf w_0

the starting weights: all zeros

\eta X^\top(\mathbf y - X\mathbf w_t)

the step: \eta times minus the gradient of \tfrac12\lVert\mathbf y - X\mathbf w\rVert^2

1. Rotate (S): let a_{j,t} = v_j^\top w_t. Since X^\top = VDU^\top, each coordinate evolves on its own.

a_{j,t}

the weights' coordinate along direction j after t steps, \mathbf v_j^\top\mathbf w_t

a_{j,t+1}

the same coordinate one step later

(1 - \eta d_j^2)

the factor by which each step shrinks the gap to least squares

1. The fixed point is the least-squares coordinate z_j = u_j^\top y/d_j. The gap to it shrinks by (1 - \eta d_j^2) each step, starting from -z_j.

(1 - \eta d_j^2)^t

the fraction of the starting gap still left after t steps

a_{j,0}

the starting coordinate: 0

1. So gradient descent is a filter on the least-squares coordinates, just as ridge is (Card 6, step 4). It converges (to least squares, or to the minimum-norm solution in Card 16) when 0 < \eta d_j^2 < 2 for every direction, Chapter 2's \eta < 2/\lambda_{\max}.

\text{filter}_{\text{GD}}(d_j^2, t)

gradient descent's filter for a direction of strength d_j^2 after t steps

\text{filter}_{\text{ridge}}(d_j^2, \lambda)

ridge's filter for the same direction

1. Match the two. For small \eta d_j^2, (1 - \eta d_j^2)^t \approx e^{-\eta td_j^2}. Strong directions (d_j^2 \gg 1/(\eta t)) have both filters near 1. Weak directions (d_j^2 \ll 1/(\eta t)) have \text{GD} \approx \eta td_j^2 and \text{ridge} \approx d_j^2/\lambda. Equating them gives \lambda = 1/(\eta t). Matching the half-way points instead (\text{filter} = \tfrac12) gives \lambda = \ln 2/(\eta t).

e^{-\eta t d^2}

the gap left after t small steps (e = 2.718…)

\eta t\,d^2

step size × steps × strength: the GD filter for a weak direction

d^2

one direction's squared singular value

\frac{\ln 2}{\eta t}

the direction strength that gradient descent has half fitted after t steps

1. The map is only rough: GD's filter rises like 1 - e^{-x} and ridge's like x/(1 + x), so they differ in the middle. Early stopping is ridge in spirit: it shrinks weak directions most, and t plays the role of 1/\lambda.

x

shorthand for \eta t d^2

1. Check. Drill 7 (\eta = 0.01, t = 100, so \lambda = 1): GD filters 1.000, 0.634, 0.0952 against ridge's 0.909, 0.5, 0.0909 for d^2 = 10, 1, 0.1, confirmed by running the iteration. On the season's degree-15 fit with \eta = 1/\lambda_{\max} = 1/47.6, 13 of the 15 directions have \eta d^2 between 0.56 and 1 and are fitted within a few steps. The test curve has the same U as ridge's and nearly the same minimum: GD 0.130 at t = 3, ridge 0.137. But at \lambda = 1/(\eta t) the two test curves differ by up to 0.10. With \eta ten times smaller the gap is 0.077. The best constant is \lambda \approx 0.6/(\eta t) (gap 0.047), close to the half-point match \ln 2/(\eta t) (gap 0.055).

Key move. SVD (S): the iteration decouples into one geometric sequence per direction.

Common slip. Claiming early stopping equals ridge. It is a different filter with the same shape; the map \lambda \approx 1/(\eta t) is a rule of thumb, and the constant depends on \eta. A second slip: forgetting the start w_0 = 0. From a random start, the null-space part of the initialization never decays (Card 16).

How it's asked. "An MLE stops training when validation loss starts rising; a skeptical PM calls it ad hoc" (Q11). A strong answer writes steps 2–3, says "t is 1/\lambda", and mentions that this is why the Search term of Card 1 can be negative.

Card 14 · Noise injection = ridge ★★

Statement. Add independent Gaussian noise of variance s^2 to every input, and average the squared-error loss over the noise. The result is exactly the ridge objective with \lambda = n\cdot s^2 for the sum-of-squares loss (s^2 for the mean loss) (Bishop, 1995).

\mathbb E_\delta

the average over the injected input noise

\boldsymbol\delta_i

the Gaussian jitter added to row i's inputs

s^2

the variance of the injected noise, per input

Derivation.

1. Split one row's noisy residual into its clean part and the noise term.

r_i

row i's clean residual

1. Square and take the expectation over \delta_i (E). The cross term vanishes because \mathbb{E}[\delta_i] = 0. The last term is w^\top \mathbb{E}[\delta_i\delta_i^\top]w = s^2\lVert w\rVert^2.

1. Sum over the n rows: one penalty of s^2\lVert w\rVert^2 per row.

\tilde X

the design matrix with every row jittered (tilde = noisy copy)

1. The same result from the normal equations. Least squares on infinitely many noisy copies solves the averaged normal equations, and averaging the Gram matrix adds n s^2 its diagonal.

1. Why it is a regularizer. Jittering the date by a few days says "the ride count shouldn't depend sharply on the exact day": an invariance. A noise level you can defend is a prior you can defend. For a non-linear model g, a second-order Taylor expansion of g(x + \delta) gives a gradient penalty plus a term in the residual r = y - g(x) times the Hessian's trace. Bishop (1995) showed the Hessian term is negligible near the minimum, leaving a gradient penalty. For linear g the Hessian is zero and \nabla g = w, so the result is exact.

y

one day's rides

g

a non-linear model's prediction function

\mathbf x

one day's clean inputs

\boldsymbol\delta

the input jitter

r

the clean residual, y - g(\mathbf x)

\nabla_{\mathbf x}g(\mathbf x)

the gradient of g in its inputs: the vector of slopes, one per input; points uphill

\nabla^2_{\mathbf x}g(\mathbf x)

the Hessian: how those slopes themselves change (curvature)

O(s^4)

terms that shrink at least as fast as s^4

1. Check on this season's centered, standardized degree-15 design (n = 30, s = 0.1, so \lambda = 30 \times 0.01 = 0.3). Least squares on 200 jittered copies of each day (6,000 rows) matches ridge with \lambda = 0.3 to 0.0031 in every coefficient. The coefficients themselves are as large as 0.685, and plain least squares differs by 0.095. Test MSE: 0.534 for the jittered fit, 0.533 for ridge, against 0.888 for least squares (Drill 6).

\hat w_j^{\text{jitter}}

coefficient j fitted on the jittered copies

\hat w_j^{\text{ridge}}

coefficient j from ridge with \lambda = 0.3

Key move. Expectation over the injected noise (E): the cross term dies and the square becomes a penalty.

Common slip. Dropping the factor n, or mixing the sum and mean conventions: \lambda = n s^2 for \lVert y - Xw\rVert^2, and s^2 for (1/n)\lVert y - Xw\rVert^2. A second slip: jittering standardized and raw features with the same s. The implied penalty is per unit of input, so the scale of each column matters exactly as it does for ridge.

How it's asked. "An engineer adds Gaussian noise to inputs during training and validation error drops. Prove what this is equivalent to for a linear model; what \lambda?" (Q25). A strong answer does steps 1–3 and then contrasts it with augmentation in general: it encodes an invariance, and a wrong invariance is bias.

Card 15 · Dropout in linear regression = per-feature ridge ★★★

Statement. Inverted dropout keeps each input with probability q and scales survivors by 1/q. Averaged over the masks, the squared-error loss becomes ridge with a separate penalty for each feature, weighted by that feature's energy \sum_ix_{ij}^2 (Wager, Wang and Liang, 2013).

\tilde x_{ij}

feature j of row i after inverted dropout

x_{ij}

the original value of feature j on row i

\delta_{ij}

the dropout mask: 1 if the input is kept, 0 if it is dropped

q

the keep probability

\text{Bernoulli}(q)

a coin that comes up 1 with probability q

\mathbb E_\delta

the average over the random dropout masks

\tilde X

the design matrix after dropout

\sum_j

add up over features j

w_j

the weight on feature j

Derivation.

1. Mean and variance of one dropped-out input. Scaling by 1/q keeps the mean unchanged; that is why "inverted" dropout needs no rescaling at test time.

1. The prediction for row i is a sum of independent masked terms, so its mean is the clean prediction and its variance adds up over features (E).

\tilde{\mathbf x}_i

row i's inputs after dropout

1. For any random variable, \mathbb{E}[(y - Z)^2] = (y - \mathbb{E}Z)^2 + \operatorname{Var}(Z), by adding and subtracting \mathbb{E}Z. Apply it to one row.

1. Sum over rows and swap the order of summation: feature j's penalty is weighted by its column energy.

\lambda_j

feature j's own ridge penalty

1. With standardized features, \sum_ix_{ij}^2 = n for every j, so the penalty is ordinary ridge with \lambda = n(1 - q)/q. Without standardization, rare or small-scale features are penalized less, which is a known difference from plain weight decay.

1. Check. On the season's standardized degree-15 design with q = 0.8, a Monte Carlo average over 200,000 masks of the dropped-out loss gives 8.769 ± 0.006 against the formula's 8.758 (0.12% apart). Drill 19 (n = 100, standardized, q = 0.8): \lambda = (0.2/0.8) \times 100 = 25. Monte Carlo gives 1440.9 ± 0.27 against the formula's 1441.4.

Key move. Expectation over the masks (E), with \mathbb{E}[(y - Z)^2] = (y - \mathbb{E}Z)^2 + \operatorname{Var}(Z).

Common slip. Using the drop probability where the keep probability belongs. With drop rate p = 1 - q, the factor is p/(1 - p), not (1 - p)/p. A second slip: forgetting to switch dropout off at inference (model.eval()). Inverted dropout's scaling makes the mean right; the noise must still go.

How it's asked. "Apply dropout with keep-probability q to a linear regression's inputs. What objective are you minimizing in expectation?" (Q26). A strong answer derives steps 1–4, notes that the penalty adapts to each feature's scale, and says that in deep networks dropout is not exactly ridge (Ch 17 owns it).

Card 16 · Minimum-norm interpolation and its risk ★★★

Statement. When p > n, infinitely many weight vectors fit the training data exactly. The pseudo-inverse picks the one with the smallest norm, and gradient descent from zero converges to the same one. With isotropic Gaussian features, its risk has an exact formula that blows up at p = n and comes back down beyond it. Hook: at the threshold there's one way to fit everything, and it's the wildest; past it, minimum norm picks the calmest.

\hat{\mathbf w}

the minimum-norm interpolator: the shortest weight vector that fits every row exactly

X^+

the pseudo-inverse of X

(XX^\top)^{-1}

the inverse of the n \times n matrix of row inner products

R

the test risk on a new isotropic Gaussian row

\dfrac{p}{n - p - 1}

the variance term below the threshold: it blows up as p nears n

p < n - 1

fewer coefficients than rows: ordinary least squares

\dfrac{n}{p - n - 1}

the variance term past the threshold: it falls as features are added

\lVert\boldsymbol\beta\rVert^2

the squared length of the true coefficients: the total signal

\dfrac np

the share of \boldsymbol\beta the fit can see: rows over coefficients

p > n + 1

more coefficients than rows: infinitely many exact fits

Derivation.

1. With p > n and X of full row rank, every interpolator is w_0 + v with Xv = 0. Take w_0 = X^\top(XX^\top)^{-1}y; it interpolates and lies in the row space of X.

\mathbf w_0

the pseudo-inverse solution, which lies in the row space of X

\mathbf c

the coefficients that build \mathbf w_0 out of the rows of X

1. The row space and the null space are orthogonal, so Pythagoras says the norm of any interpolator is at least \lVert w_0\rVert, with equality only at v = 0.

\mathbf v

any null-space direction: X\mathbf v = \mathbf 0, so adding it changes no prediction

1. Gradient descent from zero lands on it. Every gradient X^\top(Xw - y) lies in the row space, so iterates started at 0 never leave it. The only interpolator in the row space is w_0. From a random start w_{\text{init}}, GD keeps the null-space part of w_{\text{init}} forever.

\text{row}(X)

the row space: all combinations of the rows of X

\mathbf w_{\text{init}}

a random starting point for gradient descent

P_{\text{null}}

the projection onto the null space of X

1. Risk for a new x \sim N(0, I): R = \sigma^2 + \lVert\hat w - \beta\rVert^2 (E). Pure noise first (\beta = 0). For p < n this is Card 3. For p > n, \lVert \hat{w}\rVert^2 = \varepsilon^\top(XX^\top)^{-1}\varepsilon, and the trace trick applies (T).

1. XX^\top is the sum over the p columns of x_jx_j^\top, each column N(0, I_n): an n \times n Wishart matrix with p degrees of freedom. Card 3's inverse-Wishart mean, with the roles of n and p swapped, gives I_n/(p - n - 1).

I_n

the n \times n identity matrix

p

the number of features (columns of X)

1. Why the spike. In SVD form \lVert \hat{w}\rVert^2 = \sum(u_j^\top \varepsilon)^2/d_j^2, and the smallest singular value of an n \times p Gaussian matrix is about \lvert \sqrt{n} - \sqrt{p}\rvert, which is near zero when p \approx n. One noisy coordinate is divided by an almost-zero number.

\sum_{j=1}^{\min(n,p)}

add up over the non-zero singular values

d_{\min}

the smallest singular value of X

1. With signal, for p > n: the fit recovers only the projection of \beta onto the row space, P_{\text{row}}\beta, and the rest is bias. By rotational invariance \mathbb{E}[P_{\text{row}}] = (n/p)I, since its trace is n. So the bias is \lVert \beta \rVert^2(1 - n/p). It is independent of the noise part, so the two add.

P_{\text{row}}

the projection onto the row space of X: the part of \boldsymbol\beta the fit can see

1. Ridge removes the spike. Along direction j, ridge's variance is \sigma^2d_j^2/(d_j^2 + \lambda)^2 (Card 7). Over all d it is at most \sigma^2/(4\lambda), reached at d_j^2 = \lambda, so no direction can blow up, however small d_j is.

1. Check (n = 100, isotropic). Pure noise with \sigma^2 = 1, theory against simulation (Drill 8): p = 50: 2.02 (2.02); p = 90: 11.0 (11.1); p = 95: 24.75 (24.7); p = 105: 26.0 (25.5); p = 110: 12.1 (12.0); p = 200: 2.01 (2.01); p = 1000: 1.111 (1.111). With signal (\lVert \beta \rVert = 1, \sigma^2 = 0.25), p = 200: 0.25(1 + 100/99) + 0.5 = 1.0025 (simulation 1.0025). Gradient descent from zero at p = 300 ends within 10^{-12} of the pseudo-inverse. From a random start it ends 1.42 away, exactly the norm of the start's null-space part. On the core + embedding design the min-norm median test MSE spikes to 47.4 at p = 100, while ridge with CV-chosen \lambda never exceeds 0.354.

Key move. Orthogonality of row space and null space for minimum norm; SVD (S) for the spike; the trace trick (T) with the inverse-Wishart mean for the exact risk.

Common slip. Saying the spike happens "because there are too many parameters". At p = 1000 there are ten times more parameters and the risk is 1.11, nearly the noise floor. The spike is about the smallest singular value at p \approx n. A second slip: claiming gradient descent finds the minimum-norm solution from any start. It does so only from zero, or from a start in the row space.

How it's asked. "A station model with 1,000 features on 100 stations has zero training error and beats every model with fewer than 100 features. Reconcile this with bias–variance" (Q28). Or the full derivation (WP2). A strong answer derives the p > n formula, explains the spike by d_{\min}, says ridge or early stopping removes it, and states the benign-overfitting condition: signal in a few strong directions plus many weak directions to absorb the noise (Bartlett, Long, Lugosi and Tsigler, 2020).

Card 17 · Importance weighting for covariate shift; ESS ★★

Statement. If only the distribution of x changes (p(y \mid x) stays the same), weighting each training row by w(x) = p_{\text{test}}(x)/p_{\text{train}}(x) makes the weighted training loss an unbiased estimate of test loss. The price is a smaller effective sample size. Hook: weight by test over train; check the ESS.

\mathbb E_{\text{train}}

the average over days drawn as in training (80% summer)

\mathbb E_{\text{test}}

the average over days drawn as at deployment (uniform over the year)

w(X)

the importance weight of a random day X: test density over training density

X

a random day

Y

that day's rides

f

the model being scored

\text{ESS}

effective sample size: how many unweighted rows the weighted sample is worth

w_i

the importance weight of training row i

w

the importance weight, as a random quantity

N(0,1)

the training inputs: standard normal

N(\mu, 1)

the test inputs: normal, shifted by \mu

\mu

the size of the shift

Derivation.

1. Write the weighted expectation as an integral. The training density cancels, and p(y | x) is the same in both worlds by assumption. This needs p_{\text{train}}(x) > 0 wherever p_{\text{test}}(x) > 0 (overlap).

\iint

integrate over both y and x

p_{\text{test}}(x)

the density of day x at deployment

p_{\text{train}}(x)

the density of day x in training

p(y \mid x)

the chance of y rides on day x: the same in both worlds

x

a particular day

y

a particular ride count

1. Effective sample size. A weighted mean \sum w_i\ell_i/\sum w_i of independent terms with variance v has variance v\sum w_i^2/(\sum w_i)^2. Matching that to v/\text{ESS} defines the ESS. Since \mathbb{E}_{\text{train}}[w] = 1, \text{ESS}/n \approx 1/\mathbb{E}_{\text{train}}[w^2].

\ell_i

the loss on training row i

v

the variance of one row's loss

1. Gaussian mean shift. The ratio of N(\mu, 1) to N(0, 1) densities is an exponential tilt. Its second moment under N(0, 1) uses \mathbb{E}[e^{aX}] = e^{a^2/2}.

w(x)

the importance weight at input x

1. Estimating weights with a classifier. Pool the training and test x's, label them train or test, and fit a probabilistic classifier. By Bayes' rule its odds equal the density ratio times the ratio of sample sizes, so divide that back out. The classifier's AUC is also a shift test: \text{AUC} \approx 0.5 means no detectable shift (adversarial validation).

P(\text{test} \mid x)

the domain classifier's probability that day x came from the test set

P(\text{train} \mid x)

its probability that day x came from training

n_{\text{test}}

the number of test days pooled

n_{\text{train}}

the number of training days pooled

1. When weighting is worth it. With squared loss, the conditional mean minimizes the risk at every x separately (Card 1, step 5), so it is the best predictor under any distribution of x. If the family contains it (well specified), the weighted and unweighted targets coincide, and weighting only adds variance. If the family is misspecified, the best member depends on where the x's fall, and weighting moves the target to the right place (Shimodaira, 2000).

f

the true conditional mean, \mathbb E[Y \mid X]

\arg\min_{g \in \mathcal F}

the family member g with the smallest average loss

g

a candidate from the family

\notin

is not a member of

1. The running example: 80% of training days fall in the summer half [0, 0.5), and deployment is uniform over the year. The training density is 1.6 on summer days and 0.4 on winter days; the test density is 1.

w_{\text{summer}}

the weight on a summer training day

w_{\text{winter}}

the weight on a winter training day

1. The best possible domain classifier's AUC. Its score takes only two values, high on winter days and low on summer days. A random test day beats a random training day when it is winter and the training day is summer, and ties count half.

\text{AUC}

area under the ROC curve: the chance a random test day outscores a random training day

1. Check. Simulated ESS fraction 0.640 against 0.64. A logistic domain classifier on 200 + 200 days has AUC 0.649 (theory 0.65) and estimated weights averaging 0.667 and 2.27 (true 0.625 and 2.5). Drill 13: \text{ESS}/n = e^{-1} = 0.368 at \mu = 1 (Monte Carlo 0.367), and e^{-4} = 0.0183 at \mu = 2. The \mu = 2 value is exact; the Monte Carlo estimate (0.022) is unstable because \mathbb{E}[w^4] = e^{24}. Step 5 on the season with n = 200: the misspecified line improves from 0.314 to 0.293 when weighted, close to the no-shift reference of 0.290. The well-specified cubic barely moves (0.0980 to 0.0977). At the population level, the best line for the training distribution scores 0.308 on the test distribution, against 0.286 for the best line for the test distribution itself.

Key move. Expectation by change of measure (E): the training density cancels in the integral.

Common slip. Weighting by p_train/p_test (upside down), or forgetting the n_train/n_test factor when the weights come from a classifier. A second slip: weighting when there is no overlap. If deployment includes regions with p_{\text{train}}(x) = 0, no weight can help, only extrapolation. A third: reporting a weighted fit without its ESS. A handful of weights above 200 means a handful of effective rows (Q33).

How it's asked. "Reweighting by an estimated density ratio gives a few rows weights above 200, and the estimate swings wildly. What's going on, and what do you do?" (Q33). A strong answer computes the ESS, and suggests clipping or self-normalizing the weights, checking overlap, and not weighting at all if the model is well specified. It adds that label shift (p(y) moves) uses Ch 3's prior correction instead.

Card 18 · Learning curves and power laws ★

Statement. For a fixed family, more data shrinks variance like \sigma^2\cdot \text{df}/n but leaves bias untouched, so test error falls toward the floor \sigma^2 + \text{bias}^2_F. Hook: more data cures variance, never bias. When a learning curve follows a power law a + b\cdot n^{-\alpha}, three points at n, 4n and 16n pin it down.

\text{test}(n)

the test error after training on n rows

\text{bias}^2_{\mathcal F}

the squared bias of the family's best member: more data can't remove it

\text{err}(n)

the measured test error at training size n

a

the error floor the curve levels off at

b

the size of the reducible part

\alpha

the power-law exponent: how fast extra data pays off

Derivation.

1. Average variance over the design points of a least-squares fit. The fit is \hat{y} = Hy, so \operatorname{Cov} (\hat{y}) = \sigma^2HH^\top = \sigma^2H. Its trace is \sigma^2p (T). Divide by n.

1. The bias does not depend on n. The best member f^*_F of the family is fixed, and \mathbb{E}\hat f converges to it as n grows. So the floor is \sigma^2 + \text{bias}^2_F (Card 1, step 6), and the curve approaches it like 1/n.

f

the true curve, \sin(2\pi x)

1. The degree-1 floor on the season, exactly. The best line under uniform x is the L^2 projection of \sin(2\pi x) onto \{1, x\}. The mean of f is 0. Its covariance with x is -1/(2\pi) and \operatorname{Var} (x) = 1/12, so the explained part is \operatorname{Cov}^2/\operatorname{Var} = 3/\pi^2.

x

the day of the year, uniform on [0, 1)

\text{Cov}(x, \sin 2\pi x)

how the true curve moves with the date

\int_0^1

integrate over the whole year

\text{bias}^2_{\text{line}}

the best line's squared bias: its floor above the noise

1. How much data for a target excess error \varepsilon: set \sigma^2\cdot \text{df}/n = \varepsilon and solve. Degree 12 has \text{df} = 13.

\varepsilon

the target excess error above the floor

1. Power law from three points. Differences of successive points cancel a. Their ratio cancels b, leaving 4^\alpha.

1. Then recover b\cdot n^{-\alpha} from the first difference, and a from the first point. Extrapolate.

1. Check. Drill 16 (0.1632, 0.1316, 0.1158 at 1k, 4k, 16k): the differences are 0.0316 and 0.0158, the ratio is 2, so \alpha = 0.5, b\cdot n^{-\alpha} = 0.0316/0.5 = 0.0632, a = 0.100, and the 64k prediction is 0.100 + 0.0632/8 = 0.108. On the season, degree 1 levels off at the floor 0.286 from step 3. Degree 12's excess error times n stays between 1.14 and 1.27 for n from 50 to 1,000, against \sigma^2\cdot \text{df} = 0.09 \times 13 = 1.17. A power-law fit on n \ge 50 gives a = 0.0903 (the floor 0.09), b = 1.82 and \alpha = 1.09, close to the parametric rate \alpha = 1.

Key move. Trace trick (T) for the variance; Expectation (E) and Card 1's split for the floor; ratios of differences for the power law.

Common slip. Extrapolating a power law fitted on a random split to a future that differs in distribution: more data from the wrong distribution does not help (Card 17). A second slip: assuming learning curves are always monotone. Near the interpolation threshold more data can briefly hurt. Degree 12 on the season spikes to 16.3 at n = 15 (Card 16's sample-wise double descent).

How it's asked. "Three pretraining runs at 1×, 4× and 16× data give these losses. Predict 64×, and tell me when the extrapolation breaks" (Q39). Or "$200k for ten times more days: the linear model's curves are flat and meet at 0.29. Buy?" (Q6). A strong answer separates the floor a (noise + bias, unmoved by data) from the reducible part. It calls scaling laws learning curves at enormous scale (Ch 23), and names what breaks them: repeated data, distribution change, and a floor set by the family.

Card 19 · VC dimension, light ★★

Statement. A family shatters a set of points if it can realize every one of the 2^m labelings. The VC dimension is the size of the largest set it can shatter. Halfplanes in the plane have VC dimension 3: four points never allow more than 14 of the 16 labelings. Linear classifiers in \mathbb{R}^d have \text{VC} = d + 1. The one-parameter family \operatorname{sign} (\sin(\omega x)) has infinite VC dimension. Hook: Count it, Correlate it, Shatter it — this card is "Shatter it".

\text{VC}

VC dimension: the most points the family can label in every possible way

\text{sign}

+1 or -1: which side of the boundary

\mathbf w

the classifier's weight vector (normal to its boundary)

\mathbf x

an input point

b

the classifier's offset (intercept)

\mathbb R^d

d-dimensional input space

d

the number of input dimensions

\omega

the sine's frequency: the family's only parameter

x

a one-dimensional input point

f

a classifier from the family

h

the family's VC dimension

\delta

the failure probability: the bound holds with chance at least 1 - \delta

Derivation.

1. Lower bound in \mathbb{R}^d: the d + 1 \text{ points } 0, e_1, \ldots, e_d are shattered. For any labels y_0, y_1, \ldots, y_d \in \{-1, +1\}, choose w_j = y_j and b = y_0/2. At e_j the score is y_j + y_0/2, which has the sign of y_j because \lvert y_0/2\rvert < 1. At 0 the score is b, with the sign of y_0.

\mathbf e_j

the j-th unit vector: 1 in coordinate j, 0 elsewhere

y_j

the label we want at point \mathbf e_j, \pm 1

y_0

the label we want at the origin

1. Upper bound: Radon's theorem. Any d + 2 points in \mathbb{R}^d can be split into two groups whose convex hulls intersect. They are affinely dependent: \sum \lambda_ix_i = 0 with \sum \lambda_i = 0 and not all \lambda_i zero. Put the positive \lambda_i in group P and the rest in N, and normalize by \Lambda = \textstyle\sum_P \lambda_i.

\sum_{i \in P}

add up over the points in group P

P

the points with a positive coefficient \lambda_i

\lambda_i

point i's coefficient in the affine dependence; they sum to 0

\Lambda

the total of the positive coefficients, used to normalize

\mathbf x_i

the i-th of the d + 2 points

\sum_{i \in N}

add up over the points in group N

N

the remaining points

\mathbf c

the shared point, inside both hulls

\text{conv}(P)

the convex hull of P: every weighted average of its points

1. Label P positive and N negative. A separating halfplane would put all of conv(P) on one side and all of conv(N) on the other, but the point c lies in both hulls. So that labeling is impossible, and no d + 2 points are shattered.

i

which point

1. In the plane (d = 2): 3 points in general position give all 8 labelings, and 4 points fail. For four corners of a square, the two "diagonal" labelings are impossible: 16 - 2 = 14. For a triangle with a point inside, the two labelings that set the inner point against the other three are impossible: also 14.

1. One parameter, infinite VC. Take x_i = 10^{-i},\ i = 1, \ldots, m. For any labels y_i \in \{-1, +1\}, let c_i = (1 - y_i)/2 \in \{0, 1\} and set \omega as below.

\sum_{i=1}^{m}

add up over the m points

c_i

digit i: 1 if point i should be labeled -1, else 0

m

the number of points to shatter

y_i

the label wanted at point x_i = 10^{-i}

1. Evaluate at x_j. Terms with i > j are even integer multiples of \pi (10^{i-j} is a multiple of 10), so they do not change the sine. The term i = j adds c_j\pi. What remains, \varepsilon, lies strictly between 0 and 1.

x_j

point j, at 10^{-j}

j

the point being checked

\sum_{i<j}

add up over the earlier points

\sum_{i>j}

add up over the later points

\varepsilon

the leftover fraction, strictly between 0 and 1

c_j

point j's digit

1. So \operatorname{sign} (\sin(\omega x_j)) = (-1)^{c_j} = y_j for every j. Every labeling of m points is realized, for every m, and parameter count says nothing about capacity.

1. The bound's shape, finite class first. For a fixed f with loss in [0, 1], Hoeffding's inequality bounds the chance its empirical risk is \varepsilon too low. A union bound over \lvert F\rvert functions, set equal to \delta, gives a uniform guarantee.

P

probability over random training samples

\varepsilon

how far empirical risk may fall below true risk

\exists f \in \mathcal F

some function in the family

|\mathcal F|

the number of functions in a finite family

1. For an infinite family, the count that matters is the number of distinct labelings it produces on the sample. The Sauer–Shelah lemma says a family of VC dimension h produces at most \textstyle\sum_{i=0}^h C(n, i) labelings of n points; this card takes that count as given.

\sum_{i=0}^{h}

add up for i = 0 to h

\binom ni

n choose i: the number of ways to pick i of the n points

1. Bound the sum for n \ge h. Multiply by (h/n)^h \le(h/n)^i for i \le h, extend the sum to i = n, and use the binomial theorem and 1 + u \le e^u.

\sum_{i=0}^{n}

add up for i = 0 to n

1. So \ln\lvert F\rvert in step 8 becomes about h \ln(en/h). Vapnik and Chervonenkis (1971) make the substitution rigorous with a symmetrization step (a second, "ghost" sample) that changes the constants. The result has the form in the statement: the excess is roughly \sqrt{\text{VC}\cdot\ln n / n}, capacity per data point.

\sim

grows like (constants dropped)

1. Check: exact enumeration with a linear program gives 14 of 16 labelings for both 4-point configurations, and 8 of 8 for 3 points. The sine construction realizes all 32 labelings of m = 5 points (Drill 18).

Key move. Counting: an explicit construction for the lower bound, Radon's theorem for the upper bound.

Common slip. "VC dimension = number of parameters." Lines in the plane have three parameters (w_1, w_2, b) and VC 3, which is why the rule seems to work. The sine has one parameter and \text{VC } \infty. A second slip: shattering needs only some set of h points, not every set. Three collinear points cannot be shattered by a line, yet \text{VC} = 3.

How it's asked. "How many of the 16 labelings of four points can a line realize? What is the VC dimension of lines, and of \operatorname{sign} (\sin(\omega x))?" (Drill 18). A strong answer proves both bounds, then says VC bounds are loose worst-case statements. For a fixed fitting procedure, covariance df (Card 4) or held-out error is the practical measure. And huge networks fit random labels (Zhang et al., 2017), so capacity by count, or even by VC, does not explain why they generalize (Q28).

Practice protocol

1. Blank page, statement only. Cover everything below the statement. Write the derivation from memory, numbering the steps.
2. Timer. ★ cards: 3 minutes. ★★: 6 minutes. ★★★: 10 minutes. That is roughly what an interviewer allows before moving on.
3. Check every step, then the number. Compare line by line. Then redo the card's check on the running example by hand: Card 2's 0.384 at July 20, Card 6's filters 0.894 and 0.0952, Card 9's (2, 0, −0.5), Card 12's −0.570, Card 17's ESS of 19.2 days. A derivation that can't reproduce its number isn't finished.
4. Name the key move and the slip out loud. Say which S-E-A-T letter did the work and which slip you'd watch for. Then give the "How it's asked" strong answer in under a minute, as if to an interviewer.
5. Mark and re-derive. Mark any card where you looked, stalled or slipped. Re-derive marked cards after 48 hours, then after a week. A card is mastered when you get it right, inside the time, twice in a row on separate days.
6. Pair with the bank. After each card, answer its linked questions from the Interview Bank:

Suggested order, matching the chapter: Cards 1–5 first (risk, the decomposition, optimism, df, kNN), then Levels 1–2 of the bank, then Cards 6–19, then Levels 3–4.

Mastery checklist

• [ ] Card 1. Proved \mathbb{E}[\hat R_n(\hat f)] \le R(f^*_F) \le \mathbb{E}[R(\hat f)] in two inequalities, derived the noise floor \mathbb{E}[\operatorname{Var} (Y \mid X)], wrote Family-Sample-Search, and explained why the Search term can be negative.
• [ ] Card 2. Derived \sigma^2 + \text{bias}^2 + \text{variance} with all three cross terms killed and the reason each one dies, and computed the line at July 20 by hand: 0.09 + 0.274 + 0.0201 = 0.384.
• [ ] Card 3. Derived \sigma^2(1 \mp p/n) by the trace trick, the inverse-Wishart mean 1/(n - p - 1) from one \chi^2 moment, and the stations' 22.0 with an intercept.
• [ ] Card 4. Derived \text{optimism} = 2\sigma^2\cdot\text{df}/n for any procedure, \text{df} = \operatorname{tr} (S), \text{df} = n/k for kNN and \lvert A\rvert for the lasso, and explained why Gaussian AIC picks degree 15 on this season.
• [ ] Card 5. Derived \sigma^2/k and the curvature bias f''h^2m(m + 1)/6, and found k = 5 at the June peak (0.0199).
• [ ] Card 6. Derived the filter d^2/(d^2 + \lambda) and \text{df}(\lambda) from the SVD, the augmented-data and dual identities, and the season's filters 0.894 → 0.0952 at \lambda = 5.62.
• [ ] Card 7. Derived ridge's bias and variance, the per-direction MSE, the Hoerl–Kennard slope -2\sigma^2\textstyle\sum 1/d^4, and \lambda_j^* = \sigma^2/\theta_j^2 (3.0625 on the toy).
• [ ] Card 8. Completed the square for the posterior, proved the posterior mean is Bayes-optimal for any weighting, re-derived it per direction, and quoted \lambda^* = 80 with risk 5.21 against 20.7.
• [ ] Card 9. Derived the Laplace MAP, the KKT conditions, \lambda_{\max} = 2\max\lvert x_j^\top y\rvert and soft-thresholding, and converted \lambda to sklearn's \alpha = \lambda/(2n).
• [ ] Card 10. Showed identical columns split equally under the elastic net and arbitrarily under the lasso, derived the grouping bound, and computed Drill 11's three answers.
• [ ] Card 11. Derived the 3 Ls: the b/(n(K - 1)) pessimism, the (1 + (K - 1)\rho) variance and its 2.30× version, the lucky-minimum shift; stated the 1-SE rule and applied it to replicate 13.
• [ ] Card 12. Derived the LOO shortcut for ridge by the replace-the-point trick, GCV as its average-leverage version, and said why GCV fails on this season.
• [ ] Card 13. Derived the GD filter 1 - (1 - \eta d^2)^t, matched it to ridge with \lambda \approx 1/(\eta t) (and \ln 2/(\eta t)), and computed Drill 7's six filters.
• [ ] Card 14. Derived \lambda = n s^2 by the expectation over input noise, and by the averaged Gram matrix, and quoted the season check (0.0031).
• [ ] Card 15. Derived dropout's per-feature penalty ((1 - q)/q)\sum_ix_{ij}^2, reduced it to \lambda = n(1 - q)/q for standardized features, and got 25 for Drill 19.
• [ ] Card 16. Proved the pseudo-inverse is the minimum-norm interpolator and that GD from zero finds it, derived both risk formulas and the bias \lVert \beta \rVert^2(1 - n/p), and explained the spike by d_{\min}.
• [ ] Card 17. Derived the change-of-measure identity, \text{ESS} \approx n/\mathbb{E}[w^2], e^{-\mu^2}, the classifier-based weights, and the running example's 0.625, 2.5, 0.64 and AUC 0.65.
• [ ] Card 18. Derived the \sigma^2\cdot \text{df}/n variance, the degree-1 floor 0.09 + 1/2 - 3/\pi^2 = 0.286, and the three-point power-law fit (Drill 16: 0.108).
• [ ] Card 19. Proved \text{VC} = d + 1 for linear classifiers (construction + Radon), counted 14 of 16 in the plane, built the sine shattering, and sketched the bound from Hoeffding plus a union bound.