A Progressive Batching L-BFGS Method for Machine Learning

By Raghu Bollapragada, Dheevatsa Mudigere, Jorge Nocedal, Hao-Jun Michael Shi, Ping Tak Peter Tang. 2018

176 citations recorded by the source corpus.

The standard L-BFGS method relies on gradient approximations that are not dominated by noise, so that search directions are descent directions, the line search is reliable, and quasi-Newton updating yields useful quadratic models of the objective function. All of this appears to call for a full batch approach, but since small batch sizes give rise to faster algorithms with better generalization properties, L-BFGS is currently not considered an algorithm of choice for large-scale machine learning applications. One need not, however, choose between the two extremes represented by the full batch or highly stochastic regimes, and may instead follow a progressive batching approach in which the sample size increases during the course of the optimization. In this paper, we present a new version of the L-BFGS algorithm that combines three basic components - progressive batching, a stochastic line search, and stable quasi-Newton updating - and that performs well on training logistic regression and deep neural networks. We provide supporting convergence theory for the method.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “This analysis closely follows the proof of Theorem 2.2 in Bollapragada et al. (2018a).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “This approach has previously been used in the context of VRSGD methods [74, 73], and several related stochastic methods have also appeared in the recent literature [12, 64, 85].”
PyHessian: Neural Networks Through the Lens of the Hessian (2019, methodology): “[7] Raghu Bollapragada, Dheevatsa Mudigere, Jorge Nocedal, Hao-Jun Michael Shi, and Ping Tak Peter Tang.”
ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning (2020, methodology): “One reason for this is that LBFGS method requires full batch gradients, as stochastic gradients can lead to drastic errors in the approximation [6].”
A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “The column median loss [8-10]s shows the median loss over the last two seconds of the run.”