On overfitting and post-selection uncertainty assessments

Introduction

Consider the classical multiple linear regression model

can be used for inference on the mean response at the given $x$. However, as is now well-known (Berk et al. 2013), the properties that these classical procedures enjoy for a fixed/true $S$ may not hold for a data-dependent choice, $\hat{S}$. For example, $C_{\alpha}(x;\hat{S})$ may not have coverage probability equal to $1-\alpha$.

This note provides an explanation of this lack-of-validity phenomenon by showing that, when the sub-model is selected according to information criteria such as aic and bic, if the selected sub-model overfits, i.e., contains a superset of the explanatory variables in the true model, then the corresponding estimate of the error variance will be smaller than that for the true model. This explains the empirical findings in Hong et al. (2017), where prediction intervals based on the sub-model minimizing aic tend to be too short compared to those based on the true model and, consequently, they tend to undercover; see Section 3. Moreover, our Theorem 1 together with the dilation phenomenon described in Efron (2003), explains why bootstrap may not correct the selection effect for methods that tend to overfit.

Result

For a given sub-model $\Theta(S)$, corresponding to a subset $S\subseteq\{1,\ldots,p\}$, let $(\hat{\beta}_{S},\hat{\sigma}_{S})$ denote the least squares estimators of the $\Theta(S)$-specific parameters $(\beta_{S},\sigma_{S})$. We consider a selection procedure that chooses the subset $S$ by minimizing the function

where $\text{\sc sse}(S)=\|y-X_{S}\hat{\beta}_{S}\|^{2}$ is the error sum of squares for sub-model $\Theta(S)$, which is proportional to the corresponding least squares estimator $\hat{\sigma}_{S}^{2}$, $c_{n}=o(n)$ is a user-specified sequence of constants, and $|S|$ denotes the cardinality of the set $S$. The aic and bic set $c_{n}\equiv 2$ and $c_{n}=\log n$, respectively.

Suppose that there exists a subset $S^{\star}$ corresponding to the truly non-zero regression coefficients, i.e., $\beta_{i}\neq 0$ for $i\in S^{\star}$ and $\beta_{i}=0$ for $i\not\in S^{\star}$. We write $(\hat{\beta}_{S^{\star}}$, $\hat{\sigma}_{S^{\star}})$ for the oracle estimators, those based on knowledge of the true sub-model $\Theta(S^{\star})$. Of course, if $\hat{S}$ is the subset chosen by minimizing $\gamma_{n}$ in (3), then $\gamma_{n}(\hat{S})\leq\gamma_{n}(S^{\star})$ or, equivalently,

if $\hat{S}\neq S^{\star}$, then the inequality in (4) would be strict.

For the purpose of inference or prediction, it is common to naively use the classical normal linear model theory, based on the selected subset $\hat{S}$, to derive uncertainty assessments. However, using the data to select $\hat{S}$ introduces bias, violating the assumptions of that classical theory, and thereby invalidating the conclusions. The next result provides an explanation for this general phenomenon in cases where the selected sub-model $\Theta(\hat{S})$ overfits in the sense that $\hat{S}\supset S^{\star}$. In such cases, we find that $\hat{\sigma}_{\hat{S}}$ is smaller than the oracle estimator $\hat{\sigma}_{S^{\star}}$. Since the error variance estimate is involved in all uncertainty assessment calculations, and since it is common for selection methods to overfit, especially those based on aic (Hurvich & Tsai 1989), this systematic under-estimation explains the general lack of validity of the classical inferential tools applied naively in a post-selection context.

where $a_{n}=(c_{n}/n)(n-|S^{\star}|-1)$ and $D_{n}=(|\hat{S}|-|S^{\star}|)/(n-|S^{\star}|-1)$, then $\hat{\sigma}_{\hat{S}}<\hat{\sigma}_{S^{\star}}$.

