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

^*此作品的通讯作者

National University of Singapore
Nokia

科研成果: 期刊稿件 › 文章 › 同行评审

144 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	516-527
页数	12
期刊	Journal of Computer and System Sciences
卷	62
期	3
DOI	https://doi.org/10.1006/jcss.2000.1741
出版状态	已出版 - 5月 2001
已对外发布	是

访问文件

10.1006/jcss.2000.1741

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

指纹

引用此