Global Convergence of Online Limited Memory BFGS

Abstract

Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Numerical experiments on support vector machines with synthetic data showcase reductions in convergence time relative to stochastic gradient descent algorithms as well as reductions in storage and computation relative to other online quasi-Newton methods. Experimental evaluation on a search engine advertising problem corroborates that these advantages also manifest in practical applications.

37 pages

References in corpus (1)

• Variable Metric Stochastic Approximation Theory

Cited by in corpus (17)

• Straggler Mitigation in Distributed Optimization Through Data Encoding
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?
• Stochastic Subspace Descent
• Accurate and Robust Alignment of Variable-stained Histologic Images Using a General-purpose Greedy Diffeomorphic Registration Tool
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization with Applications
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
• An Adaptive Sample Size Trust-Region Method for Finite-Sum Minimization
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm
• Memory Augmented Optimizers for Deep Learning
• mL-BFGS: A Momentum-based L-BFGS for Distributed Large-Scale Neural Network Optimization
• Accelerated Stochastic Quasi-Newton Optimization on Riemann Manifolds
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach