Parallel Direct Asynchronous Stochastic Quasi-Newton (DASQN) Scheme for Multi-core Architecture

Classic first-order optimization methods, such as gradient descent (GD), have significant limitations: generally linear convergence, sensitivity to the choice of learning rate, and significant oscillations around the minimum, which are particularly pronounced in ill-conditioned problems. To overcome these limitations, some authors use the Quasi-Newton approach, which approximates the inverse of the Hessian matrix in order to obtain better curvature information. This allows us to move from the linear convergence speed (GD) to superlinear convergence speed (BFGS) using first-order information. However, in some cases, particularly those involving very large amounts of data, the computational and/or storage costs can be prohibitive. One way to reduce these computational costs is to use parallelization. There are two main methods in the literature to address this challenge: DAve-QN and AsySQN. DAve-QN, which is a distributed and asynchronous version based on the master/worker architecture with superlinear local convergence of the BFGS variant, is not very suitable for very large problems involving the entire use of the Hessian matrix. AsySQN, on the other hand, is a parallel, asynchronous, shared-memory version of a stochastic variant based on L-BFGS with variance reduction (VR). It is suitable for very large problems, but converges linearly (not superlinear as BFGS’s variant). In this paper, we propose DASQN, a parallel implementation of the Quasi-Newton method, that brings together the advantages of both DAve-QN and AsySQN. DASQN is an incremental implementation-level refinement of AsySQN where we change explicit aggregation by an implicit aggregation, and we combine it with another way to share data among threads (inspired by DAve-QN) in order to have the best information. After that, we mathematically prove the convergence of DASQN. The experiments on server with 32 cores with MNIST, CIFARD-10 and STL-10 showed that DASQN outperforms AsySQN in terms of speedup and with the same precision. For example, we show that with 32 cores, we can reach a speed-up of 10.7x and 92.6% of accuracy with DASQN’s algorithm (compared to 6.5 of speed-up and 92.43% of accuracy with AsySQN) on MNIST dataset. With CIFARD-10 dataset, we even achieved 16.5 of speed-up with DASQN (compared to 9 of speed-up with AsySQN) while keeping a better precision.