Stochastic Block BFGS: Squeezing More Curvature out of Data

By Robert Mansel Gower, Donald Goldfarb, Peter Richtárik. 2016

169 citations recorded by the source corpus.

We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

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 Vision and Pattern Recognition

Citations in the corpus

Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “In [38], the authors utilize recent progress in the area of stochastic matrix inversion [39] revealing new connections with quasi-Newton methods, and devise a new stochastic limited memory BFGS method working in tandem with SVRG.”
Distributed optimization with arbitrary local solvers (2015, background): “One might therefore want to look at local solvers based on ideas appearing in [49] or [56].”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “arge matrix, respectively. A limited memory variant of the stochastic block BFGS method for solving the empirical risk minimization problem arising in machine learning was proposed by 11 Gower et al. [22]. Tu et al. [73] utilize the sketch-and-project framework to show that breaking block locality c”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “In [67], the authors utilize recent progress in the area of stochastic matrix inversion [69] revealing new connections with quasi-Newton methods, and devise a new stochastic limited memory BFGS method working in tandem with SVRG.”
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.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “A limited memory variant of the stochastic block BFGS method for solving the empirical risk minimization problem arising in machine learning was proposed by [71].”
Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, methodology): “[23] Robert Gower, Donald Goldfarb, and Peter Richtárik.”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “Besides these, a variance reduced block L-BFGS method was proposed, which works by employing the actions of a subsampled Hessian on a set of random vectors [146].”
Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory (2017, methodology): “A limited memory variant of the stochastic block BFGS method has been used to develop new efficient stochastic quasi-Newton methods for empirical risk minimization problems appearing in machine learning [17].”
A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization (2018, methodology): “[34] establish linear convergence of a stochastic block L-BFGS method if the functions fi are strongly convex.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, methodology): “A limited memory variant of the stochastic block BFGS method for solving the empirical risk minimization problem arising in machine learning was proposed by [23].”
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.”
Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization (2016, methodology): “s> j y j>0, j= k 1;:::;k p, then H k;pis positive denite provided that H k;0 is positive denite. Recently, stochastic L-BFGS methods have been proposed for solving strongly convex problems in [10, 39, 40, 25]. However, the theoretical convergence analyses in these papers do not apply to noncon”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, methodology): “296 [9] Robert Gower, Donald Goldfarb, and Peter Richtárik.”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “Moving beyond ﬁrst order information, there have been stochastic quasi-Newton methods to approximate Hessian information [29, 18, 19, 20, 10].”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, methodology): “This difficulty is addressed by incremental computations in [11] and subsampling in [8] or circumvented altogether in stochastic quasi-Newton methods [22, 3, 14, 15, 16, 10].”
Nonconvex Variance Reduced Optimization with Arbitrary Sampling (2018, background): “, 2018), higher-order information (Qu et al., 2016; Gower et al., 2016), and a number of other techniques.”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, unknown): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017) and”