Prediction interval based on cross-validation (CV) In the text books and youtube lectures I learned a lot about iterative models such as boosting, but I never saw anything about deriving a prediction interval.
Cross validation is used for the following:


*

*Model selection: Try different models and choose the one that fits best. In the case of boosting, use CV to select tuning parameters.

*Model assessment: Estimate the performance of the selected model


Several parameters are important of the model assessment, one of them is the expected prediction error. Cross validation provides a good estimate of the prediction error, as well described in the book "The Elements of
Statistical Learning".
But how do we use the expected prediction error to build a prediction interval? 
And if you predict the price of a house for example, the prediction interval will be higher for a house of 500.000€ compared to a house of 200.000€. How do we estimate these prediction intervals using cross validation?
 A: After reading over this question again, I can give you the following bound:
Assume the samples are drawn iid, the distribution is fixed, and the loss is bounded by $B$, then with probability at least $1 - \delta$,
$$
\mathbb{E}[\mathcal{E}(h)] \leq \hat{\mathcal{E}}(h) + B\sqrt{\frac{\log \frac{1}{\delta}}{2m}}
$$
where $m$ is the sample size, and $1-\delta$ is the confidence. The bound holds trivially by McDiarmid's inequality.
$m$ is the sample size, $\mathbb{E}[\mathcal{E}(h)]$ is the generalization error, and $\hat{\mathcal{E}}(h)$ is the test error for hypothesis.
Please don't report only the cross validation error nor the test error, those are meaningless in general since they are just point estimates. 

Old post for record:
I'm not sure that I completely understood your question, but I will take a stab at it. 
First, I am not sure how you would define a prediction interval for model selection, since, as I understand it, prediction intervals make some distributional assumptions. Instead, you could derive concentration inequalities, which essentially bound a random variable by its variance for some probability. Concentration inequalities are used throught machine learning, including the advanced theory for boosting. In this case you want to bound the generalization error (your error in general, points you haven't seen) by your empirical error (your error on the test set) plus some complexity term and a term that relates to the variance.
Now I need to dispell a misunderstanding about cross validation that is extremely common. Cross validation will only give you an unbiased estimate of the expected error of a model FOR A FIXED SAMPLE SIZE. The proof for this only works for the leave one out protocol. This is actually fairly weak, since it gives you no information regarding the variance. On the other hand, cross validation will return a model that is close to the structural risk minimization solution, which is the theoretically best solution. You can find the proof in the appendix here: http://www.cns.nyu.edu/~rabadi/resources/scat-150519.pdf
So how to derive a generalization bound? (Remember a generalization bound is basically a prediction interval about the generalization error for a specific model). Well, these bounds are algorithm specific. Unfortunately there is only one textbook that puts bounds for all of the commonly used algorithms in machine learning (including boosting). The book is Foundations of Machine Learning (2012) by Mohri, Rostamizadeh, and Talwalkar. For lecture slides that cover the material, you can find them on Mohri's web-page: http://www.cs.nyu.edu/~mohri/ml14/
While Elements of Statistical Learning is an important and somewhat helpful book, it is not very rigorous and it omits many very important technical details regarding the algorithms and completely omits any sort of generalization bounds. Foundations of Machine Learning is the most comprehensive book for machine learning (which makes sense seeing as it was written by some of the best in the field). However, the textbook is advanced, so just beware of technical details. 
The generalization bound for boosting can be found (with proof) here: http://www.cs.nyu.edu/~mohri/mls/lecture_6.pdf
I hope those are enough pointers to answer your question. I'm hesitant about giving a complete answer because it will take about 50 pages to go over all of the necessary details, let alone the preliminary discussions...
Good luck!
