A Multi-Batch L-BFGS Method for Machine Learning
The question of how to parallelize the stochastic gradient descent (SGD) method has received much attention in the literature. In this paper, we focus instead on batch methods that use a sizeable fraction of the training set at each iteration to facilitate parallelism, and that employ second-order information. In order to improve the learning process, we follow a multi-batch approach in which the batch changes at each iteration. This can cause difficulties because L-BFGS employs gradient differences to update the Hessian approximations, and when these gradients are computed using different data points the process can be unstable. This paper shows how to perform stable quasi-Newton updating in the multi-batch setting, illustrates the behavior of the algorithm in a distributed computing platform, and studies its convergence properties for both the convex and nonconvex cases.
In supervised learning, one is interested in minimizing the empirical risk where efficient optimization algorithms become the key. First-order methods such as stochastic gradient descent and its variants are reasonably well understood admitting efficient implementation and parallelization techniques. However there has been a recent interest in making second-order methods such as Newton's method or L-BFGS method efficient for such large-scale problems. This paper is along this direction, presenting a new variant of the stochastic L-BFGS method  that is efficient and robust in mainly two settings: The first arises in the presence of node failures in a distributed computing environment, the second occurs when one uses an adaptive batch size that varies over iterations for accelerating learning. The main idea is to form the Hessian estimate based on the overlap between consecutive batches (the intuition why this works is that we have less limitation in choosing the second-order information matrix compared to an estimate of the true gradient). This way, the Hessian corrections and updates with L-BFGS become more stable. The results are also illustrated and supported by numerical experiments.    I would recommend this paper to be accepted. My minor concerns/questions are below:  1) If the strong convexity lower-bound mu_1 is very small, then it seems that the resulting limit in Theorem 3.2 will be worse than the limit obtained by a first-order version of your algorithm when one would choose simply H_k = I. Could you please add a few lines to clarify this point?   2) I would suggest to add a few more references to the intro regarding recent work on stochastic L-BFGS for the sake of completeness of the literature survey. Examples include [Moritz, Nishihara, Jordan, 2016], [Mokhtari, Ribeiro, 2014]   3) To my knowledge, [Schmidt, Roux, Bach] paper appeared in Math. Programming recently. I would suggest to give a reference to the Math. Programming journal instead of the reference to the arxiv version.   4) Typo in line 59: use  --> used    
The paper is readable and well-written on an interesting topic that has received much recent attention.