Learning Nested Concept Classes with Limited Storage

Abstract

Many existing learning methods use incremental algorithms that construct a generalization in one pass through a set of training data and modify it in subsequent passes (e.g., perceptrons, neural nets, and decision trees). Most of these methods do not store the entire training set, in essence employing a limited storage requirement that abstracts the notion of a compressed representation. The question we address is, how much additional processing time is required for methods with limited storage? Processing time for learning algorithms is equated in this paper with the number of passes necessary through a data set to obtain a correct generalization. For instance, neural nets require many passes through a data set before converging. Decision trees require fewer passes, but precise bounds are unknown. We consider limited storage algorithms for a particular concept class, nested hyperrectangles. We prove bounds that illustrate the fundamental trade-off between storage requirements and processing time required to learn an optimal structure. It turns out that our lower bounds apply to other algorithms and concept classes (e.g., decision trees) as well. Notably, imposing storage limitations on the learning task forces one to devise a completely different algorithm to reduce the number of passes. We also briefly discuss parallel learning algorithms. 1