apache/spark — pull request #166 by yinxusen (2014-03-18 06:43:31+00:00)
Title: [WIP] [MLLIB-28] An optimized GradientDescent implementation 

New JIRA issue [MLLIB-28](https://spark-project.atlassian.net/browse/MLLIB-28) with this pull request bring a new implementation of `GradientDescent` named `GradientDescentWithLocalUpdate`. The `GradientDescentWithLocalUpdate` can outperform the original `GradientDescent` by about 1x ~ 4x without sacrificing accuracy, and can be easily adopted by most classification and regression algorithms in MLlib.

Parallelism of many ML algorithms are limited by the sequential updating process of optimization algorithms they use. However, by carefully breaking the sequential chain, the updating process can be parallelized. In the`GradientDescentWithLocalUpdate` , we split the iteration loop into multiple supersteps. Within each superstep, an inner loop that runs a local optimization process is introduced into each partition. During the local optimization, only local data points in the partition are involved. Since different partitions are processed in parallel, the local optimization process is natually parallelized. Then, at the end of each superstep, all the gradients and loss histories computed from each partition are collected and merged in a bulk synchronous manner.

Detailed experiments and results in the original [pull request](https://github.com/apache/incubator-spark/pull/407) and [comments](https://github.com/apache/incubator-spark/pull/407#issuecomment-33356196).