L-BFGS

[Marcus Brubaker]

Quick question for everyone.  I'm considering implementing the limited memory version of BFGS in Stan.  The question is whether we would prefer this as a "new" algorithm (i.e., the users could set algorithm=bfgs or algorithm=lbfgs (or maybe algorithm=bfgs hessian_approx=limited) or simply as a drop-in replacement for BFGS.

The argument for the drop-in replacement is that, honestly, there's not a lot of reason to use BFGS if L-BFGS is available.  In general L-BFGS works better than BFGS and uses *much* less memory.  The flip side is that it's easy enough to have both just in case someone wanted to use BFGS instead.

I realize that most people may not care about this, but I thought I would check in before I got started.  Thoughts?

Cheers,

Marcus

[Bob Carpenter]

Only supporting L-BFGS makes most sense to me.

The more functions and options we have the more
testing we have to do and the more doc we have to write.
So unless there's a good motivation for keeping BFGS,
I'd say just replace it.

- Bob

[Ben Goodrich]

Nocedal and Wright

http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/264/chp%253A10.1007%252F978-0-387-40065-5_7.pdf?auth66=1383700937_ddec5bba9ea5a1994ae00038b73a436a&ext=.pdf

claims on page 180 that "The main weakness of the L-BFGS method is that it converges slowly on ill-conditioned problems—specifically, on problems where the Hessian matrix contains a wide distribution of eigenvalues." This is basically the same deal as strong Wolfe vs. weak Wolfe: I don't know how we can presume that the user has a well-conditioned / non-degenerate / etc. problem, particularly if someone is using it for some arbitrary optimization problem as opposed to finding a posterior mode or whatever.

So, I think we should have options. The documentation of L-BFGS is basically the same as the documentation of BFGS with about 1 additional option.

Ben

[Bob Carpenter]

On 11/3/13, 8:42 PM, Ben Goodrich wrote:
> Nocedal and Wright
>
> http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/264/chp%253A10.1007%252F978-0-387-40065-5_7.pdf?auth66=1383700937_ddec5bba9ea5a1994ae00038b73a436a&ext=.pdf
>
> claims on page 180 that "The main weakness of the L-BFGS method is that it converges slowly on ill-conditioned

> problems�specifically, on problems where the Hessian matrix contains a wide distribution of eigenvalues." This is

> basically the same deal as strong Wolfe vs. weak Wolfe: I don't know how we can presume that the user has a
> well-conditioned / non-degenerate / etc. problem, particularly if someone is using it for some arbitrary optimization
> problem as opposed to finding a posterior mode or whatever.

Is BFGS better behaved? I didn't see a direct comparison.
In fact, I can't seem to find much practical discussion anywhere
of plain-old BFGS.

Also, given that we're doing positive-definite Hessian
approximations, is there some connection to what we'll be
doing with Michael's SoftAbs construction for RHMC?

> So, I think we should have options. The documentation of L-BFGS is basically the same as the documentation of BFGS with
> about 1 additional option.

The effort's not in the original doc or even in the initial
coding, but in the maintenance.

And by that, I mean not only the doc, but also testing of
the algorithm and its interfaces through to command/R/Python,
as well as dealing with questions on the mailing list.

And again, these aren't just write once and they work forever,
any refactoring requires more work again because of the two alternatives.

If BFGS and L-BFGS have different behavior in terms of convergence
or efficiency, we need to doc it so that users know which one to
use. If one dominates the other, we only need the good one.

I'm not saying we shouldn't have both --- I don't know much
about either. I'm just trying to point out that multiplying
options is by no means cheap in software we plan to maintain.

- Bob

[Ben Goodrich]

I don't think L-BFGS dominates BFGS or vice versa, even within a particular class of optimization problems. Also, you wouldn't necessarily know if the Hessian were ill-conditioned until you solve the problem. In the chapter on limited memory methods, Nocedal and Wright are only comparing L-BFGS to other limited memory methods. I don't remember them ever comparing L-BFGS to BFGS because the main difference between them is that L-BFGS is simply necessary when your optimization problem has so many parameters that the machine doesn't have enough RAM to do BFGS.

