A Linearly-Convergent Stochastic L-BFGS Algorithm

Abstract

We propose a new stochastic L-BFGS algorithm and prove a linear convergence rate for strongly convex and smooth functions. Our algorithm draws heavily from a recent stochastic variant of L-BFGS proposed in Byrd et al. (2014) as well as a recent approach to variance reduction for stochastic gradient descent from Johnson and Zhang (2013). We demonstrate experimentally that our algorithm performs well on large-scale convex and non-convex optimization problems, exhibiting linear convergence and rapidly solving the optimization problems to high levels of precision. Furthermore, we show that our algorithm performs well for a wide-range of step sizes, often differing by several orders of magnitude.

10 pages, 3 figures in International Conference on Artificial Intelligence and Statistics, 2016

References in corpus (3)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Global Convergence of Online Limited Memory BFGS
• A Variance Reduced Stochastic Newton Method

Cited by in corpus (59)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
• Stochastic Conjugate Gradient Algorithm with Variance Reduction
• Variance-Reduced and Projection-Free Stochastic Optimization
• A Quasi-Newton Method Based Vertical Federated Learning Framework for Logistic Regression
• Efficient Second Order Online Learning by Sketching
• Principle-driven Fiber Transmission Model based on PINN Neural Network
• A Survey of Optimization Methods from a Machine Learning Perspective
• Predictive Coarse-Graining
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• Practical Quasi-Newton Methods for Training Deep Neural Networks
• Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
• Stochastic, Distributed and Federated Optimization for Machine Learning
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Communication-Efficient Edge AI: Algorithms and Systems
• Hemingway: Modeling Distributed Optimization Algorithms
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• A Stochastic Quasi-Newton Method with Nesterov's Accelerated Gradient
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Secant Penalized BFGS: A Noise Robust Quasi-Newton Method Via Penalizing The Secant Condition
• Fast Linear Convergence of Randomized BFGS
• Stochastic Subspace Descent
• Improved Optimization of Finite Sums with Minibatch Stochastic Variance Reduced Proximal Iterations
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization
• An Inexact Variable Metric Proximal Point Algorithm for Generic Quasi-Newton Acceleration
• A Stochastic Quasi-Newton Method for Large-Scale Nonconvex Optimization with Applications
• A Proximal Stochastic Quasi-Newton Algorithm
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
• Stochastic quasi-Newton with adaptive step lengths for large-scale problems
• Explicit Superlinear Convergence Rates of The SR1 Algorithm
• SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
• Improving SAGA via a Probabilistic Interpolation with Gradient Descent
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
• 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
• SPAN: A Stochastic Projected Approximate Newton Method
• The Outer Product Structure of Neural Network Derivatives
• Quasi-Newton Quasi-Monte Carlo for variational Bayes
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• Faster Stochastic Quasi-Newton Methods
• Trust-Region Algorithms for Training Responses: Machine Learning Methods Using Indefinite Hessian Approximations
• HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• Deep Neural Network Learning with Second-Order Optimizers -- a Practical Study with a Stochastic Quasi-Gauss-Newton Method
• Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
• Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates
• A new robust class of skew elliptical distributions
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Curvature-Exploiting Acceleration of Elastic Net Computations
• Analysis of the BFGS Method with Errors
• Accelerated Stochastic Quasi-Newton Optimization on Riemann Manifolds
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms