Learning in parallel

In this paper, we extend Valiant's (Comm. ACM 27 (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.

Authors

• Jeffrey Scott Vitter
• Jyh-Han Lin

Keywords

No keywords are indexed for this paper.