Improved bounds on the sample complexity of learning

Yi Li; Philip M. Long; Aravind Srinivasan

Improved bounds on the sample complexity of learning

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

^*Corresponding author for this work

National University of Singapore

Research output: Contribution to conference › Paper › peer-review

11 Scopus citations

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

Original language	English
Pages	309-318
Number of pages	10
State	Published - 2000
Externally published	Yes
Event	11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: 9 Jan 2000 → 11 Jan 2000

Conference

Conference	11th Annual ACM-SIAM Symposium on Discrete Algorithms
City	San Francisco, CA, USA
Period	9/01/00 → 11/01/00

Cite this

@conference{0c31c95ae147439487735c33a6c491d4,

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

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

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

year = "2000",

language = "英语",

pages = "309--318",

note = "11th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 09-01-2000 Through 11-01-2000",

}

TY - CONF

T1 - Improved bounds on the sample complexity of learning

AU - Li, Yi

AU - Long, Philip M.

AU - Srinivasan, Aravind

PY - 2000

Y1 - 2000

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

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

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

M3 - 论文

AN - SCOPUS:0033879196

SP - 309

EP - 318

T2 - 11th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 9 January 2000 through 11 January 2000

ER -

Improved bounds on the sample complexity of learning

Abstract

Conference

Other files and links

Fingerprint

Cite this