Improved bounds on the sample complexity of learning

We present a new general upper bound on the number of examples required to estimate all of the expectations of a set of random variables uniformly wel l. The quality of the estimates is measured using a variant of the relative error proposed by Haussler and Pollard. We also show that our bound is wit hin a constant factor of the best possible. Our upper bound implies improve d bounds on the sample complexity of learning according to Haussler's decis ion theoretic model. (C) 2001 Academic Press.