Константин Вячеславович Воронцов

Abstract—Combinatorial cross-validation functionals that characterize the generalization performance of learning algorithms are considered. Upper bounds are derived that are tighter than those in the Vapnik–Chervonenkis statistical theory. The initial data set is not assumed to be independent, identically distributed, or even random. The effect of localization of an algorithm family is described, and the concept of a local growth function is introduced. The basic principles of statistical theory are revised by using the combinatorial approach. The basic causes of complexity bound overestimation are analyzed. Keywords: computational learning theory, learning method, VC-dimension, local growth function, local effective VC-dimension. In learning theory, the generalization performance of a learning algorithm is characterized by the probability of an error. Unfortunately, this hypothetical quantity cannot be calculated or sometimes even satisfactorily evaluated, for example, in the case of small data sets. At the same time, in practice, any learning system deals only with finite data sets, both training and testing. Therefore, it is reasonable to characterize the generalization performance of algorithms with respect to finite data sets. Learning performance is empirically quantified by using independent testing sets, bootstrap, or cross-validation [1]. It is shown in this paper that upper bounds for cross-validation performance functionals can be derived without resorting