Asynchronous Parallel Stochastic Quasi-Newton Methods

Abstract

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.

arXiv commentAccepted by Parallel Computing Journal

References in corpus (8)

• Adam: A Method for Stochastic Optimization
• Decentralized Quasi-Newton Methods
• Stop Wasting My Gradients: Practical SVRG
• A Progressive Batching L-BFGS Method for Machine Learning
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Stochastic L-BFGS: Improved Convergence Rates and Practical Acceleration Strategies
• Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
• Fast Linear Convergence of Randomized BFGS