2
$\begingroup$

While 2nd order methods have many advantages, e.g. natural gradient (e.g. in L-BFGS) attracts to close zero gradient point, which is usually saddle. Other try to pretend that our very non-convex function is locally convex (e.g. Gauss-Newton, Levenberg-Marquardt, Fisher information matrix e.g. in K-FAC, gradient covariance matrix in TONGA - overview) - again attracting rather not only to local minima (how bad it is?).

There is a belief that the number of saddles is ~exp(dim) larger than of minima. Actively repelling them (instead of attracting) requires control of sign of curvatures (as Hessian eigenvalues) - e.g. negating step sign in these directions.

It is e.g. done in saddle-free Newton method (SFN) ( https://arxiv.org/pdf/1406.2572 ) - 2014, 600+ citations, recent github. They claim to get a few times(!) lower error e.g. on MNIST this way, other methods got stuck on some plateaus with strong negative eigenvalues:

enter image description here

Here is another very interesting paper: https://arxiv.org/pdf/1902.02366 investigating evolution of eigenvalues of Hessian for 3.3M parameters (~20 terabytes!), for example showing that rare negative curvature directions allow for relatively huge improvements:

enter image description here

So it looks great - it seems that we all should use SFN or other methods actively repelling saddles ... but it didn't happen - why is it so? What are the weaknesses?

What are other promising 2nd order approaches handling saddles?

How can we improve SFN-like methods? For example what I mostly don't like is directly estimating Hessian from noisy data, what is very problematic numerically. Instead, we are really interested in linear behavior of 1st derivative - we can optimally estimate it with (online) linear regression of gradients: with weakening weights of old gradients. Another issue is focusing on Krylov subspace due to numerical method (Lanczos) - it should be rather based on gradient statistics like their PCA, what again can be made online to get local statistically relevant directions.

$\endgroup$
1
$\begingroup$

my joint paper

https://arxiv.org/abs/2006.01512

Here is a github link for python codes:

https://github.com/hphuongdhsp/Q-Newton-method

Gives theoretical proof of the heuristic argument in the second paper you linked to in your question. We also provide a simple way of how to proceed in the case the Hessian is not invertible.

Two issues I think now prevents the use in large scale:

Cost of implementation. I read that there are some methods to reduce the cost but need to look in details.

No guarantee of convergence. Maybe for loss functions in popular DNN we can hope to prove convergence.

On the other hand, a very well theoretical justified first order methods, working well in large scale is Backtracking GD. You can check the codes here

https://github.com/hank-nguyen/MBT-optimizer

P.S. I don’t consider having an account on this site, so if you want more discussion it is better through emails.

$\endgroup$
20
  • $\begingroup$ Thanks, I haven't worked on it for a year, but will take a closer look in a few days. Some student implemented 1D subspace case: just extending e.g. ADAM with online parabola model in its single direction for better choice of step size ( arxiv.org/pdf/1907.07063 ), but it wasn't able to beat ADAM so far ... while it controls sign of eigenvalue, indeed it being close to 0 turned out to be a big problem - needs further work, especially testing if tracing Hessian for a larger subspace can be essentially better. $\endgroup$ – Jarek Duda Jul 27 '20 at 9:20
  • $\begingroup$ Thanks for the reference, I will check. Is there any theoretical guarantee for your new method? $\endgroup$ – user292463 Jul 27 '20 at 9:50
  • $\begingroup$ After fixing a direction, estimation of 2nd derivative can be seen as linear regression of 1st derivatives, what can be made online (e.g. by replacing average with exponential moving average). For parabola such linear regression would give proper 2nd derivative from just two points... the problem is that gradients are noisy here, it is not really a parabola, and that the modeled direction rotates e.g. accordingly to some momentum/ADAM (or e.g. online PCA for multiple directions). I would gladly discuss it. $\endgroup$ – Jarek Duda Jul 27 '20 at 13:34
  • $\begingroup$ Hi, I looked at your paper. While it has some good heuristic, my concern is that it is complicated and has no theoretical guarantee. Backtracking gd works better than Adam on Cifar10 (you can check the github link I gave) and it is simple: based on Armijo’s condition only. It also has a lot of theoretical guarantee. $\endgroup$ – user292463 Jul 28 '20 at 7:35
  • $\begingroup$ Complicated?? Online linear regression of gradients is just maintaining 4 exponential moving averages: of position "x += eta * (newX - x)", gradient g (as in momentum), also of x^2 and gx - can you get simpler/cheaper 2nd order method? There is theoretical guarantee of getting parabola from derivatives in just two points. The main reason for not beating adam might be that I am practically alone with that and have other projects. I will have to look at backtracking gd, but it seems orthogonal concept which could be also included here. $\endgroup$ – Jarek Duda Jul 28 '20 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.