But in the BFGS chapter

http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/265/chp%253A10.1007%252F978-0-387-40065-5_6.pdf?auth66=1383747383_b6da37dfd810ad1d77e52760cb0ffce8&ext=.pdf

they do talk about the ability of BFGS to self-correct within a few iterations if the Hessian approximation strays. Also, at some point during the process, BFGS achieves better than linear convergence on well-behaved problems, whereas I think L-BFGS is linear throughout.

Ben

[Bob Carpenter]

Thanks for the clarification.

If that's the case, then maybe it makes sense to keep BFGS.

Anyone else have an opinion?

I believe it was suggested that we get rid of Newton because
it is dominated.

What about the Nesterov method? Do we need that with the
BFGS(es)?

- Bob

On 11/4/13, 9:25 AM, Ben Goodrich wrote:
> I don't think L-BFGS dominates BFGS or vice versa, even within a particular class of optimization problems. Also, you
> wouldn't necessarily know if the Hessian were ill-conditioned until you solve the problem. In the chapter on limited
> memory methods, Nocedal and Wright are only comparing L-BFGS to other limited memory methods. I don't remember them ever
> comparing L-BFGS to BFGS because the main difference between them is that L-BFGS is simply necessary when your
> optimization problem has so many parameters that the machine doesn't have enough RAM to do BFGS.
>
> But in the BFGS chapter
>
> http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/265/chp%253A10.1007%252F978-0-387-40065-5_6.pdf?auth66=1383747383_b6da37dfd810ad1d77e52760cb0ffce8&ext=.pdf
>
> they do talk about the ability of BFGS to self-correct within a few iterations if the Hessian approximation strays.
> Also, at some point during the process, BFGS achieves better than linear convergence on well-behaved problems, whereas I
> think L-BFGS is linear throughout.
>
> Ben
>
> On Monday, November 4, 2013 2:34:45 AM UTC-5, Bob Carpenter wrote:
>
> On 11/3/13, 8:42 PM, Ben Goodrich wrote:
> > Nocedal and Wright
> >
> >
> http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/264/chp%253A10.1007%252F978-0-387-40065-5_7.pdf?auth66=1383700937_ddec5bba9ea5a1994ae00038b73a436a&ext=.pdf
> <http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/264/chp%253A10.1007%252F978-0-387-40065-5_7.pdf?auth66=1383700937_ddec5bba9ea5a1994ae00038b73a436a&ext=.pdf>
>
> >
> > claims on page 180 that "The main weakness of the L-BFGS method is that it converges slowly on ill-conditioned

> > problems�specifically, on problems where the Hessian matrix contains a wide distribution of eigenvalues." This is

> --
> You received this message because you are subscribed to the Google Groups "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.

[Marcus Brubaker]

My memory is fuzzy, but I recall seeing comparisons between BFGS and L-BFGS suggesting that, while L-BFGS has a slower theoretical rate of convergence, in practice it can actually converge a little faster, particularly when the curvature of the space varies significantly.  I can't find the paper anymore, but I think this was based on results on the CUTE test problems.  Anyway, I think I will implement both for now.  In fact, it should be straightforward to simply include L-BFGS as an option when running BFGS.  As part of it I'd like to include some tests on the models and we could use that to potentially make a final decision.

Regarding the Newton method, I know I've suggested removing it for the mean time.  The reason isn't so much that the optimization method is bad, but that it's currently computing the Hessian using a finite difference which will be, at best, inefficient.  Once we have higher-order autodiff and the Newton method uses that to get the Hessian, then it's definitely worth having for small to medium sized problems.

Cheers,

Marcus

To unsubscribe from this group and stop receiving emails from it, send an email to stan-dev+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

--
You received this message because you are subscribed to the Google Groups "stan development mailing list" group.

To unsubscribe from this group and stop receiving emails from it, send an email to stan-dev+unsubscribe@googlegroups.com.

[Matt Hoffman]

