Sample Complexity versus Approximation Error

We consider the problem of learning an unknown real valued function from a sequence of values of the function at randomly chosen points when the estimates are constrained to some class of functions called the hypothesis class Ideally the hypothesis class should be able to approximate a wide variety of target functions yet not need an excessive number of examples to ensure that a learning algorithm can choose a near optimal approximation to the target function We show that these two objectives are incompatible in the sense that as the approximation error of the hypothesis class decreases a lower bound on the sample complexity must increase The approximation error is the largest distance between an element of the class of candidate target functions and its best approximation in the hypothesis class The sample complexity is the number of examples necessary for a near optimal estimate of any target function The relationship between approximation error and sample complexity depends on a combinatorial dimension of the class of candidate target functions which are to be approximated We give an example of this relationship for the case of Lipschitz spaces  Suppose we wish to design an algorithm to estimate a real valued function given a sequence of values of the function at randomly chosen points There are two sources of error for such an algorithm approximation error and estimation error We refer to the class of all functions that the algorithm might output as the hypothesis class In general the target function is not a member of this class the error in approximating the target function is the distance to the closest function in the hypothesis class We would expect that as we consider hypothesis classes that are more complex in some sense this approximation error would decrease Estimation error arises because the algorithm must choose a hypothesis on the basis of a nite data sequence so it is unlikely to choose the best approximation to the target function For a xed length data sequence we would expect the estimation error to increase as the complexity of the hypothesis class is increased The amount of data necessary for a learning algorithm to reliably choose a near optimal approximation is called the sample complexity Approximation error and sample complexity have been determined for speci c hypothesis classes see for example It appears that there is a general tradeo between these two quantities if we choose a powerful hypothesis class so that the approximation error is small we will need a large data sequence to choose a near optimal function from the hypothesis class In this paper we quantify this tradeo The approximation error is de ned as the worst case error over all functions in some class K of functions that we wish to approximate Recent results show that the sam ple complexity of a hypothesis class depends on a measure of its complexity known as its fat shattering function We relate the fat shattering function of a hypothesis class to its approximation error in terms of properties of the class K of approximated functions This result is analogous to the Cram er Rao bound in parameter estimation it shows that if we want to choose a hypothesis class to achieve a certain approximation error there is an unavoidable statistical penalty The analogue is between the bias in the Cram er Rao bound and the approximation error and between variance and the estimation error In Section we give formal de nitions of the learning problem sample complexity and approximation error In Section we present the tradeo We apply this result in Section to speci c target function classes the homogeneous Lipschitz spaces Section contains some remarks and discussion about open problems De nitions and Notation Throughout the paper we use log to denote the logarithm to base two N to denote the natural numbers and let N N f g De ne X n let P be a probability distribution on X and let t be a valued function de ned on X We consider the problem of estimating t from a sequence x t x xm t xm where the xi are chosen according to P The estimates are restricted to some class F of valued functions de ned on X which we call the hypoth esis class The aim is to choose a function f in F so that the expected absolute di erence In this paper all functions are assumed to be measurable and the function class F satis es the mild measurability condition given in between t and f is small De ne the error of f with respect to P and t as