Model Assessment and Selection: Cp, AIC, BIC, Cross-Validation, and the Bootstrap

Intuition Beginner

You have built a model and it predicts your training data well. The dangerous question is whether it will predict new data well, and the honest answer is almost always: not as well. A model fitted to a dataset has secretly memorised some of that dataset's random quirks, so it flatters itself when graded on the same data it learned from. Model assessment is the discipline of grading a model fairly, on data it has not seen, so that you can pick the model that will actually serve you in the future rather than the one that merely looks best in the rear-view mirror.

There are two complementary ways to do this. The first way reasons about how much the training score overstates the truth, and adds a penalty to correct for it. The more flexible the model, the bigger the penalty, because more flexibility means more memorising. Mallows' Cp, the Akaike information criterion, and the Bayesian information criterion are three such penalties, differing in how harshly they punish complexity.

The second way is more direct and needs no theory of the penalty: just hold some data back. Fit on part of the data, test on the part you hid, and average the results. This is cross-validation. Repeated holding-out, or resampling the data with replacement as the bootstrap does, gives a usable estimate of future error from the data you already have. Both routes chase the same target: the error you would suffer on tomorrow's data, not yesterday's.

Visual Beginner

Picture two curves drawn against model complexity rising from left to right. The training-error curve slides steadily downward: a more flexible model always fits the data it was trained on better. The test-error curve falls at first, bottoms out, then climbs back up as the model starts chasing noise. The gap between the two curves is the self-flattery, and it widens with complexity.

approach	what it does	needs noise estimate?
Cp / AIC / BIC	add a complexity penalty to training error	yes (Cp), no (cross-validation route)
cross-validation	hold data out, test on it, average	no
bootstrap (.632)	resample with replacement, blend train and held-out errors	no

The takeaway: training error is an over-optimistic ruler. Every method here is a way to recover the honest ruler, the U-shaped test curve, and to stop at its lowest point.

Worked example Beginner

You fit three models to $n=100$ data points and record the average squared training error for each. You also know, from repeated measurements, that the noise in each response has variance about ${\sigma }^2=1$. Mallows' Cp corrects each training error by adding $2$ times the number of parameters $d$ divided by $n$, multiplied by the noise variance.

Model A uses $d=2$ parameters and has training error $1.40$. The penalty is $2\times 2/100\times 1=0.04$, so its Cp score is $1.40+0.04=1.44$.

Model B uses $d=6$ parameters and has training error $1.05$. The penalty is $2\times 6/100\times 1=0.12$, so its Cp score is $1.05+0.12=1.17$.

Model C uses $d=20$ parameters and has training error $0.80$. The penalty is $2\times 20/100\times 1=0.40$, so its Cp score is $0.80+0.40=1.20$.

Now compare. The raw training errors say Model C is best, because $0.80$ is the smallest. But after the honesty penalty, Model B wins with $1.17$, just edging out Model C's $1.20$, and beating Model A's $1.44$ by a wide margin. The penalty caught Model C in the act of memorising: its training error was lowest only because twenty parameters let it trace the noise.

What this tells us: raw training error rewards complexity for the wrong reason. Adding a penalty that grows with the parameter count restores a fair contest, and here it tells you to prefer the six-parameter model over the twenty-parameter one.

Check your understanding Beginner

Formal definition Intermediate+

Fix the regression setting of 45.06.02: data $(X_i,Y_i)$ are i.i.d., $Y=f(X)+\epsilon$ with $\mathbb{E}[\epsilon \mid X]=0$ and $\mathrm{Var}(\epsilon \mid X=x)={\sigma }^2$, and a fitting procedure returns $\hat{f}$ from a training sample $\mathcal{D}$. Write fitted values ${\hat{y}}_i=\hat{f}(X_i)$ and a loss $L$, taken to be squared error $L(y,\hat{y})=(y-\hat{y}{)}^2$ unless stated.

