[mlpack-git] [mlpack] evaluate various changes to L-BFGS optimizer (#370)

[Ryan Curtin]

Okay; I understand the changes you've made then.  Thanks for the explanation.  One thing I overlooked, though---you've split out the line search termination conditions in order to give better failure messages; but on those failures, it no longer returns false, it just breaks.  Is there a particular reason for this?  I think that this could cause `L_BFGS` to iterate forever with no improvement, although the relative improvement termination condition should catch that.  Which then implies that there's no need for `LineSearch()` to return anything at all or check whether or not it failed.  If you agree with that line of reasoning, then after I merge it I'll make `LineSearch()` `void` and remove the checks.

> In fact, if you email sam burer asking about these heuristics, he will tell you he can't even quite piece them together unless he spends quite a bit of time looking at his code.

Hah, I have one of those emails too! :)

He suggested that he avoided the R=0 problem by using the determinant of R^T R, and linked to a Mathematical Programming paper titled "Local Minima and Convergence in Low-Rank Semidefinite Programming":
http://www.researchgate.net/publication/225703502_Local_Minima_and_Convergence_in_Low-Rank_Semidefinite_Programming/file/d912f508148a86b469.pdf

and also suggested a (slightly) more recent paper:
http://link.springer.com/article/10.1007%2Fs10898-008-9328-4

It has been a very long time since I have done so much as open those papers, though...

I do think a more robust LRSDP would definitely be paperworthy and of high interest.  It would also allow mlpack to provide faster implementations of SDP-based algorithms that actually work.  (This is better than the old rejected code that was fast but didn't work...)  A dual solver would definitely help us know when a restart was necessary, but I don't know if this would cause the entire algorithm to be slower overall than just a regular SDP solver.  Either way, that is certainly an interesting avenue to investigate.

---
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/issues/370#issuecomment-70039134
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20150114/0d5f1df6/attachment-0001.html>