Learning in Parallel

J. S. Vitter and J.-H. Lin. ``Learning in Parallel,'' Information and Computation, 92(2), February 1992, 179-202. A shortened version appears in Proceedings of the 1st Annual ACM Workshop on Computational Learning Theory (COLT '88), Cambridge, MA, August 1988, published by Morgan Kaufmann, San Mateo, CA, 106-124.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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 in parallel. We say that a concept class is ${\cal 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 ${\cal NC}$-learnable in constant time. Some other classes can be shown to be ${\cal 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 ${\cal NC}$-learnable using a non-greedy technique. We also show that (unless ${\cal P}\subseteq {\cal RNC}$) several polynomial-time learnable concept classes related to linear programming are not ${\cal NC}$-learnable. Equivalence of various parallel learning models and issues of fault-tolerance are also discussed.