Large-scale L-BFGS using MapReduce
L-BFGS has been applied as an effective parameter estimation method for various machine learning algorithms since 1980s. With an increasing demand to deal with massive instances and variables, it is important to scale up and parallelize L-BFGS effectively in a distributed system. In this paper, we study the problem of parallelizing the L-BFGS algorithm in large clusters of tens of thousands of shared-nothing commodity machines. First, we show that a naive implementation of L-BFGS using Map-Reduce requires either a significant amount of memory or a large number of map-reduce steps with negative performance impact. Second, we propose a new L-BFGS algorithm, called Vector-free L-BFGS, which avoids the expensive dot product operations in the two loop recursion and greatly improves computation efficiency with a great degree of parallelism. The algorithm scales very well and enables a variety of machine learning algorithms to handle a massive number of variables over large datasets. We prove the mathematical equivalence of the new Vector-free L-BFGS and demonstrate its excellent performance and scalability using real-world machine learning problems with billions of variables in production clusters.
This paper proposes a new vector free updating formulation for the two loop recursion in L-BFGS. The main insight is that the gradient direction can be expressed as a linear combination of historical state vectors. As a result, the dot product between the state vector and the gradient can be computed as a linear combination of dot products between state vectors which can be precomputed and independent of the size of input vectors. This results in a scalable and efficient implementation of L-BFGS in the  MapReduce framework. The proposed method is evaluated on a real-world large scale problem with billions of variables thus demonstrating its efficiency. It's also compared to hashing scheme and shows better accuracy.Overall, the proposed method is efficient and practical in large-scale settings. The paper is also well written. There are some typos as follows.- Line 82: "in contract to" -> "in contrast to"- Line 322: "compare the it" -> "compare it"