<p>There have been efforts to parallelize most of the well-known classifiers, including boosting [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.1551&amp;rep=rep1&amp;type=pdf">a paper</a>], SVM [<a href="http://books.nips.cc/papers/files/nips17/NIPS2004_0190.pdf">a paper</a>], and even decision trees [<a href="http://jmlr.csail.mit.edu/papers/volume11/ben-haim10a/ben-haim10a.pdf">a paper</a>].  Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.</p>

<p>From the theory end, the question is harder because when you talk about learning you have to think about the target function.  For example, we don't even know decision trees to be PAC-learnable, so if the <em>target</em> (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem.  Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.  </p>

<p>But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice.   For example, in practice, it matters whether the parallelism is over cores or clusters.  One algorithm developed especially for practical use in large-data settings is <a href="http://hunch.net/~vw/">VW</a>, and it's starting to <a href="http://hunch.net/?p=1068">support</a> parallelism.  You might be interested in the <a href="http://lccc.eecs.berkeley.edu/papers.html">papers</a> in the NIPS 2010 <a href="http://lccc.eecs.berkeley.edu/">workshop</a> on practical parallel learning.</p>

CC BY-SA 2.5
2011-01-25T21:48:52.317Z
2011-01-25T21:54:29.660Z
2011-01-25T21:54:29.660Z
Lev Reyzin
<p>What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?</p>

<p>Off hand it looks to me like some standard classifiers I know of stack up as follows but I could be totally wrong:</p>

<p>Random Forests - Very parallelizeable as long as each machine can hold all the data (i.e. can't divide up the training data per se, but otherwise parallelizeable).</p>

<p>Boosting - ?</p>

<p>Support Vector Machine - Not very parallelizable.</p>

<p>Decision trees - Can be divided up in part, but not very efficiently. </p>

CC BY-SA 3.0
2015-01-30T10:08:56.707Z
This post need an update. Currently DNNs are the the algorithms that benefit the most from the parallel computation. and boosting are hardly parallelizable.
TNM
<lg.learning><machine-learning><dc.parallel-comp>
What machine learning classifiers are the most parallelizeable?
John Robertson
# What machine learning classifiers are the most parallelizeable?

(Asked by: username_0 on 2011-01-25)

What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?

Off hand it looks to me like some standard classifiers I know of stack up as follows but I could be totally wrong:

Random Forests - Very parallelizeable as long as each machine can hold all the data (i.e. can't divide up the training data per se, but otherwise parallelizeable).

Boosting - ?

Support Vector Machine - Not very parallelizable.

Decision trees - Can be divided up in part, but not very efficiently.

**Tags:** lg.learning, machine-learning, dc.parallel-comp

> **Comments:**
> **username_1**: This post need an update. Currently DNNs are the the algorithms that benefit the most from the parallel computation. and boosting are hardly parallelizable.  

---

## 1 answers

### Answer by username_2 on 2011-01-25. Score: 11 | Accepted answer

There have been efforts to parallelize most of the well-known classifiers, including boosting [[a paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.29.1551&rep=rep1&type=pdf)], SVM [[a paper](http://books.nips.cc/papers/files/nips17/NIPS2004_0190.pdf)], and even decision trees [[a paper](http://jmlr.csail.mit.edu/papers/volume11/ben-haim10a/ben-haim10a.pdf)]. Of course, by admitting parallelism, you sometimes lose out on other aspects, whether it be algorithm implementability, sample complexity, or other usual suspects.

From the theory end, the question is harder because when you talk about learning you have to think about the target function. For example, we don't even know decision trees to be PAC-learnable, so if the *target* (as well as the method) is a decision tree, then we can't even learn it (yet) without introducing extra facets to the problem. Boosting gets around that by assuming a weak learning condition, SVM a margin, etc. I think those assumptions transfer to the parallel case to give you PAC learning.

But as always, there's a big gap between the frontiers (and thereby concerns) of theory and of practice. For example, in practice, it matters whether the parallelism is over cores or clusters. One algorithm developed especially for practical use in large-data settings is [VW](http://hunch.net/~vw/), and it's starting to [support](http://hunch.net/?p=1068) parallelism. You might be interested in the [papers](http://lccc.eecs.berkeley.edu/papers.html) in the NIPS 2010 [workshop](http://lccc.eecs.berkeley.edu/) on practical parallel learning.


---

