Abstract: Upper bounds for the deviation between test error and training error of a learning machine are derived in the case where no probability distribution that generates the examples is assumed to exist. The bounds are data-dependent and algorithm dependent. The result justifies the concept of data-dependent and algorithm dependent VC-dimension.
nogroundtruth-1999.djvu nogroundtruth-1999.pdf nogroundtruth-1999.ps.gz
@misc{bottou-lecun-vapnik-1999,
author = {Bottou, L\'{e}on and {Le Cun}, Yann and Vapnik, Vladimir},
title = {Report: Predicting Learning Curves without the Ground Truth Hypothesis},
year = {1999},
month = {May},
note = {Available on http://leon.bottou.org/papers"},
url = {http://leon.bottou.org/papers/bottou-lecun-vapnik-1999},
}
This is a slightly modernized rewrite of (Bottou et al., 1994) with a stronger focus on the lack of independence assumptions, but these bounds were already present in the 1994 paper. Please refer to the notes associated with this earlier text.