Definition (training, in-sample, and expected error). The training error is $\overline{\mathrm{err}}=\frac{1}{n}{\sum }_{i=1}^{n}L(Y_i,{\hat{y}}_i)$. The in-sample error averages, at the same inputs $X_i$, over fresh responses $Y_i^{\text{new}}$: ${\mathrm{Err}}_{\text{in}}=\frac{1}{n}{\sum }_{i=1}^n{\mathbb{E}}_{Y^{\text{new}}}[L(Y_i^{\text{new}},{\hat{y}}_i)\mid \mathcal{D}]$. The expected (extra-sample) prediction error is $\mathrm{Err}=\mathbb{E}[L(Y_0,\hat{f}(X_0))]$ at an independently drawn $(X_0,Y_0)$. The optimism is $\mathrm{op}=\mathbb{E}[{\mathrm{Err}}_{\text{in}}]-\mathbb{E}[\overline{\mathrm{err}}]$, the systematic gap by which training error understates error [from 45.06.02].

Definition (effective degrees of freedom). For fitted values at fixed inputs and homoscedastic noise, the effective degrees of freedom is $\mathrm{df}=\frac{1}{{\sigma }^2}{\sum }_{i=1}^n\mathrm{Cov}({\hat{y}}_i,Y_i)$. For a linear smoother $\hat{\mathbf{y}}=\mathbf{Sy}$ this equals $\mathrm{tr}(\mathbf{S})$, and for ordinary least squares with $d$ predictors $\mathrm{df}=d$.

Definition (in-sample criteria). Mallows' Cp estimates in-sample error for squared-error loss with $d$ parameters as

$$C_p=\overline{\mathrm{err}}+\frac{2d}{n}{\hat{\sigma }}^2,$$

where ${\hat{\sigma }}^2$ is a noise estimate from a low-bias model. The Akaike information criterion generalises this to log-likelihood loss: with maximized log-likelihood $\hat{\ell }$ and $d$ parameters,

$$\mathrm{AIC}=-\frac{2}{n}\hat{\ell }+\frac{2d}{n},\text{equivalently}\mathrm{AIC}=-2\hat{\ell }+2d$$

on the deviance scale. The Bayesian information criterion (Schwarz) is

$$\mathrm{BIC}=-2\hat{\ell }+(\log n)d.$$

The log-likelihood $\hat{\ell }=\ell (\hat{\theta })$ uses the maximum likelihood estimate $\hat{\theta }$ of 45.01.04.

Definition (cross-validation). Partition the index set into $K$ folds $\kappa :\{1,\dots ,n\}\to \{1,\dots ,K\}$. Let ${\hat{f}}^{-k}$ be the procedure fitted with fold $k$ removed. The K-fold cross-validation estimate is

$$\mathrm{CV}(K)=\frac{1}{n}\sum _{i=1}^{n}L(Y_i,{\hat{f}}^{-\kappa (i)}(X_i)).$$

$K=n$ is leave-one-out cross-validation (LOOCV). For a model-tuning parameter $\alpha$, write $\mathrm{CV}(\alpha )$; the one-standard-error rule selects the most parsimonious $\alpha$ whose $\mathrm{CV}(\alpha )$ is within one standard error of the minimum.

Definition (bootstrap prediction error). Draw $B$ bootstrap samples ${\mathcal{D}}^{\text{astb}}$ by resampling $\mathcal{D}$ with replacement. The leave-one-out bootstrap estimate is

$${\widehat{\mathrm{Err}}}^{(1)}=\frac{1}{n}\sum _{i=1}^n\frac{1}{|C^{-i}|}\sum _{b\in C^{-i}}L(Y_i,{\hat{f}}^{\text{astb}}(X_i)),$$

where $C^{-i}$ indexes bootstrap samples not containing point $i$. The .632 estimator is ${\widehat{\mathrm{Err}}}^{(.632)}=0.368\overline{\mathrm{err}}+0.632{\widehat{\mathrm{Err}}}^{(1)}$; the .632+ estimator replaces the fixed weight by one driven by the relative overfitting rate (defined in Advanced results).

Counterexamples to common slips Intermediate+

