A Linearly-Convergent Stochastic L-BFGS Algorithm

By Philipp Moritz, Robert Nishihara, Michael I. Jordan. 2015

262 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications, 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 Computer Networks and Communications

In Optimization & Training

Citations in the corpus

Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “These assumptions imply that for any sub-sample S, the function ∑ i∈S fi/|S| is LS -smooth and μS strongly-convex, meaning that the eigenvalues of any sub-sampled Hessian can be upper and lowerbounded [9, 10, 49].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “A recent attempt at combining these methods with SVRG can be found in [63].”
Demystifying Parallel and Distributed Deep Learning (2018, background): “e quadratic increase of batch methods in memory, communication, and computations due to high dimensionality is not desirable. To overcome these issues, stochastic variants of L-BFGS have been proposed[28,172] that estimate the inverse Hessian matrix and proven to converge at a linear rate in strongl”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “A recent attempt at combining these methods with SVRG can be found in [119].”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “sian approximation matrices to reduce the noise of stochastic approximation both in gradient and Hessian inverse approximations. This is opposed to variance-reduced stochastic quasi-Newton methods in [16,20] that attempt to reduce the noise of gradient approximations only. Secondly, the IQN method a”
A Quasi-Newton Method Based Vertical Federated Learning Framework for Logistic Regression (2019, background): “However, the inverse Hessian estimated by [10] may be not stable for small batch sizes and the algorithm in [12] requires computing the full gradient which would double the communication cost in each epoch compared with SGD.”
Kalman-Based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning (2015, background): “…and SGD methods’ computational beneﬁts are reduced by two algorithmic challenges: (1) the diﬃculty of developing computationally fast or justiﬁed stop conditions, and (2) the diﬃculty of overcoming sensitivity to the conditioning of the objective function [10, 35, 14, 23, 22, 42, 37, 8, 26].”
Second-Order Stochastic Optimization for Machine Learning in Linear Time (2016, methodology): “Indeed, in applications that interest us, the condition number is not necessarily a constant as is typically assumed to be the case of the theoretical results in [MNJ16].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “The stochastic L-BFGS method discussed in [57] uses variance reduction techniques to improve its convergence and performance.”
Asynchronous Stochastic Quasi-Newton MCMC for Non-Convex Optimization (2018, methodology): “As a remedy, stochastic L-BGFS methods have been proposed (Byrd et al., 2016; Schraudolph et al., 2007; Moritz et al., 2016; Zhou et al., 2017; Youseﬁan et al., 2017; Zhao et al., 2017), which aim to reduce the computational requirements of L-BFGS by replacing ∇ U (i.e. the full gradients that are…”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “…incremental Hessian updates (G¨urb¨uzbalaban et al., 2015), stochastic dual Newton ascent (Qu et al., 2016), and stochastic quasi-Newton methods (Schraudolph et al., 2007; Mokhtari and Ribeiro, 2014, 2015; Lucchi et al., 2015; Moritz et al., 2016; Byrd et al., 2016; Mokhtari et al., 2017).”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, background): “In particular, many of these 15 new methods are based on stochastic BFGS updates [26, 32, 17, 18, 33, 4].”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “t years, with the continuous improvement of high-order optimization methods, more and more high-order methods have been proposed to handle largescale data by using stochastic techniques [124], [125], [126]. From this perspective, we discuss several high-order methods including the stochastic quasi-N”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, methodology): “This difficulty is addressed by incremental computations in [9] and subsampling in [7] or circumvented altogether in stochastic quasi-Newton methods [21, 12, 13, 11, 14].”
Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “…only important gradients for minimizing communication bandwidth [47], [38] Second-Order Methods • Stochastic quasi-Newton methods [48], [49], [50] • Approximate Newton-type methods [51], [52], [53], [54] Federated Optimization • Federated averaging algorithm [18] and dual coordinate ascent…”
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization (2016, methodology): “Recently, Moritz, Nishihara and Jordan [38] studied a stochastic L-BFGS algorithm for minimizing a finite sum of convex functions.”
Stochastic Block BFGS: Squeezing More Curvature out of Data (2016, background): “Factored forms are important as they can be used to enforce positive definiteness of the metric even in the presence numerical imprecision.”
Accelerating SVRG via second-order information (2015, methodology): “Naturally, there have also been quite a few recent works that aim to accelerate convergence of stochastic methods by incorporating curvature information [3, 4, 16, 10, 11], while maintaining a per-iteration complexity of O(p).”