A Progressive Batching L-BFGS Method for Machine Learning

Abstract

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.

arXiv commentICML 2018. 25 pages, 17 figures, 2 tables

References in corpus (18)

• Adam: A Method for Stochastic Optimization
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Revisiting Distributed Synchronous SGD
• Don't Decay the Learning Rate, Increase the Batch Size
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Large Batch Training of Convolutional Networks
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Distributed Deep Learning Using Synchronous Stochastic Gradient Descent
• Global Convergence of Online Limited Memory BFGS
• AdaBatch: Adaptive Batch Sizes for Training Deep Neural Networks
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Coupling Adaptive Batch Sizes with Learning Rates
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Global convergence rate analysis of unconstrained optimization methods based on probabilistic models

Cited by in corpus (15)

• Large batch size training of neural networks with adversarial training and second-order information
• PyHessian: Neural Networks Through the Lens of the Hessian
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Estimation of discrete choice models with hybrid stochastic adaptive batch size algorithms
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• Stochastic Calibration of Radio Interferometers
• An Adaptive Memory Multi-Batch L-BFGS Algorithm for Neural Network Training
• An Adaptive Sample Size Trust-Region Method for Finite-Sum Minimization
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm
• Stochastic Damped L-BFGS with Controlled Norm of the Hessian Approximation
• Two-Level K-FAC Preconditioning for Deep Learning
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• Asynchronous Parallel Stochastic Quasi-Newton Methods
• Approximately Exact Line Search