• AIC and Cp are not interchangeable in general. For Gaussian models with known ${\sigma }^2$ they agree, since $-2\hat{\ell }$ reduces to $\overline{\mathrm{err}}/{\sigma }^2$ up to constants; for non-Gaussian likelihoods AIC is the primary object and Cp is the squared-error special case.
• Choosing $K=n$ is not always best. LOOCV is nearly unbiased for $\mathrm{Err}$ but has high variance because its $n$ training sets are almost identical; $K=5$ or $10$ trades a little bias for a large variance reduction.
• The model-selection step must live inside the cross-validation loop. Screening predictors on the full dataset and then cross-validating only the final fit leaks the held-out responses into the selection, producing error estimates biased far below the truth.
• BIC's penalty is not "AIC with a bigger constant" in spirit. AIC estimates predictive Kullback-Leibler discrepancy; BIC approximates a posterior model probability. They answer different questions, which is why their large-$n$ behaviour diverges.

Key theorem with proof Intermediate+

The signature result links the three threads: the optimism of the training error is exactly twice the effective degrees of freedom scaled by noise, and this single identity is what Cp and AIC estimate, what BIC modifies, and what cross-validation approximates without ever naming.

Theorem (optimism, AIC, and the Cp identity). For a fitting procedure producing fitted values ${\hat{y}}_i$ at fixed inputs $X_i$ with homoscedastic noise of variance ${\sigma }^2$,

$$\mathrm{op}=\mathbb{E}[{\mathrm{Err}}_{\text{in}}]-\mathbb{E}[\overline{\mathrm{err}}]=\frac{2}{n}\sum _{i=1}^n\mathrm{Cov}({\hat{y}}_i,Y_i)=\frac{2{\sigma }^2}{n}\mathrm{df}.$$

Consequently $\mathbb{E}[{\mathrm{Err}}_{\text{in}}]=\mathbb{E}[\overline{\mathrm{err}}]+\frac{2{\sigma }^2}{n}\mathrm{df}$, and $C_p=\overline{\mathrm{err}}+\frac{2d}{n}{\hat{\sigma }}^2$ is an unbiased estimate of $\mathbb{E}[{\mathrm{Err}}_{\text{in}}]$ when $\mathrm{df}=d$ and ${\hat{\sigma }}^2$ is unbiased. For a likelihood model with $d$ free parameters, the maximized log-likelihood overstates the expected log-likelihood by $d$ asymptotically, so $\mathrm{AIC}=-2\hat{\ell }+2d$ is the bias-corrected estimate of the expected Kullback-Leibler discrepancy.

Proof. The optimism identity is established in 45.06.02, Exercise 6: for each $i$, comparing the fresh-response in-sample term with the reused-response training term,

$$\mathbb{E}[(Y_i^{\text{new}}-{\hat{y}}_i{)}^2]-\mathbb{E}[(Y_i-{\hat{y}}_i{)}^2]=2\mathrm{Cov}(Y_i,{\hat{y}}_i),$$

because the ${\hat{y}}_i^2$ and $\mathbb{E}[Y^2]$ terms cancel (the two responses share mean and variance) and $Y_i^{\text{new}}$ is independent of ${\hat{y}}_i$ while $Y_i$ is not. Averaging over $i$ gives $\mathrm{op}=\frac{2}{n}{\sum }_i\mathrm{Cov}({\hat{y}}_i,Y_i)$, and substituting the definition ${\sum }_i\mathrm{Cov}({\hat{y}}_i,Y_i)={\sigma }^2\mathrm{df}$ yields $\mathrm{op}=\frac{2{\sigma }^2}{n}\mathrm{df}$. For $C_p$, set $\mathrm{df}=d$ and replace ${\sigma }^2$ by an unbiased ${\hat{\sigma }}^2$ independent of the fit; taking expectations recovers $\mathbb{E}[C_p]=\mathbb{E}[\overline{\mathrm{err}}]+\frac{2d}{n}{\sigma }^2=\mathbb{E}[{\mathrm{Err}}_{\text{in}}]$.

