Fifty adults from the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018, aged 18 to 80, have their systolic blood pressure fitted by polynomials in age. A straight line leaves a mean squared residual of 187.0 (mm Hg squared); a polynomial of degree six leaves 159.6. The sixth-degree curve fits these fifty pressures better, but if each adult were measured again, the new pressures would not follow the curve's wiggles. By how much does the training error understate the error on new responses at the same ages, and how should that shortfall be counted for a fit that is not least squares on a fixed set of columns?
The shortfall is called the optimism of the training error. Model Selection derived the covariance identity for an arbitrary fit, specialized it to least squares and turned it into Mallows' $C_p$. This article states the identity with its conditions (finite second moments only, no independence assumed between observations, unequal variances allowed) and builds on it: for any rule that turns responses into fitted values, the expected optimism is twice the average covariance between each fitted value and its own response. The covariance defines the effective degrees of freedom of the rule. It equals the number of coefficients for least squares, the trace of the smoother matrix for ridge regression and other linear smoothers, and something larger than the number of coefficients kept when the rule chooses which coefficients to keep.
The route is as follows. First the three kinds of error and the covariance identity for optimism, proved for any fitting rule (Theorem 1). Then linear smoothers, where the degrees of freedom are a trace, measured on polynomial fits to NHANES pressures (Theorem 2). Then Mallows' $C_p$, proved unbiased under one condition and applied to ridge regression of the diabetes data (Theorem 3). Then fits that are not linear: Stein's lemma turns the covariance into an expected derivative (Theorem 4), which gives the degrees of freedom of soft thresholding exactly and shows what a discontinuous rule such as hard thresholding, or choosing the best of several inputs, adds. The article assumes The Geometry of Least Squares for the hat matrix and Expectation, Variance and Covariance for covariances of linear maps; the unit's notation is set out on its topic page.
Three errors at fixed inputs
The inputs $x_1, \ldots, x_n$ are held fixed throughout, as in Model Selection. The responses are
$$\mathbf{y} = \boldsymbol\mu + \boldsymbol\varepsilon,$$
where $\boldsymbol\mu = E[\mathbf{y}]$ is the vector of true means at the inputs (written $f$ on that page) and the errors $\varepsilon_i$ have mean zero and variances $\sigma_i^2$. Until said otherwise the errors are uncorrelated with a common variance $\sigma^2$. A fitting rule is any function $\hat{\mathbf{y}} = \hat{\mathbf{y}}(\mathbf{y})$ from responses to fitted values: least squares on chosen columns, a ridge fit, a polynomial whose degree is chosen from the data, a thresholding rule. We only need $E[\hat y_i^2] < \infty$.
Let $\mathbf{y}^0$ be a fresh vector of responses at the same inputs, independent of $\mathbf{y}$, with the same means and variances. Three quantities measure error.
- The training error $\overline{\mathrm{err}} = \frac1n\lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2 = \mathrm{RSS}/n$, computed on the responses that made the fit.
- The in-sample error $\mathrm{Err}_{\mathrm{in}} = \frac1n E_{\mathbf{y}^0}\lVert\mathbf{y}^0 - \hat{\mathbf{y}}\rVert^2$, the expected squared error of the same fitted values on fresh responses at the same inputs, with the fit held fixed (Hastie, Tibshirani and Friedman, 2009, eq. 7.18).
- The extra-sample error $\mathrm{Err}$, the expected error at new inputs drawn from the population of inputs. Its home is What Cross-Validation Estimates, which shows how cross-validation estimates it and with what bias.
The optimism is $\mathrm{Err}_{\mathrm{in}} - \overline{\mathrm{err}}$, a random quantity that depends on $\mathbf{y}$, and its expectation over the training responses is the expected optimism $\omega = E[\mathrm{Err}_{\mathrm{in}} - \overline{\mathrm{err}}]$ (Hastie et al., 2009, eqs. 7.19 and 7.20).
Why study the in-sample error when new cases rarely arrive at the old inputs? Hastie et al. (2009, §7.4) give the reason: for comparing models it is the relative size of the error that matters, and in-sample error is convenient for that. It also has an exact theory, which the extra-sample error lacks. Rosset and Tibshirani (2020) measure the difference. For least squares they prove that moving to new inputs adds a nonnegative bias term and a nonnegative variance term to the error (their Theorem 1). With normal inputs of mean zero, no intercept and a correct linear model, the added variance is $\sigma^2\,\frac{p}{n}\,\frac{p + 1}{n - p - 1}$ (their Theorem 2 and Corollary 2, in the arXiv version), which is small next to the in-sample optimism $2p\sigma^2/n$ while $p$ is small next to $n$.
Optimism is a covariance
Here is the idea. Against a fresh response, a fitted value has two independent sources of error, the new noise and its own miss of the mean. Against its own training response, the two are not independent: the fit has moved toward the noise it was built from, and the covariance between them is subtracted.
Theorem 1 (optimism is a covariance). For any fitting rule with $E[\hat y_i^2] < \infty$, and errors with mean zero and finite variances $\sigma_i^2$,
$$\omega = E[\mathrm{Err}_{\mathrm{in}}] - E[\overline{\mathrm{err}}] = \frac{2}{n}\sum_{i=1}^n \operatorname{Cov}(\hat y_i, y_i).$$
Proof. Fix $i$ and write $y_i^0 - \hat y_i = (y_i^0 - \mu_i) - (\hat y_i - \mu_i)$. The first term has mean zero, variance $\sigma_i^2$, and is independent of $\hat y_i$, which depends only on $\mathbf{y}$. Expanding the square, the cross term has expectation $E[y_i^0 - \mu_i]\,E[\hat y_i - \mu_i] = 0$, so
$$E\big[(y_i^0 - \hat y_i)^2\big] = \sigma_i^2 + E\big[(\hat y_i - \mu_i)^2\big].$$
For the training response the same expansion gives
$$E\big[(y_i - \hat y_i)^2\big] = \sigma_i^2 + E\big[(\hat y_i - \mu_i)^2\big] - 2E\big[(y_i - \mu_i)(\hat y_i - \mu_i)\big].$$
The last expectation is $E[(y_i - \mu_i)\hat y_i] - \mu_i E[y_i - \mu_i] = E[(y_i - \mu_i)\hat y_i]$, and since $E[y_i - \mu_i] = 0$ this is $\operatorname{Cov}(y_i, \hat y_i)$. The expectation of $\mathrm{Err}_{\mathrm{in}}$ is the average of the first display over $i$ (the inner expectation over $\mathbf{y}^0$ followed by the outer one over $\mathbf{y}$ is the expectation over both, since the two vectors are independent). The expectation of $\overline{\mathrm{err}}$ is the average of the second. Subtract. $\square$
The proof used no distribution beyond means and variances, did not need the errors of different observations to be independent of each other, and did not look inside the fitting rule. Hastie et al. (2009, eq. 7.21) state the identity and leave the squared-error case as their Exercise 7.4; Model Selection derives it in the same way before specializing to least squares; Efron (2004) calls penalties of this form covariance penalties and treats $C_p$, Akaike's criterion and Stein's unbiased risk estimate as members of one family.
The covariance measures how strongly each response pulls its own fitted value. For a common variance $\sigma^2$ the effective degrees of freedom of the rule are defined as
$$\operatorname{df}(\hat{\mathbf{y}}) = \frac{1}{\sigma^2}\sum_{i=1}^n \operatorname{Cov}(\hat y_i, y_i), \qquad \text{so that} \qquad \omega = \frac{2\sigma^2}{n}\operatorname{df}(\hat{\mathbf{y}})$$
(Hastie et al., 2009, eq. 7.33). Ye (1998) defined a quantity of the same kind, the generalized degrees of freedom of any modeling procedure, including variable selection, through the sensitivity of each fitted value to perturbations of its own response, a definition that his abstract says needs no analytic knowledge of the procedure.
Example (the two extremes). If the rule interpolates, $\hat{\mathbf{y}} = \mathbf{y}$, then $\operatorname{Cov}(\hat y_i, y_i) = \sigma^2$, the degrees of freedom are $n$, the training error is 0 and the in-sample error is $2\sigma^2$: all of the expected error is optimism. If the rule ignores the data and returns fixed numbers, every covariance is 0 and the training error is an unbiased estimate of the in-sample error, however poor both are. Every useful rule lies between the two.
Example (a misreading: optimism is not always positive). The theorem is about the expectation. On a particular data set the optimism $\mathrm{Err}_{\mathrm{in}} - \overline{\mathrm{err}}$ can be negative, for instance when the noise happens to push the responses away from a line that is fitted to them. Only its average over training sets is $2\sigma^2\operatorname{df}/n$, which is why a penalty can correct the training error on average and not sample by sample (Hastie et al., 2009, §7.4, call $\omega$ the quantity that can usually be estimated, rather than the optimism itself).
Linear smoothers: degrees of freedom are a trace
A rule is a linear smoother if $\hat{\mathbf{y}} = S\mathbf{y}$ for an $n \times n$ matrix $S$ that depends on the inputs but not on the responses (Hastie et al., 2009, eq. 7.31). Least squares on fixed columns is one, with $S = H$, the hat matrix. So are ridge regression with a fixed penalty, smoothing splines with a fixed penalty, kernel smoothers with a fixed bandwidth and nearest-neighbor averages with a fixed number of neighbors.
Theorem 2 (degrees of freedom of a linear smoother). If $\hat{\mathbf{y}} = S\mathbf{y}$ with $S$ fixed, and the errors are uncorrelated with variances $\sigma_i^2$, then
$$\sum_{i=1}^n \operatorname{Cov}(\hat y_i, y_i) = \sum_{i=1}^n s_{ii}\sigma_i^2, \qquad \omega = \frac{2}{n}\sum_{i=1}^n s_{ii}\sigma_i^2.$$
With a common variance, $\operatorname{df} = \operatorname{tr} S$ and $\omega = 2\sigma^2\operatorname{tr}(S)/n$. For least squares on $p$ linearly independent columns, $\operatorname{df} = p$.
Proof. The cross-covariance of $S\mathbf{y}$ with $\mathbf{y}$ is $S\operatorname{Cov}(\mathbf{y}) = S\Sigma$, with $\Sigma = \operatorname{diag}(\sigma_1^2, \ldots, \sigma_n^2)$, by the bilinearity of covariance (Expectation, Variance and Covariance). Its $i$th diagonal entry is $\operatorname{Cov}(\hat y_i, y_i) = \sum_j s_{ij}\operatorname{Cov}(y_j, y_i) = s_{ii}\sigma_i^2$, because the errors are uncorrelated. Summing gives the first formula, and Theorem 1 gives $\omega$. With $\sigma_i^2 = \sigma^2$ the sum is $\sigma^2\operatorname{tr}S$. For least squares, $\operatorname{tr}H = p$ by Theorem 2 of The Geometry of Least Squares. $\square$
Hastie et al. (2009, eq. 7.32) take $\operatorname{tr}S$ as the definition of the effective number of parameters of a linear smoother and leave its covariance form as their Exercise 7.5. The heteroscedastic form shows something the homoscedastic one hides: the optimism weights each point's variance by its leverage $s_{ii}$. A fit that bends to follow the points where the noise is largest is more optimistic than its trace suggests.
Example (ridge regression). Ridge regression on standardized inputs is the linear smoother $S_\lambda = X(X^{\mathsf T}X + \lambda I)^{-1}X^{\mathsf T}$, and with the singular values $d_j$ of $X$ its trace is $\sum_j d_j^2/(d_j^2 + \lambda)$: Theorem 2 of Ridge and Lasso Regression proves this, and Theorem 6 of The Singular Value Decomposition in Statistics reads ridge as a filter that multiplies the $j$th singular direction by $d_j^2/(d_j^2 + \lambda)$. Theorem 2 above supplies what those pages took as a definition: the trace is the covariance that drives the optimism. Each direction contributes its filter factor, between 0 and 1, so ridge with ten inputs has between 0 and 10 degrees of freedom for its slopes, and one more for the intercept.
Example (a misreading: "degrees of freedom count the coefficients"). Ridge with ten inputs estimates ten slopes at every penalty, but its degrees of freedom fall continuously from 11 to 1 (with the intercept) as the penalty grows; the diabetes table below shows the values. Degrees of freedom count how much the fit follows the noise, and coefficients that are shrunk follow it less.
Polynomial fits to blood pressure by age
The running data are the 5,176 adults of the Linear Models unit: NHANES 2017 to 2018 adults (National Center for Health Statistics, 2020) with a systolic pressure (the mean of their readings) and a body mass index, aged 18 to 80, with 80 standing for 80 and over. The adults are treated as a finite population. At each of the 63 ages the population has a mean pressure $f(a)$ and a variance $\sigma^2(a)$ (divisor the number of adults of that age). The variance rises with age: at 18 the mean is 111.8 and the standard deviation 11.1 (variance 124), at 80 the mean is 143.3 and the standard deviation 22.2 (variance 494). The average within-age variance across all 5,176 adults is 297.68.
This population defines a fixed-input model exactly. A sample of 50 adults fixes the ages $a_1, \ldots, a_{50}$. A response at age $a_i$ is a pressure drawn at random from the adults of that age, so $\mu_i = f(a_i)$ and $\sigma_i^2 = \sigma^2(a_i)$, and the errors are independent, heteroscedastic and not normal. Every quantity of Theorem 2 is known: $\mathrm{Err}_{\mathrm{in}} = \frac1n\sum_i[\sigma_i^2 + (\mu_i - \hat y_i)^2]$ can be computed for any fit, and the expected optimism is $\frac2n\sum_i h_{ii}\sigma_i^2$. Polynomials of degree 0 to 6 in age are fitted by least squares (columns $1, z, \ldots, z^6$ with $z = (\text{age} - 49)/18$), so $p$ runs from 1 to 7.
For each of 30 seeds, 50 adults were drawn, and 4,000 response vectors were drawn from the age strata at their ages. The simulated optimism is the average of $\mathrm{Err}_{\mathrm{in}} - \overline{\mathrm{err}}$ over the 4,000 response vectors. The table gives medians over the 30 seeds; $\bar\sigma^2$ is the average of the fifty $\sigma_i^2$, and the last column is explained in the next section.
| Fit | $p$ | Simulated optimism | Theorem 2, exact | $2p\bar\sigma^2/n$ | $C_p$ minus $\mathrm{Err}_{\mathrm{in}}$ |
|---|---|---|---|---|---|
| degree 0 | 1 | 12.04 | 12.06 | 12.06 | 0.22 |
| degree 1 | 2 | 23.16 | 23.26 | 24.11 | 0.87 |
| degree 2 | 3 | 35.71 | 35.82 | 36.17 | 0.77 |
| degree 3 | 4 | 47.63 | 48.01 | 48.23 | 0.36 |
| degree 4 | 5 | 58.60 | 58.71 | 60.28 | 1.35 |
| degree 5 | 6 | 69.75 | 70.21 | 72.34 | 2.48 |
| degree 6 | 7 | 80.79 | 81.23 | 84.40 | 3.71 |
Three observations, each about this experiment.
- The theorem holds within simulation error. For each of the 210 combinations of seed and degree, the difference between the simulated and the exact optimism was divided by its Monte Carlo standard error; 203 of the 210 were within two standard errors, about the 95% expected of a correct formula. For degree 6 the simulated optimism had median 80.79 (interquartile range 79.71 to 83.38) and the exact value median 81.23 (79.45 to 83.29).
- Optimism grows by about $2\sigma^2/n$ per coefficient, here between 10.70 and 12.56 per added column in the medians of the exact values. For the sample of the opening (the first seed), the exact expected optimism rises by 57.09 from the line to degree 6, while that sample's training error fell by only 27.4 over the same five columns, from 187.0 to 159.6. The better fit is more than paid for by the added optimism; the $C_p$ table below makes the same comparison with an estimated variance.
- Unequal variances changed little here. The ratio of the exact optimism to the equal-variance formula $2p\bar\sigma^2/n$ for degree 6 had median 0.97 (interquartile range 0.94 to 1.02). Polynomial leverage is highest at both ends of the age range, where the variance is low at the young end and high at the old end, and in these samples the two ends nearly balance. With all the high-leverage points at the noisy end the weighting would matter more.
Mallows' Cp is unbiased
Theorem 1 says that the training error falls short of the in-sample error by $2\sigma^2\operatorname{df}/n$ on average. Adding an estimate of that amount back gives an estimate of the in-sample error.
Theorem 3 ($C_p$ is unbiased). Let $\hat{\mathbf{y}} = S\mathbf{y}$ be a linear smoother with fixed $S$, the errors uncorrelated with common variance $\sigma^2$, and $\hat\sigma^2$ any statistic with $E[\hat\sigma^2] = \sigma^2$. Then
$$C_p = \overline{\mathrm{err}} + \frac{2\operatorname{tr}(S)\,\hat\sigma^2}{n}$$
satisfies $E[C_p] = E[\mathrm{Err}_{\mathrm{in}}]$. This holds whether or not the smoother's fitted values are unbiased for $\boldsymbol\mu$.
Proof. By linearity of expectation, $E[C_p] = E[\overline{\mathrm{err}}] + 2\operatorname{tr}(S)\sigma^2/n$, and by Theorems 1 and 2 this is $E[\mathrm{Err}_{\mathrm{in}}]$. $\square$
The proof is short because all the work was done in Theorem 1, and three points about it are worth stating.
- The candidate may be wrong. Its bias, $\boldsymbol\mu - E[\hat{\mathbf{y}}]$, appears in the training error and in the in-sample error alike, and the penalty does not have to account for it. A straight line fitted to a curved truth is scored fairly.
- The variance estimate must be unbiased, and that does need a correct model. The usual choice is $\hat\sigma^2 = \mathrm{RSS}_F/(n - p_F)$ from least squares on a fuller set of $p_F$ columns. By Theorem 1 of The Gauss–Markov Theorem, $E[\mathrm{RSS}_F] = \sigma^2(n - p_F)$ when the fuller model's columns can reproduce $\boldsymbol\mu$. If they cannot, $E[\mathrm{RSS}_F]$ exceeds that by $\lVert(I - H_F)\boldsymbol\mu\rVert^2$ (the same theorem's computation with the mean term kept), and $C_p$ overstates every candidate's error, the larger ones more.
- No independence is needed. The variance estimate may be computed from the same responses, and correlated with the training error, because only expectations are added.
Hastie et al. (2009, eq. 7.26) write $C_p$ in this form for least squares with $d$ parameters; Mallows (1973), whose name the statistic bears, discusses its interpretation, and his abstract describes extending it "to encompass arbitrary linear estimates of the regression coefficients, for example Ridge estimates", which is the smoother form above. The scaled form $\mathrm{RSS}/\hat\sigma^2 - n + 2p$ of Model Selection ranks models identically.
Back to the experiment. The last column of the polynomial table is the median over seeds of the simulated average of $C_p - \mathrm{Err}_{\mathrm{in}}$ over the 4,000 response vectors, with $\hat\sigma^2$ from the degree 6 fit on the same responses. It is positive at every degree and largest for degree 6, 3.71, which is 4.6% of that degree's exact optimism. Both conditions of Theorem 3 fail slightly here. A polynomial of degree 6 does not reproduce the population's mean curve exactly, and the variances are unequal, so the estimate is not unbiased for the leverage-weighted variance that the penalty should use: across seeds, the average of $\hat\sigma^2$ exceeded $\bar\sigma^2$ by a median of 5.2, against $\bar\sigma^2$ of median 301.4. The bias is small next to the differences between candidates.
Example (the opening sample). For the 50 adults of the first seed, whose ages run from 18 (the youngest) to 80 (the oldest), with their own measured pressures, $\hat\sigma^2 = 185.5$ from the degree 6 fit (below the population's 297.68: this sample happens to be less variable). Then
| Degree | $p$ | $\overline{\mathrm{err}}$ | $C_p$ |
|---|---|---|---|
| 0 | 1 | 267.7 | 275.1 |
| 1 | 2 | 187.0 | 201.8 |
| 2 | 3 | 180.4 | 202.6 |
| 3 | 4 | 175.7 | 205.4 |
| 4 | 5 | 170.5 | 207.6 |
| 5 | 6 | 162.7 | 207.2 |
| 6 | 7 | 159.6 | 211.5 |
The training error falls at every degree; $C_p$ is smallest for the straight line. Each coefficient costs $2\hat\sigma^2/n = 7.42$. From the line to degree 6 the training error falls by 27.4 in all, less than the 37.1 that five more coefficients cost, and no intermediate degree recovers its cost either.
Ridge regression of the diabetes data
The diabetes data of Model Selection and Ridge and Lasso Regression record ten inputs and a measure of disease progression for 442 patients (Efron, Hastie, Johnstone and Tibshirani, 2004). As on the ridge page, the inputs are standardized (divisor $n$) and the penalty is written $\kappa = \lambda/n$. The fitted values are $\bar y\mathbf{1} + S_\lambda(\mathbf{y} - \bar y\mathbf{1})$, a linear smoother whose trace is $1 + \sum_j d_j^2/(d_j^2 + \lambda)$, the 1 for the intercept. The variance estimate is the ten-input least-squares value $\hat\sigma^2 = 1{,}263{,}986/431 = 2{,}932.7$, as in Model Selection.
| $\kappa$ | df | $\overline{\mathrm{err}}$ | $C_p$ |
|---|---|---|---|
| 0 | 11.00 | 2,859.7 | 3,005.7 |
| 0.01 | 10.25 | 2,866.3 | 3,002.3 |
| 0.1 | 8.64 | 2,890.5 | 3,005.1 |
| 1 | 4.94 | 3,254.1 | 3,319.7 |
| 10 | 1.83 | 4,810.0 | 4,834.3 |
$C_p$ is smallest at $\kappa = 0.0074$, with 10.38 degrees of freedom and $C_p = 3{,}002.3$, against 3,005.7 for least squares ($\kappa = 0$). The ridge page found $\kappa = 0.0042$ by exact leave-one-out cross-validation and $\kappa = 0.0074$ by generalized cross-validation, and this script recomputes both minimizers (leave-one-out at 0.0042, generalized cross-validation at 0.0074). The agreement of $C_p$ with generalized cross-validation is expected: as Cross-Validation notes, generalized cross-validation is approximately the training error times $1 + 2\operatorname{df}/n$, a covariance penalty with the training error standing in for $\sigma^2$. All three criteria say the same thing as the ridge page: on the full data, ridge barely changes the estimated error.
A check of the covariance definition. Theorem 2 is exact, so a simulation cannot improve on it, but it can check the definition of the degrees of freedom independently of the trace. Taking the least-squares fit as the true mean and $\sigma^2 = 2{,}932.7$, 1,000 normal response vectors were drawn for each of 30 seeds, the ridge fit at $\kappa = 0.0074$ computed for each, and $\sum_i\operatorname{Cov}(\hat y_i, y_i)/\sigma^2$ estimated by the sample covariances. The estimate had median 10.37 (interquartile range 10.30 to 10.46) against the trace 10.38.
Fits that are not linear: Stein's lemma
For a rule that is not a linear smoother, $\operatorname{Cov}(\hat y_i, y_i)$ has no trace formula, and computing it seems to need the unknown $\mu_i$. For normal errors Stein's lemma removes the difficulty: the covariance of a smooth function of a normal variable with that variable is the variance times the expected derivative. Hierarchical Models and Shrinkage proves the lemma for functions with bounded derivatives (its Lemma 2). The version below allows unbounded functions and finitely many corners, which soft thresholding needs, and shows exactly what a jump adds.
Lemma 1 (Stein's lemma). Let $Z$ be normal with mean $\eta$ and variance $\sigma^2$. Let $g$ be continuous on the real line and continuously differentiable except at finitely many points, with $E[|g'(Z)|] < \infty$ and $E[|(Z - \eta)g(Z)|] < \infty$. Then
$$E[(Z - \eta)\,g(Z)] = \sigma^2\,E[g'(Z)].$$
Proof. Write $\varphi_\sigma(z) = \frac{1}{\sigma\sqrt{2\pi}}e^{-(z - \eta)^2/(2\sigma^2)}$ for the density of $Z$. Its derivative is $\varphi_\sigma'(z) = -\frac{z - \eta}{\sigma^2}\varphi_\sigma(z)$, so $(z - \eta)\varphi_\sigma(z) = -\sigma^2\varphi_\sigma'(z)$. Take $a < b$ with the exceptional points $t_1 < \cdots < t_m$ of $g$ inside $(a, b)$, and set $t_0 = a$, $t_{m+1} = b$. For small $\epsilon > 0$, $g$ is continuously differentiable on $[t_j + \epsilon, t_{j+1} - \epsilon]$, and integration by parts there, followed by $\epsilon \to 0$, gives the identity below for each piece. In the limit the boundary values converge by the continuity of $g$, the integral of $g'\varphi_\sigma$ converges because $g'\varphi_\sigma$ is absolutely integrable (by $E[|g'(Z)|] < \infty$), and the integral of $g\varphi_\sigma'$ converges because $g\varphi_\sigma'$ is bounded on the closed piece:
$$\int_{t_j}^{t_{j+1}} g\,\varphi_\sigma'\,dz = g(t_{j+1})\varphi_\sigma(t_{j+1}) - g(t_j)\varphi_\sigma(t_j) - \int_{t_j}^{t_{j+1}} g'\varphi_\sigma\,dz.$$
Summing over the pieces, the values at the interior points $t_1, \ldots, t_m$ cancel in pairs, because $g$ is continuous there. Hence
$$\int_a^b (z - \eta)g(z)\varphi_\sigma(z)\,dz = \sigma^2\int_a^b g'(z)\varphi_\sigma(z)\,dz - \sigma^2\big[g(b)\varphi_\sigma(b) - g(a)\varphi_\sigma(a)\big]. \qquad (1)$$
Let $b \to \infty$ with $a$ fixed. Both integrals converge, because their integrands are absolutely integrable by the two assumptions, so $g(b)\varphi_\sigma(b)$ converges to some number $c$. If $c$ were not 0, then $|g(z)|\varphi_\sigma(z) \ge |c|/2$ for all large $z$, and $|(z - \eta)g(z)|\varphi_\sigma(z) \ge |c|\,|z - \eta|/2$ there, which is not integrable, against the assumption. So $c = 0$, and in the same way $g(a)\varphi_\sigma(a) \to 0$ as $a \to -\infty$. Letting $a \to -\infty$ and $b \to \infty$ in (1) gives the lemma. $\square$
The proof also shows what goes wrong when $g$ jumps. At a jump the values of $g$ from the two sides do not cancel, and each jump at a point $t$ leaves the extra term $\sigma^2\,\varphi_\sigma(t)$ times the size of the jump. That term returns below.
Theorem 4 (degrees of freedom as an expected derivative; Stein's unbiased risk estimate). Let $y_1, \ldots, y_n$ be independent and normal, $y_i$ with mean $\mu_i$ and variance $\sigma^2$. Let $\hat y_i = g_i(\mathbf{y})$, where for each $i$ and each fixed value of the other coordinates, $t \mapsto g_i(y_1, \ldots, t, \ldots, y_n)$ is continuous and continuously differentiable except at finitely many points. Assume $E[|(y_i - \mu_i)\hat y_i|] < \infty$ and $E[|\partial \hat y_i/\partial y_i|] < \infty$ for each $i$. Then
$$\operatorname{Cov}(\hat y_i, y_i) = \sigma^2\,E\!\left[\frac{\partial \hat y_i}{\partial y_i}\right], \qquad \operatorname{df}(\hat{\mathbf{y}}) = E\!\left[\sum_{i=1}^n \frac{\partial \hat y_i}{\partial y_i}\right],$$
and
$$\mathrm{SURE} = \lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2 - n\sigma^2 + 2\sigma^2\sum_{i=1}^n\frac{\partial \hat y_i}{\partial y_i}$$
is an unbiased estimate of the risk $E\lVert\hat{\mathbf{y}} - \boldsymbol\mu\rVert^2$.
Proof. Fix $i$ and the other coordinates. Given them, $y_i$ is still normal with mean $\mu_i$ and variance $\sigma^2$, by independence, and Lemma 1 applied to $t \mapsto g_i$ gives $E[(y_i - \mu_i)\hat y_i \mid \text{others}] = \sigma^2 E[\partial\hat y_i/\partial y_i \mid \text{others}]$. The integrability conditions of the lemma hold for almost every value of the other coordinates, because the unconditional expectations are finite. Averaging over the other coordinates gives $E[(y_i - \mu_i)\hat y_i] = \sigma^2E[\partial\hat y_i/\partial y_i]$; the interchange of the order of integration is Fubini's theorem, cited as in Random Variables and Distribution Functions. As in the proof of Theorem 1, the left side is $\operatorname{Cov}(\hat y_i, y_i)$. Summing and dividing by $\sigma^2$ gives the degrees of freedom.
For the risk, expand $\hat{\mathbf{y}} - \boldsymbol\mu = (\hat{\mathbf{y}} - \mathbf{y}) + (\mathbf{y} - \boldsymbol\mu)$:
$$\lVert\hat{\mathbf{y}} - \boldsymbol\mu\rVert^2 = \lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2 + \lVert\mathbf{y} - \boldsymbol\mu\rVert^2 + 2\sum_i(\hat y_i - y_i)(y_i - \mu_i).$$
The second term has expectation $n\sigma^2$. In the third, $E[(\hat y_i - y_i)(y_i - \mu_i)] = \sigma^2E[\partial\hat y_i/\partial y_i] - \sigma^2$ by the first part. Adding, $E\lVert\hat{\mathbf{y}} - \boldsymbol\mu\rVert^2 = E\lVert\mathbf{y} - \hat{\mathbf{y}}\rVert^2 - n\sigma^2 + 2\sigma^2E[\sum_i\partial\hat y_i/\partial y_i] = E[\mathrm{SURE}]$. $\square$
The estimate is due to Stein (1981), whose abstract describes "an unbiased estimate of risk" obtained "for an arbitrary estimate" of the means of independent normal variables. Its value is that the derivative is computed from the data alone, with no knowledge of $\boldsymbol\mu$. The risk differs from $n\,\mathrm{Err}_{\mathrm{in}}$ by the constant $n\sigma^2$, so $\mathrm{SURE}/n + \sigma^2$ estimates the in-sample error, and for a linear smoother it is $C_p$ with $\sigma^2$ known.
Soft and hard thresholding
Two rules for one normal observation $y$ with mean $\mu$ and variance 1, with a threshold $\lambda > 0$, show what the theorem can and cannot cover.
- Soft thresholding, $\hat y = \operatorname{sign}(y)\max(|y| - \lambda, 0)$, sets small values to zero and moves large ones toward zero by $\lambda$. It is the lasso in the orthonormal case (Theorem 5 of Ridge and Lasso Regression).
- Hard thresholding, $\hat y = y\,\mathbf{1}\{|y| > \lambda\}$, keeps large values unchanged and sets small ones to zero. In the orthonormal case it is best subset selection with a fixed charge for each input kept.
Proposition 1 (degrees of freedom of thresholding). For $y$ normal with mean $\mu$ and variance 1, with $\varphi$ and $\Phi$ the standard normal density and distribution function,
$$\operatorname{df}_{\text{soft}} = P(|y| > \lambda) = \Phi(-\lambda - \mu) + 1 - \Phi(\lambda - \mu),$$
$$\operatorname{df}_{\text{hard}} = P(|y| > \lambda) + \lambda\big[\varphi(\lambda - \mu) + \varphi(\lambda + \mu)\big].$$
Proof. Soft thresholding is continuous, with derivative $\mathbf{1}\{|y| > \lambda\}$ except at $\pm\lambda$. Its absolute value is at most $|y|$, so $E[|(y - \mu)\hat y|] \le E[|y - \mu|\,|y|] < \infty$, and the derivative is bounded. Lemma 1 gives $\operatorname{Cov}(\hat y, y) = E[\mathbf{1}\{|y| > \lambda\}]$.
Hard thresholding jumps by $\lambda$ at $y = \lambda$ and at $y = -\lambda$, so the lemma does not apply, and we compute directly. Since $E[y - \mu] = 0$, $\operatorname{Cov}(\hat y, y) = E[(y - \mu)\hat y]$. With $(y - \mu)\varphi(y - \mu) = -\frac{d}{dy}\varphi(y - \mu)$ and integration by parts,
$$\int_\lambda^\infty y\,(y - \mu)\varphi(y - \mu)\,dy = \Big[-y\,\varphi(y - \mu)\Big]_\lambda^\infty + \int_\lambda^\infty\varphi(y - \mu)\,dy = \lambda\varphi(\lambda - \mu) + P(y > \lambda),$$
$$\int_{-\infty}^{-\lambda} y\,(y - \mu)\varphi(y - \mu)\,dy = \Big[-y\,\varphi(y - \mu)\Big]_{-\infty}^{-\lambda} + \int_{-\infty}^{-\lambda}\varphi(y - \mu)\,dy = \lambda\varphi(\lambda + \mu) + P(y < -\lambda),$$
using $\varphi(-\lambda - \mu) = \varphi(\lambda + \mu)$. The sum is the stated formula. $\square$
At $\lambda = 2$:
| $\mu$ | soft | hard |
|---|---|---|
| 0 | 0.046 | 0.261 |
| 1 | 0.160 | 0.653 |
| 2 | 0.500 | 1.298 |
| 3 | 0.841 | 1.325 |
| 5 | 0.999 | 1.008 |
For soft thresholding the degrees of freedom are the probability that the coordinate is kept: on average it costs exactly as much as it keeps. This is the one-coordinate case of the theorem of Zou, Hastie and Tibshirani (2007) that the number of nonzero lasso coefficients is an unbiased estimate of the lasso's degrees of freedom, which Ridge and Lasso Regression checks by simulation. Hard thresholding costs more than it keeps: at $\mu = 0$ the jump term is $2 \times 2\varphi(2)$ with $\varphi(2) = 0.0540$, and the degrees of freedom are 5.7 times the probability of keeping the coordinate. Near the threshold, at $\mu = 2$ and $\mu = 3$, the hard rule has more than one degree of freedom for a single number: a response that crosses the threshold moves its fitted value by more than its own change. A simulation of 200,000 draws at $\mu = 0$ for each of 30 seeds gave covariances with median 0.045 (interquartile range 0.045 to 0.046) for the soft rule and 0.260 (0.257 to 0.262) for the hard rule, in agreement with 0.046 and 0.261.
A soft rule has no jump; it pays for keeping a coordinate by shrinking it. The hard rule keeps the full value, and the jump term is the price of the decision.
The price of choosing
Model Selection warned, following Hastie et al. (2009, §7.5), that when a subset is chosen as the best of many, the optimism exceeds $2p\sigma^2/n$ for the $p$ coefficients finally fitted. The degrees of freedom make the warning exact in a small case.
Proposition 2 (the best of $m$ noise inputs). Let $z_1, \ldots, z_m$ be independent standard normal (the least-squares coordinates of $m$ orthonormal inputs whose true coefficients are all 0, with $\sigma = 1$). Keep the coordinate with the largest $|z_j|$ and set the others to zero. The degrees of freedom of this rule are $E[\max_j z_j^2]$.
Proof. The degrees of freedom may be computed in these coordinates. With $Q$ the $n \times m$ matrix of the orthonormal inputs, $\mathbf{z} = Q^{\mathsf T}\mathbf{y}$ and $\hat{\mathbf{y}} = Q\hat{\mathbf{z}}$, so $\sum_i\operatorname{Cov}(\hat y_i, y_i) = \operatorname{tr}\operatorname{Cov}(Q\hat{\mathbf{z}}, \mathbf{y}) = \operatorname{tr}\big(Q\operatorname{Cov}(\hat{\mathbf{z}}, \mathbf{y})\big) = \operatorname{tr}\big(\operatorname{Cov}(\hat{\mathbf{z}}, \mathbf{y})Q\big) = \operatorname{tr}\operatorname{Cov}(\hat{\mathbf{z}}, Q^{\mathsf T}\mathbf{y}) = \sum_j\operatorname{Cov}(\hat z_j, z_j)$, using $\operatorname{tr}(AB) = \operatorname{tr}(BA)$. The fitted coordinate is $\hat z_j = z_j\mathbf{1}\{j = J\}$, where $J$ is the index of the largest $|z_j|$ (ties have probability 0). Since $E[z_j] = 0$, $\operatorname{Cov}(\hat z_j, z_j) = E[z_j\hat z_j] = E[z_j^2\mathbf{1}\{j = J\}]$. Summing over $j$, exactly one indicator is 1, and the sum is $E[z_J^2] = E[\max_j z_j^2]$. $\square$
The expectation of the largest of $m$ independent chi-squared variables with one degree of freedom is $\int_0^\infty(1 - F(t)^m)\,dt$, with $F$ their distribution function, computed numerically:
| $m$ | df of the best single input |
|---|---|
| 1 | 1.00 |
| 2 | 1.64 |
| 5 | 2.77 |
| 10 | 3.80 |
One coefficient chosen as the best of 10 costs 3.80 degrees of freedom, not 1; a simulation with 100,000 draws for each of 30 seeds gave a median of 3.80 (interquartile range 3.79 to 3.80) for the best of 10. A penalty of $2\sigma^2$ for the chosen coefficient, which $C_p$ and Akaike's criterion would charge, is too small by a factor of almost four. The same effect, measured on held-out data, is the selection optimism of Training, Validation and Test Sets and the winner's curse that Selective Inference and the Garden of Forking Paths corrects. Ye's (1998) generalized degrees of freedom, defined through the sensitivity of each fitted value to its own response, apply to such procedures, variable selection included; the $C_p$ and Akaike penalties are honest only for a model fixed before the data were seen.
The hard-threshold rule of the previous section is the version with a fixed threshold rather than a fixed number of inputs. In the orthonormal case with $\sigma$ known, $C_p$ keeps coordinate $j$ exactly when $z_j^2 > 2$, since keeping it lowers the residual sum of squares by $z_j^2$ and costs 2: $C_p$ applied coordinate by coordinate is hard thresholding at $\lambda = \sqrt2$, and so it carries the jump term too. Akaike's Information Criterion, Derived returns to this threshold from the side of the likelihood, where it becomes the probability 0.157 with which the criterion keeps a useless parameter.
What is proved, what is cited, what the experiment shows
Proved on this page: the covariance identity for the expected optimism of any fitting rule with finite second moments (Theorem 1); the degrees of freedom of a linear smoother as its trace, and the leverage-weighted form for unequal variances (Theorem 2); the unbiasedness of $C_p$ for the in-sample error under an unbiased variance estimate, for any candidate, correct or not (Theorem 3); Stein's lemma for continuous, piecewise continuously differentiable functions of a normal variable (Lemma 1); the degrees of freedom as an expected derivative and Stein's unbiased risk estimate (Theorem 4); the exact degrees of freedom of soft and hard thresholding (Proposition 1) and of choosing the best of $m$ noise inputs (Proposition 2).
Cited: the definitions and equation numbers of Hastie et al. (2009, §§7.4 to 7.6); Fubini's theorem, through Random Variables and Distribution Functions; the trace of ridge regression, from Ridge and Lasso Regression; the expected residual sum of squares, from The Gauss–Markov Theorem; the extra-sample results of Rosset and Tibshirani (2020); the lasso's degrees of freedom (Zou et al., 2007); the history and scope of $C_p$ (Mallows, 1973), of the unbiased risk estimate (Stein, 1981), of generalized degrees of freedom (Ye, 1998) and of covariance penalties (Efron, 2004), each from its abstract.
What the experiments show: on 30 samples of 50 NHANES adults with responses drawn from the population's age strata, the simulated optimism of polynomial fits agreed with Theorem 2's exact value within simulation error, grew by 10.70 to 12.56 per coefficient, and differed from the equal-variance formula by a few percent; $C_p$ with a degree 6 variance estimate overstated the in-sample error by at most 3.71. On the diabetes data, $C_p$ for ridge regression chose the penalty that generalized cross-validation chose, and a direct estimate of the covariance degrees of freedom matched the trace. The thresholding and selection formulas were confirmed by simulation. These are observations of these experiments.
Worked problems
The problems were written for this article, except that Problem 1 is Exercise 7.6 of Hastie et al. (2009), solved here in our own words; each numerical answer is checked by the article's script, and Problem 3 is an algebraic derivation.
Problem 1 (nearest neighbors). A nearest-neighbor regression predicts at each input $x_i$ the average of the responses at the $k$ inputs nearest to $x_i$, counting $x_i$ itself. The $n = 50$ inputs are distinct and $k = 5$. Find the degrees of freedom and the expected optimism when the errors have variance $\sigma^2$.
Solution. The rule is a linear smoother: row $i$ of $S$ has the entry $1/k$ in the $k$ columns of the neighbors of $x_i$ and 0 elsewhere, and it does not depend on the responses. Because $x_i$ is its own nearest neighbor, $s_{ii} = 1/k$. By Theorem 2, $\operatorname{df} = \operatorname{tr}S = n/k = 50/5 = 10$, and $\omega = 2\sigma^2 \cdot 10/50 = 0.4\sigma^2$. Fewer neighbors mean more degrees of freedom; with $k = 1$ the rule interpolates and $\operatorname{df} = n$.
Problem 2 (a running mean). Seven equally spaced inputs are smoothed by a running mean of three: each interior point is replaced by the average of itself and its two neighbors, and each end point by the average of itself and its single neighbor. Find the degrees of freedom and, with $\sigma^2 = 400$ (a standard deviation of 20 mm Hg), the expected optimism.
Solution. The diagonal of $S$ is $\tfrac12$ at the two ends and $\tfrac13$ at the five interior points, so $\operatorname{tr}S = \tfrac12 + 5 \cdot \tfrac13 + \tfrac12 = 8/3$, or 2.67. By Theorem 2, $\omega = 2 \cdot 400 \cdot (8/3)/7 = 6{,}400/21 = 304.8$ (mm Hg squared). The smoother uses seven responses but costs fewer than three degrees of freedom: each fitted value depends on its own response only through a weight of one third or one half.
Problem 3 ($C_p$ for a candidate that is wrong). Responses at $n$ inputs have mean $\mu_i = \beta x_i$ with $\sum_i x_i = 0$, $\beta \ne 0$, and common variance $\sigma^2$. The candidate fits the mean only, $\hat y_i = \bar y$. Show directly that $E[C_p] = E[\mathrm{Err}_{\mathrm{in}}]$ when $\hat\sigma^2$ is unbiased.
Solution. Here $S = \frac1n\mathbf{1}\mathbf{1}^{\mathsf T}$, with trace 1, and $E[\bar y] = \frac1n\sum_i\beta x_i = 0$. The fresh-response error is $E[(y_i^0 - \bar y)^2] = \sigma^2 + \operatorname{Var}(\bar y) + \mu_i^2 = \sigma^2 + \sigma^2/n + \beta^2x_i^2$, so $E[\mathrm{Err}_{\mathrm{in}}] = \sigma^2(1 + 1/n) + \beta^2\overline{x^2}$, with $\overline{x^2} = \frac1n\sum_i x_i^2$. The training error is $\frac1n\sum_i(y_i - \bar y)^2$, whose expectation is $\frac{n-1}{n}\sigma^2 + \beta^2\overline{x^2}$ (the sample variance of the $y_i$ with divisor $n - 1$ has expectation $\sigma^2$ plus the spread of the means, here $\frac{n}{n-1}\beta^2\overline{x^2}$). Adding the penalty $2\sigma^2 \cdot 1/n$ gives $E[C_p] = \sigma^2(1 + 1/n) + \beta^2\overline{x^2}$, equal to $E[\mathrm{Err}_{\mathrm{in}}]$. The bias $\beta^2\overline{x^2}$ appears on both sides, which is point 1 after Theorem 3.
Problem 4 (Stein's estimate by hand). One observation $y$, normal with unknown mean and variance 1, is soft-thresholded at $\lambda = 2$. Compute SURE for $y = 3$ and for $y = 1$.
Solution. By Theorem 4 with $n = 1$, $\mathrm{SURE} = (y - \hat y)^2 - 1 + 2\,\mathbf{1}\{|y| > 2\}$. For $y = 3$: $\hat y = 1$, so SURE $= 4 - 1 + 2 = 5$. For $y = 1$: $\hat y = 0$, so SURE $= 1 - 1 + 0 = 0$. The estimate can be zero, and even negative (for $|y| < 1$ it is $y^2 - 1 < 0$), although the risk it estimates is positive: it is unbiased, not a bound, and averages to the risk only over repeated samples.
Summary
| Quantity | Formula | Where |
|---|---|---|
| Expected optimism, any rule | $\omega = \frac2n\sum_i\operatorname{Cov}(\hat y_i, y_i)$ | Theorem 1 |
| Degrees of freedom | $\operatorname{df} = \frac{1}{\sigma^2}\sum_i\operatorname{Cov}(\hat y_i, y_i)$ | definition |
| Linear smoother | $\operatorname{df} = \operatorname{tr}S$; with unequal variances $\omega = \frac2n\sum_i s_{ii}\sigma_i^2$ | Theorem 2 |
| Mallows' $C_p$ | $\overline{\mathrm{err}} + 2\operatorname{tr}(S)\hat\sigma^2/n$, unbiased if $E\hat\sigma^2 = \sigma^2$ | Theorem 3 |
| Normal errors, any smooth rule | $\operatorname{df} = E[\sum_i\partial\hat y_i/\partial y_i]$; SURE | Theorem 4 |
| Soft and hard thresholding | $P(\lvert y\rvert > \lambda)$; plus $\lambda[\varphi(\lambda - \mu) + \varphi(\lambda + \mu)]$ | Proposition 1 |
| Best of $m$ noise inputs | $E[\max_j z_j^2]$: 3.80 for $m = 10$ | Proposition 2 |
What we have learned
Training error is too small on average by exactly twice the average covariance between fitted values and their own responses, for any fitting rule, and that covariance, divided by the noise variance, is the effective number of parameters. For a linear smoother it is the trace of the smoother, which reduces to the number of coefficients for least squares and falls continuously for ridge; for a rule that decides which coefficients to keep it can be several times the number kept. Mallows' $C_p$ adds the covariance back and is unbiased whenever its variance estimate is, which makes it a fair judge of wrong candidates and an unfair one of candidates chosen by searching.
All of this concerned squared error. When a model is fitted by maximum likelihood, the natural loss is the negative log-likelihood of new data, and the same covariance argument becomes the derivation of Akaike's Information Criterion, Derived, which also shows that its penalty of two per parameter is exact only in the limit.
References
- Efron, B. (2004). The estimation of prediction error: covariance penalties and cross-validation. Journal of the American Statistical Association, 99(467), 619–632. https://doi.org/10.1198/016214504000000692 record · 2 pages
- Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407–499. https://doi.org/10.1214/009053604000000067 record · 18 pages
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. Sections 7.4 to 7.6. record · 31 pages
- Mallows, C. L. (1973). Some comments on $C_p$. Technometrics, 15(4), 661–675. https://doi.org/10.1080/00401706.1973.10489103 record · 2 pages
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Blood Pressure (BPX_J) and Body Measures (BMX_J) data files. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 95 pages
- Rosset, S., and Tibshirani, R. J. (2020). From fixed-X to random-X regression: bias-variance decompositions, covariance penalties, and prediction error estimation. Journal of the American Statistical Association, 115(529), 138–151. https://doi.org/10.1080/01621459.2018.1424632 (arXiv:1704.08160) record
- Stein, C. M. (1981). Estimation of the mean of a multivariate normal distribution. The Annals of Statistics, 9(6), 1135–1151. https://doi.org/10.1214/aos/1176345632 record · 2 pages
- Ye, J. (1998). On measuring and correcting the effects of data mining and model selection. Journal of the American Statistical Association, 93(441), 120–131. https://doi.org/10.1080/01621459.1998.10474094 record
- Zou, H., Hastie, T., and Tibshirani, R. (2007). On the "degrees of freedom" of the lasso. The Annals of Statistics, 35(5), 2173–2192. https://doi.org/10.1214/009053607000000127 record · 2 pages