On the Sample Complexity of Weakly Learning
Sally A. Goldman · Open Scholarship Institutional Repository (Washington University in St. Louis) · 1992
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\\Gamma p d(n)) examples. In contrast, when randomized hypotheses are allowed, we show that \\Theta(1) examples suffice in some cases. We then show that there exists an efficient algorithm using deterministic hypotheses that weakly learns against any distribution on a set of size d(n) with only O(d(n) 2=3 ) examples. Thus for the class of symmetric Boolean functions over n variables, where the strong learning sample complexity is \\Theta(n), the sample complexi...