It's hard to say anything about the relative speeds of the two
algorithms during search. During convergence, BFGS achieves
superlinear convergence whereas LBFGS only achieves linear
convergence. That is, roughly speaking, –log(distance from optimum)
increases superlinearly with BFGS, whereas it only increases linearly
with LBFGS (same as gradient descent, but with better constants). In
practical terms, this means that if you use BFGS you might as well
wait for it to converge fully (modulo early stopping-type concerns),
whereas you might be waiting a very long time for LBFGS to converge to
10 digits of accuracy or whatever.

Matt

>>> email to stan-dev+u...@googlegroups.com.

>>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "stan development mailing list" group.
>> To unsubscribe from this group and stop receiving emails from it, send an

>> email to stan-dev+u...@googlegroups.com.

>> For more options, visit https://groups.google.com/groups/opt_out.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to stan-dev+u...@googlegroups.com.

[Allen Riddell]

I wonder if some of these deliberations might be illuminated by a benchmarking
suite for a range of models (perhaps all those in the BUGS examples)?

For example, here's one of pandas's benchmarking tests:

http://pandas.pydata.org/pandas-docs/vbench/vb_groupby.html

Best,

Allen

[Bob Carpenter]

Good idea. It'll be helpful going forward, too.

We're also trying to put something like this togeter for
regression testing of the sampler and other pieces of Stan
so we don't let performance slip during refactoring.

- Bob

[Bob Carpenter]

Sorry --- forgot to mention I created an issue/project:

https://github.com/stan-dev/stan/issues/371

- Bob

[Ben Goodrich]

I have a Hessian branch for RStan that is waiting for Mav to ack that also allows stan_demo() to use optimizing() instead of sampling(). But some of the models get stuck at a point where the violate a constraint or over/under flow to NaN or something like that and do not terminate.

Ben

[Ben Goodrich]

Specifically, these are the ones that have trouble optimizing for one reason or another:

> setdiff(model_names, working)
 [1] "inhalers"         "lsat"             "salm"             "schools"        
 [5] "simt4"            "fire"             "corr-lda"         "fx_factor"      
 [9] "gp-logit-predict" "gp-predict"       "irt2_multilevel"  "irt2"            
[13] "irt_multilevel"   "irt"              "nnmf"             "nnmf_vec"        

Ben

[Marcus Brubaker]

Agreed, in theory there is little to be said about search.  I am basing my assessment on empirical results on a number of test problems.  I'm not sure which paper I'm remembering, but poking around turned up http://www.ece.northwestern.edu/~nocedal/PDFfiles/limited-memory.pdf (see table 4 on page 8).  I wish I could find the 1988 tech report they reference, as it seems likely to have more results.

Ben, thanks for posting a list of the problems having issues with optimization.  I'll take a look and see what's happening with them.

Cheers,

Marcus

[Bob Carpenter]

On 11/8/13, 3:08 PM, Marcus Brubaker wrote:
> Agreed, in theory there is little to be said about search. I am basing my assessment on empirical results on a number
> of test problems. I'm not sure which paper I'm remembering, but poking around turned up
> http://www.ece.northwestern.edu/~nocedal/PDFfiles/limited-memory.pdf (see table 4 on page 8). I wish I could find the
> 1988 tech report they reference, as it seems likely to have more results.
>
> Ben, thanks for posting a list of the problems having issues with optimization. I'll take a look and see what's
> happening with them.

We know some of them aren't going to work in practice
because there are no modes.

If it's possible and not too much work, it'd be great to diagnose that
in the same way that the sampler diagnoses an improper posterior.

And by the way, Daniel and I have been using the optimizer
for the diff-eq models we've been developing and it's awesome.
The sampler takes about 10 minutes times 4 chains to generate 100
or so effective samples using the non-hierarchial model, whereas
the optimizer runs in about 30 seconds. This is just auto-diffing
a non-stiff integrator so far.


- Bob

[Bob Carpenter]

Oh, and I meant to add that we're going to have to
develop a benchmark test suite anyway, so it shouldn't be
too onerous to compare all the optimizers, including
BFGS vs. L-BFGS.

- Bob

On 11/8/13, 3:08 PM, Marcus Brubaker wrote:

> >>> email to stan-dev+u...@googlegroups.com <mailto:stan-dev%2Bunsu...@googlegroups.com>.

> >>> For more options, visit https://groups.google.com/groups/opt_out.
> >>
> >>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "stan development mailing list" group.
> >> To unsubscribe from this group and stop receiving emails from it, send an

> >> email to stan-dev+u...@googlegroups.com <mailto:stan-dev%2Bunsu...@googlegroups.com>.

> >> For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "stan development mailing list" group.
> > To unsubscribe from this group and stop receiving emails from it, send an

> > email to stan-dev+u...@googlegroups.com <mailto:stan-dev%2Bunsu...@googlegroups.com>.

> > For more options, visit https://groups.google.com/groups/opt_out.
>
> --
> You received this message because you are subscribed to the Google Groups "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to

> stan-dev+u...@googlegroups.com <mailto:stan-dev%2Bunsu...@googlegroups.com>.

[Marcus Brubaker]

On Fri, Nov 8, 2013 at 3:26 PM, Bob Carpenter <ca...@alias-i.com> wrote:

On 11/8/13, 3:08 PM, Marcus Brubaker wrote:

Agreed, in theory there is little to be said about search.  I am basing my assessment on empirical results on a number
of test problems.  I'm not sure which paper I'm remembering, but poking around turned up
http://www.ece.northwestern.edu/~nocedal/PDFfiles/limited-memory.pdf (see table 4 on page 8).  I wish I could find the
1988 tech report they reference, as it seems likely to have more results.

Ben, thanks for posting a list of the problems having issues with optimization.  I'll take a look and see what's
happening with them.

We know some of them aren't going to work in practice
because there are no modes.

If it's possible and not too much work, it'd be great to diagnose that
in the same way that the sampler diagnoses an improper posterior.

It should be possible.  Basically, if it stops optimizing due to a small change in objective value or small move in parameter space and the gradient is still large it probably means the function is unbounded and has no mode.  (It could also be a bug, an error in the gradient or an objective with extremely bad curvature, but those are less likely.)

 

And by the way, Daniel and I have been using the optimizer
for the diff-eq models we've been developing and it's awesome.
The sampler takes about 10 minutes times 4 chains to generate 100
or so effective samples using the non-hierarchial model, whereas
the optimizer runs in about 30 seconds.  This is just auto-diffing
a non-stiff integrator so far.

Glad to hear it's useful for you guys!  It was very much me scratching my own itch...the beauty of open source :)

Cheers,

Marcus

[Ben Goodrich]

The salm model in particular appears to go into an infinite loop if started with random inits.

[Marcus Brubaker]

Thoughts on the models I've looked at so far:

- schools is known to not have a mode (there was a bug about that a few weeks ago)

- I just tested inhalers and lsat and both ran as I would have expected.  lsat looks like it might have found a large plateau, so may not be finding the optima, but that's just a limitation of quasi-Newton methods

- salm looks like random inits are putting it in such a bad spot that no decent step can be found.  (The initial log prob tends to eb around -1e189, which is clearly bad.)  Running with init=0 is fine though.

salm should be bailing out instead of looping with those bad inits.  I'll look into what's going on there when I get a chance.

Cheers,

Marcus

[Bob Carpenter]

Thanks.

I'll try to make the point about needing a mode
in the manual.

It'd be great if we could detect infinite loops either due to
bad inits or lack of modes.

I can help with adding test cases with some guidance.

- Bob

> https://github.com/stan-dev/__stan/issues/371 <https://github.com/stan-dev/stan/issues/371>

>
> - Bob
>
> On 11/6/13, 1:38 PM, Bob Carpenter wrote:
> > Good idea. It'll be helpful going forward, too.
> >
> > We're also trying to put something like this togeter for
> > regression testing of the sampler and other pieces of Stan
> > so we don't let performance slip during refactoring.
> >
> > - Bob
> >
> > On 11/6/13, 7:06 AM, Allen Riddell wrote:
> >> I wonder if some of these deliberations might be illuminated by a benchmarking
> >> suite for a range of models (perhaps all those in the BUGS examples)?
> >>
> >> For example, here's one of pandas's benchmarking tests:
> >>

