Communication Efficient Distributed Newton Method with Fast Convergence Rates

We propose a communication and computation efficient second-order method for distributed optimization. For each iteration, our method only requires O(d) communication complexity, where d is the problem dimension. We also provide theoretical analysis to show the proposed method has the similar convergence rate as the classical second-order optimization algorithms. Concretely, our method can find~big(ε, √dLε,big)-second-order stationary points for nonconvex problem by Obig(√dL,ε-3/2big) iterations, where L is the Lipschitz constant of Hessian. Moreover, it enjoys a local superlinear convergence under the strongly-convex assumption. Experiments on both convex and nonconvex problems show that our proposed method performs significantly better than baselines.