4 ms·

This is very interesting. 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. V

This is very interesting. 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. Very simple and elegant, and trivial to implement. Lots of people are going to be shaking their heads wondering why they didn't think of this first. The motivation for the idea is very nice and easy to understand. The author completely explains it before the middle of the second page. I encourage you to look at it if you know enough vector calc to make sense of the notation. Essentially, he takes a well-known fast-converging method whose steps are hard to compute and shows how these steps can be approximated cheaply while still retaining much of the convergence rate benefit. This may have implications for many large-scale optimization problems as L-M regularized Newton steps are a sort of natural halfway house between gradient descent and the full Newton's method, both theoretically and practically.

midjji 5y ago
The problem with simple innovations in old methods, is that there is very rarely anything new under the sun, odds are good its already been done. The paper does not evaluate on any of the big standard benchmark either. The paper spends a surprising/suspicious amount of time on very basic things. "The divergence issues of Newton’s method with line search seems to be a relatively unknown fact." No its well known! It looks interesting, but some things, like the L-M lambda beeing constant? No, you adapt it to the data increasing and decreasing it in accordance with the feedback from the step error predictions. Similar, but not identically to what is proposed here. Id need to read it carefully and it doesnt look bad, but think I'll just wait for the reviewers.
- civilized 5y ago
  All good points. Personally I wouldn't have known divergence of Newton's method with line search off the top of my head. What I think everyone in this field would know is that Newton's method with constant step size diverges. I'm actually curious now if Newton's method with backtracking line search from a constant step size diverges. Exact line search can go a little nuts, that doesn't surprise me, but divergence with backtracking from a constant step size seems less likely. (I guess it depends on what "constant" means here...) Seems like it could be awfully nice to have a smart theoretically backed initial guess of the dynamic lambda. The author actually uses a feedback strategy to set H in conjunction with his gradient scaling (see Algorithm 2 / AdaN), and it's possible that the scaling allows H to be basically correct more often and not have to be adjusted so much? Which is potentially really helpful since Newton steps aren't cheap and you don't want to waste them on guess-and-check. But it's not obvious it's better than other strategies and we do need benchmarks to prove it out, yes. The author is from INRIA, which does a lot of advanced optimization research, so I'd say it's a serious paper prima facie.
jedbrown 5y ago
A very similar technique is popular for rootfinding (since the 80s, convergence analysis in this 1998 paper), where scaling by the norm of the gradient (eq. 1.5) enables q-quadratic convergence. https://doi.org/10.1137/S0036142996304796 https://doi.org/10.1137/S0036142996304796 (free version https://repository.lib.ncsu.edu/bitstream/handle/1840.4/296/crsc-tr96-21.pdf https://repository.lib.ncsu.edu/bitstream/handle/1840.4/296/...)
- civilized 5y ago
  Rootfinding and optimization are so closely related!
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 ago
  Good 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 ago
    Previously 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.

midjji 5y ago

The problem with simple innovations in old methods, is that there is very rarely anything new under the sun, odds are good its already been done. The paper does not evaluate on any of the big standard benchmark either. The paper spends a surprising/suspicious amount of time on very basic things. "The divergence issues of Newton’s method with line search seems to be a relatively unknown fact." No its well known! It looks interesting, but some things, like the L-M lambda beeing constant? No, you adapt it to the data increasing and decreasing it in accordance with the feedback from the step error predictions. Similar, but not identically to what is proposed here. Id need to read it carefully and it doesnt look bad, but think I'll just wait for the reviewers.

civilized 5y ago
All good points. Personally I wouldn't have known divergence of Newton's method with line search off the top of my head. What I think everyone in this field would know is that Newton's method with constant step size diverges. I'm actually curious now if Newton's method with backtracking line search from a constant step size diverges. Exact line search can go a little nuts, that doesn't surprise me, but divergence with backtracking from a constant step size seems less likely. (I guess it depends on what "constant" means here...) Seems like it could be awfully nice to have a smart theoretically backed initial guess of the dynamic lambda. The author actually uses a feedback strategy to set H in conjunction with his gradient scaling (see Algorithm 2 / AdaN), and it's possible that the scaling allows H to be basically correct more often and not have to be adjusted so much? Which is potentially really helpful since Newton steps aren't cheap and you don't want to waste them on guess-and-check. But it's not obvious it's better than other strategies and we do need benchmarks to prove it out, yes. The author is from INRIA, which does a lot of advanced optimization research, so I'd say it's a serious paper prima facie.

jedbrown 5y ago

A very similar technique is popular for rootfinding (since the 80s, convergence analysis in this 1998 paper), where scaling by the norm of the gradient (eq. 1.5) enables q-quadratic convergence. https://doi.org/10.1137/S0036142996304796 https://doi.org/10.1137/S0036142996304796 (free version https://repository.lib.ncsu.edu/bitstream/handle/1840.4/296/crsc-tr96-21.pdf https://repository.lib.ncsu.edu/bitstream/handle/1840.4/296/...)

civilized 5y ago
Rootfinding and optimization are so closely related!

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 ago
Good 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 ago
  Previously 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.