Global convergence of online limited memory BFGS

By Aryan Mokhtari, Alejandro Ribeiro. 2014

175 citations recorded by the source corpus.

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. Experimental evaluation on a search engine advertising problem showcase reductions in convergence time relative to stochastic gradient descent algorithms.

Subfields: Computational Mechanics, Finance, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Finance

In Numerical Analysis

Citations in the corpus

DeltaGrad: Rapid retraining of machine learning models (2020, methodology): “We leverage the L-BFGS algorithm to approximate this, see e.g. Matthies & Strang (1979); Nocedal (1980); Byrd et al. (1994; 1995); Zhu et al. (1997); No-cedal & Wright (2006); Mokhtari & Ribeiro (2015) and references therein.”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Although L-BFGS is originally a batch method, requiring updates from all nodes, its stochastic variants have also been proposed recently [15, 3].”
Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy (2018, background): “Recently, several papers by [Byrd et al., 2016, Berahas et al., , Jahani et al., 2019, Berahas et al., 2016, Schraudolph et al., 2007, Berahas et al., 2019, Mokhtari and Ribeiro, 2015, Roosta-Khorasani and Mahoney, 2018] have studied how to apply second orders methods to solve ERM a r X i v : 1810 .”
A Survey of Optimization Methods From a Machine Learning Perspective (2019, methodology): “Further, an online L-BFGS was presented in [145].”
Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, methodology): “In order to alleviate these issues, stochastic Newton [4, 9, 39, 49, 55] and stochastic quasi-Newton [2, 10, 15, 23, 27, 42, 51] methods have been proposed.”
Comparison of Naive Bayes, Random Forest, Decision Tree, Support Vector Machines, and Logistic Regression Classifiers for Text Reviews Classification (2017, methodology): “…Descent optimization algorithm (Gupta et al., 2014), and Logistic Regression with limited memory Broyden–Fletcher–Goldfarb–Shanno optimization algorithm (Mokhtari et al., 2015) classification methods related to the classification accuracy, the number of product reviews, and combination of n -grams.”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, methodology): “Although L-BFGS is traditionally a batch method, requiring updates from all nodes, its stochastic variants have also been proposed by Mokhtari and Ribeiro (2015); Berahas et al. (2016).”
Incremental learning algorithms and applications (2016, methodology): “Second order numeric optimisation methods and advanced optimisation schemes can be extended as well, such as variational Bayes, convex optimization, second order perceptron learning based on higher order statistics in primal or dual space, and online realisations of the quasi-Newton Broyden-Fletcher”
A Linearly-Convergent Stochastic L-BFGS Algorithm (2015, methodology): “Conditioning on Fk,t and taking an expectation with respect to S, we find Ek,t[‖vt‖2] ≤ 2Ek,t[‖∇fS(xt)−∇fS(w∗)‖2] (16) + 2Ek,t[‖∇fS(wk)−∇fS(w∗)− µk‖2] ≤ 2Ek,t[‖∇fS(xt)−∇fS(w∗)‖2] + 2Ek,t[‖∇fS(wk)−∇fS(w∗)‖2] ≤ 4Λ(f(xt)− f(w∗) + f(wk)− f(w∗)).”
A Progressive Batching L-BFGS Method for Machine Learning (2018, methodology): “…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´aˇc, 2017; Zhou et al., 2017).”
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].”
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization (2018, unknown): “In particular, many of these new methods are based on stochastic BFGS updates [29, 35, 20, 21, 6, 8, 3].”
IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate (2017, methodology): “For the limited memory version of stochastic (online) BFGS, it has been shown in [19] that there is no need for regularization since the eigenvalues of the Hessian inverse approximation matrices are uniformly bounded by constants that depend on the size of memory.”
Stochastic Block BFGS: Squeezing More Curvature out of Data (2016, methodology): “The regularized BFGS method [24, 23] also makes use of stochastic gradients, and further modifies the BFGS update by adding a regularizer to the metric matrix.”