I do not fully understand how second-order optimization approaches help machine learning algorithms, like multilayer perceptron, to achieve the global minimum error. As you know, Stochastic Gradient Descent is in the first-order optimization family as it helps to optimize the error function by going downhill toward the global minimum. On the other hand, the second-order optimization like L-BFGS has been also an alternative approach which relies on finding the second-order derivative of the target function. I learned in calculus that second derivative tells you convexity/concavity of the function. Hence, how does that help for machine learning? In other word, does it mean that if I know if the function is concave then I can tell where the global minimum error is?
-
$\begingroup$ related (maybe even a duplicate?): Why are second-order derivatives useful in convex optimization? $\endgroup$– Oren MilmanCommented Sep 24, 2018 at 15:25
2 Answers
In other word, does it mean that if I know if the function is concave then I can tell where the global minimum error is?
Yes, you got the gist of it. You get the first two derivatives of the function, which effectively is a way to fit the parabola to the loss function. Once you know the parabola equation, you locate its minimum and jump right there, hoping that minimum would be somewhere in the vicinity. You keep repeating the procedure until you're close enough to a minimum.
There are variations of second order approaches, of course. For instance, you might know the exact second derivative (Hessian), or you might make a couple of steps and numerically estimate the curvature etc.
-
3$\begingroup$ +1 for answering the question. To expand upon it I might add that by accounting for the curvature the second order algorithms can be conceptualized as re-scaling poorly conditioned problems. @Kate, consider an extremely wide shallow bowl (a quadratic) for which we try to find the minimum. Gradient descent will take many iterations to find that minimum because once we hit the shallow region the gradient is near (but not equal) zero.For this problem, the Newton scheme (ie second order with exact Hessian) will converge in one iteration no matter how shallow the bowl. $\endgroup$ Commented Feb 14, 2018 at 3:19
Second order methods also find a downhill direction but they consider both the gradient and the curvature. For example in Newton's method, this downhill direction is computed by locally approximating the loss with a parabola and the step size and direction is taken to reach the optimum point of this parabola.
If the loss function can be exactly approximated with such parabola, Newton's method would converge in one iteration, whereas first order methods would take many iterations.
