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 efficient learning of concept classes from examples {\em in parallel}. We say that a concept class is {\em 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-learnable are {\em NC}-learnable in constant time. Some other classes, such as {\em s}-fold unions of geometrical objects in Euclidean space, which are polynomial-learnable by a greedy technique, are {\em NC}-learnable using a non-greedy technique. Some problems can be shown to be {\em NC}-learnable, but must require more than constant time. We also show that (unless $P \subset RNC$) several concept classes related to linear programming are not {\em NC}-learnable. We conclude by investigating some fault-tolerant parallel learning algorithms.