Learning in Parallel

Abstract

In this paper, we extend Valiant's sequential model of concept learning from examples [Valiant 1984] and introduce models for the e cient learning of concept classes from examples in parallel. We say that a concept class is NC-learnable if it can be learned in polylog time with a polynomial number of processors. We show that several concept classes which are polynomial-time learnable are NC-learnable in constant time. Some other classes can be shown to be NC-learnable in logarithmic time, but not in constant time. Our main result shows that other classes, such as s-fold unions of geometrical objects in Euclidean space, which are polynomial-time learnable by a greedy set cover technique, are NC-learnable using a non-greedy technique. We also show that (unless P RNC) several polynomial-time learnable concept classes related to linear programming are not NC-learnable. Equivalence of various parallel learning models and issues of fault-tolerance are also discussed.