spark-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Debasish Das <debasish.da...@gmail.com>
Subject Re: MLLib - Thoughts about refactoring Updater for LBFGS?
Date Wed, 05 Mar 2014 16:50:59 GMT
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 ?

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.

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.

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.

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 :-)

Thanks.
Deb



On Tue, Mar 4, 2014 at 8:13 PM, dlwh <david.lw.hall@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 &lt;dbtsai@&gt; 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.
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message