"Proof?" of Bias/Variance trade-off

Question

I'm unsatisfied with the "proof" that there is a trade-off between variance and bias in Hastie's text (The Element of Machine Learning). I also haven't found anything on this site that speaks to my particular concern.

In section 7.3, they show the following. Assume that the target $Y$ has the relationship $Y = f(X) + \varepsilon$ where $E(\varepsilon) = 0$ and $Var(\varepsilon) = \sigma_\varepsilon^2$. Since the target has error in it, they call $\sigma_\varepsilon^2$ "irreducible error".

$\begin{aligned} Err(x_0) &= E\big[(Y - \hat{f}(x_0))^2 \mid X = x_0\big] \\ &= \sigma_\varepsilon^2 + \big[ E(\hat{f}(x_0) - f(x_0) \big]^2 + E\big[\hat{f}(x_0)-E(\hat{f}(x_0) \big]\\ &= Irreducible Error + Bias^2 + Variance \end{aligned}$

Fine. Obviously if Err(x) were constant, than an increase in bias would lead to a decrease in variance. But, as we change the model, who is to say that the error is constant?? Wouldn't a great model have low bias and variance whereas a horrible model could have high variance and bias? So, I see no evidence here that a more complex model must have lower bias but greater variance. Is this calculation proving anything?

I would like to know if there's a rigorous, mathematical argument showing that this tradeoff is fundamental. Usually I just see intuitive arguments or case studies in the context of one specific type of analysis (such as linear regression)

Answer 1

First write the statement mathematically: define $\mathcal{F}$ as a function space, $\hat{f}_{n,\mathcal{F}} = \arg\min_{\hat{f}\in\mathcal{F}}\sum_{i=1}^n (y_i - \hat{f}(x_i))^2$ as the optimal regression in $\mathcal{F}$, $Bias^2(\hat{f}_{n,\mathcal{F}}(x_0)) = [E(\hat{f}_{n,\mathcal{F}}(x_0)) - f(x_0)]^2$ and $Variance(\hat{f}_{n,\mathcal{F}}(x_0)) = Var[\hat{f}_{n,\mathcal{F}}(x_0)]$ as you defined, where the expectation and variance are taken on the training data.

You asked that whether a more complex model must have lower bias but greater variance, which can be written as the statement: if $\mathcal{F_1} \subset \mathcal{F_2}$, $Bias^2(\hat{f}_{n, \mathcal{F}_1}(x_0)) \ge Bias^2(\hat{f}_{n, \mathcal{F}_2}(x_0))$ and $Variance(\hat{f}_{n, \mathcal{F}_1}(x_0)) \le Variance^2(\hat{f}_{n, \mathcal{F}_2}(x_0))$.

I can find a counterexample as following: assume the true $f(x) = 1$ with $\sigma_\epsilon = 0$, and consider $\mathcal{F_1} = \{ax\}$, $\mathcal{F_2} = \{ax+b\}$, number of training data $n = 2$. It can be computed that $\hat{f}_{2, \mathcal{F}_1}(x_0) = \frac{x_1 + x_2}{x_1^2 + x_2^2}x_0$, $\hat{f}_{2, \mathcal{F}_2}(x_0) = 1$. The second has zero bias and variance, which are both lower than the first.

It shows that a more complex model may have both lower bias and variance.

Answer 2

The reason is that there is sort of a proof. The initial important paper is, "Stein, C. (1956). "Inadmissibility of the usual estimator for the mean of a multivariate distribution". Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability. 1. pp. 197–206."

What is important about it is that it shows that you can construct a simple estimator that always stochastically dominates both the maximum likelihood estimator and minimum variance unbiased estimator for the mean of a multivariate Gaussian. What is interesting is that this estimator can also always be dominated. It does not appear that there is an estimator that you can construct using this method that you cannot then dominate yet again.

This proves that the bias that is created for this one case stochastically dominates the usual estimator.

What is interesting about this method is that it maps to a Bayesian solution with an empirical prior distribution. There are an infinite number of priors and if you played improper games, then you could construct dominating priors although this would violate Bayesian theory. The prior should describe prior knowledge and not improve the value of the sample estimator. In Bayesian theory, the job of the prior is to normalize the data against prior information.

Because Stein estimators map to a constrained Bayesian solution, it gives a hint as to what is really going on. Bayesian estimators condition on the information in a sample, whereas non-Bayesian estimators do not. An empirical prior uses a sample statistic that you are not interested in to inform you about a parameter you are interested in. The argument against this is that you are using the same data twice. In the case of a Stein estimator, you condition each individual mean on the grand mean.

The argument for this is that you are gaining information about the overall system through the grand mean. The bias is information based and not just random bias. The variance is declining because you are including more information rather than less. The danger in this is that a Stein estimator does not require the means have any relationship whereas the Bayesian method would require it under many axiom systems.

Jaynes also discusses this in his book Probability: The Language of Science, in his discussion on the problems with using the word "unbiased." I don't think it is all sources of bias that reduce variability in the estimator, rather it is those take advantage of sample properties that would normally be missed in standard unbiased methods and which are the equivalent to Bayesian information extraction.

As to model selection, Bayesian model selection methods are intrinsically admissible, which would deal with your problem explicitly. An admissible model stochastically dominates an inadmissible model. The topic you are looking for is called admissibility and there are two flavors. The Bayesian version is slightly different from the non-Bayesian version because the former operates in the parameter space and the latter in the sample space. Nonetheless, the reason it solves your problem is that it solves a more profound general problem.

A statistic is any function of the data, so that $\sum\sin(x_i)$ is a statistic. It is a useless statistic for almost any if not all problems, but how do you prove it? There are an infinite number of statistics that are possible, but how do you prove that almost every one is useless. Indeed, there are an infinite number of unbiased estimators for the mean, yet why use $\bar{x}$?

If there is one admissible estimator, for example, then all others with all other combinations of bias and variability are excluded. In fact you can create a partial ordering of all possible rules. Do note though that an admissible estimator when there are multiple admissible estimators is not intrinsically a good estimator, where "good" might be some common sense understanding of good. Inadmissible estimators are bad, but not all admissible ones are good. It merely reduces your set down that you have to evaluate. There are pointless admissible estimators that no one would use.

The base paper for admissibility is at https://projecteuclid.org/euclid.aoms/1177730345

It is open source.

Answer 3

One argument could be like this - In any setting where there is uncertainty about the true value of the parameter, error is inevitable. We dont have an algorithm or known way of deriving the value of the parameter right? This would automatically mean that the Quadratic risk would have to be greater than zero. This means that it shouldn't be possible to simultaneously reduce the bias and variance to arbitrarily low values and hence the trade off.