On Wed, Mar 5, 2014 at 8:50 AM, Debasish Das <debasish.da...@gmail.com>wrote:
> Hi David, > > Few questions on breeze solvers: > > 1. I feel the right place of adding useful things from RISO LBFGS (based on > Professor Nocedal's fortran code) will be breeze. It will involve stress > testing breeze LBFGS on large sparse datasets and contributing fixes to > existing breeze LBFGS with the learning from RISO LBFGS. > > You agree on that right ? > That would be great. > > 2. Normally for doing experiments like 1, I fix the line search. What's > your preferred line search in breeze BFGS ? I will also use that. > > More Thuente and Strong wolfe with backtracking helped me in the past. > The default is a Strong Wolfe search: https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/StrongWolfe.scala > > 3. The paper that you sent also says on L-BFGS-B is better on box > constraints. I feel It's worthwhile to have both the solvers because many > practical problems need box constraints or complex constraints can be > reformulated in the realm of unconstrained and box constraints. > Example use-cases for me are automatic feature extraction from photo/video > frames using factorization. > > I will compare L-BFGS-B vs constrained QN method that you have in Breeze > within an analysis similar to 1. > Great. Yeah I fully expect l-bfgs-b to be better on box constraints. It turns out that this other method looked easier to implement and gave reasonably good results even with box constraints. > > 4. Do you have a road-map on adding CG solvers in breeze ? Linear CG solver > to compare with BLAS posv seems like a good usecase for me in mllib ALS. > DB sent a paper by Professor Ng which shows the effectiveness of CG and > BFGS over SGD in the email chain. > We have a linear CG solver ( https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/linear/ConjugateGradient.scala) which is used in the Truncated Newton solver. ( https://github.com/scalanlp/breeze/blob/master/src/main/scala/breeze/optimize/TruncatedNewtonMinimizer.scala) But I've not implemented nonlinear CG, and honestly hadn't planned on it, per below. > > I believe on non-convex problems like Matrix Factorization, CG family might > converge to a better solution than BFGS. No way to know till we experiment > on the datasets :-) > I've never had good experience with CG, and a vision colleague of mine found that LBFGS was better on his (non-convex) stuff, but I could be easily persuaded. Thanks! -- David > > Thanks. > Deb > > > > On Tue, Mar 4, 2014 at 8:13 PM, dlwh <david.lw.h...@gmail.com> wrote: > > > Just subscribing to this list, so apologies for quoting weirdly and any > > other > > etiquette offenses. > > > > > > DB Tsai wrote > > > Hi Deb, > > > > > > I had tried breeze L-BFGS algorithm, and when I tried it couple weeks > > > ago, it's not as stable as the fortran implementation. I guessed the > > > problem is in the line search related thing. Since we may bring breeze > > > dependency for the sparse format support as you pointed out, we can > > > just try to fix the L-BFGS in breeze, and we can get OWL-QN and > > > L-BFGS-B. > > > > > > What do you think? > > > > I'm happy to help fix any problems. I've verified at points that the > > implementation gives the exact same sequence of iterates for a few > > different > > functions (with a particular line search) as the c port of lbfgs. So I'm > a > > little surprised it fails where Fortran succeeds... but only a little. > This > > was fixed late last year. > > > > OWL-QN seems to mostly be stable, but probably deserves more testing. > > Presumably it has whatever defects my LBFGS does. (It's really pretty > > straightforward to implement given an L-BFGS) > > > > We don't provide an L-BFGS-B implementation. We do have a more general > > constrained qn method based on > > http://jmlr.org/proceedings/papers/v5/schmidt09a/schmidt09a.pdf (which > > uses > > a L-BFGS type update as part of the algorithm). From the experiments in > > their paper, it's likely to not work as well for bound constraints, but > can > > do things that lbfgsb can't. > > > > Again, let me know what I can help with. > > > > -- David Hall > > > > > > On Mon, Mar 3, 2014 at 3:52 PM, DB Tsai <dbtsai@> wrote: > > > Hi Deb, > > > > > >> a. OWL-QN for solving L1 natively in BFGS > > > Based on what I saw from > > > > > > https://github.com/tjhunter/scalanlp-core/blob/master/learn/src/main/scala/breeze/optimize/OWLQN.scala > > > , it seems that it's not difficult to implement OWL-QN once LBFGS is > > > done. > > > > > >> > > >> b. Bound constraints in BFGS : I saw you have converted the fortran > > >> code. > > >> Is there a license issue ? I can help in getting that up to speed as > > >> well. > > > I tried to convert the code from Fortran L-BFGS-B implementation to > > > java using f2j; the translated code is just a messy, and it just > > > doesn't work at all. There is no license issue here. Any idea about > > > how to approach this? > > > > > >> c. Few variants of line searches : I will discuss on it. > > >> For the dbtsai-lbfgs branch seems like it already got merged by > Jenkins. > > > I don't think it's merged into master. Still have couple things needed > > > to be cleaned up. Just open the PR to have public feedback. > > > > > >> Is this getting merged to the master or there will be revisions on it > ? > > >> > > >> https://github.com/apache/spark/pull/53 > > >> > > >> Thanks. > > >> Deb > > > > > > Sincerely, > > > > > > DB Tsai > > > Machine Learning Engineer > > > Alpine Data Labs > > > -------------------------------------- > > > Web: http://alpinenow.com/ > > > > > > > > > > -- > > View this message in context: > > > http://apache-spark-developers-list.1001551.n3.nabble.com/MLLib-Thoughts-about-refactoring-Updater-for-LBFGS-tp2493p3935.html > > Sent from the Apache Spark Developers List mailing list archive at > > Nabble.com. > > >
