# Would there be a model selection problem if we had access to an oracle that gave us the exact generalization error?

Let $\mathcal{E(h)}$ a function that given some hypothesis $h$ returns the generalization error for that fixed $h$.

I was reading some notes about model selection and generalization error and it said:

"If we had access to $\mathcal{E(h)}$, there would be no model selection problem either. We would simply select the larges $\mathcal{H}$ so as to find a classifier that minimizes the error."

I was not sure if I fully appreciated or understood that statement or actually agreed with the statement. The reason is that, even if we had access to $\mathcal{E(h)}$ (which I think they mean an oracle that takes $h$ and just says its true generalization error) I think it would still be problematic to find the model that has the hypothesis that generalizes well. The reason is, say that the model classes $\mathcal{H}$ is infinite (i.e. there is an infinite set of models to choose from). We don't really know when $\mathcal{E(h)}$ has reached its minimum unless we check for every $\mathcal{H}$ that is possible. i.e. even if we had such a thing I don't think the problem is eliminated so easily because how can we ever be sure we have truly found the best $\mathcal{H}$ (in polynomial time)? Basically I feel the question assumes that we have an oracle for determining when generalization is minimum too. Furthermore, as I pointed out, the algorithm/turning machine the suggested is decidable and not in P (i.e. it might run forever...)

The main issue/doubt that I have with this question is that even with such an Oracle, I am not convinced that model selection has been trivialized, an answer that tries to tackles this specific issue, has higher chances to tackle my question better.

Basically I feel the question assumes that we have an oracle for determining when generalization is minimum too.

Of course, having this would be superb. Having an oracle that gives us the best model would be even better. However, you seem to misinterpret the function of the oracle.

The task of model selection is to pick the best model from a given set. We do this by choosing the model which we believe to have the best generalization performance. Without an oracle to tell us $\mathcal{E}(h)$ we are forced to estimate the generalization performance instead, lets say $\hat{\mathcal{E}}(h)$.

Because we need to choose a model based on its estimated generalization performance we have no guarantees of choosing the right one. This is what makes model selection tricky (and somewhat arbitrary). If we had access to the true generalization performance, model selection would be a trivial.

The reason is, say that the model classes $\mathcal{H}$ is infinite (i.e. there is an infinite set of models to choose from).

This is a nice theoretical question but is somewhat tangential to the practical problem since one typically wishes to choose the best model within a finite set of options.

You are correct that a truly infinite set of models would yield an undecidable problem without making further assumptions. In practice, however, some further assumptions are reasonable.

It is common and often reasonable to assume that the functional form of $\mathcal{E}(h)$ behaves in a certain way with regards to hyperparameters of a given model class (for example convex). If such assumptions hold, the globally optimal hyperparameters could be found in polynomial time.

• I think your response is an interesting one, but I failed to understand the following claim that you make: "you seem to misinterpret the function of the oracle." You just state that without providing a explicit reason of why you think that. I just want to understand this issue better and I feel if you expand on that point or clarify it, it would be nice because my question is trying more to tackle the exact issue whether there is a model selection problem or not. I know it would be nice to have such a oracle, however, with it, I still think the model selection problem is not completely trivial – Pinocchio Apr 8 '14 at 23:21
• Because of the comment I made. Even with such an oracle, how do we exactly trivialize the model selection process. That is the aspect that is still no clear to me or the part that I am not convinced about. It seems to me that, even if we had such an oracle, I still can't really see a way of trivializing model selection without having a turning machine that might go in an infinite loop. – Pinocchio Apr 8 '14 at 23:22
• or maybe as you said, the reason I am having problems understanding this is, because I might have misunderstood the oracle the original sentences is talking about. – Pinocchio Apr 8 '14 at 23:25