Title: Communication-efficient Algorithm for Distributed Sparse Learning via Two-way Truncation,
Abstract: We propose a communicationally and computationally efficient algorithm for
high-dimensional distributed sparse learning. At each iteration, local machines
compute the gradient on local data and the master machine solves one shifted
$l_1$ regularized minimization problem. The communication cost is reduced from
constant times of the dimension number for the state-of-the-art algorithm to
constant times of the sparsity number via Two-way Truncation procedure.
Theoretically, we prove that the estimation error of the proposed algorithm
decreases exponentially and matches that of the centralized method under mild
assumptions. Extensive experiments on both simulated data and real data verify
that the proposed algorithm is efficient and has performance comparable with
the centralized method on solving high-dimensional sparse learning problems.