Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/43158
Title: Improved bounds on the sample complexity of learning
Authors: Li, Yi 
Long, Philip M. 
Srinivasan, Aravind 
Issue Date: 2000
Source: Li, Yi,Long, Philip M.,Srinivasan, Aravind (2000). Improved bounds on the sample complexity of learning. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms : 309-318. ScholarBank@NUS Repository.
Abstract: We present two improved bounds on the sample complexity of learning. First, 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. Next, we prove a lower bound on the sample complexity for learning according to the prediction model that is optimal to within a factor of 1+o(1).
Source Title: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
URI: http://scholarbank.nus.edu.sg/handle/10635/43158
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

41
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.