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 (2)

• RES: Regularized Stochastic BFGS Algorithm
• Variable Metric Stochastic Approximation Theory

Cited by in corpus (42)

• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Straggler Mitigation in Distributed Optimization Through Data Encoding
• A Progressive Batching L-BFGS Method for Machine Learning
• Efficient Second Order Online Learning by Sketching
• A Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
• A Survey of Optimization Methods from a Machine Learning Perspective
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• Practical Quasi-Newton Methods for Training Deep Neural Networks
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part I
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?
• Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Secant Penalized BFGS: A Noise Robust Quasi-Newton Method Via Penalizing The Secant Condition
• Stochastic Subspace Descent
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations
• Accurate and Robust Alignment of Variable-stained Histologic Images Using a General-purpose Greedy Diffeomorphic Registration Tool
• A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization with Applications
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• An adaptive Hessian approximated stochastic gradient MCMC method
• SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
• Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
• Neumann Optimizer: A Practical Optimization Algorithm for Deep Neural Networks
• An Adaptive Sample Size Trust-Region Method for Finite-Sum Minimization
• A Class of Parallel Doubly Stochastic Algorithms for Large-Scale Learning
• Learning Networked Exponential Families with Network Lasso
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm
• Memory Augmented Optimizers for Deep Learning
• BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature Selection in Sublinear Memory
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• mL-BFGS: A Momentum-based L-BFGS for Distributed Large-Scale Neural Network Optimization
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• Accelerated Stochastic Quasi-Newton Optimization on Riemann Manifolds
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Limited-Memory BFGS with Displacement Aggregation