Improved bounds on the sample complexity of learning

Yi Li; Philip M. Long; Aravind Srinivasan

doi:10.1006/jcss.2000.1741

Improved bounds on the sample complexity of learning

Yi Li^*
, Philip M. Long
, Aravind Srinivasan

^*Corresponding author for this work

National University of Singapore
Nokia

Research output: Contribution to journal › Article › peer-review

144 Scopus citations

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.

Original language	English
Pages (from-to)	516-527
Number of pages	12
Journal	Journal of Computer and System Sciences
Volume	62
Issue number	3
DOIs	https://doi.org/10.1006/jcss.2000.1741
State	Published - May 2001
Externally published	Yes

Keywords

Agnostic learning
Empirical process theory
Machine learning
PAC learning
Sample complexity

Access to Document

10.1006/jcss.2000.1741

Cite this

@article{da63e658389443efa46c724f3a49c446,

title = "Improved bounds on the sample complexity of learning",

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.",

keywords = "Agnostic learning, Empirical process theory, Machine learning, PAC learning, Sample complexity",

author = "Yi Li and Long, \{Philip M.\} and Aravind Srinivasan",

year = "2001",

month = may,

doi = "10.1006/jcss.2000.1741",

language = "英语",

volume = "62",

pages = "516--527",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Improved bounds on the sample complexity of learning

AU - Li, Yi

AU - Long, Philip M.

AU - Srinivasan, Aravind

PY - 2001/5

Y1 - 2001/5

N2 - 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.

AB - 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.

KW - Agnostic learning

KW - Empirical process theory

KW - Machine learning

KW - PAC learning

KW - Sample complexity

UR - https://www.scopus.com/pages/publications/0035340553

U2 - 10.1006/jcss.2000.1741

DO - 10.1006/jcss.2000.1741

M3 - 文章

AN - SCOPUS:0035340553

SN - 0022-0000

VL - 62

SP - 516

EP - 527

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 3

ER -

Improved bounds on the sample complexity of learning

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this