Asynchronous Parallel Stochastic Quasi-Newton Methods

Area of Science:

• Machine Learning
• Optimization Algorithms
• Parallel Computing

Background:

• First-order stochastic algorithms like stochastic gradient descent dominate large-scale machine learning.
• Second-order quasi-Newton methods, particularly L-BFGS, show promise for ill-conditioned problems.
• Existing parallelization attempts for L-BFGS are limited.

Purpose of the Study:

• To develop a truly parallelized L-BFGS algorithm with convergence guarantees.
• To enhance the efficiency of stochastic quasi-Newton methods for large-scale optimization.
• To demonstrate the effectiveness of the proposed method on ill-conditioned problems.

Main Methods:

• Proposed an asynchronous parallel algorithm for stochastic quasi-Newton (AsySQN) optimization.
• Implemented a full parallelization of the L-BFGS method, including its two-loop recursion.
• Utilized variance reduction techniques to ensure linear convergence.

Main Results:

• The AsySQN algorithm achieves significant speedup compared to non-parallel L-BFGS.
• Maintained the linear convergence rate of its sequential counterpart.
• Demonstrated superior performance over first-order methods on ill-conditioned benchmark datasets.

Conclusions:

• AsySQN offers a practical and efficient approach to parallelizing L-BFGS.
• The method effectively addresses challenges posed by ill-conditioned optimization problems in machine learning.
• AsySQN provides a scalable solution for training large machine learning models.