[
https://issues.apache.org/jira/browse/SPARK-1503?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14598709#comment-14598709
]
Aaron Staple commented on SPARK-1503:
-------------------------------------
I believe this stopping criteria was added after the paper was written. It is
documented on page 8 of the userguide
(https://github.com/cvxr/TFOCS/raw/master/userguide.pdf) but unfortunately no
explanation is provided. (The userguide also documents this as a <= test, while
the current code uses <.) And unfortunately I couldn’t find an explanation in
the code or git history.
I think the switch to absolute tolerance may be because a relative difference
measurement could be less useful when the weights are extremely small, and 1 is
a convenient cutoff point. (Using 1, the equation is simple and the
interpretation is clear.) I believe [~mengxr] alluded to switching to an
absolute tolerance at 1 already
(https://github.com/apache/spark/pull/3636#discussion_r22078041) so he might be
able to provide more information.
With regard to using the new weight norms as the basis for measuring relative
weight difference, I think that if the convergence test passes using either the
old or new weight norms, then the old and new norms are going to be very
similar. It may not make a significant difference which test is used. (It may
also be worth pointing out that in cases where the tolerance tests with respect
to different old/new weights return different results, if the tolerance wrt new
weights is met (and wrt old weights is not) then the weight norm increased
slightly; if the tolerance wrt the old weights is met (and wrt new weights not)
then we weight norm decreased slightly.)
Finally, TFOCS adopts a policy of skipping the convergence test after the first
iteration if the weights are unchanged. I believe this condition is based on
implementation specific behavior and does not need to be adopted generally.
> Implement Nesterov's accelerated first-order method
> ---------------------------------------------------
>
> Key: SPARK-1503
> URL: https://issues.apache.org/jira/browse/SPARK-1503
> Project: Spark
> Issue Type: New Feature
> Components: MLlib
> Reporter: Xiangrui Meng
> Assignee: Aaron Staple
> Attachments: linear.png, linear_l1.png, logistic.png, logistic_l2.png
>
>
> Nesterov's accelerated first-order method is a drop-in replacement for
> steepest descent but it converges much faster. We should implement this
> method and compare its performance with existing algorithms, including SGD
> and L-BFGS.
> TFOCS (http://cvxr.com/tfocs/) is a reference implementation of Nesterov's
> method and its variants on composite objectives.
--
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
