Improved Bounds on the Sample Complexity of Learning

TitleImproved Bounds on the Sample Complexity of Learning
Publication TypeJournal Articles
Year of Publication2001
AuthorsLi Y, Long PM, Srinivasan A
JournalJournal of Computer and System Sciences
Pagination516 - 527
Date Published2001/05//
ISBN Number0022-0000
Keywordsagnostic learning, empirical process theory, machine learning, PAC learning, sample complexity

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 well. 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 within a constant factor of the best possible. Our upper bound implies improved bounds on the sample complexity of learning according to Haussler's decision theoretic model.