LEARNING IN PARALLEL

In this paper, we extend Valiant's (Comm. ACM27 (1984), 1134-1142) sequential model of concept learning from examples and introduce models for the efficient 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 nongreedy 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. © 1992.