For AIC, let the candidate model have density $g(\cdot \mid \theta )$ and let ${\theta }_0$ minimise the Kullback-Leibler divergence $D(p\Vert g_{\theta })={\mathbb{E}}_p[\log p(Y)]-{\mathbb{E}}_p[\log g(Y\mid \theta )]$ from the true density $p$ [from 45.01.04]. The quantity worth knowing is the expected log-likelihood at a fresh observation, ${\mathbb{E}}_{Y_0}[\log g(Y_0\mid \hat{\theta })]$, whose negative is the predictive part of the divergence. A second-order Taylor expansion of $\frac{1}{n}\hat{\ell }=\frac{1}{n}{\sum }_i\log g(Y_i\mid \hat{\theta })$ around ${\theta }_0$, together with the same expansion of the population objective around ${\theta }_0$, gives two correction terms. Writing $J=-\mathbb{E}[{\nabla }^2\log g]$ and $K=\mathrm{Var}(\nabla \log g)$ at ${\theta }_0$, the maximized in-sample log-likelihood exceeds $n$ times the expected log-likelihood by $\mathrm{tr}(J^{-1}K)$ in expectation, and the expected log-likelihood evaluated at $\hat{\theta }$ falls short of its value at ${\theta }_0$ by the same $\mathrm{tr}(J^{-1}K)$. The two corrections add, so $\mathbb{E}[\hat{\ell }]-n{\mathbb{E}}_{Y_0}[\log g(Y_0\mid \hat{\theta })]\approx \mathrm{tr}(J^{-1}K)$. Under correct specification the information matrix identity $J=K$ collapses $\mathrm{tr}(J^{-1}K)=\mathrm{tr}(I_d)=d$, the parameter count. Bias-correcting by subtracting $d$ from $\hat{\ell }$ and scaling by $-2$ gives $\mathrm{AIC}=-2\hat{\ell }+2d$ as an estimate of $-2n{\mathbb{E}}_{Y_0}[\log g(Y_0\mid \hat{\theta })]$, the expected predictive deviance. $\square$

Bridge. This identity is the foundational reason that complexity penalties exist at all: the training error is biased low by exactly $2{\sigma }^2\mathrm{df}/n$, so a fair score must add that amount back, and Cp does this literally while AIC does it on the likelihood scale through the Kullback-Leibler accounting. This is exactly the optimism object of 45.06.02, now read as a model-selection penalty rather than a bias-variance bookkeeping term, and the effective-degrees-of-freedom quantity that governed shrinkage there reappears here as the unit of complexity charged. The same penalty builds toward cross-validation, which estimates $\mathrm{Err}$ directly and, for linear smoothers, reproduces the $\mathrm{df}$-based correction through the leave-one-out shortcut; and it generalises to BIC, where the constant $2$ becomes $\log n$ once the question shifts from prediction to posterior model probability. Putting these together, every method in this unit is one estimator of the same U-shaped curve, differing only in whether it corrects the training score analytically, holds data out, or resamples it.

Exercises Intermediate+

Advanced results Master

The criteria, cross-validation, and the bootstrap are three estimators of one quantity, and their differences are best read off from what each is consistent for and what it is efficient for.

The AIC-versus-BIC contrast is the sharpest such difference, and it is not a matter of tuning a constant. BIC is selection-consistent: if the data-generating model is among the candidates and the candidate set is fixed, the probability that BIC selects exactly the true model tends to one as $n\to \infty$. The $\log n$ penalty grows fast enough to extinguish the constant probability with which AIC's lighter $2d$ penalty over-selects, retaining superfluous parameters whose deviance gain is order $1$ while their cost is only $2$ per parameter. AIC, by contrast, is asymptotically efficient for prediction in the nonparametric or no-true-model regime: when the best finite-dimensional approximation improves steadily with dimension and no fixed model is correct, AIC's risk approaches that of the infeasible oracle that knows the true expected prediction error, a property BIC's over-penalisation forfeits by stopping too early. The tension is genuine — Yang's theorem shows no single criterion can be simultaneously consistent and minimax-rate efficient — so the choice encodes a belief about whether a true finite model exists.

