Is "not-overfitting" a utopian scenario? We say a model overfits when classification error increases on the test data. The reason behind this is that the training data is not a representative of the distribution from which data is sampled.
Can we ever say that a model with a given set of parameters does not overfit?
My question stems from the fact that the test data is also not a representative of the distribution, so having low test error also does not mean that the model will not overfit. Instead, we can only claim that with high probability this model will not overfit.
Is there a flaw in this line of reasoning? 
 A: If a model is capable of representing the Bayes optimal decision surface then it is capable of avoiding overfitting the data, the difficulty lies in estimating the parameters of the model from a finite training sample that give that bayes optimal decision surface.  This generally will not happen because the training criterion used to estimate the parameters will have a non-zero variance, due to the noise in the finite training sample.  So the best we can probably do is to say that the method is asymptotically unbiased, in the sense that it the limit of an infinite training sample, the model will not overfit the data (it is questionable whether asymptotics are really relevant in a discussion about overfitting!).  Alternatively we can devise things like PAC (probably approximately correct) bounds, which give a bound on the error of a model that applies with a given probability.  The field of Computational Learning Theory seems to be the branch of statistics that is most relevant to this question.
Note that models can over-fit and under-fit the data, so the idea that a model can exactly avoid over-fitting the data is a bit like the idea of an exactly unbiased coin - it is a theoretical concept rather than a practical object.
