# The reason of superiority of Limited-memory BFGS over ADAM solver

I am using Multilayer Perceptron MLPClassifier for training a classification model for my problem. I noticed that using the solver lbfgs (I guess it implies Limited-memory BFGS in scikit learn) outperforms ADAM when the dataset is relatively small (less than 100K). Can someone provide a concrete justification for that? In fact, I couldn't find a good resource that explains the reason behind that. Any participation is appreciated.

Thank you

There are a lot of reasons that this could be the case. Off the top of my head I can think of one plausible cause, but without knowing more about the problem it is difficult to suggest that it is the one.

An L-BFGS solver is a true quasi-Newton method in that it estimates the curvature of the parameter space via an approximation of the Hessian. So if your parameter space has plenty of long, nearly-flat valleys then L-BFGS would likely perform well. It has the downside of additional costs in performing a rank-two update to the (inverse) Hessian approximation at every step. While this is reasonably fast, it does begin to add up, particularly as the input space grows. This may account for the fact that ADAM outperforms L-BFGS for you as you get more data.

ADAM is a first order method that attempts to compensate for the fact that it doesn't estimate the curvature by adapting the step-size in every dimension. In some sense, this is similar to constructing a diagonal Hessian at every step, but they do it cleverly by simply using past gradients. In this way it is still a first order method, though it has the benefit of acting as though it is second order. The estimate is cruder than that of the L-BFGS in that it is only along each dimension and doesn't account for what would be the off-diagonals in the Hessian. If your Hessian is nearly singular then these off-diagonals may play an important role in the curvature and ADAM is likely to underperform relative the BFGS.

• I really like this answer and it matches my understanding. ADAM works very well on large models where neither BFGS or L-BFGS are practical. That said, I don't see any amazing justification for the particular formula they use other than the intuitions of combining RMSProp and momentum... and that "it just works". I was curious whether ADAM could somehow be put on a more solid footing, e.g. justifying it as an approximation to Newton's method. Perhaps the ADAM recipe could be improved in this way. May 28, 2019 at 16:50

In my opinion, they are two different heuristics to scale the gradient, however, they are motivated differently.

Nowadays people try to find a trade-off between Adam which converges fast with possibly bad generalization and SGD which converges poorly but results in better generalizations.

Maybe you should also consider to use DiffGrad which is an extension of Adam but with better convergence properties.

@David: what I'm not understanding in your answer is that you mention that Adam does not account for the off-diagonals. However, for L-BFGS this is the case as well. It approximates the Hessian by a diagonal. Accounting for off-diagonals would mean that they have to be evaluated/stored and most importantly a non-diagonal matrix would have to be inverted.