Cross-validation occupies a middle position whose statistical character depends on $K$. Leave-one-out is approximately unbiased for $\mathrm{Err}$ and is asymptotically equivalent to AIC for smooth parametric models, by Stone's theorem; its weakness is variance, since the $n$ deletion fits are nearly identical and their errors are strongly positively correlated. Five- or ten-fold cross-validation introduces a small upward bias — each fold trains on only a fraction of the data, so the procedure is graded as if handicapped — in exchange for a large variance reduction from the more diverse, less correlated fold fits. The bias-variance of $K$ is therefore the practical reason the field standardised on $K\in \{5,10\}$ rather than $K=n$. The one-standard-error rule formalises a preference for parsimony within this noise: among models whose cross-validation curve is statistically indistinguishable from the minimum, choose the simplest, because the apparent minimiser is itself a noisy selection and the flat region around it is real.

The bootstrap estimators correct a different bias. The naive bootstrap that trains and tests on the same resample reproduces training-error optimism, so the leave-one-out bootstrap ${\widehat{\mathrm{Err}}}^{(1)}$ tests each point only on resamples excluding it. But those resamples contain only the $\approx 63.2\%$ distinct points of the original, so each is trained on an effectively smaller, less rich dataset, biasing ${\widehat{\mathrm{Err}}}^{(1)}$ upward. The $.632$ estimator $0.368\overline{\mathrm{err}}+0.632{\widehat{\mathrm{Err}}}^{(1)}$ blends the downward-biased training error with the upward-biased leave-one-out bootstrap in the proportions dictated by the expected inclusion fraction. This fixed blend overcorrects under heavy overfitting, where $\overline{\mathrm{err}}$ can reach zero. The $.632+$ refinement of Efron and Tibshirani makes the weight adaptive: define the no-information error rate $\gamma$ as the loss of the rule when inputs and responses are independent (estimated by averaging the loss over all $n^2$ input-response pairings), the relative overfitting rate $R=({\widehat{\mathrm{Err}}}^{(1)}-\overline{\mathrm{err}})/(\gamma -\overline{\mathrm{err}})$, and the weight $w=0.632/(1-0.368R)$; then ${\widehat{\mathrm{Err}}}^{(.632+)}=(1-w)\overline{\mathrm{err}}+w{\widehat{\mathrm{Err}}}^{(1)}$. When overfitting is severe ($R\to 1$) the weight rises toward the leave-one-out bootstrap, discounting the now-meaningless training error.

The minimum description length principle gives BIC a coding interpretation. Encoding the data using a model costs the negative log-likelihood $-\hat{\ell }$ bits (the cost of the residuals given the fitted parameters) plus the cost of transmitting the $d$ parameters, which to the precision worth sending scales as $\frac{d}{2}\log n$ bits. Minimising total description length $-\hat{\ell }+\frac{d}{2}\log n$ is, up to the factor of $-2$, minimising BIC. The two derivations — Schwarz's Laplace approximation to the posterior model probability and Rissanen's shortest-code accounting — arrive at the same penalty from Bayesian and information-theoretic premises, which is why BIC is read both as an evidence approximation and as a complexity-control device.

Synthesis. The foundational reason these methods cohere is the optimism identity $\mathrm{op}=\frac{2{\sigma }^2}{n}\mathrm{df}$: the in-sample criteria estimate it analytically, cross-validation and the bootstrap estimate the underlying $\mathrm{Err}$ empirically, and effective degrees of freedom is the single complexity unit they all charge. This is exactly the bias-variance trade-off of 45.06.02 viewed as a selection problem, and the central insight is that no estimator of the U-shaped curve is free: Cp and AIC need a noise estimate and assume the optimism formula, cross-validation pays in variance for its assumption-freedom, and the bootstrap pays in the inclusion-fraction bias that the $.632$ family corrects. Putting these together, the AIC-versus-BIC divide is dual to the consistency-versus-efficiency dichotomy — BIC's $\log n$ penalty is the price of selecting the true model when one exists, AIC's $2d$ penalty is the price of predicting well when none does — and Yang's impossibility result shows the duality is structural, not a defect to be engineered away. The MDL reading generalises BIC beyond the Bayesian frame, identifying the $\frac{d}{2}\log n$ penalty as the cost of describing parameters to the precision the data can support, so that model selection and data compression are the same optimisation seen from two disciplines.

Full proof set Master

The optimism identity, the AIC bias correction, the linear-smoother CV shortcut, and the Laplace derivation of BIC are proved in the Key theorem and Exercises 3, 4, and 8. The remaining Master claims are recorded here.

