Fast (distribution Speciic) Learning
pac-learning results are often criticized for demanding impractically large training samples. The common wisdom is that these large samples follow from the worst case nature of the analysis, and therefore pac-learning, though desirable, must not be a practical goal. We however consider an alternative view: perhaps these large sample sizes are due to the presumed learning strategies which make ineecient use of the available training data. To demonstrate this, we consider sequential learning strategies that autonomously decide when to stop training based on observing training examples as they arrive. We show that for distribution speciic learning these algorithms require far fewer training examples (on average) than existing xed sample size approaches, and are able to learn with certainty not just high probability. In fact, a simple sequential strategy is optimally eecient in many cases.