[Insight-users] Small problem using LBFGSB

[Rupert Brooks]

Hi Tom,

I've messed around with the LBFGSB optimizer a fair bit.  Usually its
pretty reliable, but I've seen it occasionally make a wild jump during
its line search which sends the parameters completely outside any sort
of appropriate range.  This happened when i was using a function that
had an approximate gradient and what seemed to be happening is the the
gradient and the function not truly matching up basically made the
line search divide by a very small number, leading to a very large,
erroneous step.

The line search makes a cubic polynomial fit to the function, and
polynomial fits can be sensitive to erroneous data.  I got around the
problem by making my gradient more well behaved.

I also noticed your comments about scaling on the other VNL lbfgs
optimizer the other day.  I'd be very supportive of having a general
scaling framework for the ITK optimizers.  As it is now, the scale
factors have vastly different effects between say, Powell and
RegularStepGradientDescent.  I have a big nasty switch statement in my
code to manage it.

I'd be curious about what you're working on for optimizer projects.
I've been working on a number of optimizer related projects in ITK.  I
have developed some Hessian based optimizers, and a trust-region
version of the gradient descent which im kind of fond of.

Cheers,
Rupert B.



>  Message: 3
>  Date: Tue, 29 Apr 2008 11:39:38 +0200
>  From: "Tom Vercauteren" <tom.vercauteren at m4x.org>
>  Subject: [Insight-users] Small problem using LBFGSB
>  To: "Brad King" <brad.king at kitware.com>
>  Cc: insight-users <insight-users at itk.org>
>  Message-ID:
>         <28392e8b0804290239v7cad0833pd0ae327e0c8203d4 at mail.gmail.com>
>  Content-Type: text/plain; charset="iso-8859-1"
>
>  Dear Brad,
>
>  I started using the vnl_lbfgsb optimizer and stumbled into a problem.
>  I saw that you were the author of this code which is why I am writing
>  to you directly (The insight-users mailing list is cc'ed as it may
>  interests other ITK users).
>
>  In some scenarios (which unfortunately I cannot easily isolate) the
>  optimizer dramatically fails and reports a very bad cost function
>  value (with respect to previous iterations).
>
>  What I first did was to modify the vnl wrapper to trace the problem.
>  Here is the message I get from the lbfgsb routine just before the bug:
>
>   Bad direction in the line search;
>     refresh the lbfgs memory and restart the iteration.
>
>
>  When I don't specify actual bound constraints, this message also shows
>  up from time to time but the cost function values are still being
>  optimized...
>
>  I tried to debug the code but as the problem seems to come from the
>  f2c'ed code, I have some problems understanding it...
>
>  As a work-around, I have modified the vnl_lbfgsb optimizer to make
>  sure that it reports the best value visited during the optimization.
>  So, even when the optimizer fails, the returned value remains good
>  enough.
>
>  My modifications are attached as a patch or as a single file.
>
>  As this problem concerns a vnl file within ITK, I wasn't quite sure if
>  I should file an ITK bug report or not.
>
>  Best regards,
>  Tom Vercauteren
>  -------------- next part --------------
>  A non-text attachment was scrubbed...
>  Name: vnl_lbfgsb_patch_for_best_position.diff
>  Type: text/x-diff
>  Size: 3837 bytes
>  Desc: not available
>  URL: <http://www.itk.org/pipermail/insight-users/attachments/20080429/185fd453/attachment.diff>
>  -------------- next part --------------
>  A non-text attachment was scrubbed...
>  Name: vnl_lbfgsb.cxx
>  Type: text/x-c++src
>  Size: 4584 bytes
>  Desc: not available
>  URL: <http://www.itk.org/pipermail/insight-users/attachments/20080429/185fd453/attachment.cxx>
>
>  ------------------------------
>
>  _______________________________________________
>  Insight-users mailing list
>  Insight-users at itk.org
>  http://www.itk.org/mailman/listinfo/insight-users
>
>
>  End of Insight-users Digest, Vol 48, Issue 81
>  *********************************************
>



-- 
--------------------------------------------------------------
Rupert Brooks
McGill Centre for Intelligent Machines (www.cim.mcgill.ca)
Ph.D Student, Electrical and Computer Engineering
http://www.cyberus.ca/~rbrooks