Impossible to overfit when the data generating process is deterministic?

Question

For a stochastic data generating process (DGP) $$ Y=f(X)+\varepsilon $$ and a model producing a point prediction $$ \hat{Y}=\hat{f}(X), $$ the bias-variance decomposition is

\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}

(Hastie et al. "The Elements of Statistical Learning" (2nd edition, 2009) Section 7.3 p. 223; I use the notation $\text{Bias}^2$ instead of $\text{Bias}$). If there is a range models to choose from, the highly flexible ones will have low bias and high variance and will tend to overfit. The inflexible ones will have high bias and low variance and will tend to underfit. The model yielding the lowest expected squared error will be somewhere in between the two extremes.

For a deterministic DGP that lacks the additive random error, $$ Y=f(X), $$ the bias-variance decomposition tells us that variance and irreducible error are zero and only bias is left. If there is a range models to choose from, choosing the most flexible one will yield the lowest bias and hence the lowest expected squared error. This suggests it is impossible to overfit when the DGP is deterministic.

To me this sounds too good to be true. Perhaps the caveat is that the models here use the same set of regressors as the DGP, i.e. all the relevant variables are being considered and no irrelevant variables are included. This is unlikely to hold in practice. If the sets of regressors in the models vs. the DGP differ, there might be different story.

Questions:

1. Does my reasoning for why it is impossible to overfit a deterministic DGP make sense? If not, why?
2. Does the reasoning break down if the regressors used in the DGP and the model differ? If so, how?

Update: In practice, many DGPs could be considered entirely deterministic or almost deterministic with a negligible stochastic component, even though their mechanisms may be too complex for us to comprehend, let alone model accurately. If the answer to Q1 is that the reasoning is sound and the answer to Q2 is that the reasoning does not break down, as suggested by @markowitz, then overfitting should rarely be of concern in practice. This seems counterintuitive to me...

Answer 1

If the DGP is noiseless, it is not possible to encounter overfitting problem. That’s true. In fact you can see the overfitting also as the problem to fit the noise (irreducible error) and not only the signal. For example in regression context you can improve the fit, at most in $R^2$ term the perfect fit can achieved, regardless the noise. However the bias problem remain.

To me this sounds too good to be true. Perhaps the caveat is that the models here use the same set of regressors as the DGP, i.e. all the relevant variables are being considered and no irrelevant variables are included. This is unlikely to hold in practice. If the sets of regressors in the models vs. the DGP differ, there might be different story.

In regression case the problem is precisely this one.

More in general you can also misspecify the functional form. Flexibility is not a free lunch here even if to discover the bias is hard in practice. In fact only if you know the true functional form and the correct/true set of dependent variables your work is perfect.

