Scaling Up Quasi-Newton Algorithms: Communication Efficient Distributed SR1

2019/05/30 by Jahani, Majid, Nazari, Mohammadreza, Rusakov, Sergey +2
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1905.13096

Abstract

In this paper, we present a scalable distributed implementation of the Sampled Limited-memory Symmetric Rank-1 (S-LSR1) algorithm. First, we show that a naive distributed implementation of S-LSR1 requires multiple rounds of expensive communications at every iteration and thus is inefficient. We then propose DS-LSR1, a communication-efficient variant that: (i) drastically reduces the amount of data communicated at every iteration, (ii) has favorable work-load balancing across nodes, and (iii) is matrix-free and inverse-free. The proposed method scales well in terms of both the dimension of the problem and the number of data points. Finally, we illustrate the empirical performance of DS-LSR1 on a standard neural network training task.

Related

• Quasi-Newton Updating for Large-Scale Distributed Learning
• A Distributed Newton Method for Large Scale Consensus Optimization
• L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Exploring Fast and Communication-Efficient Algorithms in Large-scale Distributed Networks