On the Sample Complexity of Weakly Learning

Authors

Sally A. Goldman, Washington University in St Louis
Michael J. Kearns, AT&T Bell Laboratories
Robert E. Schapire, AT&T Bell Laboratories

Document Type

Technical Report

Publication Date

1992-09-22

Filename

WUCS-92-33.pdf

Technical Report Number

WUCS-92-33

Abstract

In this paper, we study the sample complexity of weak learning. That is, we ask how much data must be collected from an unknown distribution in order to extract a small but significant advantage in prediction. We show that it is important to distinguish between those learning algorithms that output deterministic hypotheses and those that output randomized hypotheses. We prove that in the weak learning model, any algorithm using deterministic hypotheses to weakly learn a class of Vapnik-Chervonenkis dimension d(n) requires (omega) (square root of d(n) examples.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7PC30QS

Recommended Citation

Goldman, Sally A.; Kearns, Michael J.; and Schapire, Robert E., "On the Sample Complexity of Weakly Learning" Report Number: WUCS-92-33 (1992). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/596