Rigorous statement of expectations for the bias-variance trade-off

External question — Cross Validated Stack Exchange Author: Richard Hardy Original post: https://stats.stackexchange.com/questions/471143 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. Consider a data generating process $$Y=f(X)+\varepsilon$$ where $\varepsilon$ is independent of $x$ with $\mathbb E(\varepsilon)=0$ and $\text{Var}(\varepsilon)=\sigma^2_\varepsilon$ . According to Hastie et al. "The Elements of Statistical Learning" (2nd edition, 2009) Section 7.3 p. 223, we can derive an expression for the expected prediction error of a regression fit $\hat f(X)$ at an input point $X=x_0$ , using squared-error loss: \begin{align} \text{Err}(x_0) &=\mathbb E[(Y-\hat f(x_0))^2|X=x_0]\\ &=(\mathbb E[\hat f(x_0)−f(x_0)])^2+\mathbb E[(\hat f(x_0)−\mathbb E[\hat f(x_0)])^2]+\sigma^2_\varepsilon\\ &=\text{Bias}^2\ \ \ \quad\quad\quad\quad\quad\;\;+\text{Variance } \quad\quad\quad\quad\quad\quad+ \text{ Irreducible Error} \end{align} (where I use the notation $\text{Bias}^2$ instead of $\text{Bias}$ ). Question: What are the expectations taken over? What is held fixed and what is random? The question arose in the comments of the thread "Why is there a bias variance tradeoff? A counterexample".

External answer — Cross Validated Stack Exchange Author: Richard Hardy Original post: https://stats.stackexchange.com/a/485813 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. $X$ is assumed fixed; see Section 2.9, p. 37: For simplicity here we assume that the values of $x_i$ in the sample are fixed in advance (nonrandom). Then the only source of random variation here is $\varepsilon$ . Hence, the expectations are taken w.r.t. to the distribution of $\varepsilon$ .

External answer — Cross Validated Stack Exchange Author: Gabriel Romon Original post: https://stats.stackexchange.com/a/664944 License: CC BY-SA 4.0 — https://creativecommons.org/licenses/by-sa/4.0/ Adaptation: HTML converted to plain text; contact email addresses removed. First, we clarify the framework and notation. The number of observations is $n$ , we have training data $\mathcal D_n = ((X_1,Y_1),\ldots,(X_n,Y_n))$ and test data $(X,Y)$ . We assume that $X\perp\!\!\!\!\!\!\perp \mathcal D_n$ . We do not make the usual i.i.d. assumption on $(X,Y)$ and the $(X_i,Y_i)$ , so as not to exclude the fixed-design setting covered at the end of this post. By applying a learning algorithm to $\mathcal D_n$ we obtain a predictor $\hat f$ , which is therefore random since it depends on the training data, which is random by assumption. The prediction of $\hat f$ at any $x\in \mathcal X$ will be denoted by $\hat f(x; \mathcal D_n)$ , in order to highlight the dependence on $\mathcal D_n$ . The expected prediction error of $\hat f$ at $x_0$ is the following conditional expectation (see Chung's book or Shiryaev's book for a reference on this measure-theoretic concept) $$E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] = E\Big[\big(Y-\hat f(x_0; \mathcal D_n)\big)^2\Big|X = x_0\Big].$$ Looking at the RHS, only the randomness in $Y$ and $\mathcal D_n$ is involved in the expectation. At this point, we specify the distribution of $(X,Y)$ by assuming that $Y= f(X)+\epsilon$ , with $\epsilon \perp\!\!\!\!\!\!\perp (X,\mathcal D_n)$ , $E[\epsilon] = 0$ and $V[\epsilon] = \sigma^2$ . Under this assumption, the conditional expectation rewrites as $$\begin{align} E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n) + \epsilon\big)^2\Big|X = x_0\Big] = &\phantom{+}E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big|X = x_0\Big] \\&+ E\Big[\epsilon^2 \Big|X = x_0\Big] \\&+E\Big[\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big|X = x_0\Big] \end{align}$$ $\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2$ is a function of $\mathcal D_n$ only, and thus independent of $X$ . Consequently, the first summand rewrites as $E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big]$ . Since $\epsilon \perp\!\!\!\!\!\!\perp X$ , the second summand is $E[\epsilon^2]=\sigma^2$ . $\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)$ is a function of $\epsilon$ and $\mathcal D_n$ , and thus independent of $X$ . Consequently, the third summand rewrites as $E\Big[\epsilon\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big] = E[\epsilon] E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big) \Big] = 0$ . Hence $$\begin{align} &\phantom{+}E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] \\&= E\Big[\big(f(x_0)-\hat f(x_0; \mathcal D_n)\big)^2 \Big] + \sigma^2 \\&= \big(E[\hat f(x_0; \mathcal D_n)] - f(x_0)\big)^2 + E\Big[\big(\hat f(x_0; \mathcal D_n) - E[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] + \sigma^2 \\&= \big(E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)] - f(x_0)\big)^2 + E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] + \sigma^2, \end{align}$$ where the last line emphasizes the exact source of randomness in each of the expectation. More generally, we can formulate a bias-variance decomposition without an additive error model specification of $(X,Y)$ . If we define the Bayes predictor $f^*:x\mapsto E[Y|X=x]$ , then a similar computation shows that $$\begin{align}&\phantom{+}E\Big[\big(Y-\hat f(X; \mathcal D_n)\big)^2\Big|X = x_0\Big] \\&= \underbrace{\big(E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)] - f^*(x_0)\big)^2}_{\text{squared bias}} + \underbrace{E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big]}_{\text{variance}} + \underbrace{E[\big(Y-f^*(X)\big)^2|X=x_0]}_{\text{irreducible error}}. \end{align} $$ In some paragraphs, Hastie et al. add a fixed design assumption, i.e, that $(X_1,\ldots,X_n)$ is a degenerate random vector that is always equal to $(x_1,\ldots,x_n)\in \mathcal X^n$ . This assumption is irrelevant in the derivation of the bias-variance decomposition. It is relevant however when looking for a closed form for the bias and variance terms. For instance, consider the setting of k-NN regression, where it is further assumed that for each $i$ , $Y_i=f(x_i) + \epsilon_i$ , with $E[\epsilon_i] = 0$ , $V[\epsilon_i] = \sigma^2$ and pairwise independence of the $\epsilon_i$ . The fixed-design assumption allows for a simple expression of the predicted value: $$\hat f(x_0,\mathcal D_n) = \frac 1k \sum_{\ell=1}^k Y_{(\ell)},$$ where the indices $(1),\ldots, (k)$ are such that $x_{(1)},\ldots,x_{(k)}$ are the k-nearest neighbors of $x_0$ . The quantity $E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]$ is then simply $\frac 1k \sum_{\ell=1}^k E[Y_{(\ell)}] = \frac 1k \sum_{\ell=1}^k f(x_{(\ell)})$ and the variance term is $$E_{\mathcal D_n}\Big[\big(\hat f(x_0; \mathcal D_n) - E_{\mathcal D_n}[\hat f(x_0; \mathcal D_n)]\big)^2 \Big] = V\left[\frac 1k \sum_{\ell=1}^k Y_{(\ell)}\right] = \frac{\sigma^2}k.$$