Lower bounds for empirical and leave-one-out estimates of the generalization error

Usually re-sampling estimates are considered more efficient to estimate the generalization performances than the empirical error. In this paper we consider the leave one out estimate. We show that in the previous framework, it is not better than the empirical error. Moreover, we show that sometimes training error estimate is more efficient. The paper summarizes the framework of machine learning, defines the sample complexity, and recalls some usual results