Distributed Inexact Damped Newton Method: Data Partitioning and Work-Balancing

In this paper, we study inexact damped Newton method implemented in a distributed environment. We are motivated by the original DiSCO algorithm [Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss, Yuchen Zhang and Lin Xiao, 2015].We show that this algorithm may not scale well and propose algorithmic modifications which lead to fewer communications and better load-balancing between nodes. Those modifications lead to a more efficient algorithm with better scaling. This was made possibly by introducing our new pre-conditioner which is specially designed so that the preconditioning step can be solved exactly and efficiently.Numerical experiments for minimization of regularized empirical loss with a 273GB instance shows the efficiency of proposed algorithm.