To gain some intuition about the condition (5), first note that $a_{n}D_{n}$ will tend to be small. In particular, a very conservative bound is $a_{n}D_{n}\leq c_{n}p/n$, which is small for moderate $c_{n}$ and $n\gg p$. Next, since $x\mapsto 1-\exp(-ax)$ is convex for $x>0$ and $a>0$, we have $1-\exp(-a_{n}D_{n})>a_{n}D_{n}$ for all $D_{n}$ in an interval $(0,d)$, where $d=d(a_{n})\in[0,1)$. So, to meet (5) we need $a_{n}>1$ and, again, we have a conservative bound $a_{n}\geq c_{n}(n-p-1)/n$, which itself is greater than 1 for $n\gg p$ and $c_{n}$ not too small. In particular, if $n\gg p$ and $c_{n}\equiv 2$ as in the aic, then (5) holds.

Start by writing $\text{\sc sse}(\hat{S})$ in terms of $\text{\sc sse}(S^{\star})$. Let $X_{\hat{S}}$ and $X_{S^{\star}}$ denote the sub-matrices corresponding to the indicated subsets, and write $P_{\hat{S}}$ and $P_{S^{\star}}$ for the respective projections onto their column spaces. Then Pythagoras’ theorem implies that

and $F_{n}(S^{\star},\hat{S})$ is the usual F-statistic for testing the larger $\Theta(\hat{S})$ against the smaller $\Theta(S^{\star})$. Consequently, we choose $\hat{S}$ over the strictly smaller $S^{\star}$, according to (4), if and only if $r_{n}>1-\exp(-a_{n}D_{n})$.

Then the above connection between $\text{\sc sse}(\hat{S})$ and $\text{\sc sse}(S^{\star})$ immediately gives a comparison between the corresponding variance estimates:

As above, we find that $\hat{\sigma}_{\hat{S}}<\hat{\sigma}_{S^{\star}}$ if and only if $r_{n}>D_{n}$. By condition (5), it follows that the lower bound on $r_{n}$ derived from over-fitting is greater than that derived from the under-estimation. Therefore, over-fitting implies under-estimation, proving the claim. ∎

Illustration

Consider the model (1), with $n=50$ and $p=10$, and variance $\sigma^{2}=1$. Set $S^{\star}=\{1,2,3\}$, with corresponding coefficients $\beta_{1}^{\star}=1$, $\beta_{2}^{\star}=2$, and $\beta_{3}^{\star}=3$. The rows of the $X$ matrix are independent, $p$-variate normal, with mean zero, AR(1) dependence structure, and one-step correlation $\rho=0.5$. We simulated 1000 data sets and, for each, evaluated $\hat{\sigma}_{\hat{S}}$ and $\hat{\sigma}_{S^{\star}}$, where $\hat{S}$ is chosen based on the aic. The scatterplot shown in Figure 1(a) demonstrates the systematic under-estimation based on the AIC-selected sub-model, as predicted by Theorem 1. In all 1000 cases, we have $\hat{S}\supseteq S^{\star}$, and those on the diagonal line correspond to $\hat{S}=S^{\star}$. To further illustrate the difference between the estimates, Figure 1(b) plots a histogram of the ratio $\hat{\sigma}_{S^{\star}}/\hat{\sigma}_{\hat{S}}$, only for the strict over-fit cases. In particular, the mean from this histogram is 1.06.

While the relative difference between the two estimates does not seem remarkable, even this small of a difference can impact the quality of inference. For example, consider using the confidence interval (2) for inference on the mean response at a particular setting $x$ of the explanatory variables; here, $x$ is an independent sample from the distribution that generated the rows of $X$. The oracle 95% confidence interval $C_{0.05}(x;S^{\star})$ has coverage exactly equal to $0.95$ but, in the 1000 simulations above, the coverage probability of $C_{\alpha}(x;\hat{S})$ is roughly 0.86. It happens that the $\hat{S}$-based intervals tend to be shorter than the oracle, suggesting that valid post-selection inference on the mean response requires $\hat{\sigma}_{\hat{S}}$ to be strictly larger than $\hat{\sigma}_{S^{\star}}$, which is impossible given Theorem 1 and the aic’s tendency to over-fit.

Acknowledgement

The authors are grateful to the Editor and two referees whose comments greatly enhanced the clarity of our presentation. Kuffner was supported by the National Science Foundation, U.S.A.

References