Proposition (the expected bootstrap inclusion fraction is $1-e^{-1}$). In a size-$n$ resample drawn with replacement from $n$ points, the expected fraction of distinct original points included tends to $1-e^{-1}\approx 0.632$ as $n\to \infty$.

Proof. For a fixed original point $i$, each of the $n$ independent draws selects $i$ with probability $1/n$, so $i$ is omitted from the entire resample with probability $(1-1/n{)}^n$. The expected number of included distinct points is ${\sum }_i\mathbb{P}(i\text{ included})=n[1-(1-1/n{)}^n]$, and the expected fraction is $1-(1-1/n{)}^n$. Since $(1-1/n{)}^n\to e^{-1}$, the fraction tends to $1-e^{-1}$. The convergence is monotone increasing in $n$ from $1-1/4=0.75$ at $n=2$ down through the limit; for $n\ge 20$ the fraction is within $0.01$ of $0.632$. $\square$

Proposition (Mallows' Cp is unbiased for in-sample error in the Gaussian linear model). For $\mathbf{y}=\mathbf{X}\mathbf{\beta }+\mathbf{\epsilon }$ with $\mathbf{\epsilon }\sim (0,{\sigma }^2\mathbf{I})$, OLS fit, and an unbiased ${\hat{\sigma }}^2$ independent of the fit, $\mathbb{E}[C_p]=\mathbb{E}[{\mathrm{Err}}_{\text{in}}]$.

Proof. The OLS hat matrix $\mathbf{H}=\mathbf{X}({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }$ is the linear smoother with $\mathrm{tr}(\mathbf{H})=d$, so by Exercise 3 the optimism is $\frac{2{\sigma }^2}{n}d$. The Key theorem gives $\mathbb{E}[{\mathrm{Err}}_{\text{in}}]=\mathbb{E}[\overline{\mathrm{err}}]+\frac{2{\sigma }^2}{n}d$. Taking expectations of $C_p=\overline{\mathrm{err}}+\frac{2d}{n}{\hat{\sigma }}^2$ and using $\mathbb{E}[{\hat{\sigma }}^2]={\sigma }^2$ with independence yields $\mathbb{E}[C_p]=\mathbb{E}[\overline{\mathrm{err}}]+\frac{2d}{n}{\sigma }^2=\mathbb{E}[{\mathrm{Err}}_{\text{in}}]$. The estimate is exactly unbiased, not merely asymptotically, in this Gaussian linear case. $\square$

Proposition (BIC selection consistency for nested Gaussian models). Among a fixed finite set of candidate models containing the true model, with i.i.d. data and the regularity conditions under which the MLE is consistent and asymptotically normal, the probability that BIC selects the true model tends to one as $n\to \infty$.

Proof. Compare the true model $M_0$ of dimension $d_0$ with any competitor $M$. Two cases. If $M$ omits a true parameter (under-fitting), the likelihood-ratio statistic $2({\hat{\ell }}_{M_0}-{\hat{\ell }}_M)$ grows linearly in $n$ (the omitted effect contributes a positive Kullback-Leibler gap per observation), so ${\mathrm{BIC}}_M-{\mathrm{BIC}}_{M_0}=2({\hat{\ell }}_{M_0}-{\hat{\ell }}_M)+(d_M-d_0)\log n\to +\infty$ regardless of the bounded dimension term; $M$ is rejected with probability tending to one. If $M$ strictly contains $M_0$ (over-fitting, $d_M>d_0$), the likelihood-ratio statistic $2({\hat{\ell }}_M-{\hat{\ell }}_{M_0})$ converges in distribution to ${\chi }_{d_M-d_0}^2$, hence is $O_p(1)$, while the penalty difference $(d_M-d_0)\log n\to +\infty$; thus ${\mathrm{BIC}}_M-{\mathrm{BIC}}_{M_0}=-O_p(1)+(d_M-d_0)\log n\to +\infty$ and $M$ is again rejected. Since the candidate set is finite, with probability tending to one $M_0$ has the smallest BIC. The same argument with the fixed penalty $2$ in place of $\log n$ fails in the over-fitting case: there ${\mathrm{AIC}}_M-{\mathrm{AIC}}_{M_0}=-{\chi }_{d_M-d_0}^2+2(d_M-d_0)$, which is negative with constant positive probability, so AIC over-selects with non-vanishing probability. $\square$

Proposition (leave-one-out cross-validation is asymptotically AIC for smooth models). For a regular parametric family with the MLE plug-in predictor, $n{\mathrm{CV}}_{\text{LOO}}$ and $\mathrm{AIC}$ (on the deviance scale) agree to first order: their difference is $o_p(1)$ per observation.

Proof. Write the leave-one-out log-likelihood loss $-\log g(Y_i\mid {\hat{\theta }}^{-i})$ and Taylor-expand ${\hat{\theta }}^{-i}$ around the full-data $\hat{\theta }$. The one-step deletion update is ${\hat{\theta }}^{-i}-\hat{\theta }=-{\hat{J}}^{-1}\nabla \log g(Y_i\mid \hat{\theta })+o_p(n^{-1})$ with observed information $\hat{J}=O(n)$, by the same leave-one-out lemma used in Exercise 4 specialised to the score. Substituting into the loss and summing,

$$\sum _i-\log g(Y_i\mid {\hat{\theta }}^{-i})=\sum _i-\log g(Y_i\mid \hat{\theta })+\sum _i\nabla \log g(Y_i\mid \hat{\theta }{)}^{\top }{\hat{J}}^{-1}\nabla \log g(Y_i\mid \hat{\theta })+o_p(1).$$

The quadratic correction is $\mathrm{tr}({\hat{J}}^{-1}{\sum }_i\nabla \log g\nabla \log g^{\top })=\mathrm{tr}({\hat{J}}^{-1}\hat{K})$, the empirical version of the $\mathrm{tr}(J^{-1}K)$ term in the AIC derivation, which converges to $d$ under correct specification. So $-2n{\mathrm{CV}}_{\text{LOO}}=-2\hat{\ell }+2d+o_p(1)=\mathrm{AIC}+o_p(1)$, Stone's asymptotic equivalence. $\square$

Connections Master

The bias-variance decomposition and the optimism of training error 45.06.02 is the direct parent of this unit: the identity $\mathrm{op}=\frac{2{\sigma }^2}{n}\mathrm{df}$ proved there is what Cp and AIC estimate analytically and what cross-validation reproduces empirically, and the effective-degrees-of-freedom quantity that indexed shrinkage there is the complexity unit charged by every criterion here.

Point estimation by maximum likelihood 45.01.04 supplies the log-likelihood, the maximised value $\hat{\ell }$, and the Fisher-information machinery that the AIC bias correction and the BIC Laplace approximation both run on; the Kullback-Leibler divergence minimised in the AIC derivation is the population objective whose sample analogue the MLE maximises, so AIC is a bias-corrected estimate of the very discrepancy that defines the MLE's target under misspecification.

The lasso and its sparsity oracle 45.06.06 is where these selection criteria meet penalised estimation: the lasso's degrees of freedom equal the expected size of its active set (a Stein identity), so plugging that $\mathrm{df}$ into the Cp/AIC penalty yields a per-$\lambda$ criterion, while cross-validation along the lasso path with the one-standard-error rule is the standard route to choosing $\lambda$ in practice; the selection-bias warning of this unit is exactly why the entire path must be cross-validated rather than tuned on the full data.

Conjugate priors and exponential-family Bayes 45.03.02 underwrites the BIC derivation: the marginal likelihood $\int L(\theta )\pi (\theta )d\theta$ that BIC approximates by Laplace is the model evidence whose closed form the conjugate theory computes exactly, and differences of BIC approximate log Bayes factors, the conjugate evidence ratios that compare models. The smooth prior with positive density at the truth required by the Laplace step is the regularity condition that conjugate analysis makes explicit.

Bayesian point estimation 45.03.01 frames the BIC route as posterior model probability: where that unit minimises posterior expected loss to choose an action, BIC selects the model of highest approximate posterior probability, and the MDL coding interpretation reframes the same penalty as shortest description length, tying model selection to data compression.

Historical & philosophical context Master

The complexity-penalty idea entered regression through Colin Mallows, who circulated the $C_p$ statistic in the 1960s and published it as a diagnostic for subset selection, plotting $C_p$ against subset size to read off models that neither under- nor over-fit ^{[Mallows 1973]}. Independently and more generally, Hirotugu Akaike derived his information criterion in 1973-1974 from the principle that a fitted model should minimise the expected Kullback-Leibler divergence from the truth, showing that the maximised log-likelihood is an upward-biased estimate of the expected log-likelihood and that the bias is asymptotically the parameter count, which yields the $2k$ penalty ^{[Akaike 1974]}. Akaike's reframing of model selection as the estimation of a predictive information loss was a conceptual break from hypothesis-testing approaches to choosing model order.

Gideon Schwarz gave the Bayesian alternative in 1978, deriving BIC as the leading terms of a Laplace approximation to the marginal likelihood of a candidate model and proving that, unlike AIC, it consistently identifies the true model dimension when one exists ^{[Schwarz 1978]}. The divergence between the two criteria — Schwarz's consistency against Akaike's predictive efficiency — was clarified over the following decades and shown by Yuhong Yang to be a genuine impossibility: no model-selection rule can be both consistent and minimax-rate optimal for prediction ^{[Yang 2005]}. Jorma Rissanen supplied a third lineage, the minimum description length principle, identifying the BIC penalty as the cost of encoding parameters to the precision the data support and casting model selection as data compression ^{[Rissanen 1978]}.

The resampling tradition runs parallel. Mervyn Stone and, in the same year, Seymour Geisser formalised cross-validation as a predictive assessment, with Stone proving the asymptotic equivalence of leave-one-out cross-validation and AIC ^{[Stone 1974]}. Bradley Efron's bootstrap, introduced in 1979, was adapted to prediction-error estimation through the leave-one-out bootstrap and the $.632$ and $.632+$ estimators developed by Efron and Robert Tibshirani, which correct the inclusion-fraction bias inherent in resampling-based error estimates ^{[Efron 1997]}.

Bibliography Master

@book{hastie2009,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2nd},
  publisher = {Springer-Verlag, New York},
  year      = {2009}
}

@article{akaike1974,
  author  = {Akaike, Hirotugu},
  title   = {A New Look at the Statistical Model Identification},
  journal = {IEEE Transactions on Automatic Control},
  volume  = {19},
  number  = {6},
  pages   = {716--723},
  year    = {1974}
}

@article{schwarz1978,
  author  = {Schwarz, Gideon},
  title   = {Estimating the Dimension of a Model},
  journal = {The Annals of Statistics},
  volume  = {6},
  number  = {2},
  pages   = {461--464},
  year    = {1978}
}

@article{stone1974,
  author  = {Stone, Mervyn},
  title   = {Cross-Validatory Choice and Assessment of Statistical Predictions},
  journal = {Journal of the Royal Statistical Society, Series B},
  volume  = {36},
  number  = {2},
  pages   = {111--147},
  year    = {1974}
}

@article{mallows1973,
  author  = {Mallows, Colin L.},
  title   = {Some Comments on $C_p$},
  journal = {Technometrics},
  volume  = {15},
  number  = {4},
  pages   = {661--675},
  year    = {1973}
}

@article{rissanen1978,
  author  = {Rissanen, Jorma},
  title   = {Modeling by Shortest Data Description},
  journal = {Automatica},
  volume  = {14},
  number  = {5},
  pages   = {465--471},
  year    = {1978}
}

@article{efron1997,
  author  = {Efron, Bradley and Tibshirani, Robert},
  title   = {Improvements on Cross-Validation: The .632+ Bootstrap Method},
  journal = {Journal of the American Statistical Association},
  volume  = {92},
  number  = {438},
  pages   = {548--560},
  year    = {1997}
}

@article{yang2005,
  author  = {Yang, Yuhong},
  title   = {Can the Strengths of AIC and BIC Be Shared? A Conflict between Model Identification and Regression Estimation},
  journal = {Biometrika},
  volume  = {92},
  number  = {4},
  pages   = {937--950},
  year    = {2005}
}