The following sounds like a very basic question in learning theory to me, so I am hoping someone can point out the obvious.
Efron's "expected optimism" is the expected difference between the prediction and training errors. Efron (2004) shows that for a wide range of loss functions (the "q-family"), and virtually all modeling approaches, the expected optimism in modeling the mean of a vector is proportional to the sum of covariances of fitted and observed components. It thus seems natural that any sensible modeling approach would have non-negative expected optimism (because one tries at least in part to minimize the training error).
I wonder if a more general result exists, though. Suppose that we have an arbitrary optimization criterion (not necessarily a loss in Efron's q-family, maybe not even convex/differentiable/separable; just a function of the data and a tunable parameter). We minimize this criterion on the training data over all possible parameter values in some feasible set. Is the expected minimum obtained this way (where the expectation is taken over all training sets) necessarily an underestimate of the expected criterion value applied to new data, unseen during training (where now the expectation is over all training and all iid testing datasets, as in Efron's definition of optimism)?
In other words, is the expected optimism of a sensible modeling approach always negative? Or maybe one has to really require something of the distribution of the data and/or know something about the criterion?
Counter examples may also be enlightening.