Evaluating the Performance of a Simple Inductive Procedure in the Presence of Overfitting Error

Abstract

The theory of uniform convergence extends the classical strong law of large numbers from a single real-valued function to an ensemble, or class, of such functions. Vapnik and Cervonenkis have characterized those classes of functions for which the uniform strong law holds. We refer to such classes as being uniformly convergent. The theory provides a powerful methodology with which one can establish the consistency of simple inductive procedures for a variety of statistical problems, including pattern recognition, density estimation and the training of neural networks. In practical situations, however, we may not have sufficient information determine by analytical means whether or not a particular class of functions is uniformly convergent. Here we address several questions concerning the existence and performance of inductive procedures when uniform convergence fails to hold. We begin by noting that when the number of observations is large the relevant behavior of functions from a class F can be described by a single real constant η(T). We then show that η(F) is a bound on the performance of the simple inductive procedure known as empirical risk minimization. Finally, we note that one can estimate η(F) empirically, without knowing the underlying distribution of the observations, and without knowing whether or not the class F is uniformly convergent.