[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15820180#comment-15820180 ] Weichen Xu commented on SPARK-10078: As the detail problems I list above(I only list a small part problems), in my opinion, breeze can provide the following base class and/or abstract interface FirstOrderMinimizerlevel DiffFunction interface LineSearch implementation (including StrongWolfeLinsearch and BacktrackingLinesearch) DistributedVector abstract interface BUT, the core logic of VF-LBFGS and VF-OWLQN (based on VF-LBFGS) should be implemented in spark mllib, for better optimization. > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15819964#comment-15819964 ] Weichen Xu commented on SPARK-10078: [~debasish83] But when we implement VF-LBFGS/VF-OWLQN base on spark, we found that many optimizations need to combine spark features and the optimizer algorithm closely, make a abstract interface supporting distributed vector (for example, Vector space operator include dot, add, scale, persist/unpersist operators and so on...) seems not enough. I give two simple problem to show the complexity when considering general interface: 1. Look this VF-OWLQN implementation based on spark: https://github.com/yanboliang/spark-vlbfgs/blob/master/src/main/scala/org/apache/spark/ml/optim/VectorFreeOWLQN.scala We know that OWLQN internal will help compute the pseudo-gradient for L1 reg, look the code function `calculateComponentWithL1`, here when computing pseudo-gradient using RDD, it also use an accumulator(only spark have) to calculate the adjusted fnValue, so that will the abstract interface containing something about `accumulator` in spark ? 2. About persist, unpersist, checkpoint problem in spark. Because of spark lazy computation feature, improper persist/unpersist/checkpoint order may cause serious problem (may cause RDD recomputation, checkpoint take no effect and so on), about this complexity, we can take a look into the VF-BFGS implementation on spark: it use the pattern "persist current step RDDs, then unpersist previous step RDDs" like many other algos in spark mllib. The complexity is at, spark always do lazy computation, when you persist RDD, it do not persist immediately, but postponed to RDD.action called. If the internal code call `unpersist` too early, it will cause the problem that an RDD haven't been computed and haven't been persisted, but already been unpersisted. This feature may be much different than other distributed platform, so that a general interface can really handle this problem correctly and still keep high efficient in the same time? [~sethah] Do you consider this detail problems when you designing the general optimizer interface ? > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15819851#comment-15819851 ] Weichen Xu commented on SPARK-10078: [~debasish83] Can L-BFGS-B be distributed computed when scaled to billions of features in high efficiency ? If only the interface supporting distributed vector, but internal computation still use local vector and/or local matrix, then it seems won't make much sense... Currently VF-LBFGS can turn LBFGS two loop recursion into distributed computing mode, but the L-BFGS-B seems much more complex then L-BFGS, can it also be computed in parallel ? > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=1581#comment-1581 ] Seth Hendrickson commented on SPARK-10078: -- As a part of [SPARK-17136|https://issues.apache.org/jira/browse/SPARK-17136] I am working on a generic optimization interface for Spark, which would allow users to easily plug in their own optimizers in place of built-in ones. Because of this, I have also been looking into how we can create an interface that allows optimization with both local and distributed vector types in a single interface. I have a branch that I have been doing some prototyping on [here|https://github.com/sethah/spark/tree/spark-vlbfgs]. Actually, I was able to get Yanbo's VLogisticRegression class working (on a very small dataset) using the VLBFGS optimizer in my branch, which also works with local vector types. Maybe you can let me know if this lines up at all with what you were thinking? Thinking about this interface without adding VL-BFGS, we can avoid any code duplication with Breeze to start because we can simply plug in the Breeze code to our abstraction (in my branch, that is what is done for LBFGS and OWLQN). Adding VL-BFGS is a bit trickier. The problems I see are that we need an abstraction that will allow us to persist and unpersist the parameter vectors during optimization as needed. Adding "persist" and "unpersist" methods to a vector space, for example, seems a leaky abstraction. It might make sense to add this to Breeze itself if we can avoid leaking RDD details into the interface. However, one benefit of SPARK-17136 is that we could potentially eliminate our dependence on Breeze in the future. I think it might make sense to implement our own VL-BFGS interface, even if there is some duplication. Actually, I think this is part of an important discussion that will happen as part of the optimization interface design. I hope to post a detailed design document for that JIRA sometime in the next few days. Finally, can you provide more detail on your proposed changes to DiffFunction? DiffFunction in Breeze is already abstract in it's parameter type... > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15809876#comment-15809876 ] Debasish Das commented on SPARK-10078: -- I looked into the code and I see we are replicating Breeze BFGS and OWLQN core logic in this PR: https://github.com/yanboliang/spark-vlbfgs/tree/master/src/main/scala/org/apache/spark/ml/optim. We can provide a DiffFunction interface that works on feature partition and add the VL-BFGS paper logic as a refactoring to current Breeze BFGS code... Now DiffFunction can run with a DistributedVector or a Vector. What that helps with is that even with features < 100M, we can run multi-core VLBFGS with putting multiple partitions and a if-else switch is not necessary. I can provide breeze interfaces based on your PR if you agree with the idea. BFGS and OWLQN are few variants but Breeze has several constraint solvers that use BFGS code... > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15807484#comment-15807484 ] Yanbo Liang commented on SPARK-10078: - +1 [~sethah] > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15805366#comment-15805366 ] Seth Hendrickson commented on SPARK-10078: -- As a part of [SPARK-17136|https://issues.apache.org/jira/browse/SPARK-17136]. I am looking into a design for generic optimizer interface for Spark.ML. This should ideally, be abstracted such that, as Yanbo mentioned, users can switch between them easily. I don't think adding this to Breeze is important since we hope to add our own interface directly into Spark. > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15804899#comment-15804899 ] Yanbo Liang commented on SPARK-10078: - [~debasish83] We are aim to implement VL-BFGS as an optimizer which should be similar with Breeze LBFGS/OWLQN, and switching between them should be automatically based on the number of features. So an abstract interface between the algorithm and optimizer is really necessary. I have a basic implementation at https://github.com/yanboliang/spark-vlbfgs, please feel free to review and comment the code. Thanks. > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15804882#comment-15804882 ] Yanbo Liang commented on SPARK-10078: - [~sethah] The description is a little misleading, it means the VL-BFGS implementation can fit the current API. Feature partitioning (VL-BFGS) or not (Breeze LBFGS) will be choose automatically depends on the number of features. The purpose of VL-BFGS is not to replace Breeze LBFGS, but as a complementary method. Thanks. > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15793770#comment-15793770 ] Debasish Das commented on SPARK-10078: -- [~mengxr] [~dlwh] is it possible to implement VL-BFGS as part of breeze so that OWLQN, LBFGS, LBFGS-B and proximal.NonlinearMinimizer get benefited by it ? We can bring it the way we bring LBFGS/OWLQN right now...If it makes sense, I can look at the design doc and propose a breeze interface to abstract RDD details... > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15793760#comment-15793760 ] Debasish Das commented on SPARK-10078: -- Ideally feature partitioning should be automatically tuned...at 100M features master only processing what we do with Breeze LBFGS / OWLQN will also get benefitted by VL-BFGSIdeally it should be part of breeze and a proper interface should be defined so that the Breeze VL-BFGS solver can be called in Spark ML... > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15793488#comment-15793488 ] Seth Hendrickson commented on SPARK-10078: -- [~yanboliang] I was a bit confused by the following comment under new requirements for VL-BFGS: "API consistency with Breeze L-BFGS so we can migrate existing code smoothly." What existing code are we migrating, and to where/what? Are we planning to replace the use of the Breeze LBFGS solvers with this VL-BFGS implementation? If so, what about the numerous use cases that do not need to partition by features? Thanks! > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15413623#comment-15413623 ] Yanbo Liang commented on SPARK-10078: - I posted the design document which is still WIP here. Please feel free to give comments and feedback. Thanks. https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Yanbo Liang > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). > Design document: > https://docs.google.com/document/d/1VGKxhg-D-6-vZGUAZ93l3ze2f3LBvTjfHRFVpX68kaw/edit?usp=sharing -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15376867#comment-15376867 ] Yanbo Liang commented on SPARK-10078: - Had offline discussion with [~mengxr] and [~josephkb], I will take over this task. Firstly I will post my design document for review soon. This work will be highly inspired by https://github.com/mengxr/spark-vl-bfgs. Thanks! > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Xiangrui Meng > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14978922#comment-14978922 ] Kotaro Tanahashi commented on SPARK-10078: -- When vector-free L-BFGS applies 2D partitioning to the training data, is it necessary to create 2D distributed version of Gradient class, such as LogisticGradient or HingeGradient? > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Xiangrui Meng > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). -- 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
[jira] [Commented] (SPARK-10078) Vector-free L-BFGS
[ https://issues.apache.org/jira/browse/SPARK-10078?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14734130#comment-14734130 ] Debasish Das commented on SPARK-10078: -- [~mengxr] will it be Breeze LBFGS modification or part of mllib.optimization ? Is someone looking into it ? > Vector-free L-BFGS > -- > > Key: SPARK-10078 > URL: https://issues.apache.org/jira/browse/SPARK-10078 > Project: Spark > Issue Type: New Feature > Components: ML >Reporter: Xiangrui Meng >Assignee: Xiangrui Meng > > This is to implement a scalable version of vector-free L-BFGS > (http://papers.nips.cc/paper/5333-large-scale-l-bfgs-using-mapreduce.pdf). -- 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
