[
https://issues.apache.org/jira/browse/SPARK-14880?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15256996#comment-15256996
]
Joseph K. Bradley commented on SPARK-14880:
-------------------------------------------
Thanks for this suggestion. To get this feature merged, we would likely need
(a) more theoretical evidence supporting the algorithm and (b) significant
performance testing to demonstrate the improvements. For (a), as I recall, the
Zinkevich work requires that the loss be smooth, which would rule out support
for L1 regularization. Also, has the higher level iteration been analyzed to
prove its effect on convergence?
This could be a good algorithm to post as a Spark package. Would you be
interested in doing that?
I'm going to close this issue for now, but discussion can continue on the
closed JIRA.
> Parallel Gradient Descent with less map-reduce shuffle overhead
> ---------------------------------------------------------------
>
> Key: SPARK-14880
> URL: https://issues.apache.org/jira/browse/SPARK-14880
> Project: Spark
> Issue Type: Improvement
> Components: MLlib
> Reporter: Ahmed Mahran
> Labels: performance
>
> The current implementation of (Stochastic) Gradient Descent performs one
> map-reduce shuffle per iteration. Moreover, when the sampling fraction gets
> smaller, the algorithm becomes shuffle-bound instead of CPU-bound.
> {code}
> (1 to numIterations or convergence) {
> rdd
> .sample(fraction)
> .map(Gradient)
> .reduce(Update)
> }
> {code}
> A more performant variation requires only one map-reduce regardless from the
> number of iterations. A local mini-batch SGD could be run on each partition,
> then the results could be averaged. This is based on (Zinkevich, Martin,
> Markus Weimer, Lihong Li, and Alex J. Smola. "Parallelized stochastic
> gradient descent." In Advances in neural information processing systems,
> 2010,
> http://www.research.rutgers.edu/~lihong/pub/Zinkevich11Parallelized.pdf).
> {code}
> rdd
> .shuffle()
> .mapPartitions((1 to numIterations or convergence) {
> iter.sample(fraction).map(Gradient).reduce(Update)
> })
> .reduce(Average)
> {code}
> A higher level iteration could enclose the above variation; shuffling the
> data before the local mini-batches and feeding back the average weights from
> the last iteration. This allows more variability in the sampling of the
> mini-batches with the possibility to cover the whole dataset. Here is a Spark
> based implementation
> https://github.com/mashin-io/rich-spark/blob/master/src/main/scala/org/apache/spark/mllib/optimization/ParallelSGD.scala
> {code}
> (1 to numIterations1 or convergence) {
> rdd
> .shuffle()
> .mapPartitions((1 to numIterations2 or convergence) {
> iter.sample(fraction).map(Gradient).reduce(Update)
> })
> .reduce(Average)
> }
> {code}
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
