Improved Bounds on the Sample Complexity of Learning
| Title | Improved Bounds on the Sample Complexity of Learning |
| Publication Type | Journal Articles |
| Year of Publication | 2001 |
| Authors | Li Y, Long PM, Srinivasan A |
| Journal | Journal of Computer and System Sciences |
| Volume | 62 |
| Issue | 3 |
| Pagination | 516 - 527 |
| Date Published | 2001/05// |
| ISBN Number | 0022-0000 |
| Keywords | agnostic learning, empirical process theory, machine learning, PAC learning, sample complexity |
| Abstract | 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. |
| URL | http://www.sciencedirect.com/science/article/pii/S0022000000917410 |
| DOI | 10.1006/jcss.2000.1741 |