[
https://issues.apache.org/jira/browse/MAHOUT-1273?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13727161#comment-13727161
]
Ted Dunning commented on MAHOUT-1273:
-------------------------------------
Looking over these notes, I still see the same fundamental problem.
In the penalized case, you aggregate X'X and X'Y and then solve in the reducer
for \beta. The problem here is that changing \beta will change Y which will
correspondingly change X'Y. That means that your solution of \beta is not the
optimum value.
To do better, you would have to iterate the map-reduce until you get to actual
convergence.
What you have here is a form of mini-batch coordinate descent and, indeed, I
think a true mini-batch approach would be likely to do better.
Unless you can show that multiple map-reduce iterations don't help, I can't see
how this algorithm is likely to work. Since the values of Y are likely to
change drastically with a new value of \beta, I can't see how this is likely to
be true.
> Single Pass Algorithm for Penalized Linear Regression with Cross Validation
> on MapReduce
> ----------------------------------------------------------------------------------------
>
> Key: MAHOUT-1273
> URL: https://issues.apache.org/jira/browse/MAHOUT-1273
> Project: Mahout
> Issue Type: New Feature
> Affects Versions: 0.9
> Reporter: Kun Yang
> Labels: documentation, features, patch, test
> Fix For: 0.9
>
> Attachments: Algorithm and Numeric Stability.pdf, java files.pdf,
> Manual and Example.pdf, Notes.pdf, PenalizedLinear.pdf,
> PenalizedLinearRegression.patch
>
> Original Estimate: 720h
> Remaining Estimate: 720h
>
> Penalized linear regression such as Lasso, Elastic-net are widely used in
> machine learning, but there are no very efficient scalable implementations on
> MapReduce.
> The published distributed algorithms for solving this problem is either
> iterative (which is not good for MapReduce, see Steven Boyd's paper) or
> approximate (what if we need exact solutions, see Paralleled stochastic
> gradient descent); another disadvantage of these algorithms is that they can
> not do cross validation in the training phase, which requires a
> user-specified penalty parameter in advance.
> My ideas can train the model with cross validation in a single pass. They are
> based on some simple observations.
> The core algorithm is a modified version of coordinate descent (see J.
> Freedman's paper). They implemented a very efficient R package "glmnet",
> which is the de facto standard of penalized regression.
> I have implemented the primitive version of this algorithm in Alpine Data
> Labs.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
