On Mon, Mar 22, 2010 at 11:52 AM, Jaroslav Hajek <high...@gmail.com> wrote:
> On Mon, Mar 22, 2010 at 11:15 AM, Michael Creel <michael.cr...@uab.es>
> wrote:
> >
> >
> > On Mon, Mar 22, 2010 at 10:52 AM, Jaroslav Hajek <high...@gmail.com>
> wrote:
> >>
> >> On Mon, Mar 22, 2010 at 10:34 AM, Michael Creel <michael.cr...@uab.es>
> >> wrote:
> >> >
> >> >
> >> > On Sun, Mar 21, 2010 at 6:42 PM, Søren Hauberg <so...@hauberg.org>
> >> > wrote:
> >> >>
> >> >> One problem with the current approach is that you currently can't use
> >> >> function handles with 'bfgs'. In some situations they are more simply
> >> >> to
> >> >> use than strings.
> >> >>
> >> >> I don't think you'll see any noticeable difference in terms of speed.
> I
> >> >> actually think you would be able to re-implement the entire function
> as
> >> >> an m-file without seeing much loss of speed, as usually most of the
> >> >> computation time is spend in the function being optimised rather than
> >> >> in
> >> >> the function doing the optimisation.
> >> >>
> >> >
> >> > Well, fminunc in Octave is pretty much a perfect substitute for the
> >> > functionality of bfgsmin.
> >>
> >> I don't think this is true. bfgsmin can do limited-memory updates,
> >> fminunc can't. At present, fminunc is modelled after fsolve with its
> >> trust-region approach. I didn't actually tune the fminunc
> >> implementation at all, I thought that the trust-region approach will
> >> be superior to line search of bfgsmin. It appears this is not really
> >> true, though.
> >>
> >> At present, it seems to me that having the limited-memory updating
> >> capability is more important than trust-region stepping. So I'd be
> >> glad to reimplement fminunc using the line search strategy from
> >> bfgsmin, allowing the switch between inverse BFGS / factorized BFGS /
> >> LBFGS updating.
> >>
> >> > It works with function handles, and is an .m file
> >> > implementation. The advantage of bfgsmin is that it is faster. It is
> >> > true
> >> > that for expensive objective functions, the difference won't be
> >> > important.
> >> > However, if you are doing a lot of minimizations of cheap functions,
> >> > then
> >> > the difference is around 2X.
> >>
> >> I don't think this factor matters at all. Things can easily change
> >> when new code optimizations become available, besides, our testing was
> >> very limited and it was not in fact clear whether the factor 2x came
> >> purely out of the code efficiency or whether bfgsmin just did less
> >> work (less iterations).
> >>
> >> I probably will try to reimplement fminunc based on bfgsmin, but using
> >> m-code, in not-so-distant future.
> >> I'd appreciate any help on this.
> >>
> >
> > That sounds good. My experience with bfgsmin is that having a stepsize
> > algorithm that can switch between fast and pretty good (Newton step) to
> slow
> > but reliable (bisection) works well. I'm not knowledgeable about trust
> > regions. The other thing that has worked well is to fall back on steepest
> > descent when the bfgs direction doesn't work. It is true that limited
> memory
> > bfgs makes a big difference when there are many parameters.
> >
>
> One big advantage of a trust-region approach for fsolve is that it
> makes it meaningful to update the Jacobian matrix after each step,
> even if it increases the residual. This allows for incremental
> correction of the Jacobian by a series of bad steps, which can
> eventually make it "repair" itself and then predict a good step,
> without recomputing the Jacobian. I think this is one of the strong
> pluses of the current fsolve implementation.
> This is also true for minimization, but only if the update allows it.
> Alas, the BFGS update requires the curvature condition, which is often
> violated with bad steps, diminishing this advantage of a trust-region
> approach. It would be possible to employ a non-definite Hessian update
> like SR1, but then you lose the ability to solve the trust-region
> subproblem via the efficient dogleg method and you need to resort to
> more general approaches.
>
Another approach is to do a series of short runs with different starting
values to try to get into a well-behaved region, and then iterate to
convergence. There is a lot of room for artistry and voodoo here.
>
> Back to practice: currently fminunc only updates the hessian after a
> successful step, hence does not actually enjoy the primary benefit of
> the trust-region approach. It could be fixed, but I would need to do
> some more studying on (approximately) solving TR subproblems with
> indefinite matrices (regarding the dogleg method, I just stole it from
> MINPACK).
> Unlike bfgsmin, it also can't use limited-memory updates. That's why I
> think that rewriting it based on bfgsmin is a good idea at this
> moment, because that's the best minimizer that Octave users had for a
> while.
>
>
>
> > My claim of a 2X factor is based on the casual testing you and I did a
> few
> > months ago, plus testing I did when first moving from .m code to .cc.
> This
> > factor clearly depends a lot upon the objective function used. It
> reflects
> > the test code I was using, which is representative of my work, but
> others'
> > mileage will certainly vary. There have also been a lot of improvements
> to
> > Octave over that time, so I suspect that the factor would be closer to 1
> > now. I put a lot more weight upon reliability and crash-proofness than
> on
> > pure speed. Using .m code probably would favor reliability.
> >
>
> I know that, but I don't recall us actually compare the numbers of
> iterations. That being said, it is even possible that the cost per
> iteration was actually higher for bfgsmin, and that it simply won by
> performing significantly less iterations.
>
>
I think that wall clock time to arrive to a correct solution is the best
metric. For example, lbfgs typically uses much less time per iteration than
does bfgs, but lbfgs requires many more iterations. The user really doesn't
care about the path taken to get to the solution, but the time taken to go
along the path is important. That, and the destination being correct.
In the bisection code in __bfgsmin, there is a loop until an improvement is
found, and then it continues until there is a significant decrease in the
improvement. This is an example of a tradeoff between quality of a single
iteration, and number of iterations. Tuning the tradeoffs for good
performance for a wide variety of problems is what makes for a good
algorithm. I use wall clock time to make this kind of tuning.
M.
------------------------------------------------------------------------------
Download Intel® Parallel Studio Eval
Try the new software tools for yourself. Speed compiling, find bugs
proactively, and fine-tune applications for parallel performance.
See why Intel Parallel Studio got high marks during beta.
http://p.sf.net/sfu/intel-sw-dev
_______________________________________________
Octave-dev mailing list
Octave-dev@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/octave-dev
