A composition theorem for learning algorithms with applications to geometric concept classes
This paper solves the open problem of exact learning geometric objects bounded by hyperplanes (and more generally by any constant degree algebraic surfaces) in the constant dimensional space from equivalence queries only (i.e., in the on-line learning model). We present a novel approach that allows, under certain conditions, the composition of learning algorithms for simple classes into an algorithm for a more complicated class. Informally speaking, it shows that if a class of concepts C is learnable in time t using a small space then @, the class of all functions of the form ~(gl, . . , gm) With 91, . . . . gm E C and any boolean function ~, is learnable in polynomial time in t and m. We then show that the class of halfspaces in a fixed dimension space is learnable with a small space.