Delayed gratification and geodesic acceleration in Levenburg-Marquardt

[ChrisRackauckas]

I found this paper to be quite interesting. https://arxiv.org/pdf/1010.1449.pdf

[pkofod]

Cool stuff. Haven’t read the details, but the overall idea is interesting.

[blakejohnson]

I actually started this project with the intent of prototyping geodesic acceleration. Obviously, I never got around to it. But, I'd love to see it land in this package.

[pkofod]

The mu and nu letters represent what exactly? I'm a bit confused that they don't write the jacobian of residuals and hessian of the cost using theta. Is it just because they don't necessarily consider all the parameters in theta as ones to optimize over? Edit: oh, they're two (arbitrary) individual parameters?

[Magalame]

There is a follow-up paper: https://arxiv.org/pdf/1201.5885.pdf Along with a Fortran implementation: https://sourceforge.net/projects/geodesiclm/ (ref. 13 in the follow up paper)

I'll try to translate it into Julia and see what it yields

[pkofod]

Thanks for showing interest in this! Mark Transtrum is actually a Julia user, and has some code, on gitlab I think. I can link it when I’m at my pc

[pkofod]

The packages are here https://pulsar.byu.edu/Modeling/Geometry.jl/ and https://pulsar.byu.edu/Modeling/Models.jl

However, I think it's better to go from the sourceforge project unless you want to implement it directly from the paper instead. I think the latter might be a good idea, but it's also a bigger job.

(hoping I'm tagging the right guy, bit appears to be from the repos @mktranstrum )

[Magalame]

Oh thanks a lot for the links, it'll still be a point comparison. When reading the paper my main interrogation was how to compute the acceleration considering only the model and the Jacobian, so that'll be helpful!

I'll try to implement the algorithm as outlined at the end of the initial paper. Considering we already have an implementation of LM, it shouldn't be too much of a hassle, I hope

[pkofod]

LM, it shouldn't be too much of a hassle, I hope

famous last words :)

[Magalame]

famous last words :)

:(

It does seem like we'll need the Hessian, as we'll need the directional second derivative (https://imgur.com/a/O8ZWQCK it's what the Avvfunction computes and stores in acc ), which can be computed by v^T H v, fortunately there is TwiceDifferentiable, but it'll be interesting to see what would be the memory cost of using a non-analytic Hessian.

[Magalame]

Hmmm, seems like TwiceDifferentiable doesn't support multivariate output, so that'll be fun.

[pkofod]

The hessian is not the tensor that is the second derivative of the residual though, it's the second derivative of the actual objective, so f(x) = sum(abs2, residual), right? It's been a while since I read the papers, so I don't remember the exact details.

[pkofod]

it's been on master for a couple of months, so closing here, and hope to do a new release soon