2 ms·
> It looks like the innovation is to scale the identity matrix in the L-M step formula by the square root of the norm of the gradient. If I have f(x), then I d
by xscott 5y ago
> It looks like the innovation is to scale the identity matrix in the L-M step formula by the square root of the norm of the gradient.
If I have f(x), then I define
g(x) = 100*f(x)
h(x) = .01*f(x)
won't I get different rates of convergence with g(x) and h(x)?
Normally, the scale factor of a function cancels out when multiplying the inverse Hessian times the gradient, but the square root changes that here. This seems undesirable.
Maybe it can be hand-waved away with their constant H, which looks like a tuning parameter.
- civilized 5y agoGood question. Clearly the square root has to be there for a reason, but I agree it makes the scheme not scale-invariant. And the original L-M is also not scale-invariant so there must be some reason for this. There may be stability issues with perfect scale invariance. You don't want to drop your identity matrix term when the gradient gets too small; that would defeat the purpose of the L-M regularization. Regularization in general tends to make things less symmetric and invariant. It's kind of a necessary evil. And you're right, the H plays an important role in keeping the scheme relatively efficient. It is typically adjusted dynamically in L-M schemes (see AdaN and AdaN+ algorithms in the paper).
- xscott 5y agoPreviously I had thought of Levenberg Marquardt as it's own little island, separate from the collection of line search and trust region algorithms. I guess maybe I should think of algorithms using regularized Hessians as a third category now. (Although I guess the quasi-Newton algorithms that maintain positive definiteness are regularized in a sense, so it's kind of a fuzzy categorization) I'm curious if this square root trick performs better than a well written trust region algorithm.