EDIT: Giving some definitions is always a good idea. What is overfitting? From the cited book or from Wikipedia also (https://en.wikipedia.org/wiki/Overfitting) is easy to verify that overfitting appear when in sample performance of estimated model in notably worse than out of sample counterpart. However, this is more a consequence of overfitting than its definition. It represents the starting point for some rule like Optimism of the Training Error Rate (page 228 of the book above). I do not give you a formal definition of overfitting here, however this deals with the fact that a model encounters overfitting when it fits not only the structure/signal but also the noise. Note that structure/signal and noise/error are referred on the "true model" (=DGP). From this we can understand why the common rules work.

If the true model is noiseless

$y=f(X_1)$ where $X_1$ is the correct set of independent variables

but we estimate

$\hat{y}=\hat{g}(X_2)$ where $X_2$ is a wrong set of independent variables and/or $g$ is an incorrect functional form

regardless the fact that in-sample error of the estimated model is zero or not, is well possible that his out of sample error is bigger. Therefore, following the standard rule/practice it seems like we've encountered overfitting, while the problem is not overfitting but bias.

Moreover, if the estimated model is well specified and the true model is noiseless the prediction error is zero. Therefore for any misspecified model, it is impossible to overfit (the well specified model is unbeatable even in sample). Moreover yet, if we deal with noiseless true model, bias-variance tradeoff disappear and the bias become the only problem even in prediction.

Answer 2

I agree that overfitting is not possible when the data-generating process is deterministic. However, this is not "too good to be true" because generalization is still a problem.

Consider that we can take our model $\hat{f}$ to be a Lagrange polynomial (or any other "look-up-table"-like interpolator) of whatever order is necessary to get 100% accuracy on all data.

Each time you give me another $\{x,y\}$, I'll simply increase the complexity of my model by adding some new terms - i.e. raise the order of my polynomial $\hat{f}$.

With a deterministic $f$, one can perhaps call this "perfect fitting." But we know for generalization reasons that such a model probably won't work well outside the training data on which "over/underfitting" are defined.

However, sometimes when people say "overfitting" they also mean "won't generalize well" in which case nothing can save you. We can't guarantee perfect generalization performance in any situation unless we get to sample every possible $\{x,y\}$ (infinitely often in the stochastic case) which is really not much different than saying you already know $f$.

Edit

I feel like you know the above already, and that your confusion stems from this:

"If there is a range models to choose from, the highly flexible ones will have low bias and high variance and will tend to overfit. The inflexible ones will have high bias and low variance and will tend to underfit."

That concept makes sense when talking about performance on a specific set of data points. It doesn't hold when considering all possible data points ("generalization performance"). There is nothing about a "highly flexible" model that will definitively cause low bias for inputs it wasn't trained on.

So I took your definition of under/overfitting to mean "on the training data." (I mean, even the word "fit" implies that). If you meant "in generalization" then the fallacy in your reasoning is the above quoted text.

Also, from wikipedia on the Bias-Variance Trade-Off:

"It is an often made fallacy to assume that complex models must have high variance (and thus low bias); High variance models are 'complex' in some sense, but the reverse needs not be true."

I think the key is to understand that for generalization performance, low bias comes from model correctness, not complexity.

Unprincipled complexity only reduces "bias" if you're talking about training set performance. This is not the precisely defined bias $E(f - \hat{f})$ in the bias-variance decomposition, which involves an expectation taken over all possible inputs.

Thus, I think your underlying confusion was thinking that highly flexible models have low bias in the expected value (generalization) sense, while that is only true if the expected value is approximated by a sample mean over the training set (on which we define the word "fit").

A sort of corollary to this idea is that if you have a huge, encompassingly representative amount of training data, then a massively complex model (like those of modern deep learning) can lower bias on a sample mean error that closely approximates the actual mean. But it should be noted that most of the successful massive models aren't full of "unprincipled complexity" - they often take advantage of crucial structures inherent to the data (e.g. using convolution on images, etc). Moreover, understanding the surprising generalization ability of massive deep models is still a point of research to this day (and research on the many ways that generalization ability can silently fail too, e.g. adversarial inputs).

Answer 3

We can treat Machine Learning book by Mitchell (1997) as an authoritative reference on this subject. On p. 67 he defines overfitting

Definition: Given a hypothesis space $H$, a hypothesis $h \in H$ is said to overfit the training data if there exists some alternative hypothesis $h' \in H$, such that $h$ has smaller error than $h'$ over the training examples, but $h'$ has a smaller error than $h$ over the entire distribution of instances.

Say, that you are given a sample of points from a noiseless polynomial function. You are to find the function using the polynomial regression model. You can easily imagine how given small sample, you could find many different solutions that fit the training sample perfectly, though do not fit well the entire distribution. An extreme case would be single datapoint, in such case finding the correct model would be impossible, so the solution would surely not generalize.

Someone can argue, that the above example does not fit the definition, since $h$ fits the training data equally well as $h'$, so this does not satisfy the definition criteria. My counterargument is, that in such case many big enough neural networks can't overfit as well, you just need make them fit the training data perfectly.

Another argument, may be that the example misses the point, since overfitting is about model fitting to noise, rather than to signal, hence it does not generalize. First, the definition above does not say anything about the noise. Second, if that would be the case, than we must conclude that the definition does not apply noiseless functions, so there is no answer to this question.