A Stochastic Quasi-Newton Method for Large-Scale Optimization

By Richard H. Byrd, Samantha Hansen, Jorge Nocedal, Yoram Singer. 2014

525 citations recorded by the source corpus.

The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at regular intervals, through (sub-sampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Numerical Analysis

In Optimization & Training

Citations in the corpus

Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods (2013, methodology): “In (Byrd et al., 2014) LBFGS is performed, but with the contributing changes in gradient and position replaced by exactly computed Hessian vector products computed periodically on extra large minibatches.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “These algorithms in general try to mimic the limited memory BFGS method (L-BFGS) [54], but model the local curvature information using inexact gradients — coming from the SGD procedure.”
Distributed optimization with arbitrary local solvers (2015, neutral): “Finally, another class of extensions to SGD are stochastic quasi-Newton methods [6, 11].”
Demystifying Parallel and Distributed Deep Learning (2018, background): “To overcome these issues, stochastic variants of L-BFGS have been proposed [28, 177] that estimate the inverse Hessian matrix and proven to converge at a linear rate in strongly-convex, Lipschitz-continuous settings [177].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Finally, another class of extensions to SGD are stochastic quasi-Newton methods [17, 26].”
Meta-Learning with Warped Gradient Descent (2019, background): “As second-order curvature is typically intractable to compute, such methods resort to low-rank approximations (Martens, 2010; Martens & Grosse, 2015) suffer from instability (Byrd et al., 2016).”
L4: Practical loss-based stepsize adaptation for deep learning (2018, background): “Another approach is to make use of (an approximation of) second order information (see [3] and [19] as examples).”
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; Yousefian et al., 2017; Zhao et al., 2017), which aim to reduce the computational requirements of L-BFGS by replacing ∇U (i.”
Boosting Variational Inference (2016, background): “…for quality of inference in VI. Nonetheless, the family considered here (all possible finite mixtures of a parametric base distribution) may be more ripe for future theoretical analysis due to its desirable limiting properties, though such an analysis is outside the scope of the present paper.”
Subsampled inexact Newton methods for minimizing large sums of convex functions (2018, background): “On the other hand several papers investigate the use of second order methods in this framework and demonstrate advantages in some important problems if the second order methods are correctly implemented, [4, 7, 5, 10, 11, 18, 36, 37, 34, 40, 41].”
Second Order Stochastic Optimization in Linear Time (2016, methodology): “Other methods include taking a hybrid approach that combine the above two methods to gain improvement [SYG07, BHNS14].”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “The work in [6] proposes a limited memory stochastic quasi-Newton method that collects second-order information to compute the product of subsampled Hessian and stochastic gradient as the stochastic gradient variation required in the update of BFGS.”
Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence (2015, background): “[8, 7] propose stochastic second-order methods that use batch subsampling in order to obtain curvature information in a computationally inexpensive manner.”
Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “Workhorse stochastic gradient descent methods [3, 27] as well as the more recent variance reduction [7, 12, 24, 30] and quasiNewton [6, 18, 19, 31] variants work just as well for any finite sum minimization problem.”
A Progressive Batching L-BFGS Method for Machine Learning (2018, methodology): “Stochastic second-order methods have been explored within the context of convex and non-convex optimization; see (Schraudolph et al., 2007; Sohl-Dickstein et al., 2014; Mokhtari & Ribeiro, 2015; Berahas et al., 2016; Byrd et al., 2016; Keskar & Berahas, 2016; Curtis, 2016; Berahas & Takáč, 2017; Zho”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “Then the relevant experts and scholars also introduced this stochastic idea to the second-order optimization methods [112], [113], [218] and achieved good results.”
Optimization Methods for Supervised Machine Learning: From Linear Models to Deep Learning (2017, methodology): “• An alternative idea aimed at ensuring that s Tk y k > 0 has been proposed in [14] and extended in [33] to a block version of the BFGS method.”
Stochastic Adaptive Quasi-Newton Methods for Minimizing Expected Values (2017, background): “Linearly convergent stochastic Limited Memory BFGS algorithms (Byrd et al., 2016)(Moritz et al., 2016)(Gower et al., 2016) have also been proposed.”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “For example, [77] proposed to solve minw fIt(w) directly, while [25] presented a L-BFGS style updating.”