  Although first-order stochastic algorithms, such as stochastic gradient
descent, have been the main force to scale up machine learning models, such as
deep neural nets, the second-order quasi-Newton methods start to draw attention
due to their effectiveness in dealing with ill-conditioned optimization
problems. The L-BFGS method is one of the most widely used quasi-Newton
methods. We propose an asynchronous parallel algorithm for stochastic
quasi-Newton (AsySQN) method. Unlike prior attempts, which parallelize only the
calculation for gradient or the two-loop recursion of L-BFGS, our algorithm is
the first one that truly parallelizes L-BFGS with a convergence guarantee.
Adopting the variance reduction technique, a prior stochastic L-BFGS, which has
not been designed for parallel computing, reaches a linear convergence rate. We
prove that our asynchronous parallel scheme maintains the same linear
convergence rate but achieves significant speedup. Empirical evaluations in
both simulations and benchmark datasets demonstrate the speedup in comparison
with the non-parallel stochastic L-BFGS, as well as the better performance than
first-order methods in solving ill-conditioned problems.
