BFGS in develop; RStan doc and integration
21 views
Skip to first unread message
Bob Carpenter
May 21, 2013, 6:22:56 PM5/21/13
to stan...@googlegroups.com
[moved discussion to stan-dev]
On 5/21/13 6:15 PM, Jiqiang Guo wrote:
> Just newton's method in RStan 1.3.0. In the develop branch, there is
> nesterov's accelerated gradient method. BFGS is not there yet.
BFGS is not in the develop branch yet?
If it's not, and it's what we want people to use, can
someone add it? Or are there other issues we're waiting
to get resolved?
> It is not that documented because it's not documented in Stan.
Can you add the doc to R about what method (or methods) are available?
I'll try to review the RStan doc again soon --- both RStan
and its doc have grown tremendously since RStan 1.0 and I
haven't been keeping up as much as I should.
If anyone finds places we need more doc in Stan itself, please
do one of the following:
* add the doc yourself
* ask for help on stan-dev
* submit an issue on GitHub
- Bob
>
> --
> Jiqiang
> On Tue, May 21, 2013 at 6:10 PM, Bob Carpenter <ca...@alias-i.com> wrote:
>> On 5/21/13 6:03 PM, Matt Hoffman wrote:
>>>
>>> Was that using Newton's method or BFGS?
>>
>>
>> I don't know, which is why I said it's whatever RStan uses!
>> I don't see any explanation in the RStan doc, which only refers
>> to "Stan's optimization method".
>
On 5/21/13 6:15 PM, Jiqiang Guo wrote:
> Just newton's method in RStan 1.3.0. In the develop branch, there is
> nesterov's accelerated gradient method. BFGS is not there yet.
BFGS is not in the develop branch yet?
If it's not, and it's what we want people to use, can
someone add it? Or are there other issues we're waiting
to get resolved?
> It is not that documented because it's not documented in Stan.
Can you add the doc to R about what method (or methods) are available?
I'll try to review the RStan doc again soon --- both RStan
and its doc have grown tremendously since RStan 1.0 and I
haven't been keeping up as much as I should.
If anyone finds places we need more doc in Stan itself, please
do one of the following:
* add the doc yourself
* ask for help on stan-dev
* submit an issue on GitHub
- Bob
>
> --
> Jiqiang
> On Tue, May 21, 2013 at 6:10 PM, Bob Carpenter <ca...@alias-i.com> wrote:
>> On 5/21/13 6:03 PM, Matt Hoffman wrote:
>>>
>>> Was that using Newton's method or BFGS?
>>
>>
>> I don't know, which is why I said it's whatever RStan uses!
>> I don't see any explanation in the RStan doc, which only refers
>> to "Stan's optimization method".
>
Marcus Brubaker
May 21, 2013, 6:33:47 PM5/21/13
to stan...@googlegroups.com
On Tue, May 21, 2013 at 6:22 PM, Bob Carpenter <ca...@alias-i.com> wrote:
> [moved discussion to stan-dev]
>
> On 5/21/13 6:15 PM, Jiqiang Guo wrote:
>>
>> Just newton's method in RStan 1.3.0. In the develop branch, there is
>> nesterov's accelerated gradient method. BFGS is not there yet.
>
>
> BFGS is not in the develop branch yet?
>
> If it's not, and it's what we want people to use, can
> someone add it? Or are there other issues we're waiting
> to get resolved?
It's there, it landed pretty soon after 1.3.0 was released. It's not
> [moved discussion to stan-dev]
>
> On 5/21/13 6:15 PM, Jiqiang Guo wrote:
>>
>> Just newton's method in RStan 1.3.0. In the develop branch, there is
>> nesterov's accelerated gradient method. BFGS is not there yet.
>
>
> BFGS is not in the develop branch yet?
>
> If it's not, and it's what we want people to use, can
> someone add it? Or are there other issues we're waiting
> to get resolved?
used by default, but I would suggest that we change that. If it was
Newton that was used in your tests, I would expect BFGS to converge
*much* faster.
>> It is not that documented because it's not documented in Stan.
should probably fix this, but I would suggest waiting until the
command refactor finishes, because that will change a lot.
Cheers,
Marcus
>
>
> Can you add the doc to R about what method (or methods) are available?
>
> I'll try to review the RStan doc again soon --- both RStan
> and its doc have grown tremendously since RStan 1.0 and I
> haven't been keeping up as much as I should.
>
> If anyone finds places we need more doc in Stan itself, please
> do one of the following:
>
> * add the doc yourself
>
> * ask for help on stan-dev
>
> * submit an issue on GitHub
>
> - Bob
>
>>
>> --
>> Jiqiang
>> On Tue, May 21, 2013 at 6:10 PM, Bob Carpenter <ca...@alias-i.com> wrote:
>>>
>>> On 5/21/13 6:03 PM, Matt Hoffman wrote:
>>>>
>>>>
>>>> Was that using Newton's method or BFGS?
>>>
>>>
>>>
>>> I don't know, which is why I said it's whatever RStan uses!
>>> I don't see any explanation in the RStan doc, which only refers
>>> to "Stan's optimization method".
>>
>>
>
> 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.
>
>
Jiqiang Guo
May 21, 2013, 6:49:17 PM5/21/13
to stan...@googlegroups.com
It's not in RStan yet. I was thinking adding it after
stan/gm/command.hpp becomes stable.
--
Jiqiang
stan/gm/command.hpp becomes stable.
--
Jiqiang
Bob Carpenter
May 21, 2013, 6:54:08 PM5/21/13
to stan...@googlegroups.com
[move discussion to stan-dev]
On 5/21/13 6:24 PM, Matt Hoffman wrote:
> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>
> Three more questions:
> 1. Do we have the relevant optimization flags enabled to let Eigen
> take advantage of things like SSE?
Egads! It looks like it's not on by default. And we
haven't turned them on explicitly in the makefiles.
Any advice on how to configure g++ and clang++ to do
this in a cross-platform compatible way?
A quick scan indicates that for g++ and clang++ indicates
that we need something like
-march=native
to enable an architecture that supports SSE(2) and then
we need to explicitly set the SSE2 flag:
-msse2
Do we also need to set just SSE?
> 2. Are we letting Eigen parallelize matrix operations?
Not that I know of. This we should also check for config.
If we're running multiple chains in parallel, we probably don't
want to parallelize matrix ops. Otherwise, we probably do.
Is there a way we can turn it on at run time or is it a compile-time
option?
> 3. Do we have specialized adjoint computations for matrix ops yet? 1
> and 2 won't do much good until we do.
Yes, we have them for most ops and Marcus has been
continuing to add more.
- Bob
On 5/21/13 6:24 PM, Matt Hoffman wrote:
> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>
> Three more questions:
> 1. Do we have the relevant optimization flags enabled to let Eigen
> take advantage of things like SSE?
Egads! It looks like it's not on by default. And we
haven't turned them on explicitly in the makefiles.
Any advice on how to configure g++ and clang++ to do
this in a cross-platform compatible way?
A quick scan indicates that for g++ and clang++ indicates
that we need something like
-march=native
to enable an architecture that supports SSE(2) and then
we need to explicitly set the SSE2 flag:
-msse2
Do we also need to set just SSE?
> 2. Are we letting Eigen parallelize matrix operations?
Not that I know of. This we should also check for config.
If we're running multiple chains in parallel, we probably don't
want to parallelize matrix ops. Otherwise, we probably do.
Is there a way we can turn it on at run time or is it a compile-time
option?
> 3. Do we have specialized adjoint computations for matrix ops yet? 1
> and 2 won't do much good until we do.
Yes, we have them for most ops and Marcus has been
continuing to add more.
- Bob
Bob Carpenter
May 21, 2013, 6:58:17 PM5/21/13
to stan...@googlegroups.com
Thanks for the clarification.
It totally makes sense to wait until the commands are stabilized!
- Bob
It totally makes sense to wait until the commands are stabilized!
- Bob
Michael Betancourt
May 21, 2013, 6:59:59 PM5/21/13
to stan...@googlegroups.com
> [move discussion to stan-dev]
>
> On 5/21/13 6:24 PM, Matt Hoffman wrote:
>> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>>
>> Three more questions:
>> 1. Do we have the relevant optimization flags enabled to let Eigen
>> take advantage of things like SSE?
>
> Egads! It looks like it's not on by default. And we
> haven't turned them on explicitly in the makefiles.
>
> Any advice on how to configure g++ and clang++ to do
> this in a cross-platform compatible way?
>
> A quick scan indicates that for g++ and clang++ indicates
> that we need something like
>
> -march=native
>
> to enable an architecture that supports SSE(2) and then
> we need to explicitly set the SSE2 flag:
>
> -msse2
>
> Do we also need to set just SSE?
I remember getting huge performance increases (order of magnitude) enabling SSE3, SSE4.1, SSE 4.2, and Supplemental SSE3 with Eigen. They're all available on Intel Macs.>
> On 5/21/13 6:24 PM, Matt Hoffman wrote:
>> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>>
>> Three more questions:
>> 1. Do we have the relevant optimization flags enabled to let Eigen
>> take advantage of things like SSE?
>
> Egads! It looks like it's not on by default. And we
> haven't turned them on explicitly in the makefiles.
>
> Any advice on how to configure g++ and clang++ to do
> this in a cross-platform compatible way?
>
> A quick scan indicates that for g++ and clang++ indicates
> that we need something like
>
> -march=native
>
> to enable an architecture that supports SSE(2) and then
> we need to explicitly set the SSE2 flag:
>
> -msse2
>
> Do we also need to set just SSE?
Bob Carpenter
May 21, 2013, 7:03:28 PM5/21/13
to stan...@googlegroups.com
[move to stan-dev]
If we can do optimization faster than R's builtins,
that's fantastic.
I was not counting data read times because I was
starting with the data in R and Jiqiang wrote a tight
integration there.
Of course, reading 30MB would be faster in a format other
than R dump. It's an intrinsically slow format and the code's
hardly optimized.
And yes, I have a nice new core i7 Macbook Pro which took
3s in R, with no data read time.
- Bob
On 5/21/13 6:50 PM, Marcus Brubaker wrote:
> Ok, I just did a quick test of BFGS using the model and data generation scripts Bob sent. This is with K = 160 and N =
> 10,000
>
> Marcus-Brubakers-MacBook-Pro:stan mbrubake$ time ./logistic --data=logisitic.data --point_estimate_bfgs --init=0 --refresh=5
> STAN OPTIMIZATION COMMAND
> data = logisitic.data
> init = 0
> output = samples.csv
> save_warmup = 0
> epsilon = -1
> seed = 3496505751 (randomly generated)
> initial log joint probability = -6931.47
> Iter log prob ||dx|| ||grad|| alpha alpha0 # evals Notes
> 1 -1781.82 3.99246 514.407 0.001 0.001 2
> 5 -1148.86 1.55728 151.342 1 1 6
> 10 -1030.79 0.0556683 6.50517 1 1 11
> 15 -1030.66 0.00178793 0.189879 1 1 16
> 20 -1030.66 0.000108344 0.00874977 1 1 21
> 25 -1030.66 1.7213e-06 0.000248864 1 1 26
> 30 -1030.66 8.76987e-08 3.63224e-06 1 1 71
> 32 -1030.66 1.09407e-08 2.35202e-06 0.0001565 0.001 148 LS failed, BFGS reset;
> Optimization terminated with code -1
>
> real 0m13.129s
> user 0m12.912s
> sys 0m0.188s
>
> So, in short, 13s. Now, a few caveats:
>
> 1) The BFGS implementation is currently bad at detecting convergence. If it was better at this, that would probably be 10s.
> 2) Somewhere around 7 or 8 seconds is spent before the first iteration is ever run. I suspect that most of this is
> caused by reading in the data from the R dump format.
> 3) This timing is on a different machine than Bob's, but I suspect my 3-4yr old macbook pro is probably slower than
> whatever Bob was running on.
>
> If we assumed that 1&2 could be resolved, the time would be more like 3 or 4 seconds which is basically the same as the
> glm() reported on what is a presumably faster machine.
>
> Cheers,
> Marcus
>
> P.S. Here is the result of point_estimate_newton on my machine:
>
> Marcus-Brubakers-MacBook-Pro:stan mbrubake$ time ./logistic --data=logisitic.data --point_estimate_newton --init=0
> STAN OPTIMIZATION COMMAND
> data = logisitic.data
> init = 0
> output = samples.csv
> save_warmup = 0
> seed = 3496875472 (randomly generated)
> initial log joint probability = -6931.47
> Iteration 1. Log joint probability = -3207.55. Improved by 3723.92.
> Iteration 2. Log joint probability = -2079.52. Improved by 1128.03.
> Iteration 3. Log joint probability = -1482.83. Improved by 596.698.
> Iteration 4. Log joint probability = -1179.95. Improved by 302.88.
> Iteration 5. Log joint probability = -1059. Improved by 120.947.
> Iteration 6. Log joint probability = -1032.31. Improved by 26.6863.
> Iteration 7. Log joint probability = -1030.66. Improved by 1.64927.
> Iteration 8. Log joint probability = -1030.66. Improved by 0.00773384.
> Iteration 9. Log joint probability = -1030.66. Improved by 1.87733e-07.
>
> real 3m26.021s
> user 3m20.686s
> sys 0m0.657s
> >> iterations) looks more like Newton (a.k.a. iteratively reweighted
> >> least squares). That Newton implementation is getting the Hessian in a
> >> pretty naive way, which for LR can be much more heavily optimized.
> >
> >
> > That would certainly cause a problem with 160 params!
> >
> >
> >> Are we linking against a BLAS? I've been meaning to bring that up as a
> >> possible area for optimization. I would assume that glm is using some
> >> kind of optimized BLAS, which makes a big, big difference when your
> >> primary computational operation is matrix multiplication and
> >> inversion.
> >
> >
> > No. We're just using Eigen. Here's a link to an older benchmark
> > of Eigen vs. various BLAS implementations (they claim to be faster than
> > all of the free ones):
> >
> > http://eigen.tuxfamily.org/index.php?title=Benchmark
> >
> >
> > - Bob
> --
> You received this message because you are subscribed to the Google Groups "stan users mailing list" group.
> --
> You received this message because you are subscribed to the Google Groups "stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
If we can do optimization faster than R's builtins,
that's fantastic.
I was not counting data read times because I was
starting with the data in R and Jiqiang wrote a tight
integration there.
Of course, reading 30MB would be faster in a format other
than R dump. It's an intrinsically slow format and the code's
hardly optimized.
And yes, I have a nice new core i7 Macbook Pro which took
3s in R, with no data read time.
- Bob
On 5/21/13 6:50 PM, Marcus Brubaker wrote:
> Ok, I just did a quick test of BFGS using the model and data generation scripts Bob sent. This is with K = 160 and N =
> 10,000
>
> Marcus-Brubakers-MacBook-Pro:stan mbrubake$ time ./logistic --data=logisitic.data --point_estimate_bfgs --init=0 --refresh=5
> STAN OPTIMIZATION COMMAND
> data = logisitic.data
> init = 0
> output = samples.csv
> save_warmup = 0
> epsilon = -1
> seed = 3496505751 (randomly generated)
> initial log joint probability = -6931.47
> Iter log prob ||dx|| ||grad|| alpha alpha0 # evals Notes
> 1 -1781.82 3.99246 514.407 0.001 0.001 2
> 5 -1148.86 1.55728 151.342 1 1 6
> 10 -1030.79 0.0556683 6.50517 1 1 11
> 15 -1030.66 0.00178793 0.189879 1 1 16
> 20 -1030.66 0.000108344 0.00874977 1 1 21
> 25 -1030.66 1.7213e-06 0.000248864 1 1 26
> 30 -1030.66 8.76987e-08 3.63224e-06 1 1 71
> 32 -1030.66 1.09407e-08 2.35202e-06 0.0001565 0.001 148 LS failed, BFGS reset;
> Optimization terminated with code -1
>
> real 0m13.129s
> user 0m12.912s
> sys 0m0.188s
>
> So, in short, 13s. Now, a few caveats:
>
> 1) The BFGS implementation is currently bad at detecting convergence. If it was better at this, that would probably be 10s.
> 2) Somewhere around 7 or 8 seconds is spent before the first iteration is ever run. I suspect that most of this is
> caused by reading in the data from the R dump format.
> 3) This timing is on a different machine than Bob's, but I suspect my 3-4yr old macbook pro is probably slower than
> whatever Bob was running on.
>
> If we assumed that 1&2 could be resolved, the time would be more like 3 or 4 seconds which is basically the same as the
> glm() reported on what is a presumably faster machine.
>
> Cheers,
> Marcus
>
> P.S. Here is the result of point_estimate_newton on my machine:
>
> Marcus-Brubakers-MacBook-Pro:stan mbrubake$ time ./logistic --data=logisitic.data --point_estimate_newton --init=0
> STAN OPTIMIZATION COMMAND
> data = logisitic.data
> init = 0
> output = samples.csv
> save_warmup = 0
> seed = 3496875472 (randomly generated)
> initial log joint probability = -6931.47
> Iteration 1. Log joint probability = -3207.55. Improved by 3723.92.
> Iteration 2. Log joint probability = -2079.52. Improved by 1128.03.
> Iteration 3. Log joint probability = -1482.83. Improved by 596.698.
> Iteration 4. Log joint probability = -1179.95. Improved by 302.88.
> Iteration 5. Log joint probability = -1059. Improved by 120.947.
> Iteration 6. Log joint probability = -1032.31. Improved by 26.6863.
> Iteration 7. Log joint probability = -1030.66. Improved by 1.64927.
> Iteration 8. Log joint probability = -1030.66. Improved by 0.00773384.
> Iteration 9. Log joint probability = -1030.66. Improved by 1.87733e-07.
>
> real 3m26.021s
> user 3m20.686s
> sys 0m0.657s
>
>
>
>
> On Tue, May 21, 2013 at 6:24 PM, Matt Hoffman <mdho...@cs.princeton.edu <mailto:mdho...@cs.princeton.edu>> wrote:
>
> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>
> Three more questions:
> 1. Do we have the relevant optimization flags enabled to let Eigen
> take advantage of things like SSE?
>
>
>
> On Tue, May 21, 2013 at 6:24 PM, Matt Hoffman <mdho...@cs.princeton.edu <mailto:mdho...@cs.princeton.edu>> wrote:
>
> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>
> Three more questions:
> 1. Do we have the relevant optimization flags enabled to let Eigen
> take advantage of things like SSE?
> 2. Are we letting Eigen parallelize matrix operations?
> 3. Do we have specialized adjoint computations for matrix ops yet? 1
> and 2 won't do much good until we do.
>
> Matt
> and 2 won't do much good until we do.
>
>
> On Tue, May 21, 2013 at 3:10 PM, Bob Carpenter <ca...@alias-i.com <mailto:ca...@alias-i.com>> wrote:
> >
> >
> > On 5/21/13 6:03 PM, Matt Hoffman wrote:
> >>
> >> Was that using Newton's method or BFGS?
> >
> >
> > I don't know, which is why I said it's whatever RStan uses!
> > I don't see any explanation in the RStan doc, which only refers
> > to "Stan's optimization method".
> >
> >
> >> The convergence speed (in
> On Tue, May 21, 2013 at 3:10 PM, Bob Carpenter <ca...@alias-i.com <mailto:ca...@alias-i.com>> wrote:
> >
> >
> > On 5/21/13 6:03 PM, Matt Hoffman wrote:
> >>
> >> Was that using Newton's method or BFGS?
> >
> >
> > I don't know, which is why I said it's whatever RStan uses!
> > I don't see any explanation in the RStan doc, which only refers
> > to "Stan's optimization method".
> >
> >
> >> iterations) looks more like Newton (a.k.a. iteratively reweighted
> >> least squares). That Newton implementation is getting the Hessian in a
> >> pretty naive way, which for LR can be much more heavily optimized.
> >
> >
> > That would certainly cause a problem with 160 params!
> >
> >
> >> Are we linking against a BLAS? I've been meaning to bring that up as a
> >> possible area for optimization. I would assume that glm is using some
> >> kind of optimized BLAS, which makes a big, big difference when your
> >> primary computational operation is matrix multiplication and
> >> inversion.
> >
> >
> > No. We're just using Eigen. Here's a link to an older benchmark
> > of Eigen vs. various BLAS implementations (they claim to be faster than
> > all of the free ones):
> >
> > http://eigen.tuxfamily.org/index.php?title=Benchmark
> >
> >
> > - Bob
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "stan users mailing list" group.
> > --
> > You received this message because you are subscribed to the Google Groups
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to stan-users+...@googlegroups.com <mailto:stan-users%2Bunsu...@googlegroups.com>.
> --
> You received this message because you are subscribed to the Google Groups "stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to
> stan-users+...@googlegroups.com <mailto:stan-users%2Bunsu...@googlegroups.com>.
> --
> You received this message because you are subscribed to the Google Groups "stan users mailing list" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to stan-users+...@googlegroups.com.
Bob Carpenter
May 21, 2013, 7:04:12 PM5/21/13
to stan...@googlegroups.com
On 5/21/13 6:59 PM, Michael Betancourt wrote:
...
>> Do we also need to set just SSE?
>
> I remember getting huge performance increases (order of magnitude) enabling SSE3, SSE4.1, SSE 4.2, and Supplemental SSE3 with Eigen. They're all available on Intel Macs.
Do you remember how you did this?
>
> I remember getting huge performance increases (order of magnitude) enabling SSE3, SSE4.1, SSE 4.2, and Supplemental SSE3 with Eigen. They're all available on Intel Macs.
- Bob
Ben Goodrich
May 21, 2013, 7:21:48 PM5/21/13
to stan...@googlegroups.com
On Tuesday, May 21, 2013 6:54:08 PM UTC-4, Bob Carpenter wrote:
[move discussion to stan-dev]
On 5/21/13 6:24 PM, Matt Hoffman wrote:
> Wow, I didn't realize that the Eigen benchmark results were that compelling.
>
> Three more questions:
> 1. Do we have the relevant optimization flags enabled to let Eigen
> take advantage of things like SSE?
Egads! It looks like it's not on by default. And we
haven't turned them on explicitly in the makefiles.
It is generally on by default on x86-64 but can be turned on otherwise
http://eigen.tuxfamily.org/index.php?title=FAQ#Vectorization
Ben
Marcus Brubaker
May 21, 2013, 7:24:06 PM5/21/13
to stan...@googlegroups.com
I think adding -march=native will cover any msse flags if they're needed. See:
http://stackoverflow.com/questions/10686638/whats-the-diff-among-cflgs-sse-options-of-msse-msse2-mssse3-msse4-rtc
Cheers,
Marcus
http://stackoverflow.com/questions/10686638/whats-the-diff-among-cflgs-sse-options-of-msse-msse2-mssse3-msse4-rtc
Cheers,
Marcus
> --
> You received this message because you are subscribed to the Google Groups
> "stan development mailing list" group.
> You received this message because you are subscribed to the Google Groups
> To unsubscribe from this group and stop receiving emails from it, send an
> email to stan-dev+u...@googlegroups.com.
Michael Betancourt
May 21, 2013, 7:36:30 PM5/21/13
to stan...@googlegroups.com
I used them through only the XCode project configuration, which should just be setting the flags discussed in the stackoverflow article.
Reply all
Reply to author
Forward
0 new messages