> >> http://pandas.pydata.org/__pandas-docs/vbench/vb_groupby.__html

> http://download.springer.com.__ezproxy.cul.columbia.edu/__static/pdf/265/chp%253A10.__1007%252F978-0-387-40065-5_6.__pdf?auth66=1383747383___b6da37dfd810ad1d77e52760cb0ffc__e8&ext=.pdf

> <http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/265/chp%253A10.1007%252F978-0-387-40065-5_6.pdf?auth66=1383747383_b6da37dfd810ad1d77e52760cb0ffce8&ext=.pdf>
>
> >>>>>>
> >>>>>>
> >>>>>> they do talk about the ability of BFGS to self-correct within a few
> >>>>>> iterations if the Hessian approximation strays.
> >>>>>> Also, at some point during the process, BFGS achieves better than linear
> >>>>>> convergence on well-behaved problems, whereas I
> >>>>>> think L-BFGS is linear throughout.
> >>>>>>
> >>>>>> Ben
> >>>>>>
> >>>>>> On Monday, November 4, 2013 2:34:45 AM UTC-5, Bob Carpenter wrote:
> >>>>>>
> >>>>>> On 11/3/13, 8:42 PM, Ben Goodrich wrote:
> >>>>>> > Nocedal and Wright
> >>>>>> >
> >>>>>> >
> >>>>>>
> >>>>>>

> http://download.springer.com.__ezproxy.cul.columbia.edu/__static/pdf/264/chp%253A10.__1007%252F978-0-387-40065-5_7.__pdf?auth66=1383700937___ddec5bba9ea5a1994ae00038b73a43__6a&ext=.pdf
> <http://download.springer.com.ezproxy.cul.columbia.edu/static/pdf/264/chp%253A10.1007%252F978-0-387-40065-5_7.pdf?auth66=1383700937_ddec5bba9ea5a1994ae00038b73a436a&ext=.pdf>
>
> >>>>>>
> >>>>>>
> >>>>>>
> <http://download.springer.com.__ezproxy.cul.columbia.edu/__static/pdf/264/chp%253A10.__1007%252F978-0-387-40065-5_7.__pdf?auth66=1383700937___ddec5bba9ea5a1994ae00038b73a43__6a&ext=.pdf

> >>>>>> email to stan-dev+u...@googlegroups.com__.
> >>>>>> For more options, visit https://groups.google.com/__groups/opt_out
> <https://groups.google.com/groups/opt_out>.

> >>>>>
> >>>>>
> >>>>> --
> >>>>> You received this message because you are subscribed to the Google Groups
> >>>>> "stan development mailing list" group.
> >>>>> To unsubscribe from this group and stop receiving emails from it, send an

> >>>>> email to stan-dev+u...@googlegroups.com__.
> >>>>> For more options, visit https://groups.google.com/__groups/opt_out
> <https://groups.google.com/groups/opt_out>.

> >>>>
> >>>>
> >>>> --
> >>>> You received this message because you are subscribed to the Google Groups
> >>>> "stan development mailing list" group.
> >>>> To unsubscribe from this group and stop receiving emails from it, send an

> >>>> email to stan-dev+u...@googlegroups.com__.
> >>>> For more options, visit https://groups.google.com/__groups/opt_out
> <https://groups.google.com/groups/opt_out>.

> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups "stan development mailing
> list" group.
> >>> To unsubscribe from this group and stop receiving emails from it, send an email to

> >>> stan-dev+u...@googlegroups.com__.
> >>> For more options, visit https://groups.google.com/__groups/opt_out
> <https://groups.google.com/groups/opt_out>.

> >>
> >
>
> --
> You received this message because you are subscribed to the Google Groups "stan development mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to

> stan-dev+u...@googlegroups.com <mailto:stan-dev%2Bunsu...